default search action
Alexander A. Razborov
Person information
- affiliation: University of Chicago, Department of Computer Science, IL, USA
- award (2007): Gödel Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
- [j56]Theodoros Papamakarios, Alexander A. Razborov:
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems. J. Comput. Syst. Sci. 137: 20-36 (2023) - [j55]Leonardo Nagami Coregliano
, Alexander A. Razborov:
Natural quasirandomness properties. Random Struct. Algorithms 63(3): 624-688 (2023) - 2022
- [j54]Alexander A. Razborov:
An extremal problem motivated by triangle-free strongly regular graphs. J. Comb. Theory B 155: 52-82 (2022) - [j53]Nathan Mull, Shuo Pang
On CDCL-Based Proof Systems with the Ordered Decision Strategy. SIAM J. Comput. 51(4): 1368-1399 (2022) - [c32]Theodoros Papamakarios, Alexander A. Razborov:
Space Characterizations of Complexity Measures and Size-Space Trade-Offs in Propositional Proof Systems. ICALP 2022: 100:1-100:20 - [i27]Alexander A. Razborov:
Improved Convergence Guarantees for Shallow Neural Networks. CoRR abs/2212.02323 (2022) - 2021
- [j52]Albert Atserias, Ilario Bonacina
Clique Is Hard on Average for Regular Resolution. J. ACM 68(4): 23:1-23:26 (2021) - [i26]Theodoros Papamakarios, Alexander A. Razborov:
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [c31]Nathan Mull, Shuo Pang
On CDCL-Based Proof Systems with the Ordered Decision Strategy. SAT 2020: 149-165 - [i25]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 abs/2012.09476 (2020)
2010 – 2019
- 2019
- [i24]Nathan Mull, Shuo Pang
On CDCL-based proof systems with the ordered decision strategy. CoRR abs/1909.04135 (2019) - [i23]Leonardo Nagami Coregliano, Alexander A. Razborov:
Semantic Limits of Dense Combinatorial Objects. CoRR abs/1910.08797 (2019) - 2018
- [j51]Alexander A. Razborov:
On Space and Depth in Resolution. Comput. Complex. 27(3): 511-559 (2018) - [c30]Albert Atserias, Ilario Bonacina
Clique is hard on average for regular resolution. STOC 2018: 866-877 - 2017
- [j50]Oleg Pikhurko, Alexander A. Razborov:
Asymptotic Structure of Graphs with the Minimum Number of Triangles. Comb. Probab. Comput. 26(1): 138-160 (2017) - [j49]Leonardo Nagami Coregliano, Alexander A. Razborov:
On the Density of Transitive Tournaments. J. Graph Theory 85(1): 12-21 (2017) - [j48]Alexander A. Razborov:
On the Width of Semialgebraic Proofs and Algorithms. Math. Oper. Res. 42(4): 1106-1134 (2017) - [j47]Yuan Li, Alexander A. Razborov, Benjamin Rossman:
On the AC0 Complexity of Subgraph Isomorphism. SIAM J. Comput. 46(3): 936-971 (2017) - 2016
- [j46]Alexander A. Razborov:
A New Kind of Tradeoffs in Propositional Proof Complexity. J. ACM 63(2): 16:1-16:14 (2016) - [j45]Alexander A. Razborov:
Guest Column: Proof Complexity and Beyond. SIGACT News 47(2): 66-86 (2016) - [i22]Alexander A. Razborov:
On the Width of Semi-Algebraic Proofs and Algorithms. Electron. Colloquium Comput. Complex. TR16 (2016) - [i21]Alexander A. Razborov:
On Space and Depth in Resolution. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [i20]Alexander A. Razborov:
An Ultimate Trade-Off in Propositional Proof Complexity. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [c29]Yuan Li, Alexander A. Razborov, Benjamin Rossman:
On the AC0 Complexity of Subgraph Isomorphism. FOCS 2014: 344-353 - [i19]Yuan Li, Alexander A. Razborov, Benjamin Rossman:
On the AC0 Complexity of Subgraph Isomorphism. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j44]Hamed Hatami, Jan Hladký
On the number of pentagons in triangle-free graphs. J. Comb. Theory A 120(3): 722-732 (2013) - [j43]Alexander A. Razborov:
On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs. J. Graph Theory 74(2): 236-248 (2013) - [j42]Alexander A. Razborov, Emanuele Viola:
Real Advantage. ACM Trans. Comput. Theory 5(4): 17:1-17:8 (2013) - [p2]Alexander A. Razborov:
Flag Algebras: An Interim Report. The Mathematics of Paul Erdős II 2013: 207-232 - [p1]Alexander A. Razborov:
On Small Size Approximation Models. The Mathematics of Paul Erdős I 2013: 425-433 - 2012
- [j41]Hamed Hatami, Jan Hladký
Non-Three-Colourable Common Graphs Exist. Comb. Probab. Comput. 21(5): 734-742 (2012) - [j40]Olaf Beyersdorff
Parameterized Bounded-Depth Frege Is not Optimal. ACM Trans. Comput. Theory 4(3): 7:1-7:16 (2012) - [i18]Alexander A. Razborov, Emanuele Viola:
Real Advantage. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j39]Allan Borodin, Toniann Pitassi, Alexander A. Razborov:
Special Issue In Memory of Misha Alekhnovich. Foreword. Comput. Complex. 20(4): 579-590 (2011) - [j38]Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin tautologies. Comput. Complex. 20(4): 649-678 (2011) - [c28]Olaf Beyersdorff
Parameterized Bounded-Depth Frege Is Not Optimal. ICALP (1) 2011: 630-641 - [c27]Jakob Nordström
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. ICALP (1) 2011: 642-653 - 2010
- [j37]Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of l 1N VIA expander codes. Comb. 30(1): 47-68 (2010) - [j36]Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß:
Diameter of Polyhedra: Limits of Abstraction. Math. Oper. Res. 35(4): 786-794 (2010) - [j35]Sergei N. Artëmov, Volker Diekert, Alexander A. Razborov:
Preface. Theory Comput. Syst. 46(4): 619 (2010) - [j34]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC0. SIAM J. Comput. 39(5): 1833-1855 (2010) - [j33]Alexander A. Razborov:
On 3-Hypergraphs with Forbidden 4-Vertex Configurations. SIAM J. Discret. Math. 24(3): 946-963 (2010) - [c26]Alexander A. Razborov:
Complexity of Propositional Proofs. CSR 2010: 340-342 - [i17]Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß:
Diameter of Polyhedra: Limits of Abstraction. Flexible Network Design 2010 - [i16]Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov:
Parameterized Bounded-Depth Frege is Not Optimal. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j32]Alexander A. Razborov:
A Simple Proof of Bazzi's Theorem. ACM Trans. Comput. Theory 1(1): 3:1-3:5 (2009) - [c25]Johann A. Makowsky, Alexander A. Razborov:
The Ackermann Award 2009. CSL 2009: 561-565 - [i15]Jakob Nordström, Alexander A. Razborov:
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. CoRR abs/0910.3127 (2009) - [i14]Jakob Nordström, Alexander A. Razborov:
On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j31]Alexander A. Razborov:
On the Minimal Density of Triangles in Graphs. Comb. Probab. Comput. 17(4): 603-618 (2008) - [j30]Michael Alekhnovich, Alexander A. Razborov:
Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38(4): 1347-1363 (2008) - [c24]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC^O. FOCS 2008: 57-66 - [c23]Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of lN1 via expander codes. SODA 2008: 353-362 - [e1]Edward A. Hirsch, Alexander A. Razborov, Alexei L. Semenov
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 [contents] - [i13]Alexander A. Razborov:
A simple proof of Bazzi's theorem. Electron. Colloquium Comput. Complex. TR08 (2008) - [i12]Alexander A. Razborov, Alexander A. Sherstov:
The Sign-Rank of AC^0. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j29]Alexander A. Razborov:
Flag algebras. J. Symb. Log. 72(4): 1239-1282 (2007) - [j28]Alexander A. Razborov:
Eulogy: Michael (Misha) Alekhnovich 1978-2006. SIGACT News 38(1): 70-71 (2007) - [j27]Alexander A. Razborov, Sergey Yekhanin:
An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. Theory Comput. 3(1): 221-238 (2007) - [i11]Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of ℓ1N via expander codes. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j26]Vladimir Lifschitz, Alexander A. Razborov:
Why are there so many loop formulas? ACM Trans. Comput. Log. 7(2): 261-268 (2006) - [c22]Alexander A. Razborov, Sergey Yekhanin:
An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. FOCS 2006: 739-748 - [i10]Alexander A. Razborov, Sergey Yekhanin:
An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j25]Alexander A. Razborov:
Guessing More Secrets via List Decoding. Internet Math. 2(1): 21-30 (2005) - [c21]Erich Grädel, Janos Makowsky, Alexander A. Razborov:
The Ackermann Award 2005. CSL 2005: 557-565 - 2004
- [j24]Alexander A. Razborov:
Resolution lower bounds for perfect matching principles. J. Comput. Syst. Sci. 69(1): 3-27 (2004) - [j23]Alexander A. Razborov:
An upper bound on the threshold quantum decoherence rate. Quantum Inf. Comput. 4(3): 222-228 (2004) - [j22]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. 34(1): 67-88 (2004) - [c20]Alexander A. Razborov:
Feasible Proofs and Computations: Partnership and Fusion. ICALP 2004: 8-14 - [c19]Alexander A. Razborov:
Feasible Proofs and Computations: Partnership and Fusion. LICS 2004: 134-138 - 2003
- [j21]Alexander A. Razborov:
Propositional proof complexity. J. ACM 50(1): 80-82 (2003) - [j20]Alexander A. Razborov:
Resolution lower bounds for the weak functional pigeonhole principle. Theor. Comput. Sci. 303(1): 233-243 (2003) - 2002
- [j19]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): 555-574 (2002) - [j18]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space Complexity in Propositional Calculus. SIAM J. Comput. 31(4): 1184-1211 (2002) - [c18]Alexander A. Razborov:
Resolution Lower Bounds for Perfect Matching Principles. CCC 2002: 29-38 - [c17]Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin Tautologies. FOCS 2002: 593-603 - 2001
- [c16]Alexander A. Razborov:
Proof Complexity of Pigeonhole Principles. Developments in Language Theory 2001: 100-116 - [c15]Michael Alekhnovich, Alexander A. Razborov:
Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS 2001: 190-199 - [c14]Michael Alekhnovich, Alexander A. Razborov:
Resolution is Not Automatizable Unless W[P] is Tractable. FOCS 2001: 210-219 - [i9]Alexander A. Razborov:
Improved Resolution Lower Bounds for the Weak Pigeonhole Principle. Electron. Colloquium Comput. Complex. TR01 (2001) - [i8]Alexander A. Razborov:
Resolution Lower Bounds for the Weak Functional Pigeonhole Principle. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j17]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) - [c13]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. FOCS 2000: 43-53 - [c12]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space complexity in propositional calculus. STOC 2000: 358-367 - [i7]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [j16]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): 357-370 (1999) - [i6]Alexander A. Razborov, Nikolai K. Vereshchagin:
One Property of Cross-Intersecting Families. Electron. Colloquium Comput. Complex. TR99 (1999) - [i5]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space Complexity in Propositional Calculus. Electron. Colloquium Comput. Complex. TR99 (1999) - 1998
- [j15]Alexander A. Razborov:
Lower Bounds for the Polynomial Calculus. Comput. Complex. 7(4): 291-324 (1998) - [j14]Stasys Jukna
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much. Discret. Appl. Math. 85(3): 223-238 (1998) - [c11]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 - 1997
- [j13]Samuel R. Buss, Russell Impagliazzo
Proof Complexity in Algebraic Systems and Bounded Depth Frege Systems with Modular Counting. Comput. Complex. 6(3): 256-298 (1997) - [j12]Alexander A. Razborov, Steven Rudich:
Natural Proofs. J. Comput. Syst. Sci. 55(1): 24-35 (1997) - [c10]Stasys Jukna
On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs. MFCS 1997: 319-326 - [c9]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 - [i4]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. TR97 (1997) - 1996
- [j11]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) - [c8]Alexander A. Razborov:
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic. ICALP 1996: 48-62 - [i3]Stasys Jukna, Alexander A. Razborov:
Neither Reading Few Bits Twice nor Reading Illegally Helps Much. Electron. Colloquium Comput. Complex. TR96 (1996) - 1995
- [j10]Johan Håstad
On the Shrinkage Exponent for Read-Once Formulae. Theor. Comput. Sci. 141(1&2): 269-282 (1995) - [c7]Alexander A. Razborov:
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract). MFCS 1995: 105 - 1994
- [c6]Alexander A. Razborov, Steven Rudich:
Natural proofs. STOC 1994: 204-213 - [i2]Alexander A. Razborov:
On provably disjoint NP-pairs. Electron. Colloquium Comput. Complex. TR94 (1994) - [i1]Alexander A. Razborov, Steven Rudich:
Natural Proofs. Electron. Colloquium Comput. Complex. TR94 (1994) - 1993
- [j9]Allan Borodin, Alexander A. Razborov, Roman Smolensky:
On Lower Bounds for Read-K-Times Branching Programs. Comput. Complex. 3: 1-18 (1993) - [j8]Alexander A. Razborov, Endre Szemerédi, Avi Wigderson:
Constructing Small Sets that are Uniform in Arithmetic Progressions. Comb. Probab. Comput. 2: 513-518 (1993) - [j7]Alexander A. Razborov:
On the Parameterization of solutions for equations in Free Groups. Int. J. Algebra Comput. 3(3): 251-274 (1993) - [j6]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) - 1992
- [j5]Mikael Goldmann, Johan Håstad
Majority Gates VS. General Weighted Threshold Gates. Comput. Complex. 2: 277-300 (1992) - [j4]Alexander A. Razborov:
The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear. Discret. Math. 108(1-3): 393-396 (1992) - [j3]Alexander A. Razborov:
On the Distributional Complexity of Disjointness. Theor. Comput. Sci. 106(2): 385-390 (1992) - [c5]Mikael Goldmann, Johan Håstad, Alexander A. Razborov:
Majority Gates vs. General Weighted Threshold Gates. SCT 1992: 2-13 - [c4]Alexander A. Razborov:
On Small Depth Threshold Circuits. SWAT 1992: 42-52 - 1991
- [j2]Mike Paterson, Alexander A. Razborov:
The Set of Minimal Braids is co-NP-Complete. J. Algorithms 12(3): 393-408 (1991) - [c3]Alexander A. Razborov:
Lower Bounds for Deterministic and Nondeterministic Branching Programs. FCT 1991: 47-60 - 1990
- [j1]Alexander A. Razborov:
Applications of matrix methods to the theory of lower bounds in computational complexity. Comb. 10(1): 81-93 (1990) - [c2]Alexander A. Razborov:
On the Distributional Complexity of Disjontness. ICALP 1990: 249-253
1980 – 1989
- 1989
- [c1]Alexander A. Razborov:
On the Method of Approximations. STOC 1989: 167-176
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-20 23:05 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: