# Uriel Feige

According to our database1, Uriel Feige authored at least 194 papers between 1988 and 2021.

Collaborative distances:
• Dijkstra number2 of three.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2021
Navigating in Trees with Permanently Noisy Advice.
ACM Trans. Algorithms, 2021

A tight negative example for MMS fair allocations.
CoRR, 2021

Best-of-Both-Worlds Fair-Share Allocations.
CoRR, 2021

Are Gross Substitutes a Substitute for Submodular Valuations?
Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Fair-Share Allocations for Agents with Arbitrary Entitlements.
Proceedings of the EC '21: The 22nd ACM Conference on Economics and Computation, 2021

Fair and Truthful Mechanisms for Dichotomous Valuations.
Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, 2021

2020
On the Profile of Multiplicities of Complete Subgraphs.
SIAM J. Discret. Math., 2020

Approximate Modularity Revisited.
SIAM J. Comput., 2020

Finding cliques using few probes.
Random Struct. Algorithms, 2020

Quantitative Group Testing and the rank of random matrices.
CoRR, 2020

How to Hide a Clique?
Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Introduction to Semirandom Models.
Proceedings of the Beyond the Worst-Case Analysis of Algorithms, 2020

2019
On the path partition number of 6-regular graphs.
CoRR, 2019

Target Set Selection for Conservative Populations.
CoRR, 2019

A randomized strategy in the mirror game.
CoRR, 2019

A New Approach to Fair Distribution of Welfare.
Proceedings of the Web and Internet Economics - 15th International Conference, 2019

A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Max-min greedy matching.
Proceedings of the 14th Workshop on the Economics of Networks, Systems and Computation, 2019

2018
Random Walks with the Minimum Degree Local Rule Have O(n<sup>2)</sup> Cover Time.
SIAM J. Comput., 2018

Tighter bounds for online bipartite matching.
CoRR, 2018

The Ordered Covering Problem.
Algorithmica, 2018

On the Probe Complexity of Local Computation Algorithms.
Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Robust Inference for Multiclass Classification.
Proceedings of the Algorithmic Learning Theory, 2018

2017
Chasing Ghosts: Competing with Stateful Policies.
SIAM J. Comput., 2017

A greedy approximation algorithm for minimum-gap scheduling.
J. Sched., 2017

Optimization with Uniform Size Queries.
Algorithmica, 2017

Random Walks with the Minimum Degree Local Rule Have <i>O</i>(<i>N</i><sup>2</sup>) Cover Time.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016
On giant components and treewidth in the layers model.
Random Struct. Algorithms, 2016

Random walks with the minimum degree local rule have \$O(n^2)\$ cover time.
CoRR, 2016

Shotgun Assembly of Random Jigsaw Puzzles.
CoRR, 2016

On the effect of randomness on planted 3-coloring models.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Oblivious Rounding and the Integrality Gap.
Proceedings of the Approximation, 2016

2015
Recoverable values for independent sets.
Random Struct. Algorithms, 2015

Oblivious Algorithms for the Maximum Directed Cut Problem.
Algorithmica, 2015

Contagious Sets in Expanders.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Why are Images Smooth?
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Learning and inference in the presence of corrupted inputs.
Proceedings of The 28th Conference on Learning Theory, 2015

2014
Musical Chairs.
SIAM J. Discret. Math., 2014

Min-Max Graph Partitioning and Small Set Expansion.
SIAM J. Comput., 2014

On fair division of a homogeneous good.
Games Econ. Behav., 2014

Separation between Estimation and Approximation.
Electron. Colloquium Comput. Complex., 2014

A Unifying Hierarchy of Valuations with Complements and Substitutes.
Electron. Colloquium Comput. Complex., 2014

NP-hardness of hypercube 2-segmentation.
CoRR, 2014

On robustly asymmetric graphs.
CoRR, 2014

Short Tours through Large Linear Forests.
Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Invitation games and the price of stability.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Sequential decision making with vector outcomes.
Proceedings of the Innovations in Theoretical Computer Science, 2014

Demand Queries with Preprocessing.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

