Michael Alekhnovich

According to our database, Michael Alekhnovich authored at least 21 papers between 2001 and 2011.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2011

Satisfiability, Branch-Width and Tseitin tautologies.

Michael Alekhnovich, Alexander A. Razborov

Comput. Complex., 2011

Hardness of Approximating the Closest Vector Problem with Pre-Processing.

Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi

Comput. Complex., 2011

Toward a Model for Backtracking and Dynamic Programming.

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi

Comput. Complex., 2011

Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy.

Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis

Comput. Complex., 2011

More on Average Case vs Approximation Complexity.

Michael Alekhnovich

Comput. Complex., 2011

Lower Bounds for k-DNF Resolution on Random 3-CNFs.

Michael Alekhnovich

Comput. Complex., 2011

2009

Toward a Model for Backtracking and Dynamic Programming.

Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen

Electron. Colloquium Comput. Complex., 2009

2008

Resolution Is Not Automatizable Unless W[P] Is Tractable.

Michael Alekhnovich, Alexander A. Razborov

SIAM J. Comput., 2008

The complexity of properly learning simple concept classes.

Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi

J. Comput. Syst. Sci., 2008

2007

Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs.

Mikhail Alekhnovich, Eli Ben-Sasson

SIAM J. Comput., 2007

2005

Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes.

Michael Alekhnovich

IEEE Trans. Inf. Theory, 2005

2004

Mutilated chessboard problem is exponentially hard for resolution.

Michael Alekhnovich

Theor. Comput. Sci., 2004

Pseudorandom Generators in Propositional Proof Complexity.

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson

SIAM J. Comput., 2004

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson

Electron. Colloquium Comput. Complex., 2004

Linear Upper Bounds for Random Walk on Small Density Random 3CNFs

Michael Alekhnovich, Eli Ben-Sasson

Electron. Colloquium Comput. Complex., 2004

Learnability and Automatizability.

Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi

Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003

Linear Upper Bounds for Random Walk on Small Density Random 3-CNF.

Michael Alekhnovich, Eli Ben-Sasson

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Space Complexity in Propositional Calculus.

Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson

SIAM J. Comput., 2002

2001

Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.

Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi

J. Symb. Log., 2001

An Exponential Separation between Regular and General Resolution

Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart

Electron. Colloquium Comput. Complex., 2001

Lower Bounds for Polynomial Calculus: Non-Binomial Case.

Michael Alekhnovich, Alexander A. Razborov

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001