Uriel Feige - RankMe

295 papers A* 78A 13B 7C 2Journal 160Unranked 34

Year	Rank	Type	Title / Venue / Authors
2025	J	`jnl`	Concentration and maximin fair allocations for subadditive valuations. CoRR Uriel Feige, Shengyu Huang
2025	J	`jnl`	Fair Shares: Feasibility, Domination, and Incentives. Math. Oper. Res. Moshe Babaioff, Uriel Feige
2025	A*	`conf`	Fair allocations with subadditive and XOS valuations. EC Uriel Feige, Vadim Grinberg
2025	J	`jnl`	Fair allocations with subadditive and XOS valuations. CoRR Uriel Feige, Vadim Grinberg
2025	J	`jnl`	From multi-allocations to allocations, with subadditive valuations. CoRR Uriel Feige
2025	J	`jnl`	Large cliques and large independent sets: can they coexist? CoRR Uriel Feige, Ilia Pauzner
2025	A*	`conf`	Low communication protocols for fair allocation of indivisible goods. EC Uriel Feige
2025	A*	`conf`	Share-Based Fairness for Arbitrary Entitlements. STOC Moshe Babaioff, Uriel Feige
2025	J	`jnl`	The Query Complexity of Searching Trees with Permanently Noisy Advice. ACM Trans. Algorithms Lucas Boczkowski, Uriel Feige, Amos Korman, Yoav Rodeh
2025	J	`jnl`	The Surprising Power of Spectral Refutation. Commun. ACM Uriel Feige
2025	J	`jnl`	The residual maximin share. CoRR Uriel Feige
2025	J	`jnl`	Upper bounds on the theta function of random graphs. CoRR Uriel Feige, Vadim Grinberg
2024	J	`jnl`	Fair-Share Allocations for Agents with Arbitrary Entitlements. Math. Oper. Res. Moshe Babaioff, Tomer Ezra, Uriel Feige
2024	J	`jnl`	How to Hide a Clique? Theory Comput. Syst. Uriel Feige, Vadim Grinberg
2024	J	`jnl`	Low communication protocols for fair allocation of indivisible goods. CoRR Uriel Feige
2024	J	`jnl`	Share-Based Fairness for Arbitrary Entitlements. CoRR Moshe Babaioff, Uriel Feige
2023	A*	`ed.`	50th International Colloquium on Automata, Languages, and Programming, ICALP 2023, Paderborn, Germany, July 10-14, 2023 ICALP Kousha Etessami, Uriel Feige, Gabriele Puppis
2023	J	`jnl`	On Fair Allocation of Indivisible Goods to Submodular Agents. CoRR Gilad Ben Uziahu, Uriel Feige
2023	A*	`conf`	On picking sequences for chores. EC Uriel Feige, Xin Huang
2023	J	`jnl`	The inversion paradox, and classification of fairness notions. CoRR Uriel Feige
2022	A*	`conf`	Fair Allocations for Smoothed Utilities. EC Yushi Bai, Uriel Feige, Paul Gölz, Ariel D. Procaccia
2022	A*	`conf`	Fair Shares: Feasibility, Domination and Incentives. EC Moshe Babaioff, Uriel Feige
2022	J	`jnl`	Fair Shares: Feasibility, Domination and Incentives. CoRR Moshe Babaioff, Uriel Feige
2022	J	`jnl`	Improved maximin fair allocation of indivisible items to three agents. CoRR Uriel Feige, Alexey Norkin
2022	J	`jnl`	Max-Min Greedy Matching. Theory Comput. Alon Eden, Uriel Feige, Michal Feldman
2022	—	`conf`	On Best-of-Both-Worlds Fair-Share Allocations. WINE Moshe Babaioff, Tomer Ezra, Uriel Feige
2022	J	`jnl`	On allocations that give intersecting groups their fair share. CoRR Uriel Feige, Yehonatan Tahan
2022	J	`jnl`	On picking sequences for chores. CoRR Uriel Feige, Xin Huang
2022	J	`jnl`	On the path partition number of 6-regular graphs. J. Graph Theory Uriel Feige, Ella Fuchs
2021	—	`conf`	A Tight Negative Example for MMS Fair Allocations. WINE Uriel Feige, Ariel Sapir, Laliv Tauber
2021	J	`jnl`	A tight bound for the clique query problem in two rounds. CoRR Uriel Feige, Tom Ferster
2021	J	`jnl`	A tight negative example for MMS fair allocations. CoRR Uriel Feige, Ariel Sapir, Laliv Tauber
2021	A*	`conf`	Are Gross Substitutes a Substitute for Submodular Valuations? EC Shahar Dobzinski, Uriel Feige, Michal Feldman
2021	J	`jnl`	Are Gross Substitutes a Substitute for Submodular Valuations? CoRR Shahar Dobzinski, Uriel Feige, Michal Feldman
2021	J	`jnl`	Best-of-Both-Worlds Fair-Share Allocations. CoRR Moshe Babaioff, Tomer Ezra, Uriel Feige
2021	A*	`conf`	Fair and Truthful Mechanisms for Dichotomous Valuations. AAAI Moshe Babaioff, Tomer Ezra, Uriel Feige
2021	A*	`conf`	Fair-Share Allocations for Agents with Arbitrary Entitlements. EC Moshe Babaioff, Tomer Ezra, Uriel Feige
2021	J	`jnl`	Fair-Share Allocations for Agents with Arbitrary Entitlements. CoRR Moshe Babaioff, Tomer Ezra, Uriel Feige
2021	J	`jnl`	Navigating in Trees with Permanently Noisy Advice. ACM Trans. Algorithms Lucas Boczkowski, Uriel Feige, Amos Korman, Yoav Rodeh
2021	J	`jnl`	Target set selection for conservative populations. Discret. Appl. Math. Uriel Feige, Shimon Kogan
2020	J	`jnl`	Approximate Modularity Revisited. SIAM J. Comput. Uriel Feige, Michal Feldman, Inbal Talgam-Cohen
2020	J	`jnl`	Fair and Truthful Mechanisms for Dichotomous Valuations. CoRR Moshe Babaioff, Tomer Ezra, Uriel Feige
2020	J	`jnl`	Finding cliques using few probes. Random Struct. Algorithms Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali
2020	A*	`conf`	How to Hide a Clique? ICALP Uriel Feige, Vadim Grinberg
2020	J	`jnl`	How to hide a clique? CoRR Uriel Feige, Vadim Grinberg
2020	—	`ch.`	Introduction to Semirandom Models. Beyond the Worst-Case Analysis of Algorithms Uriel Feige
2020	J	`jnl`	On the Profile of Multiplicities of Complete Subgraphs. SIAM J. Discret. Math. Uriel Feige, Anne Kenyon, Shimon Kogan
2020	J	`jnl`	Quantitative Group Testing and the rank of random matrices. CoRR Uriel Feige, Amir Lellouche
2020	J	`jnl`	Shotgun assembly of random jigsaw puzzles. Random Struct. Algorithms Charles Bordenave, Uriel Feige, Elchanan Mossel
2019	—	`conf`	A New Approach to Fair Distribution of Welfare. WINE Moshe Babaioff, Uriel Feige
2019	J	`jnl`	A New Approach to Fair Distribution of Welfare. CoRR Moshe Babaioff, Uriel Feige
2019	A*	`conf`	A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. SODA Uriel Feige, Janardhan Kulkarni, Shi Li
2019	J	`jnl`	A randomized strategy in the mirror game. CoRR Uriel Feige
2019	—	`conf`	Max-Min Greedy Matching. APPROX-RANDOM Alon Eden, Uriel Feige, Michal Feldman
2019	—	`conf`	Max-min greedy matching. NetEcon@SIGMETRICS Alon Eden, Uriel Feige, Michal Feldman
2019	J	`jnl`	On the path partition number of 6-regular graphs. CoRR Uriel Feige, Ella Fuchs
2019	J	`jnl`	Target Set Selection for Conservative Populations. CoRR Uriel Feige, Shimon Kogan
2018	J	`jnl`	A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time. CoRR Uriel Feige, Janardhan Kulkarni, Shi Li
2018	J	`jnl`	Finding cliques using few probes. CoRR Uriel Feige, David Gamarnik, Joe Neeman, Miklós Z. Rácz, Prasad Tetali
2018	J	`jnl`	Max-Min Greedy Matching. CoRR Alon Eden, Uriel Feige, Michal Feldman
2018	A*	`conf`	On the Probe Complexity of Local Computation Algorithms. ICALP Uriel Feige, Boaz Patt-Shamir, Shai Vardi
2018	J	`jnl`	Random Walks with the Minimum Degree Local Rule Have O(n SIAM J. Comput. Roee David, Uriel Feige
2018	B	`conf`	Robust Inference for Multiclass Classification. ALT Uriel Feige, Yishay Mansour, Robert E. Schapire
2018	J	`jnl`	The Ordered Covering Problem. Algorithmica Uriel Feige, Yael Hitron
2018	J	`jnl`	Tighter bounds for online bipartite matching. CoRR Uriel Feige
2017	J	`jnl`	A greedy approximation algorithm for minimum-gap scheduling. J. Sched. Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor
2017	A*	`conf`	Approximate modularity revisited. STOC Uriel Feige, Michal Feldman, Inbal Talgam-Cohen
2017	J	`jnl`	Chasing Ghosts: Competing with Stateful Policies. SIAM J. Comput. Uriel Feige, Tomer Koren, Moshe Tennenholtz
2017	J	`jnl`	On the Probe Complexity of Local Computation Algorithms. CoRR Uriel Feige, Boaz Patt-Shamir, Shai Vardi
2017	J	`jnl`	Optimization with Uniform Size Queries. Algorithmica Uriel Feige, Moshe Tennenholtz
2017	A*	`conf`	Random Walks with the Minimum Degree Local Rule Have SODA Roee David, Uriel Feige
2016	J	`jnl`	Approximate Modularity Revisited. CoRR Uriel Feige, Michal Feldman, Inbal Talgam-Cohen
2016	—	`conf`	Oblivious Rounding and the Integrality Gap. APPROX-RANDOM Uriel Feige, Michal Feldman, Inbal Talgam-Cohen
2016	J	`jnl`	On giant components and treewidth in the layers model. Random Struct. Algorithms Uriel Feige, Jonathan Hermon, Daniel Reichman
2016	A*	`conf`	On the effect of randomness on planted 3-coloring models. STOC Roee David, Uriel Feige
2016	J	`jnl`	On the effect of randomness on planted 3-coloring models. CoRR Roee David, Uriel Feige
2016	J	`jnl`	Random walks with the minimum degree local rule have $O(n^2)$ cover time. CoRR Roee David, Uriel Feige
2016	J	`jnl`	Shotgun Assembly of Random Jigsaw Puzzles. CoRR Charles Bordenave, Uriel Feige, Elchanan Mossel
2015	A*	`conf`	A Unifying Hierarchy of Valuations with Complements and Substitutes. AAAI Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis
2015	A*	`conf`	Contagious Sets in Expanders. SODA Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman
2015	A*	`conf`	Learning and inference in the presence of corrupted inputs. COLT Uriel Feige, Yishay Mansour, Robert E. Schapire
2015	J	`jnl`	Oblivious Algorithms for the Maximum Directed Cut Problem. Algorithmica Uriel Feige, Shlomo Jozeph
2015	J	`jnl`	Recoverable values for independent sets. Random Struct. Algorithms Uriel Feige, Daniel Reichman
2015	A	`conf`	Separation between Estimation and Approximation. ITCS Uriel Feige, Shlomo Jozeph
2015	A	`conf`	Why are Images Smooth? ITCS Uriel Feige
2014	J	`jnl`	A Unifying Hierarchy of Valuations with Complements and Substitutes. CoRR Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis
2014	J	`jnl`	A Unifying Hierarchy of Valuations with Complements and Substitutes. Electron. Colloquium Comput. Complex. Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis
2014	A*	`conf`	Chasing Ghosts: Competing with Stateful Policies. FOCS Uriel Feige, Tomer Koren, Moshe Tennenholtz
2014	J	`jnl`	Chasing Ghosts: Competing with Stateful Policies. CoRR Uriel Feige, Tomer Koren, Moshe Tennenholtz
2014	—	`conf`	Demand Queries with Preprocessing. ICALP (1) Uriel Feige, Shlomo Jozeph
2014	A	`conf`	Invitation games and the price of stability. ITCS Uriel Feige, Moshe Tennenholtz
2014	J	`jnl`	Min-Max Graph Partitioning and Small Set Expansion. SIAM J. Comput. Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2014	J	`jnl`	Musical Chairs. SIAM J. Discret. Math. Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov
2014	J	`jnl`	NP-hardness of hypercube 2-segmentation. CoRR Uriel Feige
2014	J	`jnl`	On fair division of a homogeneous good. Games Econ. Behav. Uriel Feige, Moshe Tennenholtz
2014	J	`jnl`	On giant components and treewidth in the layers model. CoRR Uriel Feige, Jonathan Hermon, Daniel Reichman
2014	J	`jnl`	On robustly asymmetric graphs. CoRR Uriel Feige
2014	J	`jnl`	Separation between Estimation and Approximation. Electron. Colloquium Comput. Complex. Uriel Feige, Shlomo Jozeph
2014	A	`conf`	Sequential decision making with vector outcomes. ITCS Yossi Azar, Uriel Feige, Michal Feldman, Moshe Tennenholtz
2014	B	`conf`	Short Tours through Large Linear Forests. IPCO Uriel Feige, R. Ravi, Mohit Singh
2014	J	`jnl`	Why are images smooth? CoRR Uriel Feige
2013	C	`conf`	A Greedy Approximation Algorithm for Minimum-Gap Scheduling. CIAC Marek Chrobak, Uriel Feige, Mohammad Taghi Hajiaghayi, Sanjeev Khanna, Fei Li, Seffi Naor
2013	A*	`conf`	Competition among asymmetric sellers with fixed supply. EC Uriel Feige, Ron Lavi, Moshe Tennenholtz
2013	J	`jnl`	Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. Theory Comput. Uriel Feige, Elchanan Mossel, Dan Vilenchik
2013	—	`conf`	Connectivity of Random High Dimensional Geometric Graphs. APPROX-RANDOM Roee David, Uriel Feige
2013	J	`jnl`	Contagious Sets in Expanders. CoRR Amin Coja-Oghlan, Uriel Feige, Michael Krivelevich, Daniel Reichman
2013	J	`jnl`	PASS Approximation: A Framework for Analyzing and Designing Heuristics. Algorithmica Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh
2013	A*	`conf`	The Cascade Auction - A Mechanism for Deterring Collusion in Auctions. AAAI Uriel Feige, Gil Kalai, Moshe Tennenholtz
2013	J	`jnl`	Welfare Maximization and the Supermodular Degree. Electron. Colloquium Comput. Complex. Uriel Feige, Rani Izsak
2013	A	`conf`	Welfare maximization and the supermodular degree. ITCS Uriel Feige, Rani Izsak
2012	A	`conf`	Mastering multi-player games. AAMAS Yossi Azar, Uriel Feige, Moshe Tennenholtz, Michal Feldman
2012	J	`jnl`	Musical chairs CoRR Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov
2012	J	`jnl`	Santa claus meets hypergraph matchings. ACM Trans. Algorithms Arash Asadpour, Uriel Feige, Amin Saberi
2012	J	`jnl`	Universal Factor Graphs CoRR Uriel Feige, Shlomo Jozeph
2012	—	`conf`	Universal Factor Graphs. ICALP (1) Uriel Feige, Shlomo Jozeph
2011	B	`conf`	An O(n log n) Algorithm for a Load Balancing Problem on Paths. WADS Nikhil R. Devanur, Uriel Feige
2011	J	`jnl`	Buffer Management for Colored Packets with Deadlines. Theory Comput. Syst. Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra
2011	J	`jnl`	Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski
2011	J	`jnl`	Hardness results for approximating the bandwidth. J. Comput. Syst. Sci. Chandan K. Dubey, Uriel Feige, Walter Unger
2011	J	`jnl`	Maximizing Non-monotone Submodular Functions. SIAM J. Comput. Uriel Feige, Vahab S. Mirrokni, Jan Vondrák
2011	J	`jnl`	Mechanism design with uncertain inputs (to err is human, to forgive divine) CoRR Uriel Feige, Moshe Tennenholtz
2011	A*	`conf`	Mechanism design with uncertain inputs: (to err is human, to forgive divine). STOC Uriel Feige, Moshe Tennenholtz
2011	J	`jnl`	Min-Max Graph Partitioning and Small Set Expansion CoRR Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2011	A*	`conf`	Min-max Graph Partitioning and Small Set Expansion. FOCS Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz
2011	J	`jnl`	Oblivious Collaboration CoRR Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov
2011	A	`conf`	Oblivious Collaboration. DISC Yehuda Afek, Yakov Babichenko, Uriel Feige, Eli Gafni, Nati Linial, Benny Sudakov
2011	J	`jnl`	On the Diameter of the Set of Satisfying Assignments in Random Satisfiable SIAM J. Discret. Math. Uriel Feige, Abraham D. Flaxman, Dan Vilenchik
2011	J	`jnl`	Recoverable Values for Independent Sets CoRR Uriel Feige, Daniel Reichman
2011	—	`conf`	Recoverable Values for Independent Sets. ICALP (1) Uriel Feige, Daniel Reichman
2010	B	`conf`	A Direct Reduction from SAGT Uriel Feige, Inbal Talgam-Cohen
2010	J	`jnl`	A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium CoRR Uriel Feige, Inbal Talgam-Cohen
2010	J	`jnl`	A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. Algorithmica Yossi Azar, Uriel Feige, Daniel Glasner
2010	J	`jnl`	Balanced coloring of bipartite graphs. J. Graph Theory Uriel Feige, Shimon Kogan
2010	J	`jnl`	Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph CoRR Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan
2010	A*	`conf`	Detecting high log-densities: an STOC Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan
2010	J	`jnl`	Oblivious Algorithms for the Maximum Directed Cut Problem CoRR Uriel Feige, Shlomo Jozeph
2010	J	`jnl`	On Optimal Strategies for a Hat Game on Graphs. SIAM J. Discret. Math. Uriel Feige
2010	B	`conf`	Responsive Lotteries. SAGT Uriel Feige, Moshe Tennenholtz
2010	J	`jnl`	The Submodular Welfare Problem with Demand Queries. Theory Comput. Uriel Feige, Jan Vondrák
2009	J	`jnl`	Approximating the Bandwidth of Caterpillars. Algorithmica Uriel Feige, Kunal Talwar
2009	B	`conf`	Buffer management for colored packets with deadlines. SPAA Yossi Azar, Uriel Feige, Iftah Gamzu, Thomas Moscibroda, Prasad Raghavendra
2009	J	`jnl`	Deterministic approximation for the cover time of trees CoRR Uriel Feige, Ofer Zeitouni
2009	J	`jnl`	Faster FAST(Feedback Arc Set in Tournaments) CoRR Uriel Feige
2009	J	`jnl`	Interchanging distance and capacity in probabilistic mappings CoRR Reid Andersen, Uriel Feige
2009	J	`jnl`	On Maximizing Welfare When Utility Functions Are Subadditive. SIAM J. Comput. Uriel Feige
2009	A*	`conf`	On smoothed SODA Amin Coja-Oghlan, Uriel Feige, Alan M. Frieze, Michael Krivelevich, Dan Vilenchik
2009	A*	`conf`	On the power of two, three and four probes. SODA Noga Alon, Uriel Feige
2009	—	`conf`	PASS Approximation. APPROX-RANDOM Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh
2008	—	`conf`	A Preemptive Algorithm for Maximizing Disjoint Paths on Trees. SWAT Yossi Azar, Uriel Feige, Daniel Glasner
2008	A*	`conf`	A combinatorial allocation mechanism with penalties for banner advertising. WWW Uriel Feige, Nicole Immorlica, Vahab S. Mirrokni, Hamid Nazerzadeh
2008	J	`jnl`	Combination Can Be Hard: Approximability of the Unique Coverage Problem. SIAM J. Comput. Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour
2008	A	`conf`	Edge Coloring and Decompositions of Weighted Graphs. ESA Uriel Feige, Mohit Singh
2008	J	`jnl`	Finding a Maximum Independent Set in a Sparse Random Graph. SIAM J. Discret. Math. Uriel Feige, Eran Ofek
2008	J	`jnl`	Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee
2008	—	`conf`	On Estimation Algorithms vs Approximation Algorithms. FSTTCS Uriel Feige
2008	A*	`conf`	On allocations that maximize fairness. SODA Uriel Feige
2008	—	`conf`	Santa Claus Meets Hypergraph Matchings. APPROX-RANDOM Arash Asadpour, Uriel Feige, Amin Saberi
2008	A*	`conf`	Trust-based recommendation systems: an axiomatic approach. WWW Reid Andersen, Christian Borgs, Jennifer T. Chayes, Uriel Feige, Abraham D. Flaxman, Adam Kalai, Vahab S. Mirrokni, Moshe Tennenholtz
2007	J	`jnl`	An improved approximation ratio for the minimum linear arrangement problem. Inf. Process. Lett. Uriel Feige, James R. Lee
2007	J	`jnl`	Easily refutable subformulas of large random 3CNF formulas. Theory Comput. Uriel Feige, Eran Ofek
2007	—	`conf`	Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs. APPROX-RANDOM Uriel Feige, Mohit Singh
2007	A*	`conf`	Maximizing Non-Monotone Submodular Functions. FOCS Uriel Feige, Vahab S. Mirrokni, Jan Vondrák
2007	A*	`ed.`	Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007 STOC David S. Johnson, Uriel Feige
2007	A*	`conf`	Refuting Smoothed 3CNF Formulas. FOCS Uriel Feige
2007	B	`conf`	Robust Combinatorial Optimization with Exponential Scenarios. IPCO Uriel Feige, Kamal Jain, Mohammad Mahdian, Vahab S. Mirrokni
2007	A	`conf`	Understanding Parallel Repetition Requires Understanding Foams. CCC Uriel Feige, Guy Kindler, Ryan O'Donnell
2007	J	`jnl`	Understanding Parallel Repetition Requires Understanding Foams. Electron. Colloquium Comput. Complex. Uriel Feige, Guy Kindler, Ryan O'Donnell
2006	J	`jnl`	A Polylogarithmic Approximation of the Minimum Bisection. SIAM Rev. Robert Krauthgamer, Uriel Feige
2006	A*	`conf`	Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. FOCS Uriel Feige, Jan Vondrák
2006	A*	`conf`	Combination can be hard: approximability of the unique coverage problem. SODA Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour
2006	—	`conf`	Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems. APPROX-RANDOM Uriel Feige, Elchanan Mossel, Dan Vilenchik
2006	A*	`conf`	Finding small balanced separators. STOC Uriel Feige, Mohammad Mahdian
2006	J	`jnl`	On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph. SIAM J. Comput. Uriel Feige
2006	A*	`conf`	On maximizing welfare when utility functions are subadditive. STOC Uriel Feige
2006	J	`jnl`	On the hardness of approximating Max-Satisfy. Inf. Process. Lett. Uriel Feige, Daniel Reichman
2006	J	`jnl`	Random 3CNF formulas elude the Lovasz theta function CoRR Uriel Feige, Eran Ofek
2006	J	`jnl`	Random 3CNF formulas elude the Lovasz theta function. Electron. Colloquium Comput. Complex. Eran Ofek, Uriel Feige
2006	J	`jnl`	The RPR J. Algorithms Uriel Feige, Michael Langberg
2006	A*	`conf`	Witnesses for non-satisfiability of dense random 3CNF formulas. FOCS Uriel Feige, Jeong Han Kim, Eran Ofek
2005	—	`conf`	Approximating the Bandwidth of Caterpillars. APPROX-RANDOM Uriel Feige, Kunal Talwar
2005	J	`jnl`	Finding a Maximum Independent Set in a Sparse Random Graph Electron. Colloquium Comput. Complex. Uriel Feige, Eran Ofek
2005	—	`conf`	Finding a Maximum Independent Set in a Sparse Random Graph. APPROX-RANDOM Uriel Feige, Eran Ofek
2005	J	`jnl`	Genomic Variability within an Organism Exposes Its Cell Lineage Tree. PLoS Comput. Biol. Dan Frumkin, Adam Wasserstrom, Shai Kaplan, Uriel Feige, Ehud Shapiro
2005	A*	`conf`	Improved approximation algorithms for minimum-weight vertex separators. STOC Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee
2005	J	`jnl`	Improved approximation of the minimum cover time. Theor. Comput. Sci. Eden Chlamtac, Uriel Feige
2005	—	`conf`	On the Competitive Ratio of the Random Sampling Auction. WINE Uriel Feige, Abraham Flaxman, Jason D. Hartline, Robert D. Kleinberg
2005	A*	`conf`	Rigorous analysis of heuristics for NP-hard problems. SODA Uriel Feige
2005	J	`jnl`	Spectral techniques applied to sparse random graphs. Random Struct. Algorithms Uriel Feige, Eran Ofek
2004	J	`jnl`	Approximating Maximum Clique by Removing Subgraphs. SIAM J. Discret. Math. Uriel Feige
2004	J	`jnl`	Approximating Min Sum Set Cover. Algorithmica Uriel Feige, László Lovász, Prasad Tetali
2004	A*	`conf`	Easily Refutable Subformulas of Large Random 3CNF Formulas. ICALP Uriel Feige, Eran Ofek
2004	J	`jnl`	Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. SIAM J. Comput. Uriel Feige, Michael Langberg, Gideon Schechtman
2004	—	`conf`	On Systems of Linear Equations with Two Variables per Equation. APPROX-RANDOM Uriel Feige, Daniel Reichman
2004	J	`jnl`	On The Hardness of Approximating Max-Satisfy Electron. Colloquium Comput. Complex. Uriel Feige, Daniel Reichman
2004	A*	`conf`	On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. STOC Uriel Feige
2004	J	`jnl`	The inapproximability of lattice and coding problems with preprocessing. J. Comput. Syst. Sci. Uriel Feige, Daniele Micciancio
2003	J	`jnl`	Approximation thresholds for combinatorial optimization problems CoRR Uriel Feige
2003	J	`jnl`	Deterministic approximation of the cover time. Random Struct. Algorithms Uriel Feige, Yuri Rabinovich
2003	J	`jnl`	On Cutting a Few Vertices from a Graph. Discret. Appl. Math. Uriel Feige, Robert Krauthgamer, Kobbi Nissim
2003	J	`jnl`	On the complexity of finding balanced oneway cuts. Inf. Process. Lett. Uriel Feige, Orly Yahalom
2003	J	`jnl`	The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set. SIAM J. Comput. Uriel Feige, Robert Krauthgamer
2002	J	`jnl`	A Polylogarithmic Approximation of the Minimum Bisection. SIAM J. Comput. Uriel Feige, Robert Krauthgamer
2002	—	`conf`	Approximating Maximum Edge Coloring in Multigraphs. APPROX Uriel Feige, Eran Ofek, Udi Wieder
2002	—	`conf`	Approximating Min-sum Set Cover. APPROX Uriel Feige, László Lovász, Prasad Tetali
2002	J	`jnl`	Approximating the Domatic Number. SIAM J. Comput. Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz, Aravind Srinivasan
2002	J	`jnl`	Error Reduction by Parallel Repetition - A Negative Result. Comb. Uriel Feige, Oleg Verbitsky
2002	A*	`conf`	Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. FOCS Uriel Feige, Michael Langberg, Gideon Schechtman
2002	J	`jnl`	Improved Bounds for Acyclic Job Shop Scheduling. Comb. Uriel Feige, Christian Scheideler
2002	J	`jnl`	Improved approximation of Max-Cut on graphs of bounded degree. J. Algorithms Uriel Feige, Marek Karpinski, Michael Langberg
2002	J	`jnl`	On the drift of short schedules. Theor. Comput. Sci. Uriel Feige, Giora Rayzman
2002	J	`jnl`	On the optimality of the random hyperplane rounding technique for MAX CUT. Random Struct. Algorithms Uriel Feige, Gideon Schechtman
2002	A	`conf`	Relations between Average Case Complexity and Approximation Complexity. CCC Uriel Feige
2002	A*	`conf`	Relations between average case complexity and approximation complexity. STOC Uriel Feige
2002	A	`conf`	The Inapproximability of Lattice and Coding Problems with Preprocessing. CCC Uriel Feige, Daniele Micciancio
2001	J	`jnl`	A note on approximating Max-Bisection on regular graphs. Inf. Process. Lett. Uriel Feige, Marek Karpinski, Michael Langberg
2001	J	`jnl`	Approximation Algorithms for Maximization Problems Arising in Graph Partitioning. J. Algorithms Uriel Feige, Michael Langberg
2001	J	`jnl`	Heuristics for Semirandom Graph Problems. J. Comput. Syst. Sci. Uriel Feige, Joe Kilian
2001	A*	`conf`	On the integrality ratio of semidefinite relaxations of MAX CUT. STOC Uriel Feige, Gideon Schechtman
2001	J	`jnl`	The Dense Algorithmica Uriel Feige, Guy Kortsarz, David Peleg
2001	A*	`conf`	The RPR ICALP Uriel Feige, Michael Langberg
2000	J	`jnl`	A Note on Approximating MAX-BISECTION on Regular Graphs Electron. Colloquium Comput. Complex. Uriel Feige, Marek Karpinski, Michael Langberg
2000	A*	`conf`	A polylogarithmic approximation of the minimum bisection. FOCS Uriel Feige, Robert Krauthgamer
2000	J	`jnl`	Approximating the Bandwidth via Volume Respecting Embeddings. J. Comput. Syst. Sci. Uriel Feige
2000	A*	`conf`	Approximating the domatic number. STOC Uriel Feige, Magnús M. Halldórsson, Guy Kortsarz
2000	A*	`conf`	Approximating the minimum bisection size (extended abstract). STOC Uriel Feige, Robert Krauthgamer, Kobbi Nissim
2000	—	`conf`	Coping with the NP-Hardness of the Graph Bandwidth Problem. SWAT Uriel Feige
2000	J	`jnl`	Finding OR in a noisy broadcast network. Inf. Process. Lett. Uriel Feige, Joe Kilian
2000	J	`jnl`	Finding and certifying a large hidden clique in a semirandom graph. Random Struct. Algorithms Uriel Feige, Robert Krauthgamer
2000	J	`jnl`	Improved Approximation of MAX-CUT on Graphs of Bounded Degree Electron. Colloquium Comput. Complex. Uriel Feige, Marek Karpinski, Michael Langberg
2000	A*	`conf`	Min-Wise versus linear independence (extended abstract). SODA Andrei Z. Broder, Uriel Feige
2000	J	`jnl`	Networks on Which Hot-Potato Routing Does Not Livelock. Distributed Comput. Uriel Feige, Robert Krauthgamer
2000	J	`jnl`	On the cost of recomputing: Tight bounds on pebbling with faults. Theor. Comput. Sci. Yonatan Aumann, Judit Bar-Ilan, Uriel Feige
2000	—	`conf`	On the hardness of approximating APPROX Uriel Feige, Michael Langberg, Kobbi Nissim
2000	J	`jnl`	Two-Prover Protocols - Low Error at Affordable Rates. SIAM J. Comput. Uriel Feige, Joe Kilian
1999	J	`jnl`	Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions. SIAM J. Comput. Uriel Feige, Dror Lapidot, Adi Shamir
1999	A*	`conf`	Noncryptographic Selection Protocols. FOCS Uriel Feige
1999	A*	`conf`	Nonmonotonic Phenomena in Packet Routing. STOC Uriel Feige
1999	—	`conf`	Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example. RANDOM-APPROX Uriel Feige
1998	J	`jnl`	A Threshold of ln J. ACM Uriel Feige
1998	A*	`conf`	Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract). STOC Uriel Feige
1998	A*	`conf`	Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs. FOCS Uriel Feige, Joe Kilian
1998	A*	`conf`	Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract). STOC Uriel Feige, Christian Scheideler
1998	J	`jnl`	Zero Knowledge and the Chromatic Number. J. Comput. Syst. Sci. Uriel Feige, Joe Kilian
1997	J	`jnl`	A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity. J. Comput. Syst. Sci. Uriel Feige
1997	J	`jnl`	Collecting Coupons on Trees, and the Cover Time of Random Walks. Comput. Complex. Uriel Feige
1997	A*	`conf`	Making Games Short (Extended Abstract). STOC Uriel Feige, Joe Kilian
1997	J	`jnl`	On Limited versus Polynomial Nondeterminism. Chic. J. Theor. Comput. Sci. Uriel Feige, Joe Kilian
1997	C	`conf`	On the Drift of Short Schedules. CIAC Uriel Feige, Giora Rayzman
1997	J	`jnl`	On the Hardness of Computing the Permanent of Random Matrices. Comput. Complex. Uriel Feige, Carsten Lund
1997	J	`jnl`	Randomized Graph Products, Chromatic Numbers, and the Lovász vartheta-Funktion. Comb. Uriel Feige
1997	—	`conf`	Stereoscopic families of permutations, and their applications. ISTCS Uriel Feige, Robert Krauthgamer
1996	J	`jnl`	A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. Theor. Comput. Sci. Uriel Feige
1996	A*	`conf`	A Threshold of ln STOC Uriel Feige
1996	A*	`conf`	Adaptively Secure Multi-Party Computation. STOC Ran Canetti, Uriel Feige, Oded Goldreich, Moni Naor
1996	—	`conf`	Deterministic Approximation of the Cover Time. ISTCS Uriel Feige, Yuri Rabinovich
1996	A	`conf`	Error Reduction by Parallel Repetition - a Negative Result. CCC Uriel Feige, Oleg Verbitsky
1996	J	`jnl`	Interactive Proofs and the Hardness of Approximating Cliques. J. ACM Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
1996	J	`jnl`	Random Walks on Regular and Irregular Graphs. SIAM J. Discret. Math. Don Coppersmith, Uriel Feige, James B. Shearer
1996	J	`jnl`	Short Random Walks on Graphs. SIAM J. Discret. Math. Greg Barnes, Uriel Feige
1996	A	`conf`	Zero Knowledge and the Chromatic Number. CCC Uriel Feige, Joe Kilian
1995	J	`jnl`	A Tight Lower Bound on the Cover Time for Random Walks on Graphs. Random Struct. Algorithms Uriel Feige
1995	J	`jnl`	A Tight Upper Bound on the Cover Time for Random Walks on Graphs. Random Struct. Algorithms Uriel Feige
1995	—	`conf`	Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT. ISTCS Uriel Feige, Michel X. Goemans
1995	J	`jnl`	Derandomized Graph Products. Comput. Complex. Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
1995	A*	`conf`	Impossibility results for recycling random bits in two-prover proof systems. STOC Uriel Feige, Joe Kilian
1995	—	`conf`	Observations on Hot Potato Routing. ISTCS Uriel Feige
1995	—	`conf`	On the Role of Shared Randomness in Two Prover Proof Systems. ISTCS Mihir Bellare, Uriel Feige, Joe Kilian
1995	A*	`conf`	Randomized graph products, chromatic numbers, and Lovasz theta-function. STOC Uriel Feige
1994	A*	`conf`	A Fast Randomized LOGSPACE Algorithm for Graph Connectivity. ICALP Uriel Feige
1994	A*	`conf`	A minimal model for secure computation (extended abstract). STOC Uriel Feige, Joe Kilian, Moni Naor
1994	J	`jnl`	Computing with Noisy Information. SIAM J. Comput. Uriel Feige, Prabhakar Raghavan, David Peleg, Eli Upfal
1994	A*	`conf`	On the Cost of Recomputing: Tight Bounds on Pebbling with Faults. ICALP Yonatan Aumann, Judit Bar-Ilan, Uriel Feige
1994	A*	`conf`	Two prover protocols: low error at affordable rates. STOC Uriel Feige, Joe Kilian
1993	A*	`conf`	A Randomized Time-Space Tradeoff of \tildeO(m\tildeR) for USTCON FOCS Uriel Feige
1993	A*	`conf`	On Message Proof Systems with Known Space Verifiers. CRYPTO Yonatan Aumann, Uriel Feige
1993	A*	`conf`	Short random walks on graphs. STOC Greg Barnes, Uriel Feige
1992	A*	`conf`	Exact Analysis of Hot-Potato Routing (Extended Abstract) FOCS Uriel Feige, Prabhakar Raghavan
1992	A*	`conf`	Low Communication 2-Prover Zero-Knowledge Proofs for NP. CRYPTO Cynthia Dwork, Uriel Feige, Joe Kilian, Moni Naor, Shmuel Safra
1992	J	`jnl`	Multi-Oracle Interactive Protocols with Constant Space Verifiers. J. Comput. Syst. Sci. Uriel Feige, Adi Shamir
1992	J	`jnl`	On the Complexity of Finite Random Functions. Inf. Process. Lett. Uriel Feige
1992	A*	`conf`	On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract) STOC Uriel Feige, Carsten Lund
1992	A*	`conf`	Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract) STOC Uriel Feige, László Lovász
1991	A*	`conf`	Approximating Clique is Almost NP-Complete (Preliminary Version) FOCS Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy
1991	—	`conf`	On the Success Probability of the Two Provers in One-Round Proof Systems. SCT Uriel Feige
1990	A*	`conf`	Computing with Unreliable Information (Preliminary Version) STOC Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal
1990	A*	`conf`	Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract) FOCS Uriel Feige, Dror Lapidot, Adi Shamir
1990	—	`conf`	Randomized Broadcast in Networks. SIGAL International Symposium on Algorithms Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal
1990	J	`jnl`	Randomized Broadcast in Networks. Random Struct. Algorithms Uriel Feige, David Peleg, Prabhakar Raghavan, Eli Upfal
1990	A*	`conf`	Witness Indistinguishable and Witness Hiding Protocols STOC Uriel Feige, Adi Shamir
1989	—	`conf`	Multi-Oracle Interactive Protocols with Space Bounded Verifiers. SCT Uriel Feige, Adi Shamir
1989	—	`conf`	On Expected Polynomial Time Simulation of Zero Knowledge Protocols. Distributed Computing And Cryptography Uriel Feige, Adi Shamir
1989	A*	`conf`	Zero Knowledge Proofs of Knowledge in Two Rounds. CRYPTO Uriel Feige, Adi Shamir
1988	A*	`conf`	The Noisy Oracle Problem. CRYPTO Uriel Feige, Adi Shamir, Moshe Tennenholtz
1988	J	`jnl`	Zero-Knowledge Proofs of Identity. J. Cryptol. Uriel Feige, Amos Fiat, Adi Shamir
1987	A*	`conf`	Zero Knowledge Proofs of Identity STOC Uriel Feige, Amos Fiat, Adi Shamir