Photo of Prof. Eli Ben-Sasson

Prof. Eli Ben-Sasson

Advisor for students not in good standing

Contact information
Office Hours:
Tuesday, 15:30-16: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.