Alexander A. Razborov

118 papers A* 19A 2B 5C 1Misc 2Journal 82Unranked 5
YearRankTypeTitle / Venue / Authors
2023 J jnl
Natural quasirandomness properties.
Random Struct. Algorithms
Leonardo Nagami Coregliano, Alexander A. Razborov
2023 J jnl
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems.
J. Comput. Syst. Sci.
Theodoros Papamakarios, Alexander A. Razborov
2022 J jnl
An extremal problem motivated by triangle-free strongly regular graphs.
J. Comb. Theory B
Alexander A. Razborov
2022 J jnl
Improved Convergence Guarantees for Shallow Neural Networks.
CoRR
Alexander A. Razborov
2022 J jnl
On CDCL-Based Proof Systems with the Ordered Decision Strategy.
SIAM J. Comput.
Nathan Mull, Shuo Pang, Alexander A. Razborov
2022 A* conf
Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems.
ICALP
Theodoros Papamakarios, Alexander A. Razborov
2021 J jnl
Clique Is Hard on Average for Regular Resolution.
J. ACM
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
2021 J jnl
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems.
Electron. Colloquium Comput. Complex.
Theodoros Papamakarios, Alexander A. Razborov
2020 J jnl
Clique Is Hard on Average for Regular Resolution.
CoRR
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
2020 A conf
On CDCL-Based Proof Systems with the Ordered Decision Strategy.
SAT
Nathan Mull, Shuo Pang, Alexander A. Razborov
2019 J jnl
On CDCL-based proof systems with the ordered decision strategy.
CoRR
Nathan Mull, Shuo Pang, Alexander A. Razborov
2019 J jnl
Semantic Limits of Dense Combinatorial Objects.
CoRR
Leonardo Nagami Coregliano, Alexander A. Razborov
2018 A* conf
Clique is hard on average for regular resolution.
STOC
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
2018 J jnl
On Space and Depth in Resolution.
Comput. Complex.
Alexander A. Razborov
2017 J jnl
Asymptotic Structure of Graphs with the Minimum Number of Triangles.
Comb. Probab. Comput.
Oleg Pikhurko, Alexander A. Razborov
2017 J jnl
On the AC
SIAM J. Comput.
Yuan Li, Alexander A. Razborov, Benjamin Rossman
2017 J jnl
On the Density of Transitive Tournaments.
J. Graph Theory
Leonardo Nagami Coregliano, Alexander A. Razborov
2017 J jnl
On the Width of Semialgebraic Proofs and Algorithms.
Math. Oper. Res.
Alexander A. Razborov
2016 J jnl
A New Kind of Tradeoffs in Propositional Proof Complexity.
J. ACM
Alexander A. Razborov
2016 J jnl
Guest Column: Proof Complexity and Beyond.
SIGACT News
Alexander A. Razborov
2016 J jnl
On Space and Depth in Resolution.
Electron. Colloquium Comput. Complex.
Alexander A. Razborov
2016 J jnl
On the Width of Semi-Algebraic Proofs and Algorithms.
Electron. Colloquium Comput. Complex.
Alexander A. Razborov
2015 J jnl
An Ultimate Trade-Off in Propositional Proof Complexity.
Electron. Colloquium Comput. Complex.
Alexander A. Razborov
2014 J jnl
On the AC
Electron. Colloquium Comput. Complex.
Yuan Li, Alexander A. Razborov, Benjamin Rossman
2014 A* conf
On the AC0 Complexity of Subgraph Isomorphism.
FOCS
Yuan Li, Alexander A. Razborov, Benjamin Rossman
2013 — ch.
Flag Algebras: An Interim Report.
The Mathematics of Paul Erdős II
Alexander A. Razborov
2013 — ch.
On Small Size Approximation Models.
The Mathematics of Paul Erdős I
Alexander A. Razborov
2013 J jnl
On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs.
J. Graph Theory
Alexander A. Razborov
2013 J jnl
On the number of pentagons in triangle-free graphs.
J. Comb. Theory A
Hamed Hatami, Jan Hladký, Daniel Král', Serguei Norine, Alexander A. Razborov
2013 J jnl
Real Advantage.
ACM Trans. Comput. Theory
Alexander A. Razborov, Emanuele Viola
2012 J jnl
Non-Three-Colourable Common Graphs Exist.
Comb. Probab. Comput.
Hamed Hatami, Jan Hladký, Daniel Král', Serguei Norine, Alexander A. Razborov
2012 J jnl
Parameterized Bounded-Depth Frege Is not Optimal.
ACM Trans. Comput. Theory
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2012 J jnl
Real Advantage.
Electron. Colloquium Comput. Complex.
Alexander A. Razborov, Emanuele Viola
2011 — conf
On Minimal Unsatisfiability and Time-Space Trade-offs for
ICALP (1)
Jakob Nordström, Alexander A. Razborov
2011 — conf
Parameterized Bounded-Depth Frege Is Not Optimal.
ICALP (1)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2011 J jnl
Satisfiability, Branch-Width and Tseitin tautologies.
Comput. Complex.
Michael Alekhnovich, Alexander A. Razborov
2011 J jnl
Special Issue In Memory of Misha Alekhnovich. Foreword.
Comput. Complex.
Allan Borodin, Toniann Pitassi, Alexander A. Razborov
2010 J jnl
Almost Euclidean subspaces of
Comb.
Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
2010 Misc conf
Complexity of Propositional Proofs.
CSR
Alexander A. Razborov
2010 — conf
Diameter of Polyhedra: Limits of Abstraction.
Flexible Network Design
Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß
2010 J jnl
Diameter of Polyhedra: Limits of Abstraction.
Math. Oper. Res.
Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß
2010 J jnl
On 3-Hypergraphs with Forbidden 4-Vertex Configurations.
SIAM J. Discret. Math.
Alexander A. Razborov
2010 J jnl
Parameterized Bounded-Depth Frege is Not Optimal.
Electron. Colloquium Comput. Complex.
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
2010 J jnl
Preface.
Theory Comput. Syst.
Sergei N. Artëmov, Volker Diekert, Alexander A. Razborov
2010 J jnl
The Sign-Rank of AC
SIAM J. Comput.
Alexander A. Razborov, Alexander A. Sherstov
2009 J jnl
A Simple Proof of Bazzi's Theorem.
ACM Trans. Comput. Theory
Alexander A. Razborov
2009 J jnl
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution
CoRR
Jakob Nordström, Alexander A. Razborov
2009 J jnl
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution.
Electron. Colloquium Comput. Complex.
Jakob Nordström, Alexander A. Razborov
2009 B conf
The Ackermann Award 2009.
CSL
Johann A. Makowsky, Alexander A. Razborov
2008 J jnl
A simple proof of Bazzi's theorem.
Electron. Colloquium Comput. Complex.
Alexander A. Razborov
2008 A* conf
Almost Euclidean subspaces of l
SODA
Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
2008 Misc ed.
Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings
CSR
Edward A. Hirsch, Alexander A. Razborov, Alexei L. Semenov, Anatol Slissenko
2008 J jnl
On the Minimal Density of Triangles in Graphs.
Comb. Probab. Comput.
Alexander A. Razborov
2008 J jnl
Resolution Is Not Automatizable Unless W[P] Is Tractable.
SIAM J. Comput.
Michael Alekhnovich, Alexander A. Razborov
2008 J jnl
The Sign-Rank of AC^0.
Electron. Colloquium Comput. Complex.
Alexander A. Razborov, Alexander A. Sherstov
2008 A* conf
The Sign-Rank of AC^O.
FOCS
Alexander A. Razborov, Alexander A. Sherstov
2007 J jnl
Almost Euclidean subspaces of ℓ
Electron. Colloquium Comput. Complex.
Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
2007 J jnl
An Omega(
Theory Comput.
Alexander A. Razborov, Sergey Yekhanin
2007 J jnl
Eulogy: Michael (Misha) Alekhnovich 1978-2006.
SIGACT News
Alexander A. Razborov
2007 J jnl
Flag algebras.
J. Symb. Log.
Alexander A. Razborov
2006 A* conf
An Omega(n
FOCS
Alexander A. Razborov, Sergey Yekhanin
2006 J jnl
An Omega(n
Electron. Colloquium Comput. Complex.
Alexander A. Razborov, Sergey Yekhanin
2006 J jnl
Why are there so many loop formulas?
ACM Trans. Comput. Log.
Vladimir Lifschitz, Alexander A. Razborov
2005 J jnl
Guessing More Secrets via List Decoding.
Internet Math.
Alexander A. Razborov
2005 B conf
The Ackermann Award 2005.
CSL
Erich Grädel, Janos Makowsky, Alexander A. Razborov
2004 J jnl
An upper bound on the threshold quantum decoherence rate.
Quantum Inf. Comput.
Alexander A. Razborov
2004 A* conf
Feasible Proofs and Computations: Partnership and Fusion.
ICALP
Alexander A. Razborov
2004 A* conf
Feasible Proofs and Computations: Partnership and Fusion.
LICS
Alexander A. Razborov
2004 J jnl
Pseudorandom Generators in Propositional Proof Complexity.
SIAM J. Comput.
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2004 J jnl
Resolution lower bounds for perfect matching principles.
J. Comput. Syst. Sci.
Alexander A. Razborov
2003 J jnl
Propositional proof complexity.
J. ACM
Alexander A. Razborov
2003 J jnl
Resolution lower bounds for the weak functional pigeonhole principle.
Theor. Comput. Sci.
Alexander A. Razborov
2002 J jnl
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
Comb.
Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao
2002 A conf
Resolution Lower Bounds for Perfect Matching Principles.
CCC
Alexander A. Razborov
2002 A* conf
Satisfiability, Branch-Width and Tseitin Tautologies.
FOCS
Michael Alekhnovich, Alexander A. Razborov
2002 J jnl
Space Complexity in Propositional Calculus.
SIAM J. Comput.
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2001 J jnl
Improved Resolution Lower Bounds for the Weak Pigeonhole Principle
Electron. Colloquium Comput. Complex.
Alexander A. Razborov
2001 A* conf
Lower Bounds for Polynomial Calculus: Non-Binomial Case.
FOCS
Michael Alekhnovich, Alexander A. Razborov
2001 C conf
Proof Complexity of Pigeonhole Principles.
Developments in Language Theory
Alexander A. Razborov
2001 J jnl
Resolution Lower Bounds for the Weak Functional Pigeonhole Principle
Electron. Colloquium Comput. Complex.
Alexander A. Razborov
2001 A* conf
Resolution is Not Automatizable Unless W[P] is Tractable.
FOCS
Michael Alekhnovich, Alexander A. Razborov
2000 J jnl
Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields.
Appl. Algebra Eng. Commun. Comput.
Dima Grigoriev, Alexander A. Razborov
2000 J jnl
Pseudorandom Generators in Propositional Proof Complexity
Electron. Colloquium Comput. Complex.
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2000 A* conf
Pseudorandom Generators in Propositional Proof Complexity.
FOCS
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
2000 A* conf
Space complexity in propositional calculus.
STOC
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
1999 J jnl
On P versus NP cap co-NP for decision trees and read-once branching programs.
Comput. Complex.
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
1999 J jnl
One Property of Cross-Intersecting Families
Electron. Colloquium Comput. Complex.
Alexander A. Razborov, Nikolai K. Vereshchagin
1999 J jnl
Space Complexity in Propositional Calculus
Electron. Colloquium Comput. Complex.
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
1998 A* conf
Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields.
FOCS
Dima Grigoriev, Alexander A. Razborov
1998 J jnl
Lower Bounds for the Polynomial Calculus.
Comput. Complex.
Alexander A. Razborov
1998 J jnl
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.
Discret. Appl. Math.
Stasys Jukna, Alexander A. Razborov
1997 J jnl
Natural Proofs.
J. Comput. Syst. Sci.
Alexander A. Razborov, Steven Rudich
1997 B conf
On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.
MFCS
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
1997 J jnl
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs
Electron. Colloquium Comput. Complex.
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
1997 J jnl
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting.
Comput. Complex.
Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall
1997 A* conf
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus.
STOC
Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao
1996 A* conf
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic.
ICALP
Alexander A. Razborov
1996 J jnl
Neither Reading Few Bits Twice nor Reading Illegally Helps Much
Electron. Colloquium Comput. Complex.
Stasys Jukna, Alexander A. Razborov
1996 J jnl
The future of computational complexity theory: part I.
SIGACT News
Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser
1995 B conf
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract).
MFCS
Alexander A. Razborov
1995 J jnl
On the Shrinkage Exponent for Read-Once Formulae.
Theor. Comput. Sci.
Johan Håstad, Alexander A. Razborov, Andrew Chi-Chih Yao
1994 J jnl
Natural Proofs
Electron. Colloquium Comput. Complex.
Alexander A. Razborov, Steven Rudich
1994 A* conf
Natural proofs.
STOC
Alexander A. Razborov, Steven Rudich
1994 J jnl
On provably disjoint NP-pairs
Electron. Colloquium Comput. Complex.
Alexander A. Razborov
1993 J jnl
Constructing Small Sets that are Uniform in Arithmetic Progressions.
Comb. Probab. Comput.
Alexander A. Razborov, Endre Szemerédi, Avi Wigderson
1993 J jnl
On Lower Bounds for Read-K-Times Branching Programs.
Comput. Complex.
Allan Borodin, Alexander A. Razborov, Roman Smolensky
1993 J jnl
On the Parameterization of solutions for equations in Free Groups.
Int. J. Algebra Comput.
Alexander A. Razborov
1993 J jnl
n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom.
Inf. Process. Lett.
Alexander A. Razborov, Avi Wigderson
1992 J jnl
Majority Gates VS. General Weighted Threshold Gates.
Comput. Complex.
Mikael Goldmann, Johan Håstad, Alexander A. Razborov
1992 — conf
Majority Gates vs. General Weighted Threshold Gates.
SCT
Mikael Goldmann, Johan Håstad, Alexander A. Razborov
1992 — conf
On Small Depth Threshold Circuits.
SWAT
Alexander A. Razborov
1992 J jnl
On the Distributional Complexity of Disjointness.
Theor. Comput. Sci.
Alexander A. Razborov
1992 J jnl
The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear.
Discret. Math.
Alexander A. Razborov
1991 B conf
Lower Bounds for Deterministic and Nondeterministic Branching Programs.
FCT
Alexander A. Razborov
1991 J jnl
The Set of Minimal Braids is co-NP-Complete.
J. Algorithms
Mike Paterson, Alexander A. Razborov
1990 J jnl
Applications of matrix methods to the theory of lower bounds in computational complexity.
Comb.
Alexander A. Razborov
1990 A* conf
On the Distributional Complexity of Disjontness.
ICALP
Alexander A. Razborov
1989 A* conf
On the Method of Approximations
STOC
Alexander A. Razborov