Alexander A. Razborov

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): 722-732 (2013)

Hamed Hatami, Jan Hladký, Daniel Král', Serguei Norine, Alexander A. Razborov: Non-Three-Colourable Common Graphs Exist. Combinatorics, Probability & Computing 21(5): 734-742 (2012)

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov: Parameterized Bounded-Depth Frege Is not Optimal. TOCT 4(3): 7 (2012)

Alexander A. Razborov, Emanuele Viola: Real Advantage. Electronic Colloquium on Computational Complexity (ECCC) 19: 134 (2012)

Allan Borodin, Toniann Pitassi, Alexander A. Razborov: Special Issue In Memory of Misha Alekhnovich. Foreword. Computational Complexity 20(4): 579-590 (2011)

Michael Alekhnovich, Alexander A. Razborov: Satisfiability, Branch-Width and Tseitin tautologies. Computational Complexity 20(4): 649-678 (2011)

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov: Parameterized Bounded-Depth Frege Is Not Optimal. ICALP (1) 2011: 630-641

Jakob Nordström, Alexander A. Razborov: On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. ICALP (1) 2011: 642-653

Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of l ₁^N VIA expander codes. Combinatorica 30(1): 47-68 (2010)

Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß: Diameter of Polyhedra: Limits of Abstraction. Math. Oper. Res. 35(4): 786-794 (2010)

Sergei N. Artëmov, Volker Diekert, Alexander A. Razborov: Preface. Theory Comput. Syst. 46(4): 619 (2010)

Alexander A. Razborov, Alexander A. Sherstov: The Sign-Rank of AC⁰. SIAM J. Comput. 39(5): 1833-1855 (2010)

Alexander A. Razborov: On 3-Hypergraphs with Forbidden 4-Vertex Configurations. SIAM J. Discrete Math. 24(3): 946-963 (2010)

Alexander A. Razborov: Complexity of Propositional Proofs. CSR 2010: 340-342

Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov: Parameterized Bounded-Depth Frege is Not Optimal. Electronic Colloquium on Computational Complexity (ECCC) 17: 198 (2010)

Alexander A. Razborov: A Simple Proof of Bazzi's Theorem. TOCT 1(1) (2009)

Johann A. Makowsky, Alexander A. Razborov: The Ackermann Award 2009. CSL 2009: 561-565

Jakob Nordström, Alexander A. Razborov: On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. CoRR abs/0910.3127 (2009)

Jakob Nordström, Alexander A. Razborov: On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. Electronic Colloquium on Computational Complexity (ECCC) 16: 100 (2009)

Alexander A. Razborov: On the Minimal Density of Triangles in Graphs. Combinatorics, Probability & Computing 17(4): 603-618 (2008)

Michael Alekhnovich, Alexander A. Razborov: Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38(4): 1347-1363 (2008)

Alexander A. Razborov, Alexander A. Sherstov: The Sign-Rank of AC^O. FOCS 2008: 57-66

Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of l^N₁ via expander codes. SODA 2008: 353-362

Edward A. Hirsch, Alexander A. Razborov, Alexei L. Semenov, Anatol Slissenko (Eds.): Computer Science - Theory and Applications, Third International Computer Science Symposium in Russia, CSR 2008, Moscow, Russia, June 7-12, 2008, Proceedings. Lecture Notes in Computer Science 5010, Springer 2008, isbn 978-3-540-79708-1

Alexander A. Razborov, Alexander A. Sherstov: The Sign-Rank of AC^0. Electronic Colloquium on Computational Complexity (ECCC) 15(016) (2008)

Alexander A. Razborov: A simple proof of Bazzi's theorem. Electronic Colloquium on Computational Complexity (ECCC) 15(081) (2008)

Alexander A. Razborov: Flag algebras. J. Symb. Log. 72(4): 1239-1282 (2007)

Alexander A. Razborov: Eulogy: Michael (Misha) Alekhnovich 1978-2006. SIGACT News 38(1): 70-71 (2007)

