Arrow Research search

Author name cluster

Uriel Feige

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

60 papers
2 author rows

Possible papers

60

STOC Conference 2025 Conference Paper

Share-Based Fairness for Arbitrary Entitlements

  • Moshe Babaioff
  • Uriel Feige

We consider the problem of fair allocation of indivisible items to agents that have arbitrary entitlements to the items. Every agent i has a valuation function v i and an entitlement b i , where the entitlements sum up to 1. Which allocation should one choose in situations in which agents fail to agree on one acceptable fairness notion? We study this problem in the case in which each agent focuses on the value she gets, and fairness notions are restricted to be share based . A share s is a function that maps every ( v i , b i ) to a value s ( v i , b i ), representing the minimal value i should get, and s is feasible if it is always possible to give every agent i value of at least s ( v i , b i ). Our main result is that for additive valuations over goods, there is an allocation that gives every agent at least half her share value, regardless of which feasible share-based fairness notion the agent wishes to use. Moreover, the ratio of half is best possible. More generally, we provide tight characterizations of what can be achieved, both ex-post (as single allocations) and ex-ante (as expected values of distributions of allocations), both for goods and for chores. We also show that for chores one can achieve the ex-ante and ex-post guarantees simultaneously (a “best of both world” result), whereas for goods one cannot.

Details

AAAI Conference 2021 Conference Paper

Fair and Truthful Mechanisms for Dichotomous Valuations

  • Moshe Babaioff
  • Tomer Ezra
  • Uriel Feige

We consider the problem of allocating a set on indivisible items to players with private preferences in an efficient and fair way. We focus on valuations that have dichotomous marginals, in which the added value of any item to a set is either 0 or 1, and aim to design truthful allocation mechanisms (without money) that maximize welfare and are fair. For the case that players have submodular valuations with dichotomous marginals, we design such a deterministic truthful allocation mechanism. The allocation output by our mechanism is Lorenz dominating, and consequently satisfies many desired fairness properties, such as being envy-free up to any item (EFX), and maximizing the Nash Social Welfare (NSW). We then show that our mechanism with random priorities is envy-free ex-ante, while having all the above properties expost. Furthermore, we present several impossibility results precluding similar results for the larger class of XOS valuations.

PDF Details

SODA Conference 2019 Conference Paper

A Polynomial Time Constant Approximation For Minimizing Total Weighted Flow-time

  • Uriel Feige
  • Janardhan Kulkarni
  • Shi Li 0001

We consider the classic scheduling problem of minimizing the total weighted flow-time on a single machine (min-WPFT), when preemption is allowed. In this problem, we are given a set of n jobs, each job having a release time r j, a processing time p j, and a weight w j. The flow-time of a job is defined as the amount of time the job spends in the system before it completes; that is, F j = C j – r j, where C j is the completion time of job. The objective is to minimize the total weighted flow-time of jobs. This NP-hard problem has been studied quite extensively for decades. In a recent breakthrough, Batra, Garg, and Kumar [6] presented a pseudo-polynomial time algorithm that has an O (1) approximation ratio. The design of a truly polynomial time algorithm, however, remained an open problem. In this paper, we show a transformation from pseudo-polynomial time algorithms to polynomial time algorithms in the context of min-WPFT. Our result combined with the result of Batra, Garg, and Kumar [6] settles the long standing conjecture that there is a polynomial time algorithm with O (1)-approximation for min-WPFT.

Details

STOC Conference 2017 Conference Paper

Approximate modularity revisited

  • Uriel Feige
  • Michal Feldman
  • Inbal Talgam-Cohen

Set functions with convenient properties (such as submodularity) appear in application areas of current interest, such as algorithmic game theory, and allow for improved optimization algorithms. It is natural to ask (e.g., in the context of data driven optimization) how robust such properties are, and whether small deviations from them can be tolerated. We consider two such questions in the important special case of linear set functions. One question that we address is whether any set function that approximately satisfies the modularity equation (linear functions satisfy the modularity equation exactly) is close to a linear function. The answer to this is positive (in a precise formal sense) as shown by Kalton and Roberts [1983] (and further improved by Bondarenko, Prymak, and Radchenko [2013]). We revisit their proof idea that is based on expander graphs, and provide significantly stronger upper bounds by combining it with new techniques. Furthermore, we provide improved lower bounds for this problem. Another question that we address is that of how to learn a linear function h that is close to an approximately linear function f , while querying the value of f on only a small number of sets. We present a deterministic algorithm that makes only linearly many (in the number of items) nonadaptive queries, by this improving over a previous algorithm of Chierichetti, Das, Dasgupta and Kumar [2015] that is randomized and makes more than a quadratic number of queries. Our learning algorithm is based on a Hadamard transform.

