Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarAlexander 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
2010 – 2019
- 2019
[i24]Nathan Mull, Shuo Pang, Alexander A. Razborov:
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, Susanna F. de Rezende
, Massimo Lauria, Jakob Nordström, Alexander A. Razborov:
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. Journal of 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. Electronic Colloquium on Computational Complexity (ECCC) 23: 10 (2016) - [i21]Alexander A. Razborov:
On Space and Depth in Resolution. Electronic Colloquium on Computational Complexity (ECCC) 23: 184 (2016) - 2015
- [i20]Alexander A. Razborov:
An Ultimate Trade-Off in Propositional Proof Complexity. Electronic Colloquium on Computational Complexity (ECCC) 22: 33 (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. Electronic Colloquium on Computational Complexity (ECCC) 21: 145 (2014) - 2013
- [j44]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) - [j43]Alexander A. Razborov:
On the Caccetta-Häggkvist Conjecture with Forbidden Subgraphs. Journal of Graph Theory 74(2): 236-248 (2013) - [j42]Alexander A. Razborov, Emanuele Viola:
Real Advantage. TOCT 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ý, Daniel Král', Serguei Norine, Alexander A. Razborov:
Non-Three-Colourable Common Graphs Exist. Comb. Probab. Comput. 21(5): 734-742 (2012) - [j40]Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov:
Parameterized Bounded-Depth Frege Is not Optimal. TOCT 4(3): 7:1-7:16 (2012) - [i18]Alexander A. Razborov, Emanuele Viola:
Real Advantage. Electronic Colloquium on Computational Complexity (ECCC) 19: 134 (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, Nicola Galesi, Massimo Lauria, Alexander A. Razborov:
Parameterized Bounded-Depth Frege Is Not Optimal. ICALP (1) 2011: 630-641 - [c27]Jakob Nordström, Alexander A. Razborov:
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. Combinatorica 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. Electronic Colloquium on Computational Complexity (ECCC) 17: 198 (2010)
2000 – 2009
- 2009
- [j32]Alexander A. Razborov:
A Simple Proof of Bazzi's Theorem. TOCT 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. Electronic Colloquium on Computational Complexity (ECCC) 16: 100 (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, Anatol Slissenko:
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, Alexander A. Sherstov:
The Sign-Rank of AC^0. Electronic Colloquium on Computational Complexity (ECCC) 15(016) (2008) - [i12]Alexander A. Razborov:
A simple proof of Bazzi's theorem. Electronic Colloquium on Computational Complexity (ECCC) 15(081) (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 of Computing 3(1): 221-238 (2007) - [i11]Venkatesan Guruswami, James R. Lee, Alexander A. Razborov:
Almost Euclidean subspaces of ℓ1N via expander codes. Electronic Colloquium on Computational Complexity (ECCC) 14(086) (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(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval. Electronic Colloquium on Computational Complexity (ECCC) 13(050) (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 Information & Computation 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. Combinatorica 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. Computational Complexity Conference 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. Electronic Colloquium on Computational Complexity (ECCC) 8(55) (2001) - [i8]Alexander A. Razborov:
Resolution Lower Bounds for the Weak Functional Pigeonhole Principle. Electronic Colloquium on Computational Complexity (ECCC) 8(075) (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. Electronic Colloquium on Computational Complexity (ECCC) 7(23) (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. Electronic Colloquium on Computational Complexity (ECCC) 6(14) (1999) - [i5]Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson:
Space Complexity in Propositional Calculus. Electronic Colloquium on Computational Complexity (ECCC)(40) (1999) - 1998
- [j15]Alexander A. Razborov:
Lower Bounds for the Polynomial Calculus. Comput. Complex. 7(4): 291-324 (1998) - [j14]Stasys Jukna, Alexander A. Razborov:
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, 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): 256-298 (1997) - [j12]Alexander A. Razborov, Steven Rudich:
Natural Proofs. J. Comput. Syst. Sci. 55(1): 24-35 (1997) - [c10]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 - [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. Electronic Colloquium on Computational Complexity (ECCC) 4(23) (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. Electronic Colloquium on Computational Complexity (ECCC) 3(37) (1996) - 1995
- [j10]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) - [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. Electronic Colloquium on Computational Complexity (ECCC) 1(6) (1994) - [i1]Alexander A. Razborov, Steven Rudich:
Natural Proofs. Electronic Colloquium on Computational Complexity (ECCC) 1(10) (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. IJAC 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, Alexander A. Razborov:
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. Computational Complexity Conference 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. Combinatorica 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).
load content from web.archive.org
Privacy notice: By enabling the option above, your browser will contact the API of web.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 and opencitations.net 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 Crossref privacy policy and the OpenCitations privacy policy.
Citation data
Add a list of citing articles from 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 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.
Tweets on dblp homepage
Show tweets from 
on the dblp homepage.
Privacy notice: By enabling the option above, your browser will contact twitter.com and twimg.com to load tweets curated by our Twitter accout. At the same time, Twitter will persitently store several cookies with your web browser. While we did signal Twitter to not track our users by setting the "dnt" flag, we do not have any control over how Twitter uses your data. So please proceed with care and consider checking the Twitter privacy policy.
last updated on 2020-05-23 00:00 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
the dblp computer science bibliography is funded by:
