Eli Ben-Sasson

Eli Ben-Sasson

Contact information
Homepage:
http://www.eecs.harvard.edu/~eli/
Email:
eli[at]cs.technion.ac.il
Office:
520
Phone:
4892
Office Hours:
Sunday, 12:30-13:30
Research interests
Computational Complexity; Proof Complexity; Analysis of SAT solvers; Sub-linear time algorithms for Proof Checking and Error Correcting Codes.
Selected publications

BEN-SASSON, E. and SUDAN, M. "Short PCPs with poly-log rate and query complexity", Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, Pages: 266 275, 2005.

BEN-SASSON, E. GOLDREICH, O., HARSHA, P., SUDAN, M. and VADHAN, S. "Short PCPs verifiable in polylogarithmic time", Proceedings of the Twentieth Annual IEEE Conference on Computational Complexity, Page(s):120 134, 2005.

ALEKHNOVICH, M. and BEN-SASSON, E. "Linear Upper Bounds for Random Walk on Small Density Random 3CNFs", Proceedings of forty fourth Symposium on Foundations of Computer Science (FOCS 2003), pp. 352-361, 2003.

BEN-SASSON, E. and WIGDERSON, A. "Short proofs are narrow resolution made simple", Journal of the ACM, vol. 48(2), 2001, pp. 149-169.