Alexander A. Razborov

	2011
83		Olaf Beyersdorff, Nicola Galesi, Massimo Lauria, Alexander A. Razborov: Parameterized Bounded-Depth Frege Is Not Optimal. ICALP (1) 2011: 630-641
82		Jakob Nordström, Alexander A. Razborov: On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution. ICALP (1) 2011: 642-653
81		Allan Borodin, Toniann Pitassi, Alexander A. Razborov: Special Issue In Memory of Misha Alekhnovich. Foreword. Computational Complexity 20(4): 579-590 (2011)
80		Michael Alekhnovich, Alexander A. Razborov: Satisfiability, Branch-Width and Tseitin tautologies. Computational Complexity 20(4): 649-678 (2011)
	2010
79		Alexander A. Razborov: Complexity of Propositional Proofs. CSR 2010: 340-342
78		Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of l 1N VIA expander codes. Combinatorica 30(1): 47-68 (2010)
77		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)
76		Friedrich Eisenbrand, Nicolai Hähnle, Alexander A. Razborov, Thomas Rothvoß: Diameter of Polyhedra: Limits of Abstraction. Math. Oper. Res. 35(4): 786-794 (2010)
75		Alexander A. Razborov, Alexander A. Sherstov: The Sign-Rank of AC0. SIAM J. Comput. 39(5): 1833-1855 (2010)
74		Alexander A. Razborov: On 3-Hypergraphs with Forbidden 4-Vertex Configurations. SIAM J. Discrete Math. 24(3): 946-963 (2010)
73		Sergei N. Artëmov, Volker Diekert, Alexander A. Razborov: Preface. Theory Comput. Syst. 46(4): 619 (2010)
	2009
72		Johann A. Makowsky, Alexander A. Razborov: The Ackermann Award 2009. CSL 2009: 561-565
71		Jakob Nordström, Alexander A. Razborov: On Minimal Unsatisfiability and Time-Space Trade-offs for k-DNF Resolution CoRR abs/0910.3127: (2009)
70		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)
69		Alexander A. Razborov: A Simple Proof of Bazzi's Theorem. TOCT 1(1): (2009)
	2008
68		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
67		Alexander A. Razborov, Alexander A. Sherstov: The Sign-Rank of AC^O. FOCS 2008: 57-66
66		Venkatesan Guruswami, James R. Lee, Alexander A. Razborov: Almost Euclidean subspaces of lN1 via expander codes. SODA 2008: 353-362
65		Alexander A. Razborov: On the Minimal Density of Triangles in Graphs. Combinatorics, Probability & Computing 17(4): 603-618 (2008)
64		Alexander A. Razborov, Alexander A. Sherstov: The Sign-Rank of AC^0. Electronic Colloquium on Computational Complexity (ECCC) 15(016): (2008)
63		Alexander A. Razborov: A simple proof of Bazzi's theorem. Electronic Colloquium on Computational Complexity (ECCC) 15(081): (2008)
62		Michael Alekhnovich, Alexander A. Razborov: Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38(4): 1347-1363 (2008)
	2007
61		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)
60		Alexander A. Razborov: Flag algebras. J. Symb. Log. 72(4): 1239-1282 (2007)
59		Alexander A. Razborov: Eulogy: Michael (Misha) Alekhnovich 1978-2006. SIGACT News 38(1): 70-71 (2007)
58		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
57		Alexander A. Razborov, Sergey Yekhanin: An Omega(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval. FOCS 2006: 739-748
56		Vladimir Lifschitz, Alexander A. Razborov: Why are there so many loop formulas? ACM Trans. Comput. Log. 7(2): 261-268 (2006)
55		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
54		Erich Grädel, Janos Makowsky, Alexander A. Razborov: The Ackermann Award 2005. CSL 2005: 557-565
53		Alexander A. Razborov: Guessing More Secrets via List Decoding. Internet Mathematics 2(1): 21-30 (2005)
	2004
52		Alexander A. Razborov: Feasible Proofs and Computations: Partnership and Fusion. ICALP 2004: 8-14
51		Alexander A. Razborov: Feasible Proofs and Computations: Partnership and Fusion. LICS 2004: 134-138
50		Alexander A. Razborov: Resolution lower bounds for perfect matching principles. J. Comput. Syst. Sci. 69(1): 3-27 (2004)
49		Alexander A. Razborov: An upper bound on the threshold quantum decoherence rate. Quantum Information & Computation 4(3): 222-228 (2004)
48		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
47		Alexander A. Razborov: Propositional proof complexity. J. ACM 50(1): 80-82 (2003)
46		Alexander A. Razborov: Resolution lower bounds for the weak functional pigeonhole principle. Theor. Comput. Sci. 1(303): 233-243 (2003)
	2002
45		Michael Alekhnovich, Alexander A. Razborov: Satisfiability, Branch-Width and Tseitin Tautologies. FOCS 2002: 593-603
44		Alexander A. Razborov: Resolution Lower Bounds for Perfect Matching Principles. IEEE Conference on Computational Complexity 2002: 29-38
43		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)
42		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space Complexity in Propositional Calculus. SIAM J. Comput. 31(4): 1184-1211 (2002)
	2001
