Uriel Feige
Uriel Feige
weizmann.ac.il
Research Interests:
Mostly coping with NP-hard combinatorial optimization problems.
Also cryptography, random walks, and miscellaneous other stuff.
My CV (October 2009).
List of publications (October 2009).
Selected older publications on hardness of approximation, approximation algorithms and heuristics.
A short survey on my work on random walks.
My PHD thesis on alternative models for zero knowledge interactive proofs.
Some other publications that I like but do not fit in any of the other categories.
Follow link to search for technical reports, where some papers of mine can be found.
Talk presentations
Approximation algorithm based on Semidefinite programming , a powerpoint
presentation, November 2003.
Questions that supplement the above presentation.
Interchanging distance and capacity in probabilistic mappings , a talk delivered in the workshop on
Quantitative and Computational Aspects of Metric Geometry, IPAM, January 2009.
Teaching
Lecture notes for first part of course on algorithmic gamer theory,
November - December 2008.
Home page for advanced course on algorithms,
March 2004 - June 2004.
Home page for course on Computational Complexity,
October 2003 - February 2004.
Lecture notes for course on probabilistically checkable proofs and
hardness of approximation,
March 2003 - June 2003.
Sketch of solutions for final exam in probabilistic methods in CS,
February 2003.
Lecture notes for course on algorithms and Linear Programming,
April 2002 - July 2002.
Lecture notes for course on algorithms and their analysis,
October 1999 - February 2000, plus updates from similar courses
2001-2002, 2009-2010.
Final exam
March 13, 2002 and
solutions to final exam (prepared by Eran Tromer).
Other links
Research in Foundations of Computer Science
at the Weizmann Institute
The Puzzler Puzzles related to research by members of the department