2013
Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.
Theory Comput., 2013

Welfare Maximization and the Supermodular Degree.
Electron. Colloquium Comput. Complex., 2013

PASS Approximation: A Framework for Analyzing and Designing Heuristics.
Algorithmica, 2013

Competition among asymmetric sellers with fixed supply.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Connectivity of Random High Dimensional Geometric Graphs.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

The Cascade Auction - A Mechanism for Deterring Collusion in Auctions.
Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

2012
Santa claus meets hypergraph matchings.
ACM Trans. Algorithms, 2012

Universal Factor Graphs.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Mastering multi-player games.
Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2012

2011
On the Diameter of the Set of Satisfying Assignments in Random Satisfiable <i>k</i>-CNF Formulas.
SIAM J. Discret. Math., 2011

Maximizing Non-monotone Submodular Functions.
SIAM J. Comput., 2011

Buffer Management for Colored Packets with Deadlines.
Theory Comput. Syst., 2011

Hardness results for approximating the bandwidth.
J. Comput. Syst. Sci., 2011

Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).
Dagstuhl Reports, 2011

Oblivious Collaboration.
Proceedings of the Distributed Computing - 25th International Symposium, 2011

An O(n log n) Algorithm for a Load Balancing Problem on Paths.
Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

Mechanism design with uncertain inputs: (to err is human, to forgive divine).
Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010
The Submodular Welfare Problem with Demand Queries.
Theory Comput., 2010

On Optimal Strategies for a Hat Game on Graphs.
SIAM J. Discret. Math., 2010

Balanced coloring of bipartite graphs.
J. Graph Theory, 2010

A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium
CoRR, 2010

Detecting High Log-Densities -- an O(n^1/4) Approximation for Densest k-Subgraph
CoRR, 2010

A Preemptive Algorithm for Maximizing Disjoint Paths on Trees.
Algorithmica, 2010

Detecting high log-densities: an <i>O</i>(<i>n</i><sup>1/4</sup>) approximation for densest <i>k</i>-subgraph.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Responsive Lotteries.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

A Direct Reduction from <i>k</i>-Player to 2-Player Approximate Nash Equilibrium.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

2009
On Maximizing Welfare When Utility Functions Are Subadditive.
SIAM J. Comput., 2009

Faster FAST(Feedback Arc Set in Tournaments)
CoRR, 2009

Deterministic approximation for the cover time of trees
CoRR, 2009

Interchanging distance and capacity in probabilistic mappings
CoRR, 2009

Approximating the Bandwidth of Caterpillars.
Algorithmica, 2009

On smoothed <i>k</i>-CNF formulas and the Walksat algorithm.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

On the power of two, three and four probes.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

PASS Approximation.
Proceedings of the Approximation, 2009

2008
Finding a Maximum Independent Set in a Sparse Random Graph.
SIAM J. Discret. Math., 2008

Improved Approximation Algorithms for Minimum Weight Vertex Separators.
SIAM J. Comput., 2008

Combination Can Be Hard: Approximability of the Unique Coverage Problem.
SIAM J. Comput., 2008

A combinatorial allocation mechanism with penalties for banner advertising.
Proceedings of the 17th International Conference on World Wide Web, 2008

Trust-based recommendation systems: an axiomatic approach.
Proceedings of the 17th International Conference on World Wide Web, 2008

On allocations that maximize fairness.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

On Estimation Algorithms vs Approximation Algorithms.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2008

Edge Coloring and Decompositions of Weighted Graphs.
Proceedings of the Algorithms, 2008

2007
Easily refutable subformulas of large random 3CNF formulas.
Theory Comput., 2007

An improved approximation ratio for the minimum linear arrangement problem.
Inf. Process. Lett., 2007

Understanding Parallel Repetition Requires Understanding Foams.
Electron. Colloquium Comput. Complex., 2007

Robust Combinatorial Optimization with Exponential Scenarios.
Proceedings of the Integer Programming and Combinatorial Optimization, 2007

