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
722017
Hardness Magnification for Natural Problems
IC Oliveira, R Santhanam
Symposium on Foundations of Computer Science (FOCS), 2018
572018
NP-hardness of circuit minimization for multi-output functions
R Ilango, B Loff, IC Oliveira
Computational Complexity Conference (CCC), 2020
502020
Hardness magnification near state-of-the-art lower bounds
IC Oliveira, J Pich, R Santhanam
Computational Complexity Conference (CCC) & Theory of Computing (ToC), 2019
472019
Learning circuits with few negations
E Blais, C Canonne, IC Oliveira, R Servedio, LY Tan
International Workshop on Randomization and Computation (RANDOM), 2015
452015
Beyond natural proofs: hardness magnification and locality
L Chen, S Hirahara, IC Oliveira, J Pich, N Rajgopal, R Santhanam
Journal of the ACM (JACM) & Innovations in Theoretical Computer Science (ITCS), 2020
382020
Pseudodeterministic constructions in subexponential time
IC Oliveira, R Santhanam
Symposium on Theory of Computing (STOC), 2017
382017
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD circuits
S Hirahara, IC Oliveira, R Santhanam
Computational Complexity Conference (CCC), 2018
362018
The Power of Negations in Cryptography
S Guo, IC Oliveira, T Malkin, A Rosen
Theory of Cryptography Conference (TCC), 2015
362015
Algorithms versus circuit lower bounds
IC Oliveira
Electronic Colloquium on Computational Complexity (ECCC) - TR13-117, 2013
332013
Constructing hard functions from learning algorithms
A Klivans, P Kothari, IC Oliveira
Conference on Computational Complexity (CCC), 2013
31*2013
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
272016
Randomness and intractability in Kolmogorov complexity
IC Oliveira
International Colloquium on Automata, Languages and Programming (ICALP), 2019
252019
Pseudodeterministic algorithms and the structure of probabilistic time
Z Lu, IC Oliveira, R Santhanam
Symposium on Theory of Computing (STOC), 2021
172021
Pseudo-derandomizing learning and approximation
IC Oliveira, R Santhanam
International Conference on Randomization and Computation (RANDOM), 2018
162018
Algorithms and lower bounds for de Morgan formulas of low-communication leaf gates
V Kabanets, S Koroth, Z Lu, D Myrisiotis, IC Oliveira
Computational Complexity Conference (CCC) & ACM Trans. Comput. Theory (ToCT), 2020
152020
Parity helps to compute Majority
IC Oliveira, R Santhanam, S Srinivasan
Computational Complexity Conference (CCC), 2019
152019
Unconditional lower bounds in complexity theory
IC Oliveira
Columbia University (PhD Thesis), 2015
152015
An average-case lower bound against ACC
R Chen, IC Oliveira, R Santhanam
Latin American Symposium on Theoretical Informatics (LATIN), 2018
14*2018
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
The system can't perform the operation now. Try again later.
Articles 1–20