# Alexander A. Razborov

According to our database1, Alexander A. Razborov authored at least 93 papers between 1989 and 2018.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2018
On Space and Depth in Resolution.
Computational Complexity, 2018

Clique is hard on average for regular resolution.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

2017
On the AC0 Complexity of Subgraph Isomorphism.
SIAM J. Comput., 2017

On the Width of Semialgebraic Proofs and Algorithms.
Math. Oper. Res., 2017

On the Density of Transitive Tournaments.
Journal of Graph Theory, 2017

Asymptotic Structure of Graphs with the Minimum Number of Triangles.
Combinatorics, Probability & Computing, 2017

2016
Guest Column: Proof Complexity and Beyond.
SIGACT News, 2016

A New Kind of Tradeoffs in Propositional Proof Complexity.
J. ACM, 2016

On Space and Depth in Resolution.
Electronic Colloquium on Computational Complexity (ECCC), 2016

On the Width of Semi-Algebraic Proofs and Algorithms.
Electronic Colloquium on Computational Complexity (ECCC), 2016

2015
An Ultimate Trade-Off in Propositional Proof Complexity.
Electronic Colloquium on Computational Complexity (ECCC), 2015

2014
On the AC0 Complexity of Subgraph Isomorphism.
Electronic Colloquium on Computational Complexity (ECCC), 2014

On the AC0 Complexity of Subgraph Isomorphism.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013
Real Advantage.
TOCT, 2013

On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs.
Journal of Graph Theory, 2013

On the number of pentagons in triangle-free graphs.
J. Comb. Theory, Ser. A, 2013

Flag Algebras: An Interim Report.
Proceedings of the Mathematics of Paul Erdős II, 2013

On Small Size Approximation Models.
Proceedings of the Mathematics of Paul Erdős I, 2013

2012
Real Advantage.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Non-Three-Colourable Common Graphs Exist.
Combinatorics, Probability & Computing, 2012

2011
Special Issue In Memory of Misha Alekhnovich. Foreword.
Computational Complexity, 2011

On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Parameterized Bounded-Depth Frege Is Not Optimal.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
On 3-Hypergraphs with Forbidden 4-Vertex Configurations.
SIAM J. Discrete Math., 2010

The Sign-Rank of AC0.
SIAM J. Comput., 2010

Preface.
Theory Comput. Syst., 2010

Almost Euclidean subspaces of l 1N VIA expander codes.
Combinatorica, 2010

Diameter of Polyhedra: Limits of Abstraction.
Proceedings of the Flexible Network Design, 24.05. - 28.05.2010, 2010

Complexity of Propositional Proofs.
Proceedings of the Computer Science, 2010

2009
A Simple Proof of Bazzi's Theorem.
TOCT, 2009

On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution.
Electronic Colloquium on Computational Complexity (ECCC), 2009

The Ackermann Award 2009.
Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

2008
The Sign-Rank of AC^0.
Electronic Colloquium on Computational Complexity (ECCC), 2008

A simple proof of Bazzi's theorem.
Electronic Colloquium on Computational Complexity (ECCC), 2008

On the Minimal Density of Triangles in Graphs.
Combinatorics, Probability & Computing, 2008

Almost Euclidean subspaces of lN1 via expander codes.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

The Sign-Rank of AC^O.
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.
Theory of Computing, 2007

Eulogy: Michael (Misha) Alekhnovich 1978-2006.
SIGACT News, 2007

Flag algebras.
J. Symb. Log., 2007

Almost Euclidean subspaces of ℓ1N via expander codes.
Electronic Colloquium on Computational Complexity (ECCC), 2007

2006
Why are there so many loop formulas?
ACM Trans. Comput. Log., 2006

An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval.
Electronic Colloquium on Computational Complexity (ECCC), 2006

An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Guessing More Secrets via List Decoding.
Internet Mathematics, 2005

The Ackermann Award 2005.
Proceedings of the Computer Science Logic, 19th International Workshop, 2005

2004
An upper bound on the threshold quantum decoherence rate.
Quantum Information & Computation, 2004

Feasible Proofs and Computations: Partnership and Fusion.
Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LICS 2004), 2004

Feasible Proofs and Computations: Partnership and Fusion.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003
Resolution lower bounds for the weak functional pigeonhole principle.
Theor. Comput. Sci., 2003

Propositional proof complexity.
J. ACM, 2003

2002
Satisfiability, Branch-Width and Tseitin Tautologies.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Resolution Lower Bounds for Perfect Matching Principles.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001
Resolution Lower Bounds for the Weak Functional Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC), 2001

Improved Resolution Lower Bounds for the Weak Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC), 2001

Resolution is Not Automatizable Unless W[P] is Tractable.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Lower Bounds for Polynomial Calculus: Non-Binomial Case.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Proof Complexity of Pigeonhole Principles.
Proceedings of the Developments in Language Theory, 5th International Conference, 2001

2000
Pseudorandom Generators in Propositional Proof Complexity
Electronic Colloquium on Computational Complexity (ECCC), 2000

Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields.
Appl. Algebra Eng. Commun. Comput., 2000

Space complexity in propositional calculus.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Pseudorandom Generators in Propositional Proof Complexity.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999
Space Complexity in Propositional Calculus
Electronic Colloquium on Computational Complexity (ECCC), 1999

One Property of Cross-Intersecting Families
Electronic Colloquium on Computational Complexity (ECCC), 1999

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

1998
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.
Discrete Applied Mathematics, 1998

Lower Bounds for the Polynomial Calculus.
Computational Complexity, 1998

Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs
Electronic Colloquium on Computational Complexity (ECCC), 1997

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

Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
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.
Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

1996
The future of computational complexity theory: part I.
SIGACT News, 1996

Neither Reading Few Bits Twice nor Reading Illegally Helps Much
Electronic Colloquium on Computational Complexity (ECCC), 1996

Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic.
Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

1995
On the Shrinkage Exponent for Read-Once Formulae.
Theor. Comput. Sci., 1995

Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract).
Proceedings of the Mathematical Foundations of Computer Science 1995, 1995

1994
Natural Proofs
Electronic Colloquium on Computational Complexity (ECCC), 1994

On provably disjoint NP-pairs
Electronic Colloquium on Computational Complexity (ECCC), 1994

Natural proofs.
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.
Inf. Process. Lett., 1993

On the Parameterization of solutions for equations in Free Groups.
IJAC, 1993

Constructing Small Sets that are Uniform in Arithmetic Progressions.
Combinatorics, Probability & Computing, 1993

On Lower Bounds for Read-K-Times Branching Programs.
Computational Complexity, 1993

1992
On the Distributional Complexity of Disjointness.
Theor. Comput. Sci., 1992

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

On Small Depth Threshold Circuits.
Proceedings of the Algorithm Theory, 1992

Majority Gates vs. General Weighted Threshold Gates.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 1992

1991
The Set of Minimal Braids is co-NP-Complete.
J. Algorithms, 1991

Lower Bounds for Deterministic and Nondeterministic Branching Programs.
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.
Combinatorica, 1990

On the Distributional Complexity of Disjontness.
Proceedings of the Automata, Languages and Programming, 17th International Colloquium, 1990

1989
On the Method of Approximations
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989