| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Uriel Feige, Shlomo Jozeph |
Universal Factor Graphs  |
CoRR  |
2012 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Moshe Tennenholtz |
Mechanism design with uncertain inputs (to err is human, to forgive divine) |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov |
Oblivious Collaboration |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz |
Min-Max Graph Partitioning and Small Set Expansion |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Daniel Reichman |
Recoverable Values for Independent Sets |
CoRR |
2011 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Abraham D. Flaxman, Dan Vilenchik |
On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas. |
SIAM J. Discrete Math. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra |
Buffer Management for Colored Packets with Deadlines. |
Theory Comput. Syst. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Chandan K. Dubey, Uriel Feige, Walter Unger |
Hardness results for approximating the bandwidth. |
J. Comput. Syst. Sci. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski |
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). |
Dagstuhl Reports |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Vahab S. Mirrokni, Jan Vondrák |
Maximizing Non-monotone Submodular Functions. |
SIAM J. Comput. |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Daniel Reichman |
Recoverable Values for Independent Sets. |
ICALP |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil R. Devanur, Uriel Feige |
An O(n log n) Algorithm for a Load Balancing Problem on Paths. |
WADS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov |
Oblivious Collaboration. |
DISC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz |
Min-max Graph Partitioning and Small Set Expansion. |
FOCS |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Moshe Tennenholtz |
Mechanism design with uncertain inputs: (to err is human, to forgive divine). |
STOC |
2011 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Uriel Feige, Daniel Glasner |
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. |
Algorithmica |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Jan Vondrák |
The Submodular Welfare Problem with Demand Queries. |
Theory of Computing |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan |
Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Shlomo Jozeph |
Oblivious Algorithms for the Maximum Directed Cut Problem |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Inbal Talgam-Cohen |
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium |
CoRR |
2010 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige |
On Optimal Strategies for a Hat Game on Graphs. |
SIAM J. Discrete Math. |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Shimon Kogan |
Balanced coloring of bipartite graphs. |
Journal of Graph Theory |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Inbal Talgam-Cohen |
A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium. |
SAGT |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Moshe Tennenholtz |
Responsive Lotteries. |
SAGT |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan |
Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph. |
STOC |
2010 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Kunal Talwar |
Approximating the Bandwidth of Caterpillars. |
Algorithmica |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Ofer Zeitouni |
Deterministic approximation for the cover time of trees |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige |
Faster FAST(Feedback Arc Set in Tournaments) |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Reid Andersen, Uriel Feige |
Interchanging distance and capacity in probabilistic mappings |
CoRR |
2009 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige |
On Maximizing Welfare When Utility Functions Are Subadditive. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Uriel Feige |
On the power of two, three and four probes. |
SODA |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik |
On smoothed k-CNF formulas and the Walksat algorithm. |
SODA |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra |
Buffer management for colored packets with deadlines. |
SPAA |
2009 |
DBLP DOI BibTeX RDF |
dram scheduling, online algorithms, buffer management, packets scheduling, earliest deadline first |
| 1 | Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh |
PASS Approximation. |
APPROX-RANDOM |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Eran Ofek |
Finding a Maximum Independent Set in a Sparse Random Graph. |
SIAM J. Discrete Math. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee |
Improved Approximation Algorithms for Minimum Weight Vertex Separators. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour |
Combination Can Be Hard: Approximability of the Unique Coverage Problem. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Mohit Singh |
Edge Coloring and Decompositions of Weighted Graphs. |
ESA |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige |
On allocations that maximize fairness. |
SODA |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh |
A combinatorial allocation mechanism with penalties for banner advertising. |
WWW |
2008 |
DBLP DOI BibTeX RDF |
structural approximation, supply guarantee, combinatorial auctions, internet advertising |
| 1 | Reid Andersen, Christian Borgs, Jennifer T. Chayes, Uriel Feige, Abraham D. Flaxman, Adam Kalai, Vahab S. Mirrokni, Moshe Tennenholtz |
Trust-based recommendation systems: an axiomatic approach. |
WWW |
2008 |
DBLP DOI BibTeX RDF |
recommendation systems, reputation systems, trust networks, axiomatic approach |
| 1 | Yossi Azar, Uriel Feige, Daniel Glasner |
A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. |
SWAT |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Arash Asadpour, Uriel Feige, Amin Saberi |
Santa Claus Meets Hypergraph Matchings. |
APPROX-RANDOM |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige |
On Estimation Algorithms vs Approximation Algorithms. |
FSTTCS |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, James R. Lee |
An improved approximation ratio for the minimum linear arrangement problem. |
Inf. Process. Lett. |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Guy Kindler, Ryan O'Donnell |
Understanding Parallel Repetition Requires Understanding Foams. |
Electronic Colloquium on Computational Complexity (ECCC) |
2007 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Eran Ofek |
Easily refutable subformulas of large random 3CNF formulas. |
Theory of Computing |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab S. Mirrokni |
Robust Combinatorial Optimization with Exponential Scenarios. |
IPCO |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Mohit Singh |
Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. |
APPROX-RANDOM |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige |
Refuting Smoothed 3CNF Formulas. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Vahab S. Mirrokni, Jan Vondrák |
Maximizing Non-Monotone Submodular Functions. |
FOCS |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Guy Kindler, Ryan O'Donnell |
Understanding Parallel Repetition Requires Understanding Foams. |
IEEE Conference on Computational Complexity |
2007 |
DBLP DOI BibTeX RDF |
|
| 1 | David S. Johnson, Uriel Feige (eds.) |
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007 |
STOC |
2007 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Daniel Reichman |
On the hardness of approximating Max-Satisfy. |
Inf. Process. Lett. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Eran Ofek, Uriel Feige |
Random 3CNF formulas elude the Lovasz theta function. |
Electronic Colloquium on Computational Complexity (ECCC) |
2006 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Michael Langberg |
The RPR2 rounding technique for semidefinite programs. |
J. Algorithms |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Eran Ofek |
Random 3CNF formulas elude the Lovasz theta function |
CoRR |
2006 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige |
On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. |
SIAM J. Comput. |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour |
Combination can be hard: approximability of the unique coverage problem. |
SODA |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Elchanan Mossel, Dan Vilenchik |
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. |
APPROX-RANDOM |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Jeong Han Kim, Eran Ofek |
Witnesses for non-satisfiability of dense random 3CNF formulas. |
FOCS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Jan Vondrák |
Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. |
FOCS |
2006 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Mohammad Mahdian |
Finding small balanced separators. |
STOC |
2006 |
DBLP DOI BibTeX RDF |
fixed parameter tractability, VC dimension |
| 1 | Uriel Feige |
On maximizing welfare when utility functions are subadditive. |
STOC |
2006 |
DBLP DOI BibTeX RDF |
combinatorial auctions, randomized rounding |
| 1 | Uriel Feige, Eran Ofek |
Finding a Maximum Independent Set in a Sparse Random Graph |
Electronic Colloquium on Computational Complexity (ECCC) |
2005 |
DBLP BibTeX RDF |
|
| 1 | Eden Chlamtac, Uriel Feige |
Improved approximation of the minimum cover time. |
Theor. Comput. Sci. |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Eran Ofek |
Spectral techniques applied to sparse random graphs. |
Random Struct. Algorithms |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Dan Frumkin, Adam Wasserstrom, Shai Kaplan, Uriel Feige, Ehud Y. Shapiro |
Genomic Variability within an Organism Exposes Its Cell Lineage Tree. |
PLoS Computational Biology |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige |
Rigorous analysis of heuristics for NP-hard problems. |
SODA |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert D. Kleinberg |
On the Competitive Ratio of the Random Sampling Auction. |
WINE |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Eran Ofek |
Finding a Maximum Independent Set in a Sparse Random Graph. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Kunal Talwar |
Approximating the Bandwidth of Caterpillars. |
APPROX-RANDOM |
2005 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee |
Improved approximation algorithms for minimum-weight vertex separators. |
STOC |
2005 |
DBLP DOI BibTeX RDF |
vertex separators, approximation algorithms, semidefinite programming, treewidth, metric embeddings |
| 1 | Uriel Feige, Daniel Reichman |
On The Hardness of Approximating Max-Satisfy |
Electronic Colloquium on Computational Complexity (ECCC) |
2004 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, László Lovász, Prasad Tetali |
Approximating Min Sum Set Cover. |
Algorithmica |
2004 |
DBLP DOI BibTeX RDF |
Threshhold, NP-hardness, Greedy algorithm, Randomized rounding |
| 1 | Uriel Feige |
Approximating Maximum Clique by Removing Subgraphs. |
SIAM J. Discrete Math. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Daniele Micciancio |
The inapproximability of lattice and coding problems with preprocessing. |
J. Comput. Syst. Sci. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Michael Langberg, Gideon Schechtman |
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. |
SIAM J. Comput. |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Eran Ofek |
Easily Refutable Subformulas of Large Random 3CNF Formulas. |
ICALP |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Daniel Reichman |
On Systems of Linear Equations with Two Variables per Equation. |
APPROX-RANDOM |
2004 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige |
On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. |
STOC |
2004 |
DBLP DOI BibTeX RDF |
shortest paths, inequalities |
| 1 | Uriel Feige, Orly Yahalom |
On the complexity of finding balanced oneway cuts. |
Inf. Process. Lett. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Yuri Rabinovich |
Deterministic approximation of the cover time. |
Random Struct. Algorithms |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige |
Approximation thresholds for combinatorial optimization problems |
CoRR |
2003 |
DBLP BibTeX RDF |
|
| 1 | Uriel Feige, Robert Krauthgamer, Kobbi Nissim |
On Cutting a Few Vertices from a Graph. |
Discrete Applied Mathematics |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Robert Krauthgamer |
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set. |
SIAM J. Comput. |
2003 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Giora Rayzman |
On the drift of short schedules. |
Theor. Comput. Sci. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Gideon Schechtman |
On the optimality of the random hyperplane rounding technique for MAX CUT. |
Random Struct. Algorithms |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Marek Karpinski, Michael Langberg |
Improved approximation of Max-Cut on graphs of bounded degree. |
J. Algorithms |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Christian Scheideler |
Improved Bounds for Acyclic Job Shop Scheduling. |
Combinatorica |
2002 |
DBLP DOI BibTeX RDF |
AMS Subject Classification (2000) Classes: 68M20, 90B35, 68W25 |
| 1 | Uriel Feige, Oleg Verbitsky |
Error Reduction by Parallel Repetition - A Negative Result. |
Combinatorica |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan |
Approximating the Domatic Number. |
SIAM J. Comput. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Robert Krauthgamer |
A Polylogarithmic Approximation of the Minimum Bisection. |
SIAM J. Comput. |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Eran Ofek, Udi Wieder |
Approximating Maximum Edge Coloring in Multigraphs. |
APPROX |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, László Lovász, Prasad Tetali |
Approximating Min-sum Set Cover. |
APPROX |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Michael Langberg, Gideon Schechtman |
Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. |
FOCS |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige |
Relations between Average Case Complexity and Approximation Complexity. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
random 3sat, bipartite clique, bisection |
| 1 | Uriel Feige, Daniele Micciancio |
The Inapproximability of Lattice and Coding Problems with Preprocessing. (PDF / PS) |
IEEE Conference on Computational Complexity |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige |
Relations between average case complexity and approximation complexity. |
STOC |
2002 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, Marek Karpinski, Michael Langberg |
A note on approximating Max-Bisection on regular graphs. |
Inf. Process. Lett. |
2001 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")