Alexander A. Razborov

Publication Activity (10 Years)

Years Active: 1989-2023
Publications (10 Years): 23

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

SIAM J. Comput.

J. ACM

Publications

Leonardo Nagami Coregliano, Alexander A. Razborov
Natural quasirandomness properties. Random Struct. Algorithms 63 (3) (2023)
Theodoros Papamakarios, Alexander A. Razborov
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems. J. Comput. Syst. Sci. 137 (2023)
Nathan Mull, Shuo Pang, Alexander A. Razborov
On CDCL-Based Proof Systems with the Ordered Decision Strategy. SIAM J. Comput. 51 (4) (2022)
Alexander A. Razborov
Improved Convergence Guarantees for Shallow Neural Networks. CoRR (2022)
Alexander A. Razborov
An extremal problem motivated by triangle-free strongly regular graphs. J. Comb. Theory, Ser. B 155 (2022)
Theodoros Papamakarios, Alexander A. Razborov
Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems. ICALP (2022)
Nathan Mull, Shuo Pang, Alexander A. Razborov
On CDCL-Based Proof Systems with the Ordered Decision Strategy. SIAM J. Comput. 51 (4) (2022)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique Is Hard on Average for Regular Resolution. J. ACM 68 (4) (2021)
Theodoros Papamakarios, Alexander A. Razborov
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems. Electron. Colloquium Comput. Complex. 28 (2021)
Nathan Mull, Shuo Pang, Alexander A. Razborov
On CDCL-Based Proof Systems with the Ordered Decision Strategy. SAT (2020)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique Is Hard on Average for Regular Resolution. CoRR (2020)
Leonardo Nagami Coregliano, Alexander A. Razborov
Semantic Limits of Dense Combinatorial Objects. CoRR (2019)
Nathan Mull, Shuo Pang, Alexander A. Razborov
On CDCL-based proof systems with the ordered decision strategy. CoRR (2019)
Alexander A. Razborov
On Space and Depth in Resolution. Comput. Complex. 27 (3) (2018)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique is hard on average for regular resolution. STOC (2018)
Leonardo Nagami Coregliano, Alexander A. Razborov
On the Density of Transitive Tournaments. J. Graph Theory 85 (1) (2017)
Oleg Pikhurko, Alexander A. Razborov
Asymptotic Structure of Graphs with the Minimum Number of Triangles. Comb. Probab. Comput. 26 (1) (2017)
Alexander A. Razborov
On the Width of Semialgebraic Proofs and Algorithms. Math. Oper. Res. 42 (4) (2017)
Yuan Li, Alexander A. Razborov, Benjamin Rossman
Complexity of Subgraph Isomorphism. SIAM J. Comput. 46 (3) (2017)
Alexander A. Razborov
A New Kind of Tradeoffs in Propositional Proof Complexity. J. ACM 63 (2) (2016)
Alexander A. Razborov
Guest Column: Proof Complexity and Beyond. SIGACT News 47 (2) (2016)
Alexander A. Razborov
On Space and Depth in Resolution. Electron. Colloquium Comput. Complex. 23 (2016)
Alexander A. Razborov
On the Width of Semi-Algebraic Proofs and Algorithms. Electron. Colloquium Comput. Complex. 23 (2016)
Alexander A. Razborov
An Ultimate Trade-Off in Propositional Proof Complexity. Electron. Colloquium Comput. Complex. 22 (2015)
Yuan Li, Alexander A. Razborov, Benjamin Rossman
Complexity of Subgraph Isomorphism. Electron. Colloquium Comput. Complex. 21 (2014)
Yuan Li, Alexander A. Razborov, Benjamin Rossman
On the AC0 Complexity of Subgraph Isomorphism. FOCS (2014)
Alexander A. Razborov
On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs. J. Graph Theory 74 (2) (2013)
Hamed Hatami, Jan Hladký, Daniel Král', Serguei Norine, Alexander A. Razborov
On the number of pentagons in triangle-free graphs. J. Comb. Theory, Ser. A 120 (3) (2013)
Alexander A. Razborov, Emanuele Viola
Real Advantage. ACM Trans. Comput. Theory 5 (4) (2013)
Alexander A. Razborov, Emanuele Viola
Real Advantage. Electron. Colloquium Comput. Complex. 19 (2012)
Hamed Hatami, Jan Hladký, Daniel Král', Serguei Norine, Alexander A. Razborov
Non-Three-Colourable Common Graphs Exist. Comb. Probab. Comput. 21 (5) (2012)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
Parameterized Bounded-Depth Frege Is not Optimal. ACM Trans. Comput. Theory 4 (3) (2012)
Jakob Nordström, Alexander A. Razborov
-DNF Resolution. ICALP (1) (2011)
Michael Alekhnovich, Alexander A. Razborov
Satisfiability, Branch-Width and Tseitin tautologies. Comput. Complex. 20 (4) (2011)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
Parameterized Bounded-Depth Frege Is Not Optimal. ICALP (1) (2011)
Allan Borodin, Toniann Pitassi, Alexander A. Razborov
Special Issue In Memory of Misha Alekhnovich. Foreword. Comput. Complex. 20 (4) (2011)
Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß
Diameter of Polyhedra: Limits of Abstraction. Flexible Network Design (2010)
Alexander A. Razborov
Complexity of Propositional Proofs. CSR (2010)
Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß
Diameter of Polyhedra: Limits of Abstraction. Math. Oper. Res. 35 (4) (2010)
Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
VIA expander codes. Comb. 30 (1) (2010)
Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov
Parameterized Bounded-Depth Frege is Not Optimal. Electron. Colloquium Comput. Complex. 17 (2010)
Alexander A. Razborov, Alexander A. Sherstov
. SIAM J. Comput. 39 (5) (2010)
Sergei N. Artëmov, Volker Diekert, Alexander A. Razborov
Preface. Theory Comput. Syst. 46 (4) (2010)
Alexander A. Razborov
On 3-Hypergraphs with Forbidden 4-Vertex Configurations. SIAM J. Discret. Math. 24 (3) (2010)
Jakob Nordström, Alexander A. Razborov
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. Electron. Colloquium Comput. Complex. 16 (2009)
Jakob Nordström, Alexander A. Razborov
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution CoRR (2009)
Johann A. Makowsky, Alexander A. Razborov
The Ackermann Award 2009. CSL (2009)
Alexander A. Razborov
A Simple Proof of Bazzi's Theorem. ACM Trans. Comput. Theory 1 (1) (2009)
Alexander A. Razborov
A simple proof of Bazzi's theorem. Electron. Colloquium Comput. Complex. 15 (081) (2008)
Michael Alekhnovich, Alexander A. Razborov
Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38 (4) (2008)
Alexander A. Razborov
On the Minimal Density of Triangles in Graphs. Comb. Probab. Comput. 17 (4) (2008)
Alexander A. Razborov, Alexander A. Sherstov
The Sign-Rank of AC^O. FOCS (2008)
Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
via expander codes. SODA (2008)
Alexander A. Razborov, Alexander A. Sherstov
The Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. 15 (016) (2008)
Alexander A. Razborov, Sergey Yekhanin
) Lower Bound for Bilinear Group Based Private Information Retrieval. Theory Comput. 3 (1) (2007)
Venkatesan Guruswami, James R. Lee, Alexander A. Razborov
via expander codes. Electron. Colloquium Comput. Complex. 14 (086) (2007)
Alexander A. Razborov
Flag algebras. J. Symb. Log. 72 (4) (2007)
Alexander A. Razborov
Eulogy: Michael (Misha) Alekhnovich 1978-2006. SIGACT News 38 (1) (2007)
Vladimir Lifschitz, Alexander A. Razborov
Why are there so many loop formulas? ACM Trans. Comput. Log. 7 (2) (2006)
Alexander A. Razborov, Sergey Yekhanin
An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval. Electron. Colloquium Comput. Complex. 13 (050) (2006)
Alexander A. Razborov, Sergey Yekhanin
) Lower Bound for Bilinear Group Based Private Information Retrieval. FOCS (2006)
Alexander A. Razborov
Guessing More Secrets via List Decoding. Internet Math. 2 (1) (2005)
Erich Grädel, Janos Makowsky, Alexander A. Razborov
The Ackermann Award 2005. CSL (2005)
Alexander A. Razborov
An upper bound on the threshold quantum decoherence rate. Quantum Inf. Comput. 4 (3) (2004)
Alexander A. Razborov
Feasible Proofs and Computations: Partnership and Fusion. LICS (2004)
Alexander A. Razborov
Feasible Proofs and Computations: Partnership and Fusion. ICALP (2004)
Alexander A. Razborov
Resolution lower bounds for perfect matching principles. J. Comput. Syst. Sci. 69 (1) (2004)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. 34 (1) (2004)
Alexander A. Razborov
Propositional proof complexity. J. ACM 50 (1) (2003)
Alexander A. Razborov
Resolution lower bounds for the weak functional pigeonhole principle. Theor. Comput. Sci. 303 (1) (2003)
Alexander A. Razborov
Resolution Lower Bounds for Perfect Matching Principles. Computational Complexity Conference (2002)
Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. Comb. 22 (4) (2002)
Michael Alekhnovich, Alexander A. Razborov
Satisfiability, Branch-Width and Tseitin Tautologies. FOCS (2002)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Space Complexity in Propositional Calculus. SIAM J. Comput. 31 (4) (2002)
Michael Alekhnovich, Alexander A. Razborov
Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS (2001)
Alexander A. Razborov
Proof Complexity of Pigeonhole Principles. Developments in Language Theory (2001)
Michael Alekhnovich, Alexander A. Razborov
Resolution is Not Automatizable Unless W[P] is Tractable. FOCS (2001)
Alexander A. Razborov
Resolution Lower Bounds for the Weak Functional Pigeonhole Principle Electron. Colloquium Comput. Complex. 8 (075) (2001)
Alexander A. Razborov
Improved Resolution Lower Bounds for the Weak Pigeonhole Principle Electron. Colloquium Comput. Complex. 8 (55) (2001)
Dima Grigoriev, Alexander A. Razborov
Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. Appl. Algebra Eng. Commun. Comput. 10 (6) (2000)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Pseudorandom Generators in Propositional Proof Complexity. FOCS (2000)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Pseudorandom Generators in Propositional Proof Complexity Electron. Colloquium Comput. Complex. 7 (23) (2000)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Space complexity in propositional calculus. STOC (2000)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Space Complexity in Propositional Calculus Electron. Colloquium Comput. Complex. (40) (1999)
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
On P versus NP cap co-NP for decision trees and read-once branching programs. Comput. Complex. 8 (4) (1999)
Alexander A. Razborov, Nikolai K. Vereshchagin
One Property of Cross-Intersecting Families Electron. Colloquium Comput. Complex. 6 (14) (1999)
Alexander A. Razborov
Lower Bounds for the Polynomial Calculus. Comput. Complex. 7 (4) (1998)
Dima Grigoriev, Alexander A. Razborov
Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. FOCS (1998)
Stasys Jukna, Alexander A. Razborov
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much. Discret. Appl. Math. 85 (3) (1998)
Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jirí Sgall
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Comput. Complex. 6 (3) (1997)
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs Electron. Colloquium Comput. Complex. 4 (23) (1997)
Alexander A. Razborov, Steven Rudich
Natural Proofs. J. Comput. Syst. Sci. 55 (1) (1997)
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs. MFCS (1997)
Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao
Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. STOC (1997)
Stasys Jukna, Alexander A. Razborov
Neither Reading Few Bits Twice nor Reading Illegally Helps Much Electron. Colloquium Comput. Complex. 3 (37) (1996)
Alexander A. Razborov
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic. ICALP (1996)
Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser
The future of computational complexity theory: part I. SIGACT News 27 (3) (1996)
Alexander A. Razborov
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract). MFCS (1995)
Johan Håstad, Alexander A. Razborov, Andrew Chi-Chih Yao
On the Shrinkage Exponent for Read-Once Formulae. Theor. Comput. Sci. 141 (1&2) (1995)
Alexander A. Razborov, Steven Rudich
Natural proofs. STOC (1994)

Alexander A. Razborov.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Alexander A. Razborov