Rahul Santhanam

Iddo Tzameret

CoRR, September, 2025

Computational Complexity of Discrete Problems (Dagstuhl Seminar 25111).

[BibT_eX]

[DOI]

Dagstuhl Reports, March, 2025

How to Construct Random Strings.

[BibT_eX]

[DOI]

Oliver Korten

Proceedings of the 40th Computational Complexity Conference, 2025

2024

Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity.

[BibT_eX]

[DOI]

Zhenjian Lu

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

From Proof Complexity to Circuit Complexity via Interactive Protocols.

[BibT_eX]

[DOI]

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

On the Complexity of Avoiding Heavy Elements.

[BibT_eX]

[DOI]

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

2023

Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).

[BibT_eX]

[DOI]

Dagstuhl Reports, March, 2023

Towards P $\neq$ NP from Extended Frege Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2023

Polynomial-Time Pseudodeterministic Construction of Primes.

[BibT_eX]

[DOI]

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

An Algorithmic Approach to Uniform Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 38th Computational Complexity Conference, 2023

Pebbles and Branching Programs for Tree Evaluation.

[BibT_eX]

[DOI]

Proceedings of the Logic, 2023

2022

Robustness of average-case meta-complexity via pseudorandomness.

[BibT_eX]

[DOI]

Rahul Ilango

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

A Relativization Perspective on Meta-Complexity.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Excluding PH Pessiland.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Errorless Versus Error-Prone Average-Case Complexity.

[BibT_eX]

[DOI]

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Learning Algorithms Versus Automatability of Frege Systems.

[BibT_eX]

[DOI]

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

Why MCSP Is a More Important Problem Than SAT (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2022

On the Range Avoidance Problem for Circuits.

[BibT_eX]

[DOI]

Zhikun Wang

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

On Randomized Reductions to the Random Strings.

[BibT_eX]

[DOI]

Michael E. Saks

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Hardness on any Samplable Distribution Suffices: New Characterizations of One-Way Functions by Meta-Complexity.

[BibT_eX]

[DOI]

Rahul Ilango

Electron. Colloquium Comput. Complex., 2021

Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2021

Iterated lower bound formulas: a diagonalization-based approach to proof complexity.

[BibT_eX]

[DOI]

Iddo Tzameret

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

Strong co-nondeterministic lower bounds for NP cannot be proved feasibly.

[BibT_eX]

[DOI]

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

Pseudodeterministic algorithms and the structure of probabilistic time.

[BibT_eX]

[DOI]

Zhenjian Lu

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

Constructive Separations and Their Consequences.

[BibT_eX]

[DOI]

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

Hardness of KT Characterizes Parallel Cryptography.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

On the Pseudo-Deterministic Query Complexity of NP Search Problems.

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

On the Structure of Learnability Beyond P/Poly.

[BibT_eX]

[DOI]

Ninad Rajgopal

Proceedings of the Approximation, 2021

2020

Pseudorandomness and the Minimum Circuit Size Problem.

[BibT_eX]

[DOI]

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

Beyond Natural Proofs: Hardness Magnification and Locality.

[BibT_eX]

[DOI]

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

Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions.

[BibT_eX]

[DOI]

Michael E. Saks

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).

[BibT_eX]

[DOI]

Anna Gál

Till Tantau

Dagstuhl Reports, 2019

Expander-Based Cryptography Meets Natural Proofs.

[BibT_eX]

[DOI]

Roei Tell

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

Why are Proof Complexity Lower Bounds Hard?

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Parity Helps to Compute Majority.

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

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

[BibT_eX]

[DOI]

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Proof Complexity (Dagstuhl Seminar 18051).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2018

Deterministically Counting Satisfying Assignments for Constant-Depth Circuits with Parity Gates, with Implications for Lower Bounds.

[BibT_eX]

[DOI]

Ninad Rajgopal

Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science, 2018

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

[BibT_eX]

[DOI]

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]

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]

Electron. Colloquium Comput. Complex., 2017

Pseudodeterministic constructions in subexponential time.

[BibT_eX]

[DOI]

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

On the Average-Case Complexity of MCSP and Its Variants.

[BibT_eX]

[DOI]

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Special Section on the Forty-Fourth Annual ACM Symposium on Theory of Computing (STOC 2012).

[BibT_eX]

[DOI]

Andrew McGregor

SIAM J. Comput., 2016

Satisfiability on Mixed Instances.

[BibT_eX]

[DOI]

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