Refuting Smoothed 3CNF Formulas.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Improved Approximation Ratios for Traveling Salesperson Tours and Paths in Directed Graphs.
Proceedings of the Approximation, 2007

2006
A Polylogarithmic Approximation of the Minimum Bisection.
SIAM Rev., 2006

On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph.
SIAM J. Comput., 2006

The RPR<sup>2</sup> rounding technique for semidefinite programs.
J. Algorithms, 2006

On the hardness of approximating Max-Satisfy.
Inf. Process. Lett., 2006

Random 3CNF formulas elude the Lovasz theta function.
Electron. Colloquium Comput. Complex., 2006

Finding small balanced separators.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

Witnesses for non-satisfiability of dense random 3CNF formulas.
Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005
Improved approximation of the minimum cover time.
Theor. Comput. Sci., 2005

Spectral techniques applied to sparse random graphs.
Random Struct. Algorithms, 2005

Genomic Variability within an Organism Exposes Its Cell Lineage Tree.
PLoS Comput. Biol., 2005

On the Competitive Ratio of the Random Sampling Auction.
Proceedings of the Internet and Network Economics, First International Workshop, 2005

Rigorous analysis of heuristics for NP-hard problems.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
Approximating Maximum Clique by Removing Subgraphs.
SIAM J. Discret. Math., 2004

Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.
SIAM J. Comput., 2004

The inapproximability of lattice and coding problems with preprocessing.
J. Comput. Syst. Sci., 2004

Approximating Min Sum Set Cover.
Algorithmica, 2004

On Systems of Linear Equations with Two Variables per Equation.
Proceedings of the Approximation, 2004

2003
The Probable Value of the Lovász--Schrijver Relaxations for Maximum Independent Set.
SIAM J. Comput., 2003

Deterministic approximation of the cover time.
Random Struct. Algorithms, 2003

On the complexity of finding balanced oneway cuts.
Inf. Process. Lett., 2003

On Cutting a Few Vertices from a Graph.
Discret. Appl. Math., 2003

Approximation thresholds for combinatorial optimization problems
CoRR, 2003

2002
On the drift of short schedules.
Theor. Comput. Sci., 2002

Approximating the Domatic Number.
SIAM J. Comput., 2002

On the optimality of the random hyperplane rounding technique for MAX CUT.
Random Struct. Algorithms, 2002

Error Reduction by Parallel Repetition - A Negative Result.
Comb., 2002

Improved Bounds for Acyclic Job Shop Scheduling.
Comb., 2002

Relations between average case complexity and approximation complexity.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Approximating Maximum Edge Coloring in Multigraphs.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001
Heuristics for Semirandom Graph Problems.
J. Comput. Syst. Sci., 2001

Approximation Algorithms for Maximization Problems Arising in Graph Partitioning.
J. Algorithms, 2001

A note on approximating Max-Bisection on regular graphs.
Inf. Process. Lett., 2001

The Dense <i>k</i>-Subgraph Problem.
Algorithmica, 2001

On the integrality ratio of semidefinite relaxations of MAX CUT.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

2000
On the cost of recomputing: Tight bounds on pebbling with faults.
Theor. Comput. Sci., 2000

Two-Prover Protocols - Low Error at Affordable Rates.
SIAM J. Comput., 2000

Finding and certifying a large hidden clique in a semirandom graph.
Random Struct. Algorithms, 2000

Approximating the Bandwidth via Volume Respecting Embeddings.
J. Comput. Syst. Sci., 2000

Finding OR in a noisy broadcast network.
Inf. Process. Lett., 2000

Improved Approximation of MAX-CUT on Graphs of Bounded Degree
Electron. Colloquium Comput. Complex., 2000

Networks on Which Hot-Potato Routing Does Not Livelock.
Distributed Comput., 2000

Coping with the NP-Hardness of the Graph Bandwidth Problem.
Proceedings of the Algorithm Theory, 2000

