The Ricean Objection: An Analogue of Rice's Theorem for First-order Theories. - Igor Carboni Oliveira; Walter Alexandre Carnielli (Log. J. IGPL, 2008)

A New Look at Some Classical Results in Computational Complexity. - Arnaldo Moura; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2009)

Erratum to "The Ricean Objection: An Analogue of Rice's Theorem for First-Order Theories" . Logic Journal of the IGPL, 16(6): 585-590(2008). - Igor Carboni Oliveira; Walter Alexandre Carnielli (Log. J. IGPL, 2009)

Constructing Hard Functions Using Learning Algorithms. - Adam R. Klivans; Pravesh Kothari; Igor C. Oliveira 001 (CCC, 2013)

Constructing Hard Functions from Learning Algorithms. - Adam R. Klivans; Pravesh Kothari; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2013)

Algorithms versus Circuit Lower Bounds. - Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2013)

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)

Majority is incompressible by AC0[p] circuits. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2014)

Majority is Incompressible by AC^0[p] Circuits. - Igor Carboni Oliveira; Rahul Santhanam (CCC, 2015)

Addition is exponentially harder than counting for shallow monotone circuits. - Xi Chen 001; Igor Carboni Oliveira; Rocco A. Servedio (Electron. Colloquium Comput. Complex., 2015)

The Power of Negations in Cryptography. - Igor Carboni Oliveira; Siyao Guo; Tal Malkin; Alon Rosen (Electron. Colloquium Comput. Complex., 2015)

Unconditional Lower Bounds in Complexity Theory. - Igor Carboni Oliveira (2015)

Near-optimal small-depth lower bounds for small distance connectivity. - Xi Chen 001; Igor C. Oliveira 001; Rocco A. Servedio; Li-Yang Tan (STOC, 2016)

Unprovability of circuit upper bounds in Cook's theory PV. - Jan Krajícek; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2016)

Pseudodeterministic Constructions in Subexponential Time. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2016)

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2016)

An Algebraic Formulation of the Graph Reconstruction Conjecture. - Igor C. Oliveira 001; Bhalchandra D. Thatte (J. Graph Theory, 2016)

Erdős-Ko-Rado for Random Hypergraphs: Asymptotics and Stability. - Marcelo M. Gauy; Hiêp Hàn; Igor C. Oliveira 001 (Comb. Probab. Comput., 2017)

An Average-Case Lower Bound against ACC^0. - Igor Carboni Oliveira; Ruiwen Chen; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2017)

An Average-Case Lower Bound Against mathsf ACC^0 ACC 0. - Ruiwen Chen; Igor C. Oliveira 001; Rahul Santhanam (LATIN, 2018)

On monotone circuits with local oracles and clique lower bounds. - Jan Krajícek; Igor C. Oliveira 001 (Chic. J. Theor. Comput. Sci., 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)

Hardness magnification near state-of-the-art lower bounds. - Igor Carboni Oliveira; Ján Pich; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2018)

Pseudo-derandomizing learning and approximation. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2018)

Hardness Magnification for Natural Problems. - Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2018)

Consistency of circuit lower bounds with bounded theories. - Jan Bydzovsky; Igor Carboni Oliveira; Jan Krajícek (Electron. Colloquium Comput. Complex., 2019)

Randomness and Intractability in Kolmogorov Complexity. - Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2019)

Beyond Natural Proofs: Hardness Magnification and Locality. - Igor Carboni Oliveira; Lijie Chen 001; Shuichi Hirahara; Ján Pich; Ninad Rajgopal; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2019)

Parity helps to compute Majority. - Igor Carboni Oliveira; Rahul Santhanam; Srikanth Srinivasan 001 (Electron. Colloquium Comput. Complex., 2019)

Quantum learning algorithms imply circuit lower bounds. - Srinivasan Arunachalam; Alex Bredariol Grilo; Tom Gur; Igor C. Oliveira 001; Aarthi Sundaram (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)

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates. - Valentine Kabanets; Sajin Koroth; Zhenjian Lu; Dimitrios Myrisiotis; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2020)

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. - Lijie Chen 001; Zhenjian Lu; Xin Lyu 002; Igor C. Oliveira 001 (ICALP, 2021)

LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic. - Marco Carmosino; Valentine Kabanets; Antonina Kolokolova; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2021)

Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC1. - Lijie Chen 001; Zhenjian Lu; Xin Lyu 002; Igor Carboni Oliveira (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)

Pseudodeterministic Algorithms and the Structure of Probabilistic Time. - Zhenjian Lu; Igor Carboni Oliveira; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2021)

Expander-Based Cryptography Meets Natural Proofs. - Igor C. Oliveira 001; Rahul Santhanam; Roei Tell (Comput. Complex., 2022)

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity. - Halley Goldberg; Valentine Kabanets; Zhenjian Lu; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2022)

Theory and Applications of Probabilistic Kolmogorov Complexity. - Zhenjian Lu; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2022)

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity. - Zhenjian Lu; Igor Carboni Oliveira; Marius Zimand (Electron. Colloquium Comput. Complex., 2022)

Polynomial-Time Pseudodeterministic Construction of Primes. - Lijie Chen 001; Zhenjian Lu; Igor Carboni Oliveira; Hanlin Ren; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2023)

Constant-depth circuits vs. monotone circuits. - Bruno Pasqualotto Cavalar; 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)

Unprovability of strong complexity lower bounds in bounded arithmetic. - Jiatu Li; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2023)

Polynomial-Time Pseudodeterministic Constructions (Invited Talk). - Igor C. Oliveira 001 (STACS, 2024)

Reverse Mathematics of Complexity Lower Bounds. - Lijie Chen 001; Jiatu Li; Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2024)

On the Unprovability of Circuit Size Bounds in Intuitionistic S12. - Lijie Chen 001; Jiatu Li; Igor Carboni 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)

Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity. - Shuichi Hirahara; Valentine Kabanets; Zhenjian Lu; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2024)

One-Way Functions and pKt Complexity. - Shuichi Hirahara; Zhenjian Lu; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2024)

Lower Bounds on the Overhead of Indistinguishability Obfuscation. - Zhenjian Lu; Noam Mazor; Igor C. Oliveira 001; Rafael Pass (Electron. Colloquium Comput. Complex., 2024)

On the Complexity of Avoiding Heavy Elements. - Zhenjian Lu; Igor C. Oliveira 001; Hanlin Ren; Rahul Santhanam (Electron. Colloquium Comput. Complex., 2024)

Boolean Circuit Complexity and Two-Dimensional Cover Problems. - Bruno Pasqualotto Cavalar; Igor C. Oliveira 001 (Electron. Colloquium Comput. Complex., 2025)

Meta-Mathematics of Computational Complexity Theory. - Igor Carboni Oliveira (Electron. Colloquium Comput. Complex., 2025)

SIGACT News Complexity Theory Column 124 Meta-Mathematics of Computational Complexity Theory. - Igor C. Oliveira 001 (SIGACT News, 2025)