| 2005 | STOC | Lower bounds for k-DNF resolution on random 3-CNFs. | Michael Alekhnovich |
| 2005 | STOC | Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. | Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis |
| 2004 | FOCS | Learnability and Automatizability. | Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi |
| 2004 | ICALP | Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. | Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson |
| 2003 | FOCS | More on Average Case vs Approximation Complexity. | Michael Alekhnovich |
| 2003 | FOCS | Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. | Michael Alekhnovich, Eli Ben-Sasson |
| 2002 | FOCS | Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes. | Michael Alekhnovich |
| 2002 | FOCS | Satisfiability, Branch-Width and Tseitin Tautologies. | Michael Alekhnovich, Alexander A. Razborov |
| 2002 | STOC | An exponential separation between regular and general resolution. | Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart |
| 2001 | FOCS | Lower Bounds for Polynomial Calculus: Non-Binomial Case. | Michael Alekhnovich, Alexander A. Razborov |
| 2001 | FOCS | Resolution is Not Automatizable Unless W[P] is Tractable. | Michael Alekhnovich, Alexander A. Razborov |
| 2000 | FOCS | Pseudorandom Generators in Propositional Proof Complexity. | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
| 2000 | STOC | Space complexity in propositional calculus. | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
| 1998 | MFCS | Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. | Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi |