Technical Reports

The links below are to some of my technical reports. Newer technical reports can be found on the arXiv.

Uriel Feige and Kobbi Nissim.
On the use of interactive proofs for formal program verification.
Technical report CS97-06 of the Weizmann Institute, 1997.

Uriel Feige and Michael Seltser.
On the densest k-subgraph problem.
Technical report CS97-16 of the Weizmann Institute, 1997.

Uriel Feige.
Vertex cover is hardest to approximate on regular graphs.
Technical report MCS03-15 of the Weizmann Institute, 2003.

Uriel Feige.
You can leave your hat on (if you guess its color).
Technical report MCS04-03 of the Weizmann Institute, 2004.

Uriel Feige and Shimon Kogan.
Hardness of Approximation of the Balanced Complete Bipartite Subgraph Problem.
Technical report MCS04-04 of the Weizmann Institute, 2004.

Uriel Feige and Dan Vilenchik.
A local search algorithm for 3SAT.
Technical report MCS04-07 of the Weizmann Institute, 2004.

Uriel Feige and Shimon Kogan.
The Hardness of Approximating Hereditary Properties.
Manuscript.
Version: April 2005.

Uri Barenholz, Uriel Feige and David Peleg.
Improved Approximation for Min-Sum Vertex Cover.
Technical report MCS06-07 of the Weizmann Institute, 2006.

Yossi Azar, Uriel Feige, Suman Nath.
On the work function algorithm for two state task systems.
Technical Report MSR-TR-2007-20, Microsoft Corporation, February 2007.


Additional work done by students working with me.


Yuval Filmus.
Bandwidth approximation of a restricted family of trees.
MSc thesis, 2002.

Eran Keydar.
Finding Hamiltonian cycles in semi-random graphs.
MSc thesis, 2002.

Gabriel Nivasch.
Experimental Results on Hamiltonian-Cycle-Finding Algorithms.
Manuscript, 2003.

Simon Korman.
On the use of randomization in the online set cover problem.
MSc thesis, 2004.

Shira Kritchman.
Path coloring on the mesh - constructive version.
Manuscript, 2010.

Alina Arbitman.
Planted random 3SAT with a small fraction of 1-clauses.
MSc thesis, 2012.

Elana Bereznik.
Spectral graph theory.
In Hebrew, 2012.

Itay Gonshorovitz.
Reducing the maximum flow.
MSc thesis, 2012.

Roee David.
Finding planted k-coloring in vector k-colorable graphs.
MSc thesis, 2012.

Tal Wagner.
Generalized Girth Problems in Graphs and Hypergraphs.
MSc thesis, 2013.

Uri Sherman.
A Different Perspective For Approximating Max Set Packing.
MSc thesis, 2013.

Yuval Madar.
A capacitated cut and choose game.
MSc thesis, 2015.