Google
Google Scholar
MS Academic
CiteSeerX
CORE
Semantic ScholarAlexander A. Razborov
Person information
- affiliation: University of Chicago, Department of Computer Science, IL, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2010 – today
- 2018
[j51]Alexander A. Razborov:
On Space and Depth in Resolution. Computational Complexity 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. Combinatorics, Probability & Computing 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]
- [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]
- [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. Combinatorics, Probability & Computing 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. Computational Complexity 20(4): 579-590 (2011) - [j38]Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin tautologies. Computational Complexity 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. Discrete Math. 24(3): 946-963 (2010) - [c26]
- [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]
- [c25]
- [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. Combinatorics, Probability & Computing 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]
- [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]
- [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 Mathematics 2(1): 21-30 (2005) - [c21]
- 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]
- [c19]
- 2003
- [j21]
- [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. IEEE Conference on Computational Complexity 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. Computational Complexity 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. Computational Complexity 7(4): 291-324 (1998) - [j14]Stasys Jukna, Alexander A. Razborov:
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much. Discrete Applied Mathematics 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. Computational Complexity 6(3): 256-298 (1997) - [j12]
- [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]
- [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. Computational Complexity 3: 1-18 (1993) - [j8]Alexander A. Razborov, Endre Szemerédi, Avi Wigderson:
Constructing Small Sets that are Uniform in Arithmetic Progressions. Combinatorics, Probability & Computing 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. Computational Complexity 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. Discrete Mathematics 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. Structure in Complexity Theory Conference 1992: 2-13 - [c4]
- 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]
1980 – 1989
- 1989
- [c1]
Coauthor Index
maintained by 
, founded at 
, founded at 
last updated on 2019-02-07 21:53 CET by the dblp team
data released under the ODC-BY 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
the dblp computer science bibliography is funded by:
