Michael Alekhnovich

Publication Activity (10 Years)

Years Active: 1998-2011
Publications (10 Years): 0

Publications

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. 20 (4) (2011)
Michael Alekhnovich
Lower Bounds for k-DNF Resolution on Random 3-CNFs. Comput. Complex. 20 (4) (2011)
Michael Alekhnovich
More on Average Case vs Approximation Complexity. Comput. Complex. 20 (4) (2011)
Michael Alekhnovich, Alexander A. Razborov
Satisfiability, Branch-Width and Tseitin tautologies. Comput. Complex. 20 (4) (2011)
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen
Toward a Model for Backtracking and Dynamic Programming. Electron. Colloquium Comput. Complex. 16 (2009)
Michael Alekhnovich, Alexander A. Razborov
Resolution Is Not Automatizable Unless W[P] Is Tractable. SIAM J. Comput. 38 (4) (2008)
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) (2008)
Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
An Exponential Separation between Regular and General Resolution. Theory Comput. 3 (1) (2007)
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
Toward a Model for Backtracking and Dynamic Programming. Computational Complexity Conference (2005)
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. J. Autom. Reason. 35 (1-3) (2005)
Michael Alekhnovich
Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. IEEE Trans. Inf. Theory 51 (7) (2005)
Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis
Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. STOC (2005)
Michael Alekhnovich
Lower bounds for k-DNF resolution on random 3-CNFs. STOC (2005)
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas Electron. Colloquium Comput. Complex. (041) (2004)
Michael Alekhnovich
Mutilated chessboard problem is exponentially hard for resolution. Theor. Comput. Sci. 310 (1-3) (2004)
Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi
Learnability and Automatizability. FOCS (2004)
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. ICALP (2004)
Michael Alekhnovich, Eli Ben-Sasson
Linear Upper Bounds for Random Walk on Small Density Random 3CNFs Electron. Colloquium Comput. Complex. (016) (2004)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Pseudorandom Generators in Propositional Proof Complexity. SIAM J. Comput. 34 (1) (2004)
Michael Alekhnovich, Eli Ben-Sasson
Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. FOCS (2003)
Michael Alekhnovich
More on Average Case vs Approximation Complexity. FOCS (2003)
Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
An exponential separation between regular and general resolution. STOC (2002)
Michael Alekhnovich
Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. FOCS (2002)
Michael Alekhnovich, Alexander A. Razborov
Satisfiability, Branch-Width and Tseitin Tautologies. FOCS (2002)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Space Complexity in Propositional Calculus. SIAM J. Comput. 31 (4) (2002)
Michael Alekhnovich, Alexander A. Razborov
Lower Bounds for Polynomial Calculus: Non-Binomial Case. FOCS (2001)
Michael Alekhnovich, Alexander A. Razborov
Resolution is Not Automatizable Unless W[P] is Tractable. FOCS (2001)
Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
An Exponential Separation between Regular and General Resolution Electron. Colloquium Comput. Complex. 8 (056) (2001)
Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate. J. Symb. Log. 66 (1) (2001)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Pseudorandom Generators in Propositional Proof Complexity. FOCS (2000)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Pseudorandom Generators in Propositional Proof Complexity Electron. Colloquium Comput. Complex. 7 (23) (2000)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Space complexity in propositional calculus. STOC (2000)
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
Space Complexity in Propositional Calculus Electron. Colloquium Comput. Complex. (40) (1999)
Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS (1998)