Alexander A. Razborov

Leonardo Nagami Coregliano

J. Comput. Syst. Sci., November, 2023

Natural quasirandomness properties.

[BibT_eX]

[DOI]

Random Struct. Algorithms, October, 2023

2022

On CDCL-Based Proof Systems with the Ordered Decision Strategy.

[BibT_eX]

[DOI]

Nathan Mull

Shuo Pang

SIAM J. Comput., August, 2022

An extremal problem motivated by triangle-free strongly regular graphs.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2022

Improved Convergence Guarantees for Shallow Neural Networks.

[BibT_eX]

[DOI]

CoRR, 2022

2021

Clique Is Hard on Average for Regular Resolution.

[BibT_eX]

[DOI]

Albert Atserias

Ilario Bonacina

Susanna F. de Rezende

Massimo Lauria

Jakob Nordström

Leonardo Nagami Coregliano

J. ACM, 2021

2019

Semantic Limits of Dense Combinatorial Objects.

[BibT_eX]

[DOI]

CoRR, 2019

2018

On Space and Depth in Resolution.

[BibT_eX]

[DOI]

Comput. Complex., 2018

2017

On the AC0 Complexity of Subgraph Isomorphism.

[BibT_eX]

[DOI]

Yuan Li

Benjamin Rossman

SIAM J. Comput., 2017

On the Width of Semialgebraic Proofs and Algorithms.

[BibT_eX]

[DOI]

Leonardo Nagami Coregliano

Math. Oper. Res., 2017

On the Density of Transitive Tournaments.

[BibT_eX]

[DOI]

J. Graph Theory, 2017

Asymptotic Structure of Graphs with the Minimum Number of Triangles.

[BibT_eX]

[DOI]

Oleg Pikhurko

Comb. Probab. Comput., 2017

2016

Guest Column: Proof Complexity and Beyond.

[BibT_eX]

[DOI]

SIGACT News, 2016

A New Kind of Tradeoffs in Propositional Proof Complexity.

[BibT_eX]

[DOI]

J. ACM, 2016

On the Width of Semi-Algebraic Proofs and Algorithms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

2015

An Ultimate Trade-Off in Propositional Proof Complexity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2014

On the AC0 Complexity of Subgraph Isomorphism.

[BibT_eX]

[DOI]

Yuan Li

Benjamin Rossman

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs.

[BibT_eX]

[DOI]

J. Graph Theory, 2013

On the number of pentagons in triangle-free graphs.

[BibT_eX]

[DOI]

J. Comb. Theory A, 2013

Flag Algebras: An Interim Report.

[BibT_eX]

[DOI]

Proceedings of the Mathematics of Paul Erdős II, 2013

On Small Size Approximation Models.

[BibT_eX]

[DOI]

Proceedings of the Mathematics of Paul Erdős I, 2013

2012

Real Advantage.

[BibT_eX]

[DOI]

Emanuele Viola

Electron. Colloquium Comput. Complex., 2012

Non-Three-Colourable Common Graphs Exist.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2012

2011

Special Issue In Memory of Misha Alekhnovich. Foreword.

[BibT_eX]

[DOI]

Allan Borodin

Toniann Pitassi

Comput. Complex., 2011

Satisfiability, Branch-Width and Tseitin tautologies.

[BibT_eX]

[DOI]

Comput. Complex., 2011

On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution.

[BibT_eX]

[DOI]

Jakob Nordström

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

2010

On 3-Hypergraphs with Forbidden 4-Vertex Configurations.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2010

The Sign-Rank of AC0.

[BibT_eX]

[DOI]

Alexander A. Sherstov

SIAM J. Comput., 2010

Preface.

[BibT_eX]

[DOI]

Sergei N. Artëmov

Volker Diekert

Theory Comput. Syst., 2010

Diameter of Polyhedra: Limits of Abstraction.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Nicolai Hähnle

Thomas Rothvoß

Math. Oper. Res., 2010

Parameterized Bounded-Depth Frege is Not Optimal.

[BibT_eX]

[DOI]

Olaf Beyersdorff

Nicola Galesi

Massimo Lauria

Electron. Colloquium Comput. Complex., 2010

Almost Euclidean subspaces of l 1N VIA expander codes.

[BibT_eX]

[DOI]

Venkatesan Guruswami

James R. Lee

Comb., 2010

Complexity of Propositional Proofs.

[BibT_eX]

[DOI]

Proceedings of the Computer Science, 2010

2009

On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution.

[BibT_eX]

[DOI]

Jakob Nordström

Electron. Colloquium Comput. Complex., 2009

The Ackermann Award 2009.

[BibT_eX]

[DOI]

Johann A. Makowsky

Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

2008

Resolution Is Not Automatizable Unless W[P] Is Tractable.

[BibT_eX]

[DOI]

SIAM J. Comput., 2008

The Sign-Rank of AC^0.

[BibT_eX]

[DOI]

Alexander A. Sherstov

Electron. Colloquium Comput. Complex., 2008

A simple proof of Bazzi's theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

On the Minimal Density of Triangles in Graphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2008

