Prof. Eli Ben-Sasson
- 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.