Follow
Igor Carboni Oliveira
Title
Cited by
Cited by
Year
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
IC Oliveira, R Santhanam
Computational Complexity Conference (CCC), 2017
572017
Hardness Magnification for Natural Problems
IC Oliveira, R Santhanam
Symposium on Foundations of Computer Science (FOCS), 2018
412018
Hardness magnification near state-of-the-art lower bounds
IC Oliveira, J Pich, R Santhanam
Computational Complexity Conference (CCC), 2019
402019
Learning circuits with few negations
E Blais, C Canonne, IC Oliveira, R Servedio, LY Tan
International Workshop on Randomization and Computation (RANDOM), 2015
372015
NP-hardness of circuit minimization for multi-output functions
R Ilango, B Loff, IC Oliveira
Computational Complexity Conference (CCC), 2020
332020
The Power of Negations in Cryptography
S Guo, IC Oliveira, T Malkin, A Rosen
Theory of Cryptography Conference (TCC), 2015
312015
Pseudodeterministic constructions in subexponential time
IC Oliveira, R Santhanam
Symposium on Theory of Computing (STOC), 2017
302017
Algorithms versus circuit lower bounds
IC Oliveira
Electronic Colloquium on Computational Complexity (ECCC) - TR13-117, 2013
302013
Constructing hard functions from learning algorithms
A Klivans, P Kothari, IC Oliveira
Conference on Computational Complexity (CCC), 2013
28*2013
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD circuits
S Hirahara, IC Oliveira, R Santhanam
Computational Complexity Conference (CCC), 2018
262018
Near-optimal small-depth lower bounds for small-distance connectivity
X Chen, IC Oliveira, R Servedio, LY Tan
Symposium on Theory of Computing (STOC), 2016
232016
Beyond natural proofs: hardness magnification and locality
L Chen, S Hirahara, IC Oliveira, J Pich, N Rajgopal, R Santhanam
Journal of the ACM (JACM) and Innovations in Theoretical Computer Science (ITCS), 2020
212020
Randomness and intractability in Kolmogorov complexity
IC Oliveira
International Colloquium on Automata, Languages and Programming (ICALP), 2019
172019
Erdos-Ko-Rado in random hypergraphs: asymptotics and stability
MM Gauy, H Han, IC Oliveira
Combinatorics, Probability and Computing (CPC) 26 (3), 406-422, 2017
142017
Unconditional lower bounds in complexity theory
IC Oliveira
Columbia University (PhD Thesis), 2015
132015
Pseudo-derandomizing learning and approximation
IC Oliveira, R Santhanam
International Conference on Randomization and Computation (RANDOM), 2018
122018
Addition is exponentially harder than counting for shallow monotone circuits
X Chen, IC Oliveira, R Servedio
Symposium on the Theory of Computing (STOC), 2017
122017
Majority is incompressible by AC^0[p] circuits
IC Oliveira, R Santhanam
Conference on Computational Complexity (CCC), 2015
102015
An efficient coding theorem via probabilistic representations and its applications
Z Lu, IC Oliveira
International Colloquium on Automata, Languages and Programming (ICALP), 2021
92021
On monotone circuits with local oracles and clique lower bounds
J Krajicek, IC Oliveira
Chicago Journal of Theoretical Computer Science (CJTCS), 2018
92018
The system can't perform the operation now. Try again later.
Articles 1–20