Dan Gutfreund
I am a lecturer at the Department of Mathematics at MIT.
My field of research is the theory of computer science, mainly computational complexity
and the foundations of cryptography.
My office is 2-339. My e-mail address is: danny (at) math (dot) mit (dot) edu.
Teaching:
In fall 2008 I'm teaching the course Introduction to Probability and Statistics (18.05).
Papers:
- The complexity of local list-decoding. With Guy Rothblum. In proceedings of the 12th International Workshop on Randomization and Computation (RANDOM), 2008.
- Limitations of hardness vs. randomness under uniform reductions. With Salil Vadhan. In proceedings of the 12th International Workshop on Randomization and Computation (RANDOM), 2008.
- A (De)constructive Approach to Program Checking. With Shafi Goldwasser, Alex Healy, Tali Kaufman and Guy Rothblum. To appear in proceedings of the 40th ACM Symposium on Theory of Computing (STOC), 2008.
- Worst-case to average-case reductions revisited. With Amnon Ta-Shma. In proceedings of the 11th International Workshop on Randomization and Computation (RANDOM), 2007.
- Verifying and decoding in constant depth. With Shafi Goldwasser, Alex Healy, Tali Kaufman and Guy Rothblum. Preliminary version in proceedings of the 39th ACM Symposium on Theory of Computing (STOC), 2007.
- If NP languages are hard on the worst-case then it is easy to find their hard instances. With Ronen Shaltiel and Amnon Ta-Shma. Journal of Computational Complexity (special issue on worst-case vs. average-case) 2007.
A shorter version appeared in Proceedings of the 20th Conference on Computational Complexity (CCC), 2005.
- Worst-case vs. algorithmic average-case complexity in the polynomial-time hierarchy. A shorter version in Proceedings of the 10th International Workshop on Randomization and Computation (RANDOM) 2006.
- Fooling parity tests with parity gates. With Emanuele Viola. In Proceedings of the 8th International Workshop on Randomization and Computation (RANDOM) 2004.
- A lower bound for testing juntas. With Hana Chockler. Information Processing Letters, 2004.
- Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. With Ronen Shaltiel and Amnon Ta-Shma. Journal of Computational Complexity, 2003.
Preliminary version appeared in Proceedings of the 18th Conference on Computational Complexity (CCC), 2003.
- Trading help for interaction in statistical zero-knowledge proofs. With Michael Ben-Or. Journal of Cryptology, 2003.
Preliminary version
(titled "Increasing the power of the dealer in non-interactive zero-knowledge proof systems") appeared in Proceedings of ASIACRYPT 2000.
Thesis: