Michael Alekhnovich

2008
29	EE	Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi: The complexity of properly learning simple concept classes. J. Comput. Syst. Sci. 74(1): 16-34 (2008)
28	EE	Michael Alekhnovich, Alexander A. Razborov: Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38(4): 1347-1363 (2008)
2007
27	EE	Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An Exponential Separation between Regular and General Resolution. Theory of Computing 3(1): 81-102 (2007)
2005
26	EE	Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi: Toward a Model for Backtracking and Dynamic Programming. IEEE Conference on Computational Complexity 2005: 308-322
25	EE	Michael Alekhnovich: Lower bounds for k-DNF resolution on random 3-CNFs. STOC 2005: 251-256
24	EE	Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. STOC 2005: 294-303
23	EE	Michael Alekhnovich: Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. IEEE Transactions on Information Theory 51(7): 2257-2265 (2005)
22	EE	Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson: Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J. Autom. Reasoning 35(1-3): 51-72 (2005)
2004
21	EE	Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi: Learnability and Automatizability. FOCS 2004: 621-630
20	EE	Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson: Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. ICALP 2004: 84-96
19	EE	Michael Alekhnovich, Eli Ben-Sasson: Linear Upper Bounds for Random Walk on Small Density Random 3CNFs Electronic Colloquium on Computational Complexity (ECCC)(016): (2004)
18	EE	Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson: Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas Electronic Colloquium on Computational Complexity (ECCC)(041): (2004)
17	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)
16	EE	Michael Alekhnovich: Mutilated chessboard problem is exponentially hard for resolution. Theor. Comput. Sci. 310(1-3): 513-525 (2004)
2003
15	EE	Michael Alekhnovich: More on Average Case vs Approximation Complexity. FOCS 2003: 298-307
14	EE	Michael Alekhnovich, Eli Ben-Sasson: Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. FOCS 2003: 352-361
2002
13	EE	Michael Alekhnovich: Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. FOCS 2002: 439-448
12	EE	Michael Alekhnovich, Alexander A. Razborov: Satisfiability, Branch-Width and Tseitin Tautologies. FOCS 2002: 593-603
11	EE	Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An exponential separation between regular and general resolution. STOC 2002: 448-456
10	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
9		Michael Alekhnovich, Alexander A. Razborov: Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS 2001: 190-199
8		Michael Alekhnovich, Alexander A. Razborov: Resolution is Not Automatizable Unless W[P] is Tractable. FOCS 2001: 210-219
7	EE	Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart: An Exponential Separation between Regular and General Resolution Electronic Colloquium on Computational Complexity (ECCC) 8(056): (2001)
6		Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi: Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate. J. Symb. Log. 66(1): 171-191 (2001)
2000
5		Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Pseudorandom Generators in Propositional Proof Complexity. FOCS 2000: 43-53
4	EE	Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson: Space complexity in propositional calculus. STOC 2000: 358-367
3	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
2	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
1	EE	Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi: Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS 1998: 176-184

Coauthor Index

1	Sanjeev Arora	[24]
2	Eli Ben-Sasson	[2] [3] [4] [5] [10] [14] [17] [19]
3	Allan Borodin	[26]
4	Mark Braverman	[21] [29]
5	Joshua Buresh-Oppenheim (Josh Buresh-Oppenheim)	[26]
6	Samuel R. Buss	[1] [6]
7	Vitaly Feldman	[21] [29]
8	Edward A. Hirsch	[18] [20] [22]
9	Russell Impagliazzo	[26]
10	Dmitry Itsykson	[18] [20] [22]
11	Jan Johannsen	[7] [11] [27]
12	Adam R. Klivans (Adam Klivans)	[21] [29]
13	Avner Magen	[26]
14	Shlomo Moran	[1] [6]
15	Toniann Pitassi	[1] [6] [7] [11] [21] [26] [27] [29]
16	Alexander A. Razborov	[2] [3] [4] [5] [8] [9] [10] [12] [17] [28]
17	Iannis Tourlakis	[24]
18	Alasdair Urquhart	[7] [11] [27]
19	Avi Wigderson	[2] [3] [4] [5] [10] [17]