Approximating the minimum bisection size (extended abstract).
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Approximating the domatic number.
Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Min-Wise versus linear independence (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

On the hardness of approximating <i>N P</i> witnesses.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions.
SIAM J. Comput., 1999

Nonmonotonic Phenomena in Packet Routing.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Randomized Rounding for Semidefinite Programs-Variations on the MAX CUT Example.
Proceedings of the Randomization, 1999

Noncryptographic Selection Protocols.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
Zero Knowledge and the Chromatic Number.
J. Comput. Syst. Sci., 1998

A Threshold of ln <i>n</i> for Approximating Set Cover.
J. ACM, 1998

Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract).
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997
A Spectrum of Time-Space Trade-Offs for Undirected s-t Connectivity.
J. Comput. Syst. Sci., 1997

Randomized Graph Products, Chromatic Numbers, and the Lovász vartheta-Funktion.
Comb., 1997

On Limited versus Polynomial Nondeterminism.
Chic. J. Theor. Comput. Sci., 1997

On the Hardness of Computing the Permanent of Random Matrices.
Comput. Complex., 1997

Collecting Coupons on Trees, and the Cover Time of Random Walks.
Comput. Complex., 1997

Making Games Short (Extended Abstract).
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Stereoscopic families of permutations, and their applications.
Proceedings of the Fifth Israel Symposium on Theory of Computing and Systems, 1997

1996
A Fast Randomized LOGSPACE Algorithm for Graph Connectivity.
Theor. Comput. Sci., 1996

Random Walks on Regular and Irregular Graphs.
SIAM J. Discret. Math., 1996

Short Random Walks on Graphs.
SIAM J. Discret. Math., 1996

Interactive Proofs and the Hardness of Approximating Cliques.
J. ACM, 1996

A Threshold of ln <i>n</i> for Approximating Set Cover (Preliminary Version).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995
A Tight Lower Bound on the Cover Time for Random Walks on Graphs.
Random Struct. Algorithms, 1995

A Tight Upper Bound on the Cover Time for Random Walks on Graphs.
Random Struct. Algorithms, 1995

Derandomized Graph Products.
Comput. Complex., 1995

Impossibility results for recycling random bits in two-prover proof systems.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Randomized graph products, chromatic numbers, and Lovasz theta-function.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Aproximating the Value of Two Prover Proof Systems, With Applications to MAX 2SAT and MAX DICUT.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

Observations on Hot Potato Routing.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

On the Role of Shared Randomness in Two Prover Proof Systems.
Proceedings of the Third Israel Symposium on Theory of Computing and Systems, 1995

1994
Computing with Noisy Information.
SIAM J. Comput., 1994

A minimal model for secure computation (extended abstract).
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993
A Randomized Time-Space Tradeoff of \tildeO(m\tildeR) for USTCON
Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

On Message Proof Systems with Known Space Verifiers.
Proceedings of the Advances in Cryptology, 1993

1992
Multi-Oracle Interactive Protocols with Constant Space Verifiers.
J. Comput. Syst. Sci., 1992

On the Complexity of Finite Random Functions.
Inf. Process. Lett., 1992

Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

On the Hardness of Computing the Permanent of Random Matrices (Extended Abstract)
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Exact Analysis of Hot-Potato Routing (Extended Abstract)
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Low Communication 2-Prover Zero-Knowledge Proofs for NP.
Proceedings of the Advances in Cryptology, 1992

1991
Approximating Clique is Almost NP-Complete (Preliminary Version)
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

On the Success Probability of the Two Provers in One-Round Proof Systems.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991

1990
Random Struct. Algorithms, 1990

Witness Indistinguishable and Witness Hiding Protocols
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Computing with Unreliable Information (Preliminary Version)
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract)
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989
On Expected Polynomial Time Simulation of Zero Knowledge Protocols.
Proceedings of the Distributed Computing And Cryptography, 1989

Zero Knowledge Proofs of Knowledge in Two Rounds.
Proceedings of the Advances in Cryptology, 1989

Multi-Oracle Interactive Protocols with Space Bounded Verifiers.
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988
Zero-Knowledge Proofs of Identity.
J. Cryptol., 1988

The Noisy Oracle Problem.
Proceedings of the Advances in Cryptology, 1988