Concepedia

Michael Alekhnovich

MA

Statistics

Publications

10

Citations

518

H-Index

10

Active since

2001

Affiliations

Massachusetts Institute of Technology(Current)

Institute for Advanced Study

University of Toronto

Ludwig-Maximilians-Universität München

Michael Alekhnovich is an author at Massachusetts Institute of Technology specializing in computer science, theory of computation, and computing.

Publications per year

2001–2011

10

Publications

10

Pseudorandom Generators in Propositional Proof Complexity

Michael Alekhnovich, Eli Ben‐Sasson, Alexander Razborov et al. · SIAM Journal on Computing · 2004 · 107 citations

, , +17

An exponential separation between regular and general resolution

Michael Alekhnovich, Jan Johannsen, Toniann Pitassi et al. · 2002 · 74 citations

, , +5

Resolution Is Not Automatizable Unless W[P] Is Tractable

Michael Alekhnovich, Alexander Razborov · SIAM Journal on Computing · 2008 · 71 citations

, , +13

Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas

Michael Alekhnovich, Edward Hirsch, Dmitry Itsykson · Journal of Automated Reasoning · 2006 · 62 citations

, , +10

More on Average Case vs Approximation Complexity

Michael Alekhnovich · Computational Complexity · 2011 · 53 citations

, , +14

1–5 of 10