# Uriel Feige

According to our database1, Uriel Feige authored at least 177 papers between 1987 and 2019.

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

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

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

2018
Random Walks with the Minimum Degree Local Rule Have O(n2) Cover Time.
SIAM J. Comput., 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
Optimization with Uniform Size Queries.
Algorithmica, 2017

Approximate modularity revisited.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Random Walks with the Minimum Degree Local Rule Have O(N2) 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

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
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

Separation between Estimation and Approximation.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 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

A Unifying Hierarchy of Valuations with Complements and Substitutes.
Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, 2015

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

On fair division of a homogeneous good.
Games and Economic Behavior, 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

Chasing Ghosts: Competing with Stateful Policies.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

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

Welfare maximization and the supermodular degree.
Proceedings of the Innovations in Theoretical Computer Science, 2013

A Greedy Approximation Algorithm for Minimum-Gap Scheduling.
Proceedings of the Algorithms and Complexity, 8th International Conference, 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
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 k-CNF Formulas.
SIAM J. Discrete Math., 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

Recoverable Values for Independent Sets.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

Min-max Graph Partitioning and Small Set Expansion.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
The Submodular Welfare Problem with Demand Queries.
Theory of Computing, 2010

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

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

Detecting high log-densities: an O(n1/4) approximation for densest k-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 k-Player to 2-Player Approximate Nash Equilibrium.
Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

2009
Buffer management for colored packets with deadlines.
Proceedings of the SPAA 2009: Proceedings of the 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2009

On smoothed k-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
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

A Preemptive Algorithm for Maximizing Disjoint Paths on Trees.
Proceedings of the Algorithm Theory, 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

Santa Claus Meets Hypergraph Matchings.
Proceedings of the Approximation, 2008

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

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

Maximizing Non-Monotone Submodular Functions.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

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

Understanding Parallel Repetition Requires Understanding Foams.
Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 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 Review, 2006

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

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

Random 3CNF formulas elude the Lovasz theta function.
Electronic Colloquium on Computational Complexity (ECCC), 2006

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

On maximizing welfare when utility functions are subadditive.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Combination can be hard: approximability of the unique coverage problem.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

Complete Convergence of Message Passing Algorithms for Some Satisfiability Problems.
Proceedings of the Approximation, 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 Computational Biology, 2005

Finding a Maximum Independent Set in a Sparse Random Graph
Electronic Colloquium on Computational Complexity (ECCC), 2005

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

Improved approximation algorithms for minimum-weight vertex separators.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

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

Approximating the Bandwidth of Caterpillars.
Proceedings of the Approximation, 2005

Finding a Maximum Independent Set in a Sparse Random Graph.
Proceedings of the Approximation, 2005

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

On The Hardness of Approximating Max-Satisfy
Electronic Colloquium on Computational Complexity (ECCC), 2004

On sums of independent random variables with unbounded variance, and estimating the average degree in a graph.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Easily Refutable Subformulas of Large Random 3CNF Formulas.
Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 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

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

On Cutting a Few Vertices from a Graph.
Discrete Applied Mathematics, 2003

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

Improved approximation of Max-Cut on graphs of bounded degree.
J. Algorithms, 2002

Improved Bounds for Acyclic Job Shop Scheduling.
Combinatorica, 2002

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

Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

The Inapproximability of Lattice and Coding Problems with Preprocessing.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

Relations between Average Case Complexity and Approximation Complexity.
Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

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

Approximating Min-sum Set Cover.
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 k-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

The RPR2 Rounding Technique for Semidefinite Programs.
Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

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

A Note on Approximating MAX-BISECTION on Regular Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2000

Improved Approximation of MAX-CUT on Graphs of Bounded Degree
Electronic Colloquium on Computational Complexity (ECCC), 2000

Networks on Which Hot-Potato Routing Does Not Livelock.
Distributed Computing, 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

A polylogarithmic approximation of the minimum bisection.
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

On the hardness of approximating N P 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
A Threshold of ln n 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.
Combinatorica, 1997

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

On the Hardness of Computing the Permanent of Random Matrices.
Computational Complexity, 1997

Collecting Coupons on Trees, and the Cover Time of Random Walks.
Computational Complexity, 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

On the Drift of Short Schedules.
Proceedings of the Algorithms and Complexity, Third Italian Conference, 1997

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

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

A Threshold of ln n 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

Deterministic Approximation of the Cover Time.
Proceedings of the Fourth Israel Symposium on Theory of Computing and Systems, 1996

Error Reduction by Parallel Repetition - a Negative Result.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

Zero Knowledge and the Chromatic Number.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 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.
Computational Complexity, 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

Two prover protocols: low error at affordable rates.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

A Fast Randomized LOGSPACE Algorithm for Graph Connectivity.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

On the Cost of Recomputing: Tight Bounds on Pebbling with Faults.
Proceedings of the Automata, Languages and Programming, 21st International Colloquium, 1994

1993
Short random walks on graphs.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 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, Chicago, Illinois, USA, June 30, 1991

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

Proceedings of the Algorithms, 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. Cryptology, 1988

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

1987
Zero Knowledge Proofs of Identity
Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987