Igor Carboni Oliveira

43 papers A* 2A 4Journal 35Unranked 1

Year	Rank	Type	Title / 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