Alexander A. Razborov

Random Struct. Algorithms, October, 2023

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

Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems.

[BibT_eX]

[DOI]

Theodoros Papamakarios

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

2020

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

[BibT_eX]

[DOI]

Nathan Mull

Shuo Pang

Leonardo Nagami Coregliano

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

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

Clique is hard on average for regular resolution.

[BibT_eX]

[DOI]

Albert Atserias

Ilario Bonacina

Susanna F. de Rezende

Massimo Lauria

Jakob Nordström

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

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

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

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

Parameterized Bounded-Depth Frege Is Not Optimal.

[BibT_eX]

[DOI]

Olaf Beyersdorff

Nicola Galesi

Massimo Lauria

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

Almost Euclidean subspaces of l 1N VIA expander codes.

[BibT_eX]

[DOI]

Venkatesan Guruswami

James R. Lee

Comb., 2010

Diameter of Polyhedra: Limits of Abstraction.

[BibT_eX]

[DOI]

Friedrich Eisenbrand

Nicolai Hähnle

Thomas Rothvoß

Proceedings of the Flexible Network Design, 24.05. - 28.05.2010, 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

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

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 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

An upper bound on the threshold quantum decoherence rate.

[BibT_eX]

[DOI]

Quantum Inf. Comput., 2004

Feasible Proofs and Computations: Partnership and Fusion.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

Propositional proof complexity.

[BibT_eX]

[DOI]

J. ACM, 2003

2002

Satisfiability, Branch-Width and Tseitin Tautologies.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Resolution Lower Bounds for Perfect Matching Principles.

[BibT_eX]

[DOI]

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Resolution Lower Bounds for the Weak Functional Pigeonhole Principle

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

Improved Resolution Lower Bounds for the Weak Pigeonhole Principle

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

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

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 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

Space complexity in propositional calculus.

[BibT_eX]

[DOI]

Eli Ben-Sasson

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Pseudorandom Generators in Propositional Proof Complexity.

[BibT_eX]

[DOI]

Eli Ben-Sasson

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 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

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

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

[BibT_eX]

[DOI]

Jirí Sgall

Comput. Complex., 1997

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

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 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

Neither Reading Few Bits Twice nor Reading Illegally Helps Much

[BibT_eX]

[DOI]

Stasys Jukna

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

Natural proofs.

[BibT_eX]

[DOI]

Steven Rudich

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 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

On Small Depth Threshold Circuits.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 1992

Majority Gates vs. General Weighted Threshold Gates.

[BibT_eX]

[DOI]

Mikael Goldmann

Johan Håstad

Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 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]