
See also my CV and Statement of Research in PDF format
Objective

Faculty position in Theoretical Computer Science for Fall 2005 
Research Interests

Computational Complexity Propositional Complexity Algorithms 
References

Avi Wigderson
Faculty member of School of Mathematics
Institute for Advanced Study, Princeton NJ 

Alexander A. Razborov
Visiting professor of School of Mathematics
Institute for Advanced Study, Princeton NJ
On leave from Steklov Mathematical Institute, Moscow, Russia 

Madhu Sudan
Professor of Computer Science Department
Massachusetts Institute of Technology, Cambridge MA


Toniann Pitassi
Professor of Computer Science Department
University of Toronto, Canada

Education
Massachusetts Institute of Technology
Fall 20012003: 
Graduate student in Department of Mathematics 

Degree awarded: 
Ph.D. of Science (Applied Mathematics and Computer Science) 

Diploma thesis: 
Propositional Proof Systems: Efficiency and Automatizability 

Thesis Supervisor: 
Prof. Madhu Sudan 
Moscow State University
Fall 19952000: 
Student in Department of Mathematics and Mechanics 

Degree awarded: 
Diploma with Honors (B.A. equivalent) 

Diploma thesis: 
Pseudorandom generators in Propositional Proof Complexity 

Thesis Supervisor: 
Prof. Alexander A. Razborov 
Professional Experience
Insitute for Advanced Study
Massachusetts Institute of Technology
Fall 20022003: 
Research Assistant 

Supervisor 
Prof. Madhu Sudan 
Insitute for Advanced Study
Fall 20002001: 
Member in the special program on Computational Complexity 
Awards
 Recipient of the MIT Applied Mathematics Fellowship Award, 20002001
Conferences, Speaking and Refereeing
Invited participant
 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
Invited speaker
 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
Conference talks
 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 ReedSolomon Codes
43rd Annual IEEE Symposium on FOCS, Vancouver, Canada, 2002
 Satisfiability, BranchWidth 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 NPHard to Linearly Approximate
23rd International Symposium MFCS, Brno, Czech Republic, 1998
Referee for
 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
Publications
Recently Submitted

Hardness of approximating the closest vector problem with preprocessing
Michael Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth Vishnoi

Inapproximability of Fixed Parameter Problems
Michael Alekhnovich, Subhash Khot, Toniann Pitassi
In Journals

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 ReedSolomon 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: NonBinomial Case
Michael Alekhnovich, Alexander A. Razborov
In Proceedings of the Steklov Institute of Mathematics, 2003
 Pseudorandom Generators in Propositional Proof Complexity
Michael Alekhnovich, Eli BenSasson, Alexander A. Razborov, Avi Wigderson
SIAM Journal on Computing, 2004
 Space Complexity in Propositional Calculus
Michael Alekhnovich, Eli BenSasson, Alexander A. Razborov, Avi Wigderson
SIAM Journal on Computing, 2002
 Minimum Propositional Proof Length is NPHard to Linearly Approximate
Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
Journal of Symbolic Logic, 2001
In Refereed Conferences

Toward a Model for Backtracking and Dynamic Programming
Michael Alekhnovich, Allan Borodin, Joshua BureshOppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi
To appear in Proc. 20th Annual Conference on Computational Complexity, 2005

Towards strong nonapproximability results in the LovászSchrijver hierarchy
Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis
To appear in Proc. 37th Annual ACM STOC, 2005

Lower bounds for kDNF Resolution on random 3CNFs
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 3CNF
Michael Alekhnovich, Eli BenSasson
In Proc. 44th IEEE Symposium on FOCS, 2003

Linear Diophantine Equations over Polynomials and Soft Decoding of ReedSolomon Codes
Michael Alekhnovich
In Proc. 43rd IEEE Symposium on FOCS, 2002

Satisfiability, BranchWidth 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: NonBinomial 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 BenSasson, Alexander A. Razborov, Avi Wigderson
In Proc. 41st IEEE Symposium on FOCS, 2000
 Space Complexity in Propositional Calculus
Michael Alekhnovich, Eli BenSasson, Alexander A. Razborov, Avi Wigderson
In Proc. 32nd Annual ACM STOC, 2000
 Minimum Propositional Proof Length is NPHard to Linearly Approximate
Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi
In Proc. 23rd International Symposium MFCS, 1998
