Igor Carboni Oliveira

Publication Activity (10 Years)

Years Active: 2008-2024
Publications (10 Years): 76

Top Topics

Worst Case Analysis

Learning Algorithm

Kolmogorov Complexity

Top Venues

Electron. Colloquium Comput. Complex.

Computational Complexity Conference

Publications

Lijie Chen, Jiatu Li, Igor Carboni Oliveira
Reverse Mathematics of Complexity Lower Bounds. Electron. Colloquium Comput. Complex. (2024)
Lijie Chen, Jiatu Li, Igor Carboni Oliveira
. Electron. Colloquium Comput. Complex. (2024)
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
A Duality between One-Way Functions and Average-Case Symmetry of Information. STOC (2023)
Jiatu Li, Igor Carboni Oliveira
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic. CoRR (2023)
Bruno Pasqualotto Cavalar, Igor Carboni Oliveira
Constant-depth circuits vs. monotone circuits. Electron. Colloquium Comput. Complex. (2023)
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
A Duality Between One-Way Functions and Average-Case Symmetry of Information. IACR Cryptol. ePrint Arch. 2023 (2023)
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam
Polynomial-Time Pseudodeterministic Construction of Primes. Electron. Colloquium Comput. Complex. (2023)
Jiatu Li, Igor Carboni Oliveira
Unprovability of strong complexity lower bounds in bounded arithmetic. Electron. Colloquium Comput. Complex. (2023)
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
A Duality Between One-Way Functions and Average-Case Symmetry of Information. Electron. Colloquium Comput. Complex. (2023)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Carboni Oliveira
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. Electron. Colloquium Comput. Complex. (2022)
Zhenjian Lu, Igor Carboni Oliveira
Theory and Applications of Probabilistic Kolmogorov Complexity. Bull. EATCS 137 (2022)
Zhenjian Lu, Igor Carboni Oliveira
Theory and Applications of Probabilistic Kolmogorov Complexity. CoRR (2022)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2022)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. CoRR (2022)
Zhenjian Lu, Igor Carboni Oliveira
Theory and Applications of Probabilistic Kolmogorov Complexity. Electron. Colloquium Comput. Complex. (2022)
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. FOCS (2022)
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
Quantum learning algorithms imply circuit lower bounds. FOCS (2022)
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor Carboni Oliveira
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. CCC (2022)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. J. ACM 69 (4) (2022)
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. ICALP (2022)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. Comput. Complex. 31 (1) (2022)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic algorithms and the structure of probabilistic time. STOC (2021)
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. ICALP (2021)
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1. Electron. Colloquium Comput. Complex. 28 (2021)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Algorithms and the Structure of Probabilistic Time. CoRR (2021)
Zhenjian Lu, Igor Carboni Oliveira
An Efficient Coding Theorem via Probabilistic Representations and Its Applications. ICALP (2021)
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
Quantum learning algorithms imply circuit lower bounds. FOCS (2021)
Zhenjian Lu, Igor Carboni Oliveira
An Efficient Coding Theorem via Probabilistic Representations and its Applications. Electron. Colloquium Comput. Complex. 28 (2021)
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. FOCS (2021)
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. Electron. Colloquium Comput. Complex. 28 (2021)
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
Hardness Magnification Near State-of-the-Art Lower Bounds. Theory Comput. 17 (2021)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. ACM Trans. Comput. Theory 13 (4) (2021)
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Algorithms and the Structure of Probabilistic Time. Electron. Colloquium Comput. Complex. 28 (2021)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. CoRR (2020)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. ITCS (2020)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates. Computational Complexity Conference (2020)
Srinivasan Arunachalam, Alex Bredariol Grilo, Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
Quantum learning algorithms imply circuit lower bounds. Electron. Colloquium Comput. Complex. 27 (2020)
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Carboni Oliveira
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. Electron. Colloquium Comput. Complex. 27 (2020)
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor Carboni Oliveira, Aarthi Sundaram
Quantum learning algorithms imply circuit lower bounds. CoRR (2020)
Jan Bydzovsky, Jan Krajícek, Igor Carboni Oliveira
Consistency of circuit lower bounds with bounded theories. Log. Methods Comput. Sci. 16 (2) (2020)
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira
NP-Hardness of Circuit Minimization for Multi-Output Functions. Computational Complexity Conference (2020)
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira
NP-Hardness of Circuit Minimization for Multi-Output Functions. Electron. Colloquium Comput. Complex. 27 (2020)
Igor Carboni Oliveira
Randomness and Intractability in Kolmogorov Complexity. Electron. Colloquium Comput. Complex. 26 (2019)
Igor Carboni Oliveira
Randomness and Intractability in Kolmogorov Complexity. ICALP (2019)
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. CoRR (2019)
Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajícek
Consistency of circuit lower bounds with bounded theories. Electron. Colloquium Comput. Complex. 26 (2019)
Jan Bydzovsky, Jan Krajícek, Igor Carboni Oliveira
Consistency of circuit lower bounds with bounded theories. CoRR (2019)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. ITCS (2019)
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
Hardness Magnification near State-Of-The-Art Lower Bounds. Computational Complexity Conference (2019)
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan
Parity Helps to Compute Majority. Computational Complexity Conference (2019)
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam
Beyond Natural Proofs: Hardness Magnification and Locality. Electron. Colloquium Comput. Complex. 26 (2019)
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan
Parity helps to compute Majority. Electron. Colloquium Comput. Complex. 26 (2019)
Igor Carboni Oliveira, Rahul Santhanam
Hardness Magnification for Natural Problems. Electron. Colloquium Comput. Complex. 25 (2018)
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
Expander-Based Cryptography Meets Natural Proofs. Electron. Colloquium Comput. Complex. 25 (2018)
Jan Krajícek, Igor Carboni Oliveira
On monotone circuits with local oracles and clique lower bounds. Chic. J. Theor. Comput. Sci. 2018 (2018)
Igor Carboni Oliveira, Rahul Santhanam
Pseudo-derandomizing learning and approximation. Electron. Colloquium Comput. Complex. 25 (2018)
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. Computational Complexity Conference (2018)
Igor Carboni Oliveira, Rahul Santhanam
Pseudo-Derandomizing Learning and Approximation. APPROX-RANDOM (2018)
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Ruiwen Chen, Igor Carboni Oliveira, Rahul Santhanam
An Average-Case Lower Bound Against \mathsf ACC^0 ACC 0. LATIN (2018)
Igor Carboni Oliveira, Rahul Santhanam
Hardness Magnification for Natural Problems. FOCS (2018)
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
Hardness magnification near state-of-the-art lower bounds. Electron. Colloquium Comput. Complex. 25 (2018)
Jan Krajícek, Igor Carboni Oliveira
On monotone circuits with local oracles and clique lower bounds. CoRR (2017)
Igor Carboni Oliveira, Rahul Santhanam
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness. Computational Complexity Conference (2017)
Jan Krajícek, Igor Carboni Oliveira
Unprovability of circuit upper bounds in Cook's theory PV. Log. Methods Comput. Sci. 13 (1) (2017)
Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam
An Average-Case Lower Bound against ACC^0. Electron. Colloquium Comput. Complex. 24 (2017)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
Addition is exponentially harder than counting for shallow monotone circuits. STOC (2017)
Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic constructions in subexponential time. STOC (2017)
Marcelo M. Gauy, Hiêp Hàn, Igor Carboni Oliveira
Erdős-Ko-Rado for Random Hypergraphs: Asymptotics and Stability. Comb. Probab. Comput. 26 (3) (2017)
Jan Krajícek, Igor Carboni Oliveira
Unprovability of circuit upper bounds in Cook's theory PV. Electron. Colloquium Comput. Complex. 23 (2016)
Igor Carboni Oliveira, Bhalchandra D. Thatte
An Algebraic Formulation of the Graph Reconstruction Conjecture. J. Graph Theory 81 (4) (2016)
Igor Carboni Oliveira, Rahul Santhanam
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. CoRR (2016)
Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Constructions in Subexponential Time. CoRR (2016)
Igor Carboni Oliveira, Rahul Santhanam
Pseudodeterministic Constructions in Subexponential Time. Electron. Colloquium Comput. Complex. 23 (2016)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Near-optimal small-depth lower bounds for small distance connectivity. STOC (2016)
Igor Carboni Oliveira, Rahul Santhanam
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. Electron. Colloquium Comput. Complex. 23 (2016)
Igor Carboni Oliveira, Rahul Santhanam
Majority is Incompressible by AC^0[p] Circuits. Computational Complexity Conference (2015)
Siyao Guo, Tal Malkin, Igor Carboni Oliveira, Alon Rosen
The Power of Negations in Cryptography. TCC (1) (2015)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
Addition is exponentially harder than counting for shallow monotone circuits. CoRR (2015)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Near-optimal small-depth lower bounds for small distance connectivity. CoRR (2015)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
Addition is exponentially harder than counting for shallow monotone circuits. Electron. Colloquium Comput. Complex. 22 (2015)
Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen
The Power of Negations in Cryptography. Electron. Colloquium Comput. Complex. 22 (2015)
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Learning Circuits with few Negations. APPROX-RANDOM (2015)
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Learning circuits with few negations. CoRR (2014)
Siyao Guo, Tal Malkin, Igor Carboni Oliveira, Alon Rosen
The Power of Negations in Cryptography. IACR Cryptol. ePrint Arch. 2014 (2014)
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Learning circuits with few negations. Electron. Colloquium Comput. Complex. 21 (2014)
Igor Carboni Oliveira, Rahul Santhanam
[p] circuits. Electron. Colloquium Comput. Complex. 21 (2014)
Igor Carboni Oliveira
Algorithms versus Circuit Lower Bounds. CoRR (2013)
Igor Carboni Oliveira, Bhalchandra D. Thatte
An algebraic formulation of the graph reconstruction conjecture CoRR (2013)
Adam R. Klivans, Pravesh Kothari, Igor Carboni Oliveira
Constructing Hard Functions Using Learning Algorithms. Computational Complexity Conference (2013)
Adam R. Klivans, Pravesh Kothari, Igor Carboni Oliveira
Constructing Hard Functions from Learning Algorithms. Electron. Colloquium Comput. Complex. 20 (2013)
Igor Carboni Oliveira, Walter Alexandre Carnielli
. Log. J. IGPL 17 (6) (2009)
Arnaldo Moura, Igor Carboni Oliveira
A New Look at Some Classical Results in Computational Complexity. Electron. Colloquium Comput. Complex. 16 (2009)
Igor Carboni Oliveira, Walter Alexandre Carnielli
The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories. Log. J. IGPL 16 (6) (2008)