Michael Alekhnovich

Allan Borodin

Joshua Buresh-Oppenheim

Russell Impagliazzo

Avner Magen

Electron. Colloquium Comput. Complex., 2009

2008

The complexity of properly learning simple concept classes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2008

2007

Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs.

[BibT_eX]

[DOI]

Mikhail Alekhnovich

SIAM J. Comput., 2007

2005

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy.

[BibT_eX]

[DOI]

Sanjeev Arora

Iannis Tourlakis

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Lower bounds for k-DNF resolution on random 3-CNFs.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Hardness of Approximating the Closest Vector Problem with Pre-Processing.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

Toward a Model for Backtracking and Dynamic Programming.

[BibT_eX]

[DOI]

Allan Borodin

Joshua Buresh-Oppenheim

Russell Impagliazzo

Avner Magen

Toniann Pitassi

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Mutilated chessboard problem is exponentially hard for resolution.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Linear Upper Bounds for Random Walk on Small Density Random 3CNFs

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

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

[BibT_eX]

[DOI]

Edward A. Hirsch

Dmitry Itsykson

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

Learnability and Automatizability.

[BibT_eX]

[DOI]

Proceedings of the 45th Symposium on Foundations of Computer Science, 2004

2003

Linear Upper Bounds for Random Walk on Small Density Random 3-CNF.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

More on Average Case vs Approximation Complexity.

[BibT_eX]

[DOI]

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

2002

An exponential separation between regular and general resolution.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Satisfiability, Branch-Width and Tseitin Tautologies.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

Linear Diophantine Equations over Polynomials and Soft Decoding of Reed-Solomon Codes.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 2002

2001

Resolution is Not Automatizable Unless W[P] is Tractable.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Lower Bounds for Polynomial Calculus: Non-Binomial Case.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Space complexity in propositional calculus.

[BibT_eX]

[DOI]

Avi Wigderson

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Pseudorandom Generators in Propositional Proof Complexity.

[BibT_eX]

[DOI]