Igor Carboni Oliveira

43 papers A* 2A 4Journal 35Unranked 1
YearRankTypeTitle / Venue / Authors
2025 J jnl
Meta-Mathematics of Computational Complexity Theory.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira
2024 J jnl
On the Unprovability of Circuit Size Bounds in Intuitionistic S
Electron. Colloquium Comput. Complex.
Lijie Chen, Jiatu Li, Igor Carboni Oliveira
2024 J jnl
Provability of the Circuit Size Hierarchy and Its Consequences.
Electron. Colloquium Comput. Complex.
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira, Dimitrios Tsintsilidas
2024 J jnl
Reverse Mathematics of Complexity Lower Bounds.
Electron. Colloquium Comput. Complex.
Lijie Chen, Jiatu Li, Igor Carboni Oliveira
2023 J jnl
A Duality Between One-Way Functions and Average-Case Symmetry of Information.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira
2023 J jnl
Constant-depth circuits vs. monotone circuits.
Electron. Colloquium Comput. Complex.
Bruno Pasqualotto Cavalar, Igor Carboni Oliveira
2023 J jnl
Polynomial-Time Pseudodeterministic Construction of Primes.
Electron. Colloquium Comput. Complex.
Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam
2023 J jnl
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic.
CoRR
Jiatu Li, Igor Carboni Oliveira
2023 J jnl
Unprovability of strong complexity lower bounds in bounded arithmetic.
Electron. Colloquium Comput. Complex.
Jiatu Li, Igor Carboni Oliveira
2022 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
J. ACM
Lijie Chen, Shuichi Hirahara, Igor Carboni Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2022 J jnl
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand
2021 J jnl
An Efficient Coding Theorem via Probabilistic Representations and its Applications.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor Carboni Oliveira
2021 J jnl
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1.
Electron. Colloquium Comput. Complex.
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira
2021 J jnl
Pseudodeterministic Algorithms and the Structure of Probabilistic Time.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam
2020 J jnl
NP-Hardness of Circuit Minimization for Multi-Output Functions.
Electron. Colloquium Comput. Complex.
Rahul Ilango, Bruno Loff, Igor Carboni Oliveira
2019 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2019 J jnl
Consistency of circuit lower bounds with bounded theories.
Electron. Colloquium Comput. Complex.
Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajícek
2019 A conf
Expander-Based Cryptography Meets Natural Proofs.
ITCS
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
2019 A conf
Hardness Magnification near State-Of-The-Art Lower Bounds.
CCC
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
2019 A conf
Parity Helps to Compute Majority.
CCC
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan
2019 J jnl
Parity helps to compute Majority.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan
2019 A* conf
Randomness and Intractability in Kolmogorov Complexity.
ICALP
Igor Carboni Oliveira
2019 J jnl
Randomness and Intractability in Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira
2018 J jnl
Expander-Based Cryptography Meets Natural Proofs.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam, Roei Tell
2018 A* conf
Hardness Magnification for Natural Problems.
FOCS
Igor Carboni Oliveira, Rahul Santhanam
2018 J jnl
Hardness Magnification for Natural Problems.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2018 J jnl
Hardness magnification near state-of-the-art lower bounds.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Ján Pich, Rahul Santhanam
2018 J jnl
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam
2018 — conf
Pseudo-Derandomizing Learning and Approximation.
APPROX-RANDOM
Igor Carboni Oliveira, Rahul Santhanam
2018 J jnl
Pseudo-derandomizing learning and approximation.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2017 J jnl
An Average-Case Lower Bound against ACC^0.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam
2016 J jnl
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2016 J jnl
Pseudodeterministic Constructions in Subexponential Time.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2016 J jnl
Unprovability of circuit upper bounds in Cook's theory PV.
Electron. Colloquium Comput. Complex.
Jan Krajícek, Igor Carboni Oliveira
2015 J jnl
Addition is exponentially harder than counting for shallow monotone circuits.
Electron. Colloquium Comput. Complex.
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
2015 A conf
Majority is Incompressible by AC^0[p] Circuits.
CCC
Igor Carboni Oliveira, Rahul Santhanam
2015 J jnl
The Power of Negations in Cryptography.
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen
2015 — —
Unconditional Lower Bounds in Complexity Theory.
Igor Carboni Oliveira
2014 J jnl
Learning circuits with few negations.
Electron. Colloquium Comput. Complex.
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
2014 J jnl
Majority is incompressible by AC
Electron. Colloquium Comput. Complex.
Igor Carboni Oliveira, Rahul Santhanam
2009 J jnl
A New Look at Some Classical Results in Computational Complexity.
Electron. Colloquium Comput. Complex.
Arnaldo Moura, Igor Carboni Oliveira
2009 J jnl
Erratum to "The Ricean Objection: An Analogue of Rice's Theorem for First-Order Theories" .
Log. J. IGPL
Igor Carboni Oliveira, Walter Alexandre Carnielli
2008 J jnl
The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories.
Log. J. IGPL
Igor Carboni Oliveira, Walter Alexandre Carnielli