Alexander A. Razborov

Affiliations:
  • University of Chicago, Department of Computer Science, IL, USA


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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2023
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems.
J. Comput. Syst. Sci., November, 2023

Natural quasirandomness properties.
Random Struct. Algorithms, October, 2023

2022
On CDCL-Based Proof Systems with the Ordered Decision Strategy.
SIAM J. Comput., August, 2022

An extremal problem motivated by triangle-free strongly regular graphs.
J. Comb. Theory B, 2022

Improved Convergence Guarantees for Shallow Neural Networks.
CoRR, 2022

2021
Clique Is Hard on Average for Regular Resolution.
J. ACM, 2021

2019
Semantic Limits of Dense Combinatorial Objects.
CoRR, 2019

2018
On Space and Depth in Resolution.
Comput. Complex., 2018

2017
On the AC<sup>0</sup> 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.
J. Graph Theory, 2017

Asymptotic Structure of Graphs with the Minimum Number of Triangles.
Comb. Probab. Comput., 2017

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

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

On the Width of Semi-Algebraic Proofs and Algorithms.
Electron. Colloquium Comput. Complex., 2016

2015
An Ultimate Trade-Off in Propositional Proof Complexity.
Electron. Colloquium Comput. Complex., 2015

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

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

On the number of pentagons in triangle-free graphs.
J. Comb. Theory 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.
Electron. Colloquium Comput. Complex., 2012

Non-Three-Colourable Common Graphs Exist.
Comb. Probab. Comput., 2012

2011
Special Issue In Memory of Misha Alekhnovich. Foreword.
Comput. Complex., 2011

Satisfiability, Branch-Width and Tseitin tautologies.
Comput. Complex., 2011

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

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

The Sign-Rank of AC<sup>0</sup>.
SIAM J. Comput., 2010

Preface.
Theory Comput. Syst., 2010

Diameter of Polyhedra: Limits of Abstraction.
Math. Oper. Res., 2010

Parameterized Bounded-Depth Frege is Not Optimal.
Electron. Colloquium Comput. Complex., 2010

Almost Euclidean subspaces of <i>l</i> <sub>1</sub><sup><i>N</i></sup> VIA expander codes.
Comb., 2010

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

2009
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution.
Electron. Colloquium Comput. Complex., 2009

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

2008
Resolution Is Not Automatizable Unless W[P] Is Tractable.
SIAM J. Comput., 2008

The Sign-Rank of AC^0.
Electron. Colloquium Comput. Complex., 2008

A simple proof of Bazzi's theorem.
Electron. Colloquium Comput. Complex., 2008

On the Minimal Density of Triangles in Graphs.
Comb. Probab. Comput., 2008

Almost Euclidean subspaces of l<sup>N</sup><sub>1</sub> 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(<i>n</i><sup>1/3</sup>) Lower Bound for Bilinear Group Based Private Information Retrieval.
Theory Comput., 2007

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

Flag algebras.
J. Symb. Log., 2007

Almost Euclidean subspaces of ℓ<sub>1</sub><sup>N</sup> via expander codes.
Electron. Colloquium Comput. Complex., 2007

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

An Omega(n<sup>1/3</sup>) Lower Bound for Bilinear Group Based Private Information Retrieval.
Electron. Colloquium Comput. Complex., 2006

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

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

2004
Pseudorandom Generators in Propositional Proof Complexity.
SIAM J. Comput., 2004

An upper bound on the threshold quantum decoherence rate.
Quantum Inf. Comput., 2004

Resolution lower bounds for perfect matching principles.
J. Comput. Syst. Sci., 2004

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

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

Propositional proof complexity.
J. ACM, 2003

2002
Space Complexity in Propositional Calculus.
SIAM J. Comput., 2002

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

2001
Improved Resolution Lower Bounds for the Weak Pigeonhole Principle
Electron. Colloquium Comput. Complex., 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
Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields.
Appl. Algebra Eng. Commun. Comput., 2000

1999
One Property of Cross-Intersecting Families
Electron. Colloquium Comput. Complex., 1999

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

1998
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.
Discret. Appl. Math., 1998

Lower Bounds for the Polynomial Calculus.
Comput. Complex., 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
Natural Proofs.
J. Comput. Syst. Sci., 1997

Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.
Comput. Complex., 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

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
On provably disjoint NP-pairs
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.
Inf. Process. Lett., 1993

On the Parameterization of solutions for equations in Free Groups.
Int. J. Algebra Comput., 1993

Constructing Small Sets that are Uniform in Arithmetic Progressions.
Comb. Probab. Comput., 1993

On Lower Bounds for Read-K-Times Branching Programs.
Comput. Complex., 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.
Discret. Math., 1992

Majority Gates VS. General Weighted Threshold Gates.
Comput. Complex., 1992

On Small Depth Threshold Circuits.
Proceedings of the Algorithm Theory, 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.
Comb., 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


  Loading...