default search action
Alexander A. Razborov
- > Home > Persons > Alexander A. Razborov
Publications
- 2022
- [j53]Nathan Mull, Shuo Pang, Alexander A. Razborov:
On CDCL-Based Proof Systems with the Ordered Decision Strategy. SIAM J. Comput. 51(4): 1368-1399 (2022) - 2021
- [j52]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): 23:1-23:26 (2021) - 2020
- [c31]Nathan Mull, Shuo Pang, Alexander A. Razborov:
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) - 2019
- [i24]Nathan Mull, Shuo Pang, Alexander A. Razborov:
On CDCL-based proof systems with the ordered decision strategy. CoRR abs/1909.04135 (2019) - 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) - [j47]Yuan Li, Alexander A. Razborov, Benjamin Rossman:
On the AC0 Complexity of Subgraph Isomorphism. SIAM J. Comput. 46(3): 936-971 (2017) - 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ý, Daniel Král', Serguei Norine, Alexander A. Razborov:
On the number of pentagons in triangle-free graphs. J. Comb. Theory A 120(3): 722-732 (2013) - [j42]Alexander A. Razborov, Emanuele Viola:
Real Advantage. ACM Trans. Comput. Theory 5(4): 17:1-17:8 (2013) - 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. 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, 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. 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) - [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) - 2009
- [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
- [j30]Michael Alekhnovich, Alexander A. Razborov:
Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38(4): 1347-1363 (2008) - [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] - 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
- [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) - 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) - 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) - [c17]Michael Alekhnovich, Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin Tautologies. FOCS 2002: 593-603 - 2001
- [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 - 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) - 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
- [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. 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) - [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, Alexander A. Razborov, Andrew Chi-Chih Yao:
On the Shrinkage Exponent for Read-Once Formulae. Theor. Comput. Sci. 141(1&2): 269-282 (1995) - 1994
- [c6]Alexander A. Razborov, Steven Rudich:
Natural proofs. STOC 1994: 204-213 - [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) - [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) - [c5]Mikael Goldmann, Johan Håstad, Alexander A. Razborov:
Majority Gates vs. General Weighted Threshold Gates. SCT 1992: 2-13 - 1991
- [j2]Mike Paterson, Alexander A. Razborov:
The Set of Minimal Braids is co-NP-Complete. J. Algorithms 12(3): 393-408 (1991)
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 2024-08-08 20:18 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint