Lower Bounds for Polynomial Calculus: Non-Binomial Case. - Michael Alekhnovich; Alexander A. Razborov (FOCS, 2001)

An Exponential Separation between Regular and General Resolution - Michael Alekhnovich; Jan Johannsen; Toniann Pitassi; Alasdair Urquhart (Electron. Colloquium Comput. Complex., 2001)

Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate. - Michael Alekhnovich; Samuel R. Buss; Shlomo Moran; Toniann Pitassi (J. Symb. Log., 2001)

Space Complexity in Propositional Calculus. - Michael Alekhnovich; Eli Ben-Sasson; Alexander A. Razborov; Avi Wigderson (SIAM J. Comput., 2002)

Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. - Michael Alekhnovich; Eli Ben-Sasson (FOCS, 2003)

Learnability and Automatizability. - Michael Alekhnovich; Mark Braverman; Vitaly Feldman; Adam R. Klivans; Toniann Pitassi (FOCS, 2004)

Linear Upper Bounds for Random Walk on Small Density Random 3CNFs - Michael Alekhnovich; Eli Ben-Sasson (Electron. Colloquium Comput. Complex., 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)

Pseudorandom Generators in Propositional Proof Complexity. - Michael Alekhnovich; Eli Ben-Sasson; Alexander A. Razborov; Avi Wigderson (SIAM J. Comput., 2004)

Mutilated chessboard problem is exponentially hard for resolution. - Michael Alekhnovich (Theor. Comput. Sci., 2004)

Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes. - Michael Alekhnovich (IEEE Trans. Inf. Theory, 2005)

Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs. - Mikhail Alekhnovich; Eli Ben-Sasson (SIAM J. Comput., 2007)

The complexity of properly learning simple concept classes. - Michael Alekhnovich; Mark Braverman; Vitaly Feldman; Adam R. Klivans; Toniann Pitassi (J. Comput. Syst. Sci., 2008)

Resolution Is Not Automatizable Unless W[P] Is Tractable. - Michael Alekhnovich; Alexander A. Razborov (SIAM J. Comput., 2008)

Toward a Model for Backtracking and Dynamic Programming. - Michael Alekhnovich; Allan Borodin; Joshua Buresh-Oppenheim; Russell Impagliazzo; Avner Magen (Electron. Colloquium Comput. Complex., 2009)

Lower Bounds for k-DNF Resolution on Random 3-CNFs. - Michael Alekhnovich (Comput. Complex., 2011)

More on Average Case vs Approximation Complexity. - Michael Alekhnovich (Comput. Complex., 2011)

Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. - Mikhail Alekhnovich; Sanjeev Arora; Iannis Tourlakis (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)

Hardness of Approximating the Closest Vector Problem with Pre-Processing. - Mikhail Alekhnovich; Subhash Khot; Guy Kindler; Nisheeth K. Vishnoi (Comput. Complex., 2011)

Satisfiability, Branch-Width and Tseitin tautologies. - Michael Alekhnovich; Alexander A. Razborov (Comput. Complex., 2011)