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 (2012).
List of publications (2011).
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.
Technical reports, and unpublished work of some students who worked with me.
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
Home page for course on algorithmic game theory,
March 2013 - July 2013.
Lecture notes for first part of course on algorithmic game theory,
November - December 2008.
Home page for advanced course on algorithms (together with Robert Krauthgamer)
November 2011 - February 2012.
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