Eulogy: Michael (Misha) Alekhnovich 1978-2006

ABSTRACT

Misha Alekhnovich was born in Moscow, USSR, on October 26, 1978. In 1995 Misha began his studies at Moscow State University and graduated in 2000 with the equivalent of a B.A. in mathematics. In 2000-2001 Misha participated in the Special Year on Computational Complexity at the Institute for Advanced Study, and in 2001-2003 he attended graduate school at MIT. Upon receiving his PhD in 2003, Misha returned to IAS as a postdoctoral member and spent the next two years, 2003-2005, there. In 2005 he moved on to a faculty position at the University of California San Diego.

REFERENCES

• 1: M. Alekhnovich, S. Buss, S. Moran, and T. Pitassi. Minimum propositional proof length is NP-hard to linearly approximate. Journal of Symbolic Logic, 66:171--191, 2001.
• 2: M. Alekhnovich , A. Razborov, Resolution is Not Automatizable Unless W[P] is Tractable, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.210, October 14-17, 2001
• 3: Michael Alekhnovich , Eli Ben-Sasson , Alexander A. Razborov , Avi Wigderson, Pseudorandom Generators in Propositional Proof Complexity, SIAM Journal on Computing, v.34 n.1, p.67-88, 2005 [doi>10.1137/S0097539701389944]
• 4: M. Alekhnovich and A. Razborov. Lower bounds for the polynomial calculus: non-binomial case. Proceedings of the Steklov Institute of Mathematics, 242:18--35, 2003.
• 5: Michael Alekhnovich , Jan Johannsen , Toniann Pitassi , Alasdair Urquhart, An exponential separation between regular and general resolution, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509974]
• 6: Michael Alekhnovich, Lower bounds for k-DNF resolution on random 3-CNFs, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060628]
• 7: Misha Alekhnovich , Mark Braverman , Vitaly Feldman , Adam R. Klivans , Toniann Pitassi, Learnability and Automatizability, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.621-630, October 17-19, 2004 [doi>10.1109/FOCS.2004.36]
• 8: Mikhail Alekhnovich , Sanjeev Arora , Iannis Tourlakis, Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060634]
• 9: M. Alekhnovich, E. Hirsch, and D. Itsykson. Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas. In Proceedings of the 31st ICALP, pages 84--96, 2004.

INDEX TERMS

Primary Classification:
  A. General Literature
  A.0 GENERAL
      Subjects: Biographies/autobiographies

Additional Classification:
  K. Computing Milieux
  K.2 HISTORY OF COMPUTING
      Subjects: People