41		Alexander A. Razborov: Proof Complexity of Pigeonhole Principles. Developments in Language Theory 2001: 100-116
40		Michael Alekhnovich, Alexander A. Razborov: Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS 2001: 190-199
39		Michael Alekhnovich, Alexander A. Razborov: Resolution is Not Automatizable Unless W[P] is Tractable. FOCS 2001: 210-219
38		Alexander A. Razborov: Resolution Lower Bounds for the Weak Functional Pigeonhole Principle Electronic Colloquium on Computational Complexity (ECCC) 8(075): (2001)
37		Alexander A. Razborov: Improved Resolution Lower Bounds for the Weak Pigeonhole Principle Electronic Colloquium on Computational Complexity (ECCC) 8(55): (2001)
	2000
36		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. FOCS 2000: 43-53
35		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space complexity in propositional calculus. STOC 2000: 358-367
34		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)
33		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
32		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)
31		Alexander A. Razborov, Nikolai K. Vereshchagin: One Property of Cross-Intersecting Families Electronic Colloquium on Computational Complexity (ECCC) 6(14): (1999)
30		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space Complexity in Propositional Calculus Electronic Colloquium on Computational Complexity (ECCC)(40): (1999)
	1998
29		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
28		Alexander A. Razborov: Lower Bounds for the Polynomial Calculus. Computational Complexity 7(4): 291-324 (1998)
27		Stasys Jukna, Alexander A. Razborov: Neither Reading Few Bits Twice Nor Reading Illegally Helps Much. Discrete Applied Mathematics 85(3): 223-238 (1998)
	1997
26		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
25		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
24		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)
23		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)
22		Alexander A. Razborov, Steven Rudich: Natural Proofs. J. Comput. Syst. Sci. 55(1): 24-35 (1997)
	1996
21		Alexander A. Razborov: Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic. ICALP 1996: 48-62
20		Stasys Jukna, Alexander A. Razborov: Neither Reading Few Bits Twice nor Reading Illegally Helps Much Electronic Colloquium on Computational Complexity (ECCC) 3(37): (1996)
19		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)
	1995
18		Alexander A. Razborov: Lower Bounds for Propositional Proofs and Independence Results in Bounded Arithmetic (Abstract). MFCS 1995: 105
17		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		Alexander A. Razborov, Steven Rudich: Natural proofs. STOC 1994: 204-213
15		Alexander A. Razborov, Steven Rudich: Natural Proofs Electronic Colloquium on Computational Complexity (ECCC) 1(10): (1994)
14		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		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

Coauthor Index

1	Michael Alekhnovich	[30] [33] [35] [36] [39] [40] [42] [45] [48] [62] [80]
2	Sergei N. Artëmov	[73]
3	Eli Ben-Sasson	[30] [33] [35] [36] [42] [48]
4	Olaf Beyersdorff	[77] [83]
5	Allan Borodin	[12] [81]
6	Samuel R. Buss	[24]
7	Volker Diekert	[73]
8	Friedrich Eisenbrand	[76]
9	Nicola Galesi	[77] [83]
10	Mikael Goldmann	[8] [9]
11	Oded Goldreich	[19]
12	Erich Grädel	[54]
13	Dima Grigoriev	[29] [34]
14	Venkatesan Guruswami	[61] [66] [78]
15	Nicolai Hähnle	[76]
16	Johan Håstad	[8] [9] [17]
17	Edward A. Hirsch	[68]
18	Russell Impagliazzo	[24]
19	Stasys Jukna	[20] [23] [26] [27] [32]
20	Jan Krajícek	[24]
21	Massimo Lauria	[77] [83]
22	James R. Lee	[61] [66] [78]
23	Vladimir Lifschitz	[56]
24	Johann A. Makowsky (Janos Makowsky)	[54] [72]
25	Jakob Nordström	[70] [71] [82]
26	Christos H. Papadimitriou	[19]
27	Mike Paterson	[4]
28	Toniann Pitassi	[81]
29	Pavel Pudlák	[24]
30	Thomas Rothvoß	[76]
31	Steven Rudich	[15] [16] [22]
32	Petr Savický	[23] [26] [32]
33	Alexei L. Semenov	[68]
34	Jiri Sgall	[24]
35	Alexander A. Sherstov	[64] [67] [75]
36	Michael Sipser	[19]
37	Anatol Slissenko	[68]
38	Roman Smolensky	[12]
39	Endre Szemerédi	[13]
40	Nikolai K. Vereshchagin (Nikolay K. Vereshchagin)	[31]
41	Ingo Wegener	[23] [26] [32]
42	Avi Wigderson	[11] [13] [19] [25] [30] [33] [35] [36] [42] [43] [48]
43	Andrew Chi-Chih Yao (Andrew C. Yao)	[17] [25] [43]
44	Sergey Yekhanin	[55] [57] [58]

Colors in the list of coauthors

Last update Sat May 26 02:31:23 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page