Rahul Santhanam

Electron. Colloquium Comput. Complex., 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

2023

Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111).

[BibT_eX]

[DOI]

Dagstuhl Reports, March, 2023

An Algorithmic Approach to Uniform Lower Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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]

Lijie Chen

Zhenjian Lu

Electron. Colloquium Comput. Complex., 2023

Pebbles and Branching Programs for Tree Evaluation.

[BibT_eX]

[DOI]

Proceedings of the Logic, 2023

2022

Beyond Natural Proofs: Hardness Magnification and Locality.

[BibT_eX]

[DOI]

Lijie Chen

Ninad Rajgopal

J. ACM, 2022

On Randomized Reductions to the Random Strings.

[BibT_eX]

[DOI]

Michael E. Saks

Electron. Colloquium Comput. Complex., 2022

On the Range Avoidance Problem for Circuits.

[BibT_eX]

[DOI]

Zhikun Wang

Electron. Colloquium Comput. Complex., 2022

Expander-Based Cryptography Meets Natural Proofs.

[BibT_eX]

[DOI]

Igor C. Oliveira

Roei Tell

Comput. Complex., 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

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

2021

Hardness Magnification Near State-of-the-Art Lower Bounds.

[BibT_eX]

[DOI]

Igor C. Oliveira

Theory Comput., 2021

Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity.

[BibT_eX]

[DOI]

Iddo Tzameret

Electron. Colloquium Comput. Complex., 2021

A Relativization Perspective on Meta-Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Hardness of KT Characterizes Parallel Cryptography.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

On the Structure of Learnability beyond P/poly.

[BibT_eX]

[DOI]

Ninad Rajgopal

Electron. Colloquium Comput. Complex., 2021

Pseudodeterministic Algorithms and the Structure of Probabilistic Time.

[BibT_eX]

[DOI]

Zhenjian Lu

Electron. Colloquium Comput. Complex., 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

Constructive Separations and Their Consequences.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2021

Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121).

[BibT_eX]

[DOI]

Dagstuhl Reports, 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

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

[BibT_eX]

[DOI]

Proceedings of the 36th Computational Complexity Conference, 2021

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

Pseudorandomness and the Minimum Circuit Size Problem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Parity helps to compute Majority.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121).

[BibT_eX]

[DOI]

Anna Gál

Till Tantau

Dagstuhl Reports, 2019

Why are Proof Complexity Lower Bounds Hard?

[BibT_eX]

[DOI]

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

2018

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

[BibT_eX]

[DOI]

Theory Comput., 2018

Hardness Magnification for Natural Problems.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

Pseudo-derandomizing learning and approximation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2018

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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]

Igor C. Oliveira

Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2017

Robust simulations and significant separations.

[BibT_eX]

[DOI]

Inf. Comput., 2017

An Average-Case Lower Bound against ACC^0.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

Conspiracies between Learning Algorithms, Circuit Lower Bounds and Pseudorandomness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Pseudodeterministic Constructions in Subexponential Time.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2015

Exponential Lower Bounds for AC<sup>0</sup>-Frege Imply Superpolynomial Frege Lower Bounds.

[BibT_eX]

[DOI]

Yuval Filmus

Toniann Pitassi

ACM Trans. Comput. Theory, 2015

Satisfiability on Mixed Instances.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

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 AC<sup>0</sup>[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

Permanent does not have succinct polynomial size arithmetic circuits of constant depth.

[BibT_eX]

[DOI]

Inf. Comput., 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

The Complexity of Explicit Constructions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 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

Lower Bounds on Interactive Compressibility by Constant-Depth Circuits.

[BibT_eX]

[DOI]

Arkadev Chattopadhyay

Electron. Colloquium Comput. Complex., 2012

Instance Compression for the Polynomial Hierarchy and Beyond.

[BibT_eX]

[DOI]

Chiranjit Chakraborty

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

2011

Infeasibility of instance compression and succinct PCPs for NP.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2011

On the Limits of Sparsification.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Marginal Hitting Sets Imply Super-Polynomial Lower Bounds for Permanent.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 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

2009

Unconditional Lower Bounds against Advice.

[BibT_eX]

[DOI]

Harry Buhrman

Electron. Colloquium Comput. Complex., 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

Fixed-Polynomial Size Circuit Bounds.

[BibT_eX]

[DOI]

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

2007

Circuit Lower Bounds for Merlin-Arthur Classes.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Time Hierarchies: A Survey.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

2006

Fixed-Polynomial Size Circuit Bounds.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Making Hard Problems Harder

[BibT_eX]

[DOI]

Joshua Buresh-Oppenheim

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

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 (FOCS 2004), 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]