Michael Alekhnovich

Affiliations:
  • Institute for Advanced Study, Princeton, NJ, USA


According to our database1, Michael Alekhnovich authored at least 21 papers between 1999 and 2011.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2011
Satisfiability, Branch-Width and Tseitin tautologies.
Comput. Complex., 2011

Hardness of Approximating the Closest Vector Problem with Pre-Processing.
Comput. Complex., 2011

Toward a Model for Backtracking and Dynamic Programming.
Comput. Complex., 2011

Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy.
Comput. Complex., 2011

More on Average Case vs Approximation Complexity.
Comput. Complex., 2011

Lower Bounds for k-DNF Resolution on Random 3-CNFs.
Comput. Complex., 2011

2009
Toward a Model for Backtracking and Dynamic Programming.
Electron. Colloquium Comput. Complex., 2009

2008
Resolution Is Not Automatizable Unless W[P] Is Tractable.
SIAM J. Comput., 2008

The complexity of properly learning simple concept classes.
J. Comput. Syst. Sci., 2008

2007
An Exponential Separation between Regular and General Resolution.
Theory Comput., 2007

Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs.
SIAM J. Comput., 2007

2005
Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes.
IEEE Trans. Inf. Theory, 2005

2004
Mutilated chessboard problem is exponentially hard for resolution.
Theor. Comput. Sci., 2004

Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas
Electron. Colloquium Comput. Complex., 2004

Linear Upper Bounds for Random Walk on Small Density Random 3CNFs
Electron. Colloquium Comput. Complex., 2004

Learnability and Automatizability.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Linear Upper Bounds for Random Walk on Small Density Random 3-CNF.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2001
Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.
J. Symb. Log., 2001

Lower Bounds for Polynomial Calculus: Non-Binomial Case.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000
Pseudorandom Generators in Propositional Proof Complexity
Electron. Colloquium Comput. Complex., 2000

1999
Space Complexity in Propositional Calculus
Electron. Colloquium Comput. Complex., 1999


  Loading...