|
|
-
Hardness of approximating the closest vector problem with pre-processing
Michael Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth Vishnoi
To appear in Proc. 46th IEEE Symposium on FOCS, 2005
-
Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis
In Proc. 37th Annual ACM STOC: 294-303, 2005
-
Inapproximability of Fixed Parameter Problems
Michael Alekhnovich, Subhash Khot, Toniann Pitassi
Manuscript, 2004
-
Toward a Model for Backtracking and Dynamic Programming
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
In Proc. 20th Annual Conference on Computational Complexity:
308-322, 2005
-
Lower bounds for k-DNF Resolution on random 3-CNFs
Michael Alekhnovich
In Proc. 37th Annual ACM STOC: 251-256, 2005
-
Learnability and Automatizability
Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi
Invited to JCSS special issue on learning
theory papers
In Proc. 44th IEEE Symposium on FOCS, 2004
-
Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson
To appear in 2005 SAT special issue of the Journal of Automated
Reasoning
In Proc. 31st ICALP: 84-96, 2004
-
More on Average Case vs Approximation Complexity
Michael Alekhnovich
In Proc. 44th IEEE Symposium on FOCS: 298-307, 2003
-
Linear Upper Bounds for Random Walk on Small Density Random 3-CNF
Michael Alekhnovich, Eli Ben-Sasson
In Proc. 44th IEEE Symposium on FOCS: 352-361, 2003
-
Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes
Michael Alekhnovich
To appear in IEEE Transactions on Information Theory
In Proc. 43rd IEEE Symposium on FOCS: 439-448, 2002
-
Satisfiability, Branch-Width and Tseitin Tautologies
Michael Alekhnovich, Alexander A. Razborov
In Proc. 43rd IEEE Symposium on FOCS: 593-603, 2002
-
An exponential separation between regular and general resolution
Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
In Proc. 34th Annual ACM STOC: 448-456, 2002
-
Lower Bounds for Polynomial Calculus: Non-Binomial Case
Michael Alekhnovich, Alexander A. Razborov
In Proceedings of the Steklov Institute of Mathematics 242: 18-35, 2003
In Proc. 42nd IEEE Symposium on FOCS: 190-199, 2001
-
Resolution is Not Automatizable Unless W[P] is Tractable
Michael Alekhnovich, Alexander A. Razborov
In Proc. 42nd IEEE Symposium on FOCS: 210-219, 2001
-
Mutilated chessboard problem is exponentially hard for resolution
Michael Alekhnovich
Theoretical Computer Science 310(1-3): 513-525, 2004
-
Pseudorandom Generators in Propositional Proof Complexity
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
SIAM Journal on Computing 34(1): 67 - 88, 2004
In Proc. 41st IEEE Symposium on FOCS: 43-53, 2000
-
Space Complexity in Propositional Calculus
Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
SIAM Journal on Computing 31(4): 1184-1211, 2002
In Proc. 32nd Annual ACM STOC: 358-367, 2000
-
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate
Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
Journal of Symbolic Logic 66(1): 171-191, 2001
In Proc. 23rd International Symposium MFCS: 176-184, 1998
|