Exponential Time Paradigms Through the Polynomial Time Lens.

[BibT_eX]

[DOI]

Andrew Drucker

Jesper Nederlof

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

New Non-Uniform Lower Bounds for Uniform Classes.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits.

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

Beating Exhaustive Search for Quantified Boolean Formulas and Connections to Circuit Complexity.

[BibT_eX]

[DOI]

Richard Ryan Williams

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP.

[BibT_eX]

[DOI]

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2015, 2015

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

[BibT_eX]

[DOI]

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Majority is incompressible by AC0[p] circuits.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Hierarchies Against Sublinear Advice.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Optimal algorithms and proofs (Dagstuhl Seminar 14421).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

On Uniformity and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Comput. Complex., 2014

2013

New Algorithms for QBF Satisfiability and Implications for Circuit Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

On Medium-Uniformity and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Pebbles and Branching Programs for Tree Evaluation.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2012

Uniform Circuits, Lower Bounds, and QBF Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Macroscopes: models for collective decision making

[BibT_eX]

[DOI]

Subramanian Ramamoorthy

András Z. Salamon

CoRR, 2012

Stronger Lower Bounds and Randomness-Hardness Trade-Offs Using Associated Algebraic Complexity Classes.

[BibT_eX]

[DOI]

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Instance Compression for the Polynomial Hierarchy and beyond.

[BibT_eX]

[DOI]

Chiranjit Chakraborty

Proceedings of the Parameterized and Exact Computation - 7th International Symposium, 2012

Marginal hitting sets imply super-polynomial lower bounds for permanent.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

On the Limits of Sparsification.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Lower Bounds on Interactive Compressibility by Constant-Depth Circuits.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011

Stronger Lower Bounds and Randomness-Hardness Tradeoffs using Associated Algebraic Complexity Classes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Robust Simulations and Significant Separations.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds.

[BibT_eX]

[DOI]

Yuval Filmus

Toniann Pitassi

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010

Effectively Polynomial Simulations.

[BibT_eX]

[DOI]

Toniann Pitassi

Proceedings of the Innovations in Computer Science, 2010

Bounding Rationality by Discounting Time.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2010

Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability.

[BibT_eX]

[DOI]

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

The Complexity of Explicit Constructions.

[BibT_eX]

[DOI]

Proceedings of the Programs, Proofs, Processes, 6th Conference on Computability in Europe, 2010

2009

Branching Programs for Tree Evaluation.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Fractional Pebbling and Thrifty Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Unconditional Lower Bounds against Advice.

[BibT_eX]

[DOI]

Harry Buhrman

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

Fixed-Polynomial Size Circuit Bounds.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Infeasibility of instance compression and succinct PCPs for NP.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Time Hierarchies: A Survey.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Circuit lower bounds for Merlin-Arthur classes.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Fixed-Polynomial Size Circuit Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Uniform Hardness Amplification in NP via Monotone Codes.

[BibT_eX]

[DOI]

Joshua Buresh-Oppenheim

Valentine Kabanets

Electron. Colloquium Comput. Complex., 2006

Graph splicing systems.

[BibT_eX]

[DOI]

Kamala Krithivasan

Discret. Appl. Math., 2006

Graph model selection using maximum likelihood.

[BibT_eX]

[DOI]

Ivona Bezáková

Adam Kalai

Proceedings of the Machine Learning, 2006

Some Results on Average-Case Hardness Within the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Aduri Pavan

N. V. Vinodchandran

Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Making Hard Problems Harder.

[BibT_eX]

[DOI]

Joshua Buresh-Oppenheim

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Holographic Proofs and Derandmization.

[BibT_eX]

[DOI]

Dieter van Melkebeek

SIAM J. Comput., 2005

Hierarchies for semantic classes.

[BibT_eX]

[DOI]

Luca Trevisan

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

Promise Hierarchies

[BibT_eX]

[DOI]

Luca Trevisan

Electron. Colloquium Comput. Complex., 2004

Hierarchy Theorems for Probabilistic Polynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

2003

Holographic Proofs and Derandomization.

[BibT_eX]

[DOI]

Dieter van Melkebeek

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Resource Tradeoffs and Derandomization

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

2001

Lower bounds on the complexity of recognizing SAT by Turing machines.

[BibT_eX]

[DOI]

Inf. Process. Lett., 2001

On segregators, separators and time versus space

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

On Separators, Segregators and Time versus Space.

[BibT_eX]

[DOI]