Uriel Feige
Theory Group
Microsoft Research
One Microsoft Way
Redmond, WA 98052-6399
Office: (425) 722-6648
Fax: (425) 936-7329
email: urifeige@microsoft.com
See also Weizmann home page.
CV: ps
pdf.
Publications: ps
pdf.
STOC 07 CALL FOR PAPERS
STOC 07 LIST OF ACCEPTED PAPERS
Some STATISTICS regarding the work of the STOC program committee,
including a disclaimer concerning comments to the authors.
Research Interests:
- Coping with NP hardness.
-
Algorithms.
- Computational complexity.
The P versus NP question: is there any progress? Slides for talk given on March 8, 2007.
Some recent work. (The versions accessible through this home page are the author's version of the papers.
For the definitive version of those papers that have been published, please see the relevant journal or conference proceedings. )
[1] Uriel Feige On sums of independent random variables with unbounded variance,
and estimating the average degree in a graph.
ps
pdf.
Final version in SICOMP 2006.
Preliminary version appeared in Proceedings of 36th STOC, 594--603,
2004.
[2] Uriel Feige and Daniel Reichman.
On the hardness of approximating Max-Satisfy.
ps
pdf.
IPL 2006. The version posted here has a more accurate reference list.
[3] Uriel Feige, MohammadTaghi Hajiaghayi and James Lee.
Improved approximation algorithms for minimum-weight vertex
separators.
ps.
pdf.
Submitted for journal publication (SICOMP), 2005.
Preliminary version appeared in
Proceedings of 37th STOC, 2005, 563--572.
[4] Uriel Feige.
Rigorous Analysis of Heuristics for NP-hard Problems.
pdf.
Manuscript corresponding to invited presentations in SODA (Vancouver 2005) and Workshop on New Horizons in Computing (Kyoto 2005).
[5] Uriel Feige and Shimon Kogan.
The hardness of approximating hereditary properties.
ps
pdf.
Submitted for journal publication, 2005.
[6] Uriel Feige and Shimon Kogan.
Balanced coloring of bipartite graphs.
ps
pdf.
Submitted for journal publication, 2005.
[7] Uriel Feige and Kunal Talwar.
Approximating the bandwidth of caterpillars.
ps
pdf.
In proceedings of Approx 2005, LNCS 3624 Springer, 62--73, 2005.
[8] Uriel Feige and Eran Ofek.
Finding a maximum independent set
in a sparse random graph.
ps
pdf.
In Proceedings of Random 2005, LNCS
3624 Springer, 282--293, 2005.
[9] Erik Demaine, Uriel Feige, MohammadTaghi Hajiaghayi and
Mohammad R. Salavatipour.
Combination can be hard:
approximability of the unique coverage problem.
ps
pdf.
SODA 2006.
[10] Uriel Feige and Mohammad Mahdian.
Finding small balanced separators.
ps
pdf.
In proceedings of STOC 2006.
[11] Uriel Feige, Abraham Flaxman,
Jason D. Hartline and Robert Kleinberg.
On the Competitive Ratio of the Random Sampling Auction.
ps
pdf.
WINE 2005.
[12] Uriel Feige.
On maximizing welfare when utility functions are subadditive.
ps
pdf.
STOC 2006.
[13] Uriel Feige and James Lee.
An improved approximation ratio for the minimum linear arrangement problem.
ps
pdf.
To appear in IPL.
[14] Uriel Feige and Jan Vondrak.
The allocation problem with submodular utility functions.
ps
pdf.
Manuscript, February 2006. Part of a paper that will appear in FOCS 2006.
[15] Uriel Feige and Eran Ofek.
Random 3CNF formulas elude the Lov\'{a}sz theta function.
ps
pdf.
Manuscript, April 2006.
[16] Uriel Feige, Jeong Han Kim and Eran Ofek.
Witnesses for non-satisfiability of dense random 3CNF formulas.
ps
pdf.
Manuscript, May 2006. To appear in FOCS 2006.
[17] Uriel Feige and Mohit Singh.
Improved approximation ratios for traveling salesperson tours and paths in directed graphs.
ps
pdf.
Manuscript, August 2006.
[18] Uriel Feige, Kamal Jain, Mohammad Mahdian and Vahab Mirrokni
Robust Combinatorial Optimization with Exponential Scenarios.
ps
pdf.
Manuscript, November 2006.
[19] Uriel Feige, Elchanan Mossel and Dan Vilenchik.
Complete convergence of message passing algorithms for some satisfiability problems.
ps
pdf.
Preliminary version from April 2006. In Proceedings of Random 2006, LNCS
4110 Springer, 339--350, 2006.