| 2008 |
|---|
| 65 | | 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
Springer 2008 |
| 64 | EE | Alexander A. Razborov,
Alexander A. Sherstov:
The Sign-Rank of AC^O.
FOCS 2008: 57-66 |
| 63 | EE | Venkatesan Guruswami,
James R. Lee,
Alexander A. Razborov:
Almost Euclidean subspaces of lN1 via expander codes.
SODA 2008: 353-362 |
| 62 | EE | Alexander A. Razborov:
On the Minimal Density of Triangles in Graphs.
Combinatorics, Probability & Computing 17(4): 603-618 (2008) |
| 61 | EE | Alexander A. Razborov,
Alexander A. Sherstov:
The Sign-Rank of AC^0.
Electronic Colloquium on Computational Complexity (ECCC) 15(016): (2008) |
| 60 | EE | Alexander A. Razborov:
A simple proof of Bazzi's theorem.
Electronic Colloquium on Computational Complexity (ECCC) 15(081): (2008) |
| 59 | EE | Michael Alekhnovich,
Alexander A. Razborov:
Resolution Is Not Automatizable Unless W[P] Is Tractable.
SIAM J. Comput. 38(4): 1347-1363 (2008) |
| 2007 |
|---|
| 58 | EE | 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) |
| 57 | EE | Alexander A. Razborov:
Eulogy: Michael (Misha) Alekhnovich 1978-2006.
SIGACT News 38(1): 70-71 (2007) |
| 56 | EE | 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) |
| 2006 |
|---|
| 55 | EE | Alexander A. Razborov,
Sergey Yekhanin:
An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval.
FOCS 2006: 739-748 |
| 54 | EE | Vladimir Lifschitz,
Alexander A. Razborov:
Why are there so many loop formulas?
ACM Trans. Comput. Log. 7(2): 261-268 (2006) |
| 53 | EE | 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 |
|---|
| 52 | EE | Erich Grädel,
Janos Makowsky,
Alexander A. Razborov:
The Ackermann Award 2005.
CSL 2005: 557-565 |
| 51 | | Alexander A. Razborov:
Guessing More Secrets via List Decoding.
Internet Mathematics 2(1): (2005) |
| 2004 |
|---|
| 50 | EE | Alexander A. Razborov:
Feasible Proofs and Computations: Partnership and Fusion.
ICALP 2004: 8-14 |
| 49 | EE | Alexander A. Razborov:
Feasible Proofs and Computations: Partnership and Fusion.
LICS 2004: 134-138 |
| 48 | EE | Alexander A. Razborov:
Resolution lower bounds for perfect matching principles.
J. Comput. Syst. Sci. 69(1): 3-27 (2004) |
| 47 | EE | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity.
SIAM J. Comput. 34(1): 67-88 (2004) |
| 2003 |
|---|
| 46 | EE | Alexander A. Razborov:
Propositional proof complexity.
J. ACM 50(1): 80-82 (2003) |
| 45 | EE | Alexander A. Razborov:
Resolution lower bounds for the weak functional pigeonhole principle.
Theor. Comput. Sci. 1(303): 233-243 (2003) |
| 2002 |
|---|
| 44 | EE | Michael Alekhnovich,
Alexander A. Razborov:
Satisfiability, Branch-Width and Tseitin Tautologies.
FOCS 2002: 593-603 |
| 43 | EE | Alexander A. Razborov:
Resolution Lower Bounds for Perfect Matching Principles.
IEEE Conference on Computational Complexity 2002: 29-38 |
| 42 | EE | 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) |
| 41 | EE | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Space Complexity in Propositional Calculus.
SIAM J. Comput. 31(4): 1184-1211 (2002) |
| 2001 |
|---|
| 40 | EE | Alexander A. Razborov:
Proof Complexity of Pigeonhole Principles.
Developments in Language Theory 2001: 100-116 |
| 39 | | Michael Alekhnovich,
Alexander A. Razborov:
Lower Bounds for Polynomial Calculus: Non-Binomial Case.
FOCS 2001: 190-199 |
| 38 | | Michael Alekhnovich,
Alexander A. Razborov:
Resolution is Not Automatizable Unless W[P] is Tractable.
FOCS 2001: 210-219 |
| 37 | EE | Alexander A. Razborov:
Resolution Lower Bounds for the Weak Functional Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC) 8(075): (2001) |
| 36 | EE | Alexander A. Razborov:
Improved Resolution Lower Bounds for the Weak Pigeonhole Principle
Electronic Colloquium on Computational Complexity (ECCC) 8(55): (2001) |
| 2000 |
|---|
| 35 | | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Pseudorandom Generators in Propositional Proof Complexity.
FOCS 2000: 43-53 |
| 34 | EE | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Space complexity in propositional calculus.
STOC 2000: 358-367 |
| 33 | EE | 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) |
| 32 | EE | 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) |
| 1999 |
|---|
| 31 | EE | 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) |
| 30 | EE | Alexander A. Razborov,
Nikolai K. Vereshchagin:
One Property of Cross-Intersecting Families
Electronic Colloquium on Computational Complexity (ECCC) 6(14): (1999) |
| 29 | EE | Michael Alekhnovich,
Eli Ben-Sasson,
Alexander A. Razborov,
Avi Wigderson:
Space Complexity in Propositional Calculus
Electronic Colloquium on Computational Complexity (ECCC)(40): (1999) |
| 1998 |
|---|
| 28 | EE | 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 |
| 27 | EE | Alexander A. Razborov:
Lower Bounds for the Polynomial Calculus.
Computational Complexity 7(4): 291-324 (1998) |
| 26 | EE | Stasys Jukna,
Alexander A. Razborov:
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.
Discrete Applied Mathematics 85(3): 223-238 (1998) |
| 1997 |
|---|
| 25 | | 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 |
| 24 | EE | 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 |
| 23 | | 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) |
| 22 | EE | 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) |
| 21 | | Alexander A. Razborov,
Steven Rudich:
Natural Proofs.
J. Comput. Syst. Sci. 55(1): 24-35 (1997) |
| 1996 |
|---|
| 20 | | Alexander A. Razborov:
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic.
ICALP 1996: 48-62 |
| 19 | EE | 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 |
|---|
| 18 | | Alexander A. Razborov:
Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract).
MFCS 1995: 105 |
| 17 | EE | 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 |
|---|
| 16 | EE | Alexander A. Razborov,
Steven Rudich:
Natural proofs.
STOC 1994: 204-213 |
| 15 | EE | Alexander A. Razborov,
Steven Rudich:
Natural Proofs
Electronic Colloquium on Computational Complexity (ECCC) 1(10): (1994) |
| 14 | EE | Alexander A. Razborov:
On provably disjoint NP-pairs
Electronic Colloquium on Computational Complexity (ECCC) 1(6): (1994) |
| 1993 |
|---|
| 13 | | Alexander A. Razborov,
Endre Szemerédi,
Avi Wigderson:
Constructing Small Sets that are Uniform in Arithmetic Progressions.
Combinatorics, Probability & Computing 2: 513-518 (1993) |
| 12 | | Allan Borodin,
Alexander A. Razborov,
Roman Smolensky:
On Lower Bounds for Read-K-Times Branching Programs.
Computational Complexity 3: 1-18 (1993) |
| 11 | | 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 |
|---|
| 10 | | Alexander A. Razborov:
On Small Depth Threshold Circuits.
SWAT 1992: 42-52 |
| 9 | | Mikael Goldmann,
Johan Håstad,
Alexander A. Razborov:
Majority Gates vs. General Weighted Threshold Gates.
Structure in Complexity Theory Conference 1992: 2-13 |
| 8 | | Mikael Goldmann,
Johan Håstad,
Alexander A. Razborov:
Majority Gates VS. General Weighted Threshold Gates.
Computational Complexity 2: 277-300 (1992) |
| 7 | EE | 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) |
| 6 | | Alexander A. Razborov:
On the Distributional Complexity of Disjointness.
Theor. Comput. Sci. 106(2): 385-390 (1992) |
| 1991 |
|---|
| 5 | | Alexander A. Razborov:
Lower Bounds for Deterministic and Nondeterministic Branching Programs.
FCT 1991: 47-60 |
| 4 | | Mike Paterson,
Alexander A. Razborov:
The Set of Minimal Braids is co-NP-Complete.
J. Algorithms 12(3): 393-408 (1991) |
| 1990 |
|---|
| 3 | | Alexander A. Razborov:
On the Distributional Complexity of Disjontness.
ICALP 1990: 249-253 |
| 2 | | Alexander A. Razborov:
Applications of matrix methods to the theory of lower bounds in computational complexity.
Combinatorica 10(1): 81-93 (1990) |
| 1989 |
|---|
| 1 | | Alexander A. Razborov:
On the Method of Approximations
STOC 1989: 167-176 |
