Igor C. Oliveira

SIGACT News, March, 2025

On the Unprovability of Circuit Size Bounds in Intuitionistic $\mathsf{S}^1_2$.

[BibT_eX]

[DOI]

Log. Methods Comput. Sci., 2025

Meta-Mathematics of Computational Complexity Theory.

[BibT_eX]

[DOI]

Bruno Pasqualotto Cavalar

Electron. Colloquium Comput. Complex., 2025

Boolean Circuit Complexity and Two-Dimensional Cover Problems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2025

Provability of the Circuit Size Hierarchy and Its Consequences.

[BibT_eX]

[DOI]

Dimitrios Tsintsilidas

Proceedings of the 16th Innovations in Theoretical Computer Science Conference, 2025

2024

Lower Bounds on the Overhead of Indistinguishability Obfuscation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

On the Unprovability of Circuit Size Bounds in Intuitionistic S12.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2024

One-Way Functions and pKt Complexity.

[BibT_eX]

[DOI]

Shuichi Hirahara

Proceedings of the Theory of Cryptography - 22nd International Conference, 2024

Polynomial-Time Pseudodeterministic Constructions (Invited Talk).

[BibT_eX]

[DOI]

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

On the Complexity of Avoiding Heavy Elements.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

Reverse Mathematics of Complexity Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

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

[BibT_eX]

[DOI]

Proceedings of the 39th Computational Complexity Conference, 2024

2023

Unprovability of Strong Complexity Lower Bounds in Bounded Arithmetic.

[BibT_eX]

[DOI]

Bruno Pasqualotto Cavalar

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

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

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Polynomial-Time Pseudodeterministic Construction of Primes.

[BibT_eX]

[DOI]

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

Constant-Depth Circuits vs. Monotone Circuits.

[BibT_eX]

[DOI]

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Theory and Applications of Probabilistic Kolmogorov Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Optimal Coding Theorems in Time-Bounded Kolmogorov Complexity.

[BibT_eX]

[DOI]

Marius Zimand

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Probabilistic Kolmogorov Complexity with Applications to Average-Case Complexity.

[BibT_eX]

[DOI]

Proceedings of the 37th Computational Complexity Conference, 2022

2021

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

[BibT_eX]

[DOI]

Xin Lyu

Electron. Colloquium Comput. Complex., 2021

Pseudodeterministic algorithms and the structure of probabilistic time.

[BibT_eX]

[DOI]

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

An Efficient Coding Theorem via Probabilistic Representations and Its Applications.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Quantum learning algorithms imply circuit lower bounds.

[BibT_eX]

[DOI]

Srinivasan Arunachalam

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

2020

Beyond Natural Proofs: Hardness Magnification and Locality.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

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

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

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

[BibT_eX]

[DOI]

Rahul Ilango

Bruno Loff

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Consistency of circuit lower bounds with bounded theories.

[BibT_eX]

[DOI]

Jan Bydzovsky

Jan Krajícek

Electron. Colloquium Comput. Complex., 2019

Expander-Based Cryptography Meets Natural Proofs.

[BibT_eX]

[DOI]

Roei Tell

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Randomness and Intractability in Kolmogorov Complexity.

[BibT_eX]

[DOI]

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Parity Helps to Compute Majority.

[BibT_eX]

[DOI]

Srikanth Srinivasan

Proceedings of the 34th Computational Complexity Conference, 2019

Hardness Magnification near State-Of-The-Art Lower Bounds.

[BibT_eX]

[DOI]

Ján Pich

Proceedings of the 34th Computational Complexity Conference, 2019

2018

On monotone circuits with local oracles and clique lower bounds.

[BibT_eX]

[DOI]

Jan Krajícek

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

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

[BibT_eX]

[DOI]

Ruiwen Chen

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

Hardness Magnification for Natural Problems.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

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

[BibT_eX]

[DOI]

Shuichi Hirahara

Proceedings of the 33rd Computational Complexity Conference, 2018

Pseudo-Derandomizing Learning and Approximation.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

An Average-Case Lower Bound against ACC^0.

[BibT_eX]

[DOI]

Ruiwen Chen

Electron. Colloquium Comput. Complex., 2017

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

[BibT_eX]

[DOI]

Marcelo M. Gauy

Hiêp Hàn

Comb. Probab. Comput., 2017

Pseudodeterministic constructions in subexponential time.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Addition is exponentially harder than counting for shallow monotone circuits.

[BibT_eX]

[DOI]

Xi Chen

Rocco A. Servedio

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Conspiracies Between Learning Algorithms, Circuit Lower Bounds, and Pseudorandomness.

[BibT_eX]

[DOI]

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

An Algebraic Formulation of the Graph Reconstruction Conjecture.

[BibT_eX]

[DOI]

Bhalchandra D. Thatte

J. Graph Theory, 2016

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

[BibT_eX]

[DOI]

Jan Krajícek

Electron. Colloquium Comput. Complex., 2016

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

[BibT_eX]

[DOI]

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

2015

Unconditional Lower Bounds in Complexity Theory.

[BibT_eX]

[DOI]

PhD thesis, 2015

The Power of Negations in Cryptography.

[BibT_eX]

[DOI]

Proceedings of the Theory of Cryptography - 12th Theory of Cryptography Conference, 2015

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

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

Learning Circuits with few Negations.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Majority is incompressible by AC0[p] circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

2013

Algorithms versus Circuit Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Constructing Hard Functions from Learning Algorithms.

[BibT_eX]

[DOI]

Adam R. Klivans

Pravesh Kothari

Electron. Colloquium Comput. Complex., 2013

Constructing Hard Functions Using Learning Algorithms.

[BibT_eX]

[DOI]

Adam R. Klivans

Pravesh Kothari

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" . Logic Journal of the IGPL, 16(6): 585-590(2008).

[BibT_eX]

[DOI]

Walter Alexandre Carnielli

Log. J. IGPL, 2009

A New Look at Some Classical Results in Computational Complexity.

[BibT_eX]

[DOI]

Arnaldo Moura

Electron. Colloquium Comput. Complex., 2009

2008

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

[BibT_eX]

[DOI]