Computational Complexity Propositional Complexity Algorithms

Insitute for Advanced Study

• Recipient of the MIT Applied Mathematics Fellowship Award, 2000-2001

• Workshop on: The Propositional Satisfiability Problem -- Algorithms and Lower Bounds
  Schloss Dagstuhl, 2003
• Workshop on Complexity of Boolean Functions
  Schloss Dagstuhl, 2002
• Workshop on Circuit and Proof Complexity
  ICMS Edinburgh, 2001

• Analysis of the Random Walk Algorithm on Random CNF Formulas
  NEC Labs Research Seminar, 2003
• More on Average case vs. approximation complexity
  NYU Cryptography Seminar, 2003

• More on Average Case vs Approximation Complexity
  44th Annual IEEE Symposium on FOCS 2003, Cambridge, MA, 2003
• Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes
  43rd Annual IEEE Symposium on FOCS, Vancouver, Canada, 2002
• Satisfiability, Branch-Width and Tseitin Tautologies
  43rd Annual IEEE Symposium on FOCS, Vancouver, Canada, 2002
• An exponential separation between regular and general resolution
  34th Annual ACM STOC, Montréal, Québec, Canada, 2002
• Resolution is Not Automatizable Unless W[P] is Tractable
  42nd Annual IEEE Symposium on FOCS, Las Vegas, Nevada, 2001
• Pseudorandom Generators in Propositional Proof Complexity
  41st Annual IEEE Symposium on FOCS, Redondo Beach, California, 2000
• Minimum Propositional Proof Length is NP-Hard to Linearly Approximate
  23rd International Symposium MFCS, Brno, Czech Republic, 1998

• ACM Transactions on Computational Logic
• SIAM Journal on Computing
• IEEE Transactions on Information Theory
• Information Processing Letters
• 45th Annual IEEE Symposium on FOCS, 2004
• 36th Annual ACM STOC, 2004
• 19th Annual IEEE Conf. on Computational Complexity, 2004

• Hardness of approximating the closest vector problem with pre-processing
  Michael Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth Vishnoi
 
• Inapproximability of Fixed Parameter Problems
  Michael Alekhnovich, Subhash Khot, Toniann Pitassi
 

• Learnability and Automatizability
  Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi
  To appear in JCSS special issue on learning theory papers of 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
 
• Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes
  Michael Alekhnovich
  To appear in IEEE Transactions on Information Theory
 
• Mutilated chessboard problem is exponentially hard for resolution
  Michael Alekhnovich
  Theoretical Computer Science , 2004
 
• Lower Bounds for Polynomial Calculus: Non-Binomial Case
  Michael Alekhnovich, Alexander A. Razborov
  In Proceedings of the Steklov Institute of Mathematics, 2003
 
• Pseudorandom Generators in Propositional Proof Complexity
  Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
  SIAM Journal on Computing, 2004
 
• Space Complexity in Propositional Calculus
  Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
  SIAM Journal on Computing, 2002
 
• Minimum Propositional Proof Length is NP-Hard to Linearly Approximate
  Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
  Journal of Symbolic Logic, 2001

• Toward a Model for Backtracking and Dynamic Programming
  Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
  To appear in Proc. 20th Annual Conference on Computational Complexity, 2005
 
• Towards strong nonapproximability results in the Lovász-Schrijver hierarchy
  Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis
  To appear in Proc. 37th Annual ACM STOC, 2005
 
• Lower bounds for k-DNF Resolution on random 3-CNFs
  Michael Alekhnovich
  To appear in Proc. 37th Annual ACM STOC, 2005
 
• Learnability and Automatizability
  Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam Klivans, Toniann Pitassi
  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
  In Proc. 31st ICALP, 2004
 
• More on Average Case vs Approximation Complexity
  Michael Alekhnovich
  In Proc. 44th IEEE Symposium on FOCS, 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, 2003
 
• Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes
  Michael Alekhnovich
  In Proc. 43rd IEEE Symposium on FOCS, 2002
 
• Satisfiability, Branch-Width and Tseitin Tautologies
  Michael Alekhnovich, Alexander A. Razborov
  In Proc. 43rd IEEE Symposium on FOCS, 2002
 
• An exponential separation between regular and general resolution
  Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart
  In Proc. 34th Annual ACM STOC, 2002
 
• Lower Bounds for Polynomial Calculus: Non-Binomial Case
  Michael Alekhnovich, Alexander A. Razborov
  In Proc. 42nd IEEE Symposium on FOCS, 2001
 
• Resolution is Not Automatizable Unless W[P] is Tractable
  Michael Alekhnovich, Alexander A. Razborov
  In Proc. 42nd IEEE Symposium on FOCS, 2001
 
• Pseudorandom Generators in Propositional Proof Complexity
  Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
  In Proc. 41st IEEE Symposium on FOCS, 2000
 
• Space Complexity in Propositional Calculus
  Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson
  In Proc. 32nd Annual ACM STOC, 2000
 
• Minimum Propositional Proof Length is NP-Hard to Linearly Approximate
  Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
  In Proc. 23rd International Symposium MFCS, 1998