Igor C. Oliveira

83 papers A* 14A 11B 1Journal 54Unranked 3
YearRankTypeTitle / Venue / Authors
2026 J jnl
A Theory for Probabilistic Polynomial-Time Reasoning.
CoRR
Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams
2026 J jnl
A Theory for Probabilistic Polynomial-Time Reasoning.
Electron. Colloquium Comput. Complex.
Lijie Chen, Jiatu Li, Igor C. Oliveira, Ryan Williams
2026 J jnl
Failure of Symmetry of Information for Randomized Computations.
Electron. Colloquium Comput. Complex.
Jinqiao Hu, Yahel Manor, Igor C. Oliveira
2025 J jnl
Boolean Circuit Complexity and Two-Dimensional Cover Problems.
CoRR
Bruno Pasqualotto Cavalar, Igor C. Oliveira
2025 J jnl
Boolean Circuit Complexity and Two-Dimensional Cover Problems.
Electron. Colloquium Comput. Complex.
Bruno Pasqualotto Cavalar, Igor C. Oliveira
2025 J jnl
Boolean Circuit Complexity and Two-Dimensional Cover Problems.
ACM Trans. Comput. Theory
Bruno Cavalar, Igor C. Oliveira
2025 J jnl
Equivalence Between Coding and Complexity Lower Bounds.
Electron. Colloquium Comput. Complex.
Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira
2025 J jnl
Hardness of Computing Nondeterministic Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Jinqiao Hu, Zhenjian Lu, Igor C. Oliveira
2025 J jnl
Meta-Mathematics of Computational Complexity Theory.
CoRR
Igor C. Oliveira
2025 J jnl
On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$.
Log. Methods Comput. Sci.
Lijie Chen, Jiatu Li, Igor C. Oliveira
2025 A conf
Provability of the Circuit Size Hierarchy and Its Consequences.
ITCS
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira, Dimitrios Tsintsilidas
2025 J jnl
SIGACT News Complexity Theory Column 124 Meta-Mathematics of Computational Complexity Theory.
SIGACT News
Igor C. Oliveira
2025 J jnl
Synergies Between Complexity Theory and Nondeterministic Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Halley Goldberg, Jinqiao Hu, Zhenjian Lu, Jingyi Lyu, Igor C. Oliveira
2024 A conf
Exact Search-To-Decision Reductions for Time-Bounded Kolmogorov Complexity.
CCC
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
Exact Search-to-Decision Reductions for Time-Bounded Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
Lower Bounds on the Overhead of Indistinguishability Obfuscation.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass
2024 J jnl
Lower Bounds on the Overhead of Indistinguishability Obfuscation.
IACR Cryptol. ePrint Arch.
Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass
2024 A* conf
On the Complexity of Avoiding Heavy Elements.
FOCS
Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2024 J jnl
On the Complexity of Avoiding Heavy Elements.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2024 J jnl
On the Unprovability of Circuit Size Bounds in Intuitionistic S
CoRR
Lijie Chen, Jiatu Li, Igor C. Oliveira
2024 — conf
One-Way Functions and pKt Complexity.
TCC (1)
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
One-Way Functions and pKt Complexity.
Electron. Colloquium Comput. Complex.
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 J jnl
One-Way Functions and pKt Complexity.
IACR Cryptol. ePrint Arch.
Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira
2024 A conf
Polynomial-Time Pseudodeterministic Constructions (Invited Talk).
STACS
Igor C. Oliveira
2024 A* conf
Reverse Mathematics of Complexity Lower Bounds.
FOCS
Lijie Chen, Jiatu Li, Igor C. Oliveira
2023 J jnl
A Duality Between One-Way Functions and Average-Case Symmetry of Information.
IACR Cryptol. ePrint Arch.
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira
2023 A* conf
A Duality between One-Way Functions and Average-Case Symmetry of Information.
STOC
Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira
2023 A conf
Constant-Depth Circuits vs. Monotone Circuits.
CCC
Bruno Pasqualotto Cavalar, Igor C. Oliveira
2023 J jnl
Constant-depth circuits vs. monotone circuits.
CoRR
Bruno Pasqualotto Cavalar, Igor C. Oliveira
2023 A* conf
Polynomial-Time Pseudodeterministic Construction of Primes.
FOCS
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2023 J jnl
Polynomial-Time Pseudodeterministic Construction of Primes.
CoRR
Lijie Chen, Zhenjian Lu, Igor C. Oliveira, Hanlin Ren, Rahul Santhanam
2023 A* conf
Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic.
STOC
Jiatu Li, Igor C. Oliveira
2022 J jnl
Expander-Based Cryptography Meets Natural Proofs.
Comput. Complex.
Igor C. Oliveira, Rahul Santhanam, Roei Tell
2022 A* conf
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.
ICALP
Zhenjian Lu, Igor C. Oliveira, Marius Zimand
2022 J jnl
Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.
CoRR
Zhenjian Lu, Igor C. Oliveira, Marius Zimand
2022 A conf
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.
CCC
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2022 J jnl
Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.
Electron. Colloquium Comput. Complex.
Halley Goldberg, Valentine Kabanets, Zhenjian Lu, Igor C. Oliveira
2022 J jnl
Theory and Applications of Probabilistic Kolmogorov Complexity.
CoRR
Zhenjian Lu, Igor C. Oliveira
2022 J jnl
Theory and Applications of Probabilistic Kolmogorov Complexity.
Bull. EATCS
Zhenjian Lu, Igor C. Oliveira
2022 J jnl
Theory and Applications of Probabilistic Kolmogorov Complexity.
Electron. Colloquium Comput. Complex.
Zhenjian Lu, Igor C. Oliveira
2021 J jnl
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates.
ACM Trans. Comput. Theory
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2021 A* conf
An Efficient Coding Theorem via Probabilistic Representations and Its Applications.
ICALP
Zhenjian Lu, Igor C. Oliveira
2021 J jnl
Hardness Magnification Near State-of-the-Art Lower Bounds.
Theory Comput.
Igor C. Oliveira, Ján Pich, Rahul Santhanam
2021 A* conf
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic.
FOCS
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira
2021 J jnl
LEARN-Uniform Circuit Lower Bounds and Provability in Bounded Arithmetic.
Electron. Colloquium Comput. Complex.
Marco Carmosino, Valentine Kabanets, Antonina Kolokolova, Igor C. Oliveira
2021 A* conf
Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹.
ICALP
Lijie Chen, Zhenjian Lu, Xin Lyu, Igor C. Oliveira
2021 J jnl
Pseudodeterministic Algorithms and the Structure of Probabilistic Time.
CoRR
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
2021 A* conf
Pseudodeterministic algorithms and the structure of probabilistic time.
STOC
Zhenjian Lu, Igor C. Oliveira, Rahul Santhanam
2021 A* conf
Quantum learning algorithms imply circuit lower bounds.
FOCS
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
2020 A conf
Algorithms and Lower Bounds for De Morgan Formulas of Low-Communication Leaf Gates.
CCC
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020 J jnl
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates.
CoRR
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020 J jnl
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates.
Electron. Colloquium Comput. Complex.
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor C. Oliveira
2020 A conf
Beyond Natural Proofs: Hardness Magnification and Locality.
ITCS
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2020 J jnl
Consistency of circuit lower bounds with bounded theories.
Log. Methods Comput. Sci.
Jan Bydzovsky, Jan Krajícek, Igor C. Oliveira
2020 A conf
NP-Hardness of Circuit Minimization for Multi-Output Functions.
CCC
Rahul Ilango, Bruno Loff, Igor C. Oliveira
2020 J jnl
Quantum learning algorithms imply circuit lower bounds.
CoRR
Srinivasan Arunachalam, Alex B. Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
2020 J jnl
Quantum learning algorithms imply circuit lower bounds.
Electron. Colloquium Comput. Complex.
Srinivasan Arunachalam, Alex Bredariol Grilo, Tom Gur, Igor C. Oliveira, Aarthi Sundaram
2019 J jnl
Beyond Natural Proofs: Hardness Magnification and Locality.
CoRR
Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, Rahul Santhanam
2019 J jnl
Consistency of circuit lower bounds with bounded theories.
CoRR
Jan Bydzovsky, Jan Krajícek, Igor C. Oliveira
2018 B conf
An Average-Case Lower Bound Against \mathsf ACC^0 ACC 0.
LATIN
Ruiwen Chen, Igor C. Oliveira, Rahul Santhanam
2018 A conf
NP-hardness of Minimum Circuit Size Problem for OR-AND-MOD Circuits.
CCC
Shuichi Hirahara, Igor C. Oliveira, Rahul Santhanam
2018 J jnl
On monotone circuits with local oracles and clique lower bounds.
Chic. J. Theor. Comput. Sci.
Jan Krajícek, Igor C. Oliveira
2017 A* conf
Addition is exponentially harder than counting for shallow monotone circuits.
STOC
Xi Chen, Igor C. Oliveira, Rocco A. Servedio
2017 A conf
Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness.
CCC
Igor C. Oliveira, Rahul Santhanam
2017 J jnl
Erdős-Ko-Rado for Random Hypergraphs: Asymptotics and Stability.
Comb. Probab. Comput.
Marcelo M. Gauy, Hiêp Hàn, Igor C. Oliveira
2017 J jnl
On monotone circuits with local oracles and clique lower bounds.
CoRR
Jan Krajícek, Igor C. Oliveira
2017 A* conf
Pseudodeterministic constructions in subexponential time.
STOC
Igor C. Oliveira, Rahul Santhanam
2017 J jnl
Unprovability of circuit upper bounds in Cook's theory PV.
Log. Methods Comput. Sci.
Jan Krajícek, Igor C. Oliveira
2016 J jnl
An Algebraic Formulation of the Graph Reconstruction Conjecture.
J. Graph Theory
Igor C. Oliveira, Bhalchandra D. Thatte
2016 J jnl
Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness.
CoRR
Igor C. Oliveira, Rahul Santhanam
2016 A* conf
Near-optimal small-depth lower bounds for small distance connectivity.
STOC
Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2016 J jnl
Pseudodeterministic Constructions in Subexponential Time.
CoRR
Igor C. Oliveira, Rahul Santhanam
2015 J jnl
Addition is exponentially harder than counting for shallow monotone circuits.
CoRR
Xi Chen, Igor C. Oliveira, Rocco A. Servedio
2015 — conf
Learning Circuits with few Negations.
APPROX-RANDOM
Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2015 J jnl
Near-optimal small-depth lower bounds for small distance connectivity.
CoRR
Xi Chen, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2015 — conf
The Power of Negations in Cryptography.
TCC (1)
Siyao Guo, Tal Malkin, Igor C. Oliveira, Alon Rosen
2014 J jnl
Learning circuits with few negations.
CoRR
Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2014 J jnl
The Power of Negations in Cryptography.
IACR Cryptol. ePrint Arch.
Siyao Guo, Tal Malkin, Igor C. Oliveira, Alon Rosen
2013 J jnl
Algorithms versus Circuit Lower Bounds.
CoRR
Igor C. Oliveira
2013 J jnl
Algorithms versus Circuit Lower Bounds.
Electron. Colloquium Comput. Complex.
Igor C. Oliveira
2013 J jnl
An algebraic formulation of the graph reconstruction conjecture
CoRR
Igor C. Oliveira, Bhalchandra D. Thatte
2013 A conf
Constructing Hard Functions Using Learning Algorithms.
CCC
Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira
2013 J jnl
Constructing Hard Functions from Learning Algorithms.
Electron. Colloquium Comput. Complex.
Adam R. Klivans, Pravesh Kothari, Igor C. Oliveira