Details

STOC Conference 2016 Conference Paper

On the effect of randomness on planted 3-coloring models

  • Roee David
  • Uriel Feige

We present the hosted coloring framework for studying al- gorithmic and hardness results for the k-coloring problem. There is a class H of host graphs. One selects a graph H ∈ H and plants in it a balanced k-coloring (by partitioning the vertex set into k roughly equal parts, and removing all edges within each part). The resulting graph G is given as input to a polynomial time algorithm that needs to k-color G (any legal k-coloring would do – the algorithm is not required to recover the planted k-coloring). Earlier planted models correspond to the case that H is the class of all n-vertex d-regular graphs, a member H ∈ H is chosen at random, and then a balanced k-coloring is planted at random. Blum and Spencer [1995] designed algorithms for this model when d = n δ (for 0 < δ ≤ 1), and Alon and Kahale [1997] managed to do so even when d is a sufficiently large constant. The new aspect in our framework is that it need not in- volve randomness. In one model within the framework (with k = 3) H is a d regular spectral expander (meaning that ex- cept for the largest eigenvalue of its adjacency matrix, every other eigenvalue has absolute value much smaller than d) chosen by an adversary, and the planted 3-coloring is ran- dom. We show that the 3-coloring algorithm of Alon and Kahale [1997] can be modified to apply to this case. In an- other model H is a random d-regular graph but the planted balanced 3-coloring is chosen by an adversary, after seeing H. We show that for a certain range of average degrees somewhat below √ n, finding a 3-coloring is NP-hard. To- gether these results (and other results that we have) help clarify which aspects of randomness in the planted coloring model are the key to successful 3-coloring algorithms.

Details

AAAI Conference 2015 Conference Paper

A Unifying Hierarchy of Valuations with Complements and Substitutes

  • Uriel Feige
  • Michal Feldman
  • Nicole Immorlica
  • Rani Izsak
  • Brendan Lucier
  • Vasilis Syrgkanis

We introduce a new hierarchy over monotone set functions, that we refer to as MPH (Maximum over Positive Hypergraphs). Levels of the hierarchy correspond to the degree of complementarity in a given function. The highest level of the hierarchy, MPH-m (where m is the total number of items) captures all monotone functions. The lowest level, MPH-1, captures all monotone submodular functions, and more generally, the class of functions known as XOS. Every monotone function that has a positive hypergraph representation of rank k (in the sense defined by Abraham, Babaioff, Dughmi and Roughgarden [EC 2012]) is in MPH-k. Every monotone function that has supermodular degree k (in the sense defined by Feige and Izsak [ITCS 2013]) is in MPH-(k+1). In both cases, the converse direction does not hold, even in an approximate sense. We present additional results that demonstrate the expressiveness power of MPH-k. One can obtain good approximation ratios for some natural optimization problems, provided that functions are required to lie in low levels of the MPH hierarchy. We present two such applications. One shows that the maximum welfare problem can be approximated within a ratio of k + 1 if all players hold valuation functions in MPH-k. The other is an upper bound of 2k on the price of anarchy of simultaneous first price auctions.

PDF Details

SODA Conference 2015 Conference Paper

Contagious Sets in Expanders

  • Amin Coja-Oghlan
  • Uriel Feige
  • Michael Krivelevich
  • Daniel Reichman 0001

