Igor Carboni Oliveira
Title
Cited by
Cited by
Year
Conspiracies between learning algorithms, circuit lower bounds and pseudorandomness
IC Oliveira, R Santhanam
32nd Computational Complexity Conference (CCC), 2017
342017
Learning circuits with few negations
E Blais, C Canonne, IC Oliveira, R Servedio, LY Tan
19th International Workshop on Randomization and Computation (RANDOM), 2015
302015
The Power of Negations in Cryptography
S Guo, IC Oliveira, T Malkin, A Rosen
12th Theory of Cryptography Conference (TCC), 2015
272015
Algorithms versus circuit lower bounds
IC Oliveira
Electronic Colloquium on Computational Complexity (ECCC) - TR13-117, 2013
262013
Constructing hard functions from learning algorithms
A Klivans, P Kothari, IC Oliveira
28th Conference on Computational Complexity (CCC), 2013
24*2013
Hardness Magnification for Natural Problems
IC Oliveira, R Santhanam
59th Symposium on Foundations of Computer Science (FOCS), 2018
212018
Hardness magnification near state-of-the-art lower bounds
IC Oliveira, J Pich, R Santhanam
Computational Complexity Conference (CCC), 2019
162019
Near-optimal small-depth lower bounds for small-distance connectivity
X Chen, IC Oliveira, R Servedio, LY Tan
48th Symposium on Theory of Computing (STOC), 2016
162016
Pseudodeterministic constructions in subexponential time
IC Oliveira, R Santhanam
49th Symposium on Theory of Computing (STOC), 2017
152017
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
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD circuits
S Hirahara, IC Oliveira, R Santhanam
Computational Complexity Conference (CCC), 2018
112018
Unconditional lower bounds in complexity theory
IC Oliveira
Columbia University (PhD Thesis), 2015
10*2015
Majority is incompressible by AC^0[p] circuits
IC Oliveira, R Santhanam
30th Conference on Computational Complexity (CCC), 2015
102015
Addition is exponentially harder than counting for shallow monotone circuits
X Chen, IC Oliveira, R Servedio
49th Symposium on the Theory of Computing (STOC), 2017
82017
On monotone circuits with local oracles and clique lower bounds
J Krajicek, IC Oliveira
Chicago Journal of Theoretical Computer Science (CJTCS), 2018
72018
Randomness and intractability in Kolmogorov complexity
IC Oliveira
46th International Colloquium on Automata, Languages and Programming (ICALP), 2019
62019
Unprovability of circuit upper bounds in Cook's theory PV
J Krajicek, IC Oliveira
Logical Methods in Computer Science (LMCS) 13 (1), 2017
62017
Pseudo-derandomizing learning and approximation
IC Oliveira, R Santhanam
22nd International Conference on Randomization and Computation (RANDOM), 2018
52018
Beyond natural proofs: hardness magnification and locality
L Chen, S Hirahara, IC Oliveira, J Pich, N Rajgopal, R Santhanam
Innovations in Theoretical Computer Science (ITCS), 2020
42020
Parity helps to compute Majority
IC Oliveira, R Santhanam, S Srinivasan
Computational Complexity Conference (CCC), 2019
42019
The system can't perform the operation now. Try again later.
Articles 1–20