Igor C. Oliveira

According to our database, Igor C. Oliveira authored at least 53 papers between 2008 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

On the Complexity of Avoiding Heavy Elements.

Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2024

Lower Bounds on the Overhead of Indistinguishability Obfuscation.

Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass

Electron. Colloquium Comput. Complex., 2024

One-Way Functions and pKt Complexity.

Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2024

Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity.

Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2024

Provability of the Circuit Size Hierarchy and Its Consequences.

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor Carboni Oliveira, Dimitrios Tsintsilidas

Electron. Colloquium Comput. Complex., 2024

On the Unprovability of Circuit Size Bounds in Intuitionistic S¹₂.

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2024

Reverse Mathematics of Complexity Lower Bounds.

Lijie Chen, Jiatu Li, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2024

Polynomial-Time Pseudodeterministic Constructions (Invited Talk).

Igor C. Oliveira

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

2023

Unprovability of strong complexity lower bounds in bounded arithmetic.

Jiatu Li, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2023

A Duality Between One-Way Functions and Average-Case Symmetry of Information.

Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2023

Constant-depth circuits vs. monotone circuits.

Bruno Pasqualotto Cavalar, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2023

Polynomial-Time Pseudodeterministic Construction of Primes.

Lijie Chen, Zhenjian Lu, Igor Carboni Oliveira, Hanlin Ren, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2023

2022

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.

Zhenjian Lu, Igor Carboni Oliveira, Marius Zimand

Electron. Colloquium Comput. Complex., 2022

Theory and Applications of Probabilistic Kolmogorov Complexity.

Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2022

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.

Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2022

Expander-Based Cryptography Meets Natural Proofs.

Igor C. Oliveira, Rahul Santhanam, Roei Tell

Comput. Complex., 2022

2021

Pseudodeterministic Algorithms and the Structure of Probabilistic Time.

Zhenjian Lu, Igor Carboni Oliveira, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2021

An Efficient Coding Theorem via Probabilistic Representations and its Applications.

Zhenjian Lu, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1.

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2021

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic.

Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2021

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.

Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates.

Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2020

NP-Hardness of Circuit Minimization for Multi-Output Functions.

Rahul Ilango, Bruno Loff, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2020

Quantum learning algorithms imply circuit lower bounds.

Srinivasan Arunachalam, Alex Bredariol Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram

Electron. Colloquium Comput. Complex., 2020

2019

Parity helps to compute Majority.

Igor Carboni Oliveira, Rahul Santhanam, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2019

Beyond Natural Proofs: Hardness Magnification and Locality.

Igor Carboni Oliveira, Lijie Chen, Shuichi Hirahara, Ján Pich, Ninad Rajgopal, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2019

Randomness and Intractability in Kolmogorov Complexity.

Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2019

Consistency of circuit lower bounds with bounded theories.

Jan Bydzovsky, Igor Carboni Oliveira, Jan Krajícek

Electron. Colloquium Comput. Complex., 2019

2018

Hardness Magnification for Natural Problems.

Igor Carboni Oliveira, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2018

Pseudo-derandomizing learning and approximation.

Igor Carboni Oliveira, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2018

Hardness magnification near state-of-the-art lower bounds.

Igor Carboni Oliveira, Ján Pich, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2018

NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.

Shuichi Hirahara, Igor Carboni Oliveira, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2018

On monotone circuits with local oracles and clique lower bounds.

Jan Krajícek, Igor C. Oliveira

Chic. J. Theor. Comput. Sci., 2018

An Average-Case Lower Bound Against \mathsf ACC^0 ACC 0.

Ruiwen Chen, Igor C. Oliveira, Rahul Santhanam

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2017

An Average-Case Lower Bound against ACC^0.

Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2017

Erdős-Ko-Rado for Random Hypergraphs: Asymptotics and Stability.

Marcelo M. Gauy, Hiêp Hàn, Igor C. Oliveira

Comb. Probab. Comput., 2017

2016

An Algebraic Formulation of the Graph Reconstruction Conjecture.

Igor C. Oliveira, Bhalchandra D. Thatte

J. Graph Theory, 2016

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness.

Igor Carboni Oliveira, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2016

Pseudodeterministic Constructions in Subexponential Time.

Igor Carboni Oliveira, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2016

Unprovability of circuit upper bounds in Cook's theory PV.

Jan Krajícek, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2016

Near-optimal small-depth lower bounds for small distance connectivity.

Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

2015

Unconditional Lower Bounds in Complexity Theory.

Igor Carboni Oliveira

PhD thesis, 2015

The Power of Negations in Cryptography.

Igor Carboni Oliveira, Siyao Guo, Tal Malkin, Alon Rosen

Electron. Colloquium Comput. Complex., 2015

Addition is exponentially harder than counting for shallow monotone circuits.

Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2015

Majority is Incompressible by AC^0[p] Circuits.

Igor Carboni Oliveira, Rahul Santhanam

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Majority is incompressible by AC⁰[p] circuits.

Igor Carboni Oliveira, Rahul Santhanam

Electron. Colloquium Comput. Complex., 2014

Learning circuits with few negations.

Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan

Electron. Colloquium Comput. Complex., 2014

2013

Algorithms versus Circuit Lower Bounds.

Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2013

Constructing Hard Functions from Learning Algorithms.

Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira

Electron. Colloquium Comput. Complex., 2013

Constructing Hard Functions Using Learning Algorithms.

Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira

Proceedings of the 28th Conference on Computational Complexity, 2013

2009

Erratum to "The Ricean Objection: An Analogue of Rice's Theorem for First-Order Theories" . <i>Logic Journal of the IGPL, 16(6): 585-590(2008)</i>.

Igor Carboni Oliveira, Walter Alexandre Carnielli

Log. J. IGPL, 2009

A New Look at Some Classical Results in Computational Complexity.

Arnaldo Moura, Igor Carboni Oliveira

Electron. Colloquium Comput. Complex., 2009

2008

The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories.

Igor Carboni Oliveira, Walter Alexandre Carnielli

Log. J. IGPL, 2008