We consider the following activation process in undirected graphs: a vertex is active either if it belongs to a set of initially activated vertices or if at some point it has at least r active neighbors, where r > 1 is the activation threshold. A contagious set is a set whose activation results with the entire graph being active. Given a graph G, let m ( G, r ) be the minimal size of a contagious set. It is known that for every d -regular or nearly d -regular graph on n vertices, . We consider such graphs that additionally have expansion properties, parameterized by the spectral gap and/or the girth of the graphs. The general flavor of our results is that sufficiently strong expansion properties imply that (and more generally, . In addition, we demonstrate that rather weak assumptions on the girth and/or the spectral gap suffice in order to imply that. For example, we show this for graphs of girth at least 7, and for graphs with λ( G ) < (1 − ε ) d, provided the graph has no 4-cycles. Our results are algorithmic, entailing simple and effcient algorithms for selecting contagious sets.

Details

FOCS Conference 2014 Conference Paper

Chasing Ghosts: Competing with Stateful Policies

  • Uriel Feige
  • Tomer Koren
  • Moshe Tennenholtz

We consider sequential decision making in a setting where regret is measured with respect to a set of stateful reference policies, and feedback is limited to observing the rewards of the actions performed (the so called “bandit” setting). If either the reference policies are stateless rather than stateful, or the feedback includes the rewards of all actions (the so called “expert” setting), previous work shows that the √ optimal regret grows like Θ(√T) in terms of the number of decision rounds T. The difficulty in our setting is that the decision maker unavoidably loses track of the internal states of the reference policies, and thus cannot reliably attribute rewards observed in a certain round to any of the reference policies. In fact, in this setting it is impossible for the algorithm to estimate which policy gives the highest (or even approximately highest) total reward. Nevertheless, we design an algorithm that achieves expected regret that is sublinear in T, of the form O(T/ log 1/4 T). Our algorithm is based on a certain local repetition lemma that may be of independent interest. We also show that no algorithm can guarantee expected regret better than O(T/ log 3/2 T).

Details

AAAI Conference 2013 Conference Paper

The Cascade Auction — A Mechanism for Deterring Collusion in Auctions

  • Uriel Feige
  • Gil Kalai
  • Moshe Tennenholz

We introduce a sealed bid auction of a single item in which the winner is chosen at random among the highest k bidders according to a fixed probability distribution, and the price for the chosen winner is the Vickrey-Clarke-Groves price. We call such an auction a cascade auction. Our analysis suggests that this type of auction may give higher revenues compared to second price auction in cases of collusion.

PDF Details

AAMAS Conference 2012 Conference Paper

Mastering multi-player games

  • Yossi Azar
  • Uriel Feige
  • Michal Feldman
  • Moshe Tennenholtz

We consider multi-player games, and the guarantees that a master player that plays on behalf of a set of players can offer them, without making any assumptions on the rationality of the other players. Our model consists of an $(n+1)$-player game, with $m$ strategies per player, in which a \emph{master} player $M$ forms a coalition with nontransferable utilities among $n$ players, and the remaining player is called the {\em independent} player. Existentially, it is shown that every game admits a \emph{product-minimax-safe} strategy for $M$ -- a strategy that guarantees for every player in $M$'s coalition an expected value of at least her \emph{product minimax value} (which is at least as high as her minimax value and is often higher). Algorithmically, for any given vector of values for the players, one can decide in polytime whether it can be ensured by $M$, and if so, compute a mixed strategy that guarantees it. In symmetric games, a product minimax strategy for $M$ can be computed efficiently, even without being given the safety vector. We also consider the performance guarantees that $M$ can offer his players in repeated settings. Our main result here is the extension of the oblivious setting of Feldman, Kalai and Tennenholtz, showing that in every symmetric game, a master player who never observes a single payoff can guarantee for each of its players a {\em similar} performance to that of the independent player, even if the latter gets to choose the payoff matrix after the fact.

PDF

FOCS Conference 2011 Conference Paper

Min-max Graph Partitioning and Small Set Expansion

  • Nikhil Bansal 0001
  • Uriel Feige
  • Robert Krauthgamer
  • Konstantin Makarychev
  • Viswanath Nagarajan
  • Joseph Naor
  • Roy Schwartz 0002

We study graph partitioning problems from a min-max perspective, in which an input graph on n vertices should be partitioned into k parts, and the objective is to minimize the maximum number of edges leaving a single part. The two main versions we consider are: (i) the k parts need to be of equal size, and (ii) the parts must separate a set of k given terminals. We consider a common generalization of these two problems, and design for it an O(√log n log k)-approximation algorithm. This improves over an O(log 2 n) approximation for the second version due to Svitkina and Tardos, and roughly O(k log n) approximation for the first version that follows from other previous work. We also give an improved O(1)-approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the Small Set Expansion problem. In this problem, we are given a graph G and the goal is to find a non-empty subset S of V of size at most pn with minimum edge-expansion. We give an O(√log n log (1/p)) bicriteria approximation algorithm for the general case of Small Set Expansion and O(1) approximation algorithm for graphs that exclude any fixed minor.

Details

STOC Conference 2010 Conference Paper

Detecting high log-densities: an O ( n 1/4 ) approximation for densest k -subgraph

  • Aditya Bhaskara
  • Moses Charikar
  • Eden Chlamtac
  • Uriel Feige
  • Aravindan Vijayaraghavan

In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of n 1/3 - c for some fixed c>0 (later estimated at around c= 1/90). We present an algorithm that for every ε> 0 approximates the Densest k-Subgraph problem within a ratio of n ¼ + ε in time n O(1/ε) . If allowed to run for time n O(log n) , the algorithm achieves an approximation ratio of O(n ¼ ). Our algorithm is inspired by studying an average-case version of the problem where the goal is to distinguish random graphs from random graphs with planted dense subgraphs -- the approximation ratio we achieve for the general case matches the "distinguishing ratio" we obtain for this planted problem. At a high level, our algorithms involve cleverly counting appropriately defined trees of constant size in G, and using these counts to identify the vertices of the dense subgraph. We say that a graph G(V,E) has log-density α if its average degree is Θ(|V| α ). The algorithmic core of our result is a procedure to output a k-subgraph of 'nontrivial' density whenever the log-density of the densest k-subgraph is larger than the log-density of the host graph. We outline an extension to our approximation algorithm which achieves an O(n ¼ -ε )-approximation in O(2 n O(ε) ) time. We also show that, for certain parameter ranges, eigenvalue and SDP based techniques can outperform our basic distinguishing algorithm for random instances (in polynomial time), though without improving upon the O(n ¼ ) guarantee overall.

Details

SODA Conference 2009 Conference Paper

On smoothed k -CNF formulas and the Walksat algorithm

  • Amin Coja-Oghlan
  • Uriel Feige
  • Alan M. Frieze
  • Michael Krivelevich
  • Dan Vilenchik

In this paper we study the model of ∊ -smoothed k -CNF formulas. Starting from an arbitrary instance F with n variables and m = dn clauses, apply the ∊ -smoothing operation of flipping the polarity of every literal in every clause independently at random with probability ∊. Keeping ∊ and k fixed, and letting the density d = m / n grow, it is rather easy to see that for d ≥ ∊ −- k ln 2, F becomes whp unsatisfiable after smoothing. We show that a lower density that behaves roughly like ∊ −- k +1 suffices for this purpose. We also show that our bound on d is nearly best possible in the sense that there are k -CNF formulas F of slightly lower density that whp remain satisfiable after smoothing. One consequence of our proof is a new lower bound of Ω(2 k / k 2 ) on the density up to which Walksat solves random k -CNFs in polynomial time whp. We are not aware of any previous rigorous analysis showing that Walksat is successful at densities that are increasing as a function of k.

Details

FOCS Conference 2007 Conference Paper

Maximizing Non-Monotone Submodular Functions

  • Uriel Feige
  • Vahab Mirrokni
  • Jan Vondrák

Submodular maximization generalizes many important problems including Max Cut in directed/undirected graphs and hypergraphs, certain constraint satisfaction problems and maximum facility location problems. Unlike the problem of minimizing submodular functions, the problem of maximizing submodular functions is NP-hard.

Details

FOCS Conference 2007 Conference Paper

Refuting Smoothed 3CNF Formulas

  • Uriel Feige

We introduce the following model for generating. semi-random 3CNF formulas. First, an adversary is allowed to pick an arbitrary formula with n varialdes and in clauses. Then, the formula is slightly perturbed at random. Namely, the smoothing operation leaves the variables of the formula unchanged, but flips the polarity of every variable occurrence in the formula independently with probability a. If the density m/n of a 3CNF formula exceeds a certain threshold value (say, 5epsiv -3 ) then the smoothing operation almost surely results in a non-satisfiable formula. We present a randomized polynomial time refutation algorithm that for every sufficiently dense 3CNF formula manages to refute most of its smoothed instantiations. The density requirement for our refutation algorithm is roughly epsiv -2 radic(n log log n), which almost matches the density Omega( radicn) required bv known algorithms for refuting 3CNF formulas that are completely random.

Details

FOCS Conference 2006 Conference Paper

Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e

  • Uriel Feige
  • Jan Vondrák

Combinatorial allocation problems require allocating items to players in a way that maximizes the total utility. Two such problems received attention recently, and were addressed using the same linear programming (LP) relaxation. In the maximum submodular welfare (SMW) problem, utility functions of players are submodular, and for this case Dobzinski and Schapira [SODA 2006] showed an approximation ratio of 1 - 1/e. In the generalized assignment problem (GAP) utility functions are linear but players also have capacity constraints. GAP admits a (1 - 1/e)-approximation as well, as shown by Fleischer, Goemans, Mirrokni and Sviridenko [SODA 2006]. In both cases, the approximation ratio was in fact shown for a more general version of the problem, for which improving 1 - 1/e is NP-hard. In this paper, we show how to improve the 1 - 1/e approximation ratio, both for SMW and for GAP. A common theme in both improvements is the use of a new and optimal fair contention resolution technique. However, each of the improvements involves a different rounding procedure for the above mentioned LP. In addition, we prove APX-hardness results for SMW (such results were known for GAP). An important feature of our hardness results is that they apply even in very restricted settings, e. g. when every player has nonzero utility only for a constant number of items

Details

STOC Conference 2006 Conference Paper

Finding small balanced separators

  • Uriel Feige
  • Mohammad Mahdian

Let G be an n-vertex graph that has a vertex separator of size k that partitions the graph into connected components of size smaller than α n, for some fixed 2/3 ≤ α < 1. Such a separator is called an α-separator. Finding an α-separator of size at most k is NP-hard. Moreover, under reasonable complexity theoretic assumptions, it is shown that this problem is not polynomially solvable even when k=O(log n). In this paper, we give a randomized algorithm that finds an α-separator of size k in the given graph, unless the graph contains an (α+ε)-separator of size strictly less than k, in which case our algorithm finds one such separator. For fixed ε, the running time of our algorithm is n O(1) 2 O(k) , which is polynomial for k = O(log n). For bounded degree graphs (as well as for the case of finding balanced edge separators), we present a deterministic algorithm with similar running time.Our algorithm involves (among other things) a new concept that we call (ε,k)-samples. This is related to the notion of detection sets for network failures, introduced by Kleinberg [FOCS 2000]. Our proofs adapt and simplify techniques that were introduced by Kleinberg. As a by-product, our proof improves the known bounds on the size of detection sets. We also show applications of (ε,k)-samples to problems in approximation algorithms and rigorous analysis of heuristics.

Details

STOC Conference 2006 Conference Paper

On maximizing welfare when utility functions are subadditive

  • Uriel Feige

We consider the problem of maximizing welfare when allocating m items to n players with subadditive utility functions. Our main result is a way of rounding any fractional solution to a linear programming relaxation to this problem so as to give a feasible solution of welfare at least half that of the value of the fractional solution. This approximation ratio of 1/2 improves over an Ω(1/log m) ratio of Dobzinski, Nisan and Schapira [STOC 2005]. We also show an approximation ratio of 1 - 1/e when utility functions are fractionally subadditive. A result similar to this last result was previously obtained by Dobzinski and Schapira [Soda 2006], but via a different rounding technique that requires the use of a so called "XOS oracle".The randomized rounding techniques that we use are oblivious in the sense that they only use the primal solution to the linear program relaxation, but have no access to the actual utility functions of the players. This allows us to suggest new incentive compatible mechanisms for combinatorial auctions, extending previous work of Lavi and Swamy [FOCS 2005].

Details

FOCS Conference 2006 Conference Paper

Witnesses for non-satisfiability of dense random 3CNF formulas

  • Uriel Feige
  • Jeong Han Kim
  • Eran Ofek

We consider random 3CNF formulas with n variables and m clauses. It is well known that when m > cn (for a sufficiently large constant c), most formulas are not satisfiable. However, it is not known whether such formulas are likely to have polynomial size witnesses that certify that they are not satisfiable. A value of m sime n 3/2 was the forefront of our knowledge in this respect. When m > cn 3/2, such witnesses are known to exist, based on spectral techniques. When m 3/2-epsi, it is known that resolution (which is a common approach for refutation) cannot produce witnesses of size smaller than 2 nepsiv. Likewise, it is known that certain variants of the spectral techniques do not work in this range. In the current paper we show that when m > cn 7/5, almost all 3CNF formulas have polynomial size witnesses for non-satisfiability. We also show that such a witness can be found in time 2(O(n0. 2 log n)), whenever it exists. Our approach is based on an extension of the known spectral techniques, and involves analyzing a certain fractional packing problem for random 3-uniform hypergraphs

Details

STOC Conference 2005 Conference Paper

Improved approximation algorithms for minimum-weight vertex separators

  • Uriel Feige
  • MohammadTaghi Hajiaghayi
  • James R. Lee

We develop the algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into L 1 (and even Euclidean embeddings) are insufficient, but that the additional structure provided by many embedding theorems does suffice for our purposes.We obtain an O(√log n) approximation for min-ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be Θ(√log n). We also prove various approximate max-flow/min-vertex-cut theorems, which in particular give a constant-factor approximation for min-ratio vertex cuts in any excluded-minor family of graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best-known ratio was O(log n).These results have a number of applications. We exhibit an O(√log n) pseudo-approximation for finding balanced vertex separators in general graphs. In fact, we achieve an approximation ratio of O(√log opt) where opt is the size of an optimal separator, improving over the previous best bound of O(log opt). Likewise, we obtain improved approximation ratios for treewidth: In any graph of treewidth k, we show how to find a tree decomposition of width at most O(k √log k), whereas previous algorithms yielded O(k log k). For graphs excluding a fixed graph as a minor (which includes, e.g., bounded genus graphs), we give a constant-factor approximation for the treewidth; this can be used to obtain the first polynomial-time approximation schemes for problems like minimum feedback vertex set and minimum connected dominating set in such graphs.

Details

TCS Journal 2005 Journal Article

Improved approximation of the minimum cover time

  • Eden Chlamtac
  • Uriel Feige

Feige and Rabinovich, in [Feige and Rabinovich, Rand. Struct. Algorithms 23(1) (2003) 1–22], gave a deterministic O ( log 4 n ) approximation for the time it takes a random walk to cover a given graph starting at a given vertex. This approximation algorithm was shown to work for arbitrary reversible Markov chains. We build on the results of [Feige and Rabinovich, Rand. Struct. Algorithms 23(1) (2003) 1–22], and show that the original algorithm gives a O ( log 2 n ) approximation as it is, and that it can be modified to give a O ( log n ( log log n ) 2 ) approximation. Moreover, we show that given any c ( n ) -approximation algorithm for the maximum cover time (maximized over all initial vertices) of a reversible Markov chain, we can give a corresponding algorithm for the general cover time (of a random walk or reversible Markov chain) with approximation ratio O ( c ( n ) log n ).

Details DOI

FOCS Conference 2002 Conference Paper

Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers

  • Uriel Feige
  • Michael Langberg
  • Gideon Schechtman

Karger Motwani and Sudan (1998) introduced the notion of a vector coloring of a graph. In particular they show that every k-colorable graph is also vector k-colorable, and that for constant k, graphs that are vector k-colorable can be colored by roughly /spl Delta//sup 1-2/k/ colors. Here /spl Delta/ is the maximum degree in the graph. Their results play a major role in the best approximation algorithms for coloring and for maximal independent set. We show that for every positive integer k there are graphs that are vector k-colorable but do not have independent sets significantly larger than n//spl Delta//sup 1-2/k/ (and hence cannot be colored with significantly less that /spl Delta//sup 1-2/k/ colors). For k = O(log n/log log n) we show vector k-colorable graphs that do not have independent sets of size (log n)/sup c/, for some constant c. This shows that the vector chromatic number does not approximate the chromatic number within factors better than n/polylogn. As part of our proof, we analyze "property testing" algorithms that distinguish between graphs that have an independent set of size n/k, and graphs that are "far" from having such an independent set. Our bounds on the sample size improve previous bounds of Goldreich, Goldwasser and Ron (1998) for this problem.

Details

TCS Journal 2002 Journal Article

On the drift of short schedules

  • Uriel Feige
  • Giora Rayzman

For the job shop scheduling problem, the drift of a schedule is the maximum difference between the number of operations performed by two jobs within a time interval. We show instances of the problem for which every short schedule must allow for nonconstant drift.

Details DOI

STOC Conference 2002 Conference Paper

Relations between average case complexity and approximation complexity

  • Uriel Feige

We investigate relations between average case complexity and the complexity of approximation. Our preliminary findings indicate that this is a research direction that leads to interesting insights. Under the assumption that refuting 3SAT is hard on average on a natural distribution, we derive hardness of approximation results for min bisection, dense k -subgraph, max bipartite clique and the 2-catalog segmentation problem. No NP-hardness of approximation results are currently known for these problems.

Details

STOC Conference 2001 Conference Paper

On the integrality ratio of semidefinite relaxations of MAX CUT

  • Uriel Feige
  • Gideon Schechtman

MAX CUT is the problem of partitioning the vertices of a graph into two sets, maximizing the number of edges joining these sets. This problem is NP-hard. Goemans and Williamson proposed an algorithm that first uses a semidefinite programming relaxation of MAX CUT to embed the vertices of the graph on the surface of an n dimensional sphere, and then uses a random hyperplane to cut the sphere in two, giving a cut of the graph. They show that the expected number of edges in the random cut is at least α \cdot sdp, where α \simeq 0.87856 and sdp is the value of the semidefinite program.

Details

FOCS Conference 2000 Conference Paper

A polylogarithmic approximation of the minimum bisection

  • Uriel Feige
  • Robert Krauthgamer

A bisection of a graph with n vertices is a partition of its vertices into two sets, each of size n/2. The bisection cost is the number of edges connecting the two sets. Finding the bisection of minimum cost is NP-hard. We present an algorithm that finds a bisection whose cost is within ratio of O(log/sup 2/ n) from the optimal. For graphs excluding any fixed graph as a minor (e. g. planar graphs) we obtain an improved approximation ratio of O(log n). The previously known approximation ratio for bisection was roughly /spl radic/n.

Details

TCS Journal 2000 Journal Article

On the cost of recomputing: Tight bounds on pebbling with faults

  • Yonatan Aumann
  • Judit Bar-Ilan
  • Uriel Feige

We introduce a formal framework to study the time and space complexity of computing with faulty memory. For the fault-free case, time and space complexities were studied using the “pebbling game” model. We extend this model to the faulty case, where the content of memory cells may be erased. The model captures notions such as “check points” (keeping multiple copies of intermediate results), and “recovery” (partial recomputing in the case of failure). Using this model, we derive tight bounds on the time and/or space overhead inflicted by faults. As a lower bound, we exhibit cases where f worst-case faults may necessitate an Ω(f) multiplicative factor overhead in computation resources (time, space, or their product). The lower bound holds regardless of the computing and recomputing strategy employed. A matching upper-bound algorithm establishes that an O(f) multiplicative overhead always suffices. For the special class of binary tree computations, we show that f faults necessitates only Θ(f) additive factor in space.

Details DOI

FOCS Conference 1999 Conference Paper

Noncryptographic Selection Protocols

  • Uriel Feige

Selection tasks generalize some well studied problems, such as collective coin flipping and leader election. We present new selection protocols in the full information model, and new negative results. In particular when there are (1+/spl delta/)n/2 good players, we show a protocol that chooses a good leader with probability /spl Omega/(/spl delta//sup 1. 65/), and show that every leader election protocol has success probability O(/spl delta//sup 1-/spl epsiv//), for every /spl epsiv/>0. Previously known protocols for this problem have success probability that is exponentially small in 1//spl delta/, and no nontrivial upper bounds on the success probability were known.

Details

FOCS Conference 1998 Conference Paper

Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs

  • Uriel Feige
  • Joe Kilian

We study a semi-random graph model for finding independent sets. For /spl alpha/>0, an n-vertex graph with an independent set S of site /spl alpha/n is constructed by blending random and adversarial decisions. Randomly and independently with probability p, each pair of vertices, such that one is in S and the other is not, is connected by an edge. An adversary can then add edges arbitrarily (provided that S remains an independent set). The smaller p is, the larger the control the adversary has over the semi-random graph. We design heuristics that with high probability recover S when p>(1+/spl epsiv/)ln n/|S|, for any constant /spl epsiv/>0. We show that when p<(1-/spl epsiv/) In n/|S|, an independent set of size |S| cannot be recovered, unless NP/spl sube/BPP. We use our remits to obtain greatly improved coloring algorithms for the model of k-colorable semi-random graphs introduced by A. Blum and J. Spencer (1995).

Details

TCS Journal 1996 Journal Article

A fast randomized LOGSPACE algorithm for graph connectivity

  • Uriel Feige

We study the relationship between undirected graph reachability and graph connectivity, in the context of randomized LOGSPACE algorithms. Aleluinas et al. [2] show that graph reachability (checking whether there is a path connecting vertices J and ℸ) can be decided in logarithmic space and polynomial time, by starting a random walk at J, and checking whether ℸ is hit within some time limit. The randomized algorithm has one-sided error (with small probability, it fails to determine that J and ℸ are connected). The reachability algorithm may be used in order to decide (with one-sided error) whether a graph is connected, by running it n − 1 times, each time with a different target vertex ℸ. This increases the running time by a factor of n. In this paper we give an alternative randomized LOGSPACE algorithm for graph connectivity. Its running time varies between O(n 2) steps and O(n 3) steps, depending on the structure of the input graph. This matches the fastest known RLOGSPACE algorithm for reachability, up to a constant factor. Our algorithm has two-sided error.

Details DOI

FOCS Conference 1993 Conference Paper

A Randomized Time-Space Tradeoff of \tildeO(m\tildeR) for USTCON

  • Uriel Feige

We present a randomized time space tradeoff of O/spl tilde/(mR/spl circ/) for undirected S-T-connectivity, where R/spl circ/ /spl Sigma//sub /spl upsi//spl epsiv/V/ 1/d/sub /spl upsi// is the virtual resistance of the graph. This solves an open question of Broder et al. (1989) (implicit also in Aleliunas et al. (1979)) who asked whether a tradeoff of O/spl tilde/(mn) is achievable, and also improves upon a tradeoff of O/spl tilde/(mn/d/sub min/) conjectured by Barnes and Feige (1993). Our algorithm is a modification of the Broder et al. algorithm. In passing, we also improve a result from Barnes and Feige regarding the rate at which a random walk discovers new vertices in a graph. >

Details

FOCS Conference 1992 Conference Paper

Exact Analysis of Hot-Potato Routing (Extended Abstract)

  • Uriel Feige
  • Prabhakar Raghavan

The authors consider a form of packet routing known as hot potato routing or deflection routing. Its striking feature is that there are no buffers at intermediate nodes. Thus packets are always moving (possibly in the 'wrong' direction), giving rise to the term 'hot potato'. They give a simple deterministic algorithm that on a n*n torus will route a random instance in 2n+O(log n) steps with high probability. They add random delays to this algorithm so that it solves the permutation routing problem on the torus in 9n steps with high probability, on every instance. On a hypercube with N=2/sup n/ nodes, they give a simple deterministic algorithm that will route a random instance in O(n) steps with high probability. Various other results are discussed. >

Details

STOC Conference 1992 Conference Paper

Two-Prover One-Round Proof Systems: Their Power and Their Problems (Extended Abstract)

  • Uriel Feige
  • László Lovász 0001

We characterize the power of two-prover one-round ( MIP (2,1)) proof systems, showing that MIP (2,1)= NEXPTIME . However, the following intriguing question remains open: Does parallel repetition decrease the error probability of MIP (2,1) proof systems?. We use techniques based on quadratic programming to study this problem, and prove the parallel repetition conjecture in some special cases. Interestingly, our work leads to a general polynomial time heuristic for any NP -problem. We prove the effectiveness of this heuristic for several problems, such as computing the chromatic number of perfect graphs.

Details

FOCS Conference 1991 Conference Paper

Approximating Clique is Almost NP-Complete (Preliminary Version)

  • Uriel Feige
  • Shafi Goldwasser
  • László Lovász 0001
  • Muli Safra
  • Mario Szegedy

The computational complexity of approximating omega (G), the size of the largest clique in a graph G, within a given factor is considered. It is shown that if certain approximation procedures exist, then EXPTIME=NEXPTIME and NP=P. >

Details

FOCS Conference 1990 Conference Paper

Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract)

  • Uriel Feige
  • Dror Lapidot
  • Adi Shamir

The authors solve the two major open problems associated with noninteractive zero-knowledge proofs: how to enable polynomially many provers to prove in writing polynomially many theorems based on the basis of a single random string, and how to construct such proofs under general (rather than number-theoretic) assumptions. The constructions can be used in cryptographic applications in which the prover is restricted to polynomial time, and they are much simpler than earlier (and less capable) proposals. >

Details

STOC Conference 1987 Conference Paper

Zero Knowledge Proofs of Identity

  • Uriel Feige
  • Amos Fiat
  • Adi Shamir

In this paper we extend the notion of zero knowledge proofs of membership (which reveal one bit of information) to zero knowledge proofs of knowledge (which reveal no information whatsoever). After formally defining this notion, we show its relevance to identification schemes, in which parties prove their identity by demonstrating their knowledge rather than by proving the validity of assertions. We describe a novel scheme which is provably secure if factoring is difficult and whose practical implementations are about two orders of magnitude faster than RSA-based identification schemes. In the last part of the paper we consider the question of sequential versus parallel executions of zero knowledge protocols, define a new notion of “transferable information”, and prove that the parallel version of our identification scheme (which is not known to be zero knowledge) is secure since it reveals no transferable information.

Details
v2026.09.13