Almost Euclidean subspaces of lN1 via expander codes.

[BibT_eX]

[DOI]

Venkatesan Guruswami

James R. Lee

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

The Sign-Rank of AC^O.

[BibT_eX]

[DOI]

Alexander A. Sherstov

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval.

[BibT_eX]

[DOI]

Sergey Yekhanin

Theory Comput., 2007

Eulogy: Michael (Misha) Alekhnovich 1978-2006.

[BibT_eX]

[DOI]

SIGACT News, 2007

Flag algebras.

[BibT_eX]

[DOI]

J. Symb. Log., 2007

Almost Euclidean subspaces of ℓ1N via expander codes.

[BibT_eX]

[DOI]

Venkatesan Guruswami

James R. Lee

Electron. Colloquium Comput. Complex., 2007

2006

Why are there so many loop formulas?

[BibT_eX]

[DOI]

Vladimir Lifschitz

ACM Trans. Comput. Log., 2006

An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval.

[BibT_eX]

[DOI]

Sergey Yekhanin

Electron. Colloquium Comput. Complex., 2006

2005

Guessing More Secrets via List Decoding.

[BibT_eX]

[DOI]

Internet Math., 2005

The Ackermann Award 2005.

[BibT_eX]

[DOI]

Erich Grädel

Janos Makowsky

Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004

Pseudorandom Generators in Propositional Proof Complexity.

[BibT_eX]

[DOI]

Eli Ben-Sasson

SIAM J. Comput., 2004

An upper bound on the threshold quantum decoherence rate.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2004

Resolution lower bounds for perfect matching principles.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Feasible Proofs and Computations: Partnership and Fusion.

[BibT_eX]

[DOI]

Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

2003

Resolution lower bounds for the weak functional pigeonhole principle.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Propositional proof complexity.

[BibT_eX]

[DOI]

J. ACM, 2003

2002

Space Complexity in Propositional Calculus.

[BibT_eX]

[DOI]

Eli Ben-Sasson

SIAM J. Comput., 2002

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

Comb., 2002

2001

Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Lower Bounds for Polynomial Calculus: Non-Binomial Case.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Proof Complexity of Pigeonhole Principles.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory, 5th International Conference, 2001

2000

Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields.

[BibT_eX]

[DOI]

Dima Grigoriev

Appl. Algebra Eng. Commun. Comput., 2000

1999

One Property of Cross-Intersecting Families

[BibT_eX]

[DOI]

Nikolai K. Vereshchagin

Electron. Colloquium Comput. Complex., 1999

On P versus NP cap co-NP for decision trees and read-once branching programs.

[BibT_eX]

[DOI]

Stasys Jukna

Petr Savický

Ingo Wegener

Comput. Complex., 1999

1998

Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.

[BibT_eX]

[DOI]

Stasys Jukna

Discret. Appl. Math., 1998

Lower Bounds for the Polynomial Calculus.

[BibT_eX]

[DOI]

Comput. Complex., 1998

Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields.

[BibT_eX]

[DOI]

Dima Grigoriev

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Natural Proofs.

[BibT_eX]

[DOI]

Steven Rudich

J. Comput. Syst. Sci., 1997

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.

[BibT_eX]

[DOI]

Jirí Sgall

Comput. Complex., 1997

On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.

[BibT_eX]

[DOI]

Stasys Jukna

Christos H. Papadimitriou

Petr Savický

Ingo Wegener

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

1996

The future of computational complexity theory: part I.

[BibT_eX]

[DOI]

Oded Goldreich

Michael Sipser

SIGACT News, 1996

Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995

On the Shrinkage Exponent for Read-Once Formulae.

[BibT_eX]

[DOI]

Johan Håstad

Andrew Chi-Chih Yao

Theor. Comput. Sci., 1995

Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract).

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994

On provably disjoint NP-pairs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1994

1993

n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1993

On the Parameterization of solutions for equations in Free Groups.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 1993

Constructing Small Sets that are Uniform in Arithmetic Progressions.

[BibT_eX]

[DOI]

Endre Szemerédi

Comb. Probab. Comput., 1993

On Lower Bounds for Read-K-Times Branching Programs.

[BibT_eX]

[DOI]

Allan Borodin

Roman Smolensky

Comput. Complex., 1993

1992

On the Distributional Complexity of Disjointness.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1992

The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear.

[BibT_eX]

[DOI]

Discret. Math., 1992

Majority Gates VS. General Weighted Threshold Gates.

[BibT_eX]

[DOI]

Mikael Goldmann

Johan Håstad

Comput. Complex., 1992

On Small Depth Threshold Circuits.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1992

1991

The Set of Minimal Braids is co-NP-Complete.

[BibT_eX]

[DOI]

Mike Paterson

J. Algorithms, 1991

Lower Bounds for Deterministic and Nondeterministic Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1990

Applications of matrix methods to the theory of lower bounds in computational complexity.

[BibT_eX]

[DOI]

Comb., 1990

On the Distributional Complexity of Disjontness.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989

On the Method of Approximations

[BibT_eX]

[DOI]