Image of Uriel Feige Uriel Feige

Department of Computer Science and Applied Mathematics, the Weizmann Institute, Rehovot 76100, Israel.
Office: Zyskind 251
Office Phone: (972)-8-9343364
Fax: (972)-8-9344122 (attn. Uri Feige)

Research Interests:
Coping with NP-hard combinatorial optimization problems (approximation algorithms, beyond worst case analysis, hardness results).
Algorithmic game theory (allocation problems, fairness).
Past interests: cryptography, random walks, and miscellaneous other stuff.

My CV (2021).
List of publications (2017).

Summer Internships:
If you wish to apply for a summer internship in the department of Computer Science and Applied Mathematics please follow the instructions on the home page of the Feinberg Graduate School regarding the Kupcinet-Getz International Summer School.

Some online publications:

Publications since 2007.

Publications 2005-2007.

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 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.

Home page for reading course on advanced algorithms, March 2022 - July 2022.
Home page course on beyond worst case analysis of algorithms, March 2021 - July 2021.
Home page course on approximation algorithms, November 2018 - February 2019, and advanced course March 2019 - July 2019.
Home page course on algorithms, November 2017 - February 2018.
Home page course on linear programming and combinatorial optimization, March 2015 - June 2015.
Home page course on algorithms, March 2014 - June 2014.
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).
Lecture notes for course on algorithms and Linear Programming, April 2002 - July 2002.
Home page for advanced course on algorithms, March 2004 - June 2004.
Home page for advanced course on algorithms (together with Robert Krauthgamer) November 2011 - February 2012.
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 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.

Other links
On the diversity principle and local falsifiability Some of my thoughts while evaluating papers on Algorithmic Game Theory, as a program committee member for the 2013 ITCS (Innovations in Theoretical Computer Science) conference.
Research in Foundations of Computer Science at the Weizmann Institute
The Puzzler Puzzles related to research by members of the department