Alexander A. Razborov, Sergey Yekhanin: An Omega(n^1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. Theory of Computing 3(1): 221-238 (2007)

Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of $\ell_1^N$ via expander codes. Electronic Colloquium on Computational Complexity (ECCC) 14(086) (2007)

Vladimir Lifschitz, Alexander A. Razborov: Why are there so many loop formulas? ACM Trans. Comput. Log. 7(2): 261-268 (2006)

Alexander A. Razborov, Sergey Yekhanin: An Omega(n^1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. FOCS 2006: 739-748

Alexander A. Razborov, Sergey Yekhanin: An Omega(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval. Electronic Colloquium on Computational Complexity (ECCC) 13(050) (2006)

Alexander A. Razborov: Guessing More Secrets via List Decoding. Internet Mathematics 2(1): 21-30 (2005)

Erich Grädel, Janos Makowsky, Alexander A. Razborov: The Ackermann Award 2005. CSL 2005: 557-565

Alexander A. Razborov: Resolution lower bounds for perfect matching principles. J. Comput. Syst. Sci. 69(1): 3-27 (2004)

Alexander A. Razborov: An upper bound on the threshold quantum decoherence rate. Quantum Information & Computation 4(3): 222-228 (2004)

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. 34(1): 67-88 (2004)

Alexander A. Razborov: Feasible Proofs and Computations: Partnership and Fusion. ICALP 2004: 8-14

Alexander A. Razborov: Feasible Proofs and Computations: Partnership and Fusion. LICS 2004: 134-138

Alexander A. Razborov: Propositional proof complexity. J. ACM 50(1): 80-82 (2003)

Alexander A. Razborov: Resolution lower bounds for the weak functional pigeonhole principle. Theor. Comput. Sci. 1(303): 233-243 (2003)

Alexander A. Razborov, Avi Wigderson, Andrew Chi-Chih Yao: Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. Combinatorica 22(4): 555-574 (2002)

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space Complexity in Propositional Calculus. SIAM J. Comput. 31(4): 1184-1211 (2002)

Alexander A. Razborov: Resolution Lower Bounds for Perfect Matching Principles. IEEE Conference on Computational Complexity 2002: 29-38

Michael Alekhnovich, Alexander A. Razborov: Satisfiability, Branch-Width and Tseitin Tautologies. FOCS 2002: 593-603

Alexander A. Razborov: Proof Complexity of Pigeonhole Principles. Developments in Language Theory 2001: 100-116

Michael Alekhnovich, Alexander A. Razborov: Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS 2001: 190-199

Michael Alekhnovich, Alexander A. Razborov: Resolution is Not Automatizable Unless W[P] is Tractable. FOCS 2001: 210-219

Alexander A. Razborov: Improved Resolution Lower Bounds for the Weak Pigeonhole Principle. Electronic Colloquium on Computational Complexity (ECCC) 8(55) (2001)

Alexander A. Razborov: Resolution Lower Bounds for the Weak Functional Pigeonhole Principle. Electronic Colloquium on Computational Complexity (ECCC) 8(075) (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): 465-487 (2000)

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. FOCS 2000: 43-53

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space complexity in propositional calculus. STOC 2000: 358-367

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. Electronic Colloquium on Computational Complexity (ECCC) 7(23) (2000)

Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener: On P versus NP cap co-NP for decision trees and read-once branching programs. Computational Complexity 8(4): 357-370 (1999)

Alexander A. Razborov, Nikolai K. Vereshchagin: One Property of Cross-Intersecting Families. Electronic Colloquium on Computational Complexity (ECCC) 6(14) (1999)

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space Complexity in Propositional Calculus. Electronic Colloquium on Computational Complexity (ECCC)(40) (1999)

Alexander A. Razborov: Lower Bounds for the Polynomial Calculus. Computational Complexity 7(4): 291-324 (1998)

Stasys Jukna, Alexander A. Razborov: Neither Reading Few Bits Twice Nor Reading Illegally Helps Much. Discrete Applied Mathematics 85(3): 223-238 (1998)

Dima Grigoriev, Alexander A. Razborov: Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. FOCS 1998: 269-278

Samuel R. Buss, Russell Impagliazzo, Jan Krajícek, Pavel Pudlák, Alexander A. Razborov, Jiri Sgall: Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Computational Complexity 6(3): 256-298 (1997)

Alexander A. Razborov, Steven Rudich: Natural Proofs. J. Comput. Syst. Sci. 55(1): 24-35 (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: 319-326

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: 739-748

Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener: On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs. Electronic Colloquium on Computational Complexity (ECCC) 4(23) (1997)

Christos H. Papadimitriou, Oded Goldreich, Avi Wigderson, Alexander A. Razborov, Michael Sipser: The future of computational complexity theory: part I. SIGACT News 27(3): 6-12 (1996)

Alexander A. Razborov: Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic. ICALP 1996: 48-62

Stasys Jukna, Alexander A. Razborov: Neither Reading Few Bits Twice nor Reading Illegally Helps Much. Electronic Colloquium on Computational Complexity (ECCC) 3(37) (1996)

Johan Håstad, Alexander A. Razborov, Andrew Chi-Chih Yao: On the Shrinkage Exponent for Read-Once Formulae. Theor. Comput. Sci. 141(1&2): 269-282 (1995)

Alexander A. Razborov: Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract). MFCS 1995: 105

Alexander A. Razborov, Steven Rudich: Natural proofs. STOC 1994: 204-213

Alexander A. Razborov: On provably disjoint NP-pairs. Electronic Colloquium on Computational Complexity (ECCC) 1(6) (1994)

Alexander A. Razborov, Steven Rudich: Natural Proofs. Electronic Colloquium on Computational Complexity (ECCC) 1(10) (1994)

Allan Borodin, Alexander A. Razborov, Roman Smolensky: On Lower Bounds for Read-K-Times Branching Programs. Computational Complexity 3: 1-18 (1993)

Alexander A. Razborov, Endre Szemerédi, Avi Wigderson: Constructing Small Sets that are Uniform in Arithmetic Progressions. Combinatorics, Probability & Computing 2: 513-518 (1993)

Alexander A. Razborov, Avi Wigderson: n^Omega(log n) Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom. Inf. Process. Lett. 45(6): 303-307 (1993)

Mikael Goldmann, Johan Håstad, Alexander A. Razborov: Majority Gates VS. General Weighted Threshold Gates. Computational Complexity 2: 277-300 (1992)

Alexander A. Razborov: The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear. Discrete Mathematics 108(1-3): 393-396 (1992)

Alexander A. Razborov: On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106(2): 385-390 (1992)

Mikael Goldmann, Johan Håstad, Alexander A. Razborov: Majority Gates vs. General Weighted Threshold Gates. Structure in Complexity Theory Conference 1992: 2-13

Alexander A. Razborov: On Small Depth Threshold Circuits. SWAT 1992: 42-52

Mike Paterson, Alexander A. Razborov: The Set of Minimal Braids is co-NP-Complete. J. Algorithms 12(3): 393-408 (1991)

Alexander A. Razborov: Lower Bounds for Deterministic and Nondeterministic Branching Programs. FCT 1991: 47-60

Alexander A. Razborov: Applications of matrix methods to the theory of lower bounds in computational complexity. Combinatorica 10(1): 81-93 (1990)

Alexander A. Razborov: On the Distributional Complexity of Disjontness. ICALP 1990: 249-253

Alexander A. Razborov: On the Method of Approximations. STOC 1989: 167-176