
A tight negative example for MMS fair allocations
We consider the problem of allocating indivisible goods to agents with a...
read it

FairShare Allocations for Agents with Arbitrary Entitlements
We consider the problem of fair allocation of indivisible goods to n age...
read it

Are Gross Substitutes a Substitute for Submodular Valuations?
The class of gross substitutes (GS) set functions plays a central role i...
read it

BestofBothWorlds FairShare Allocations
We consider the problem of fair allocation of indivisible items among n ...
read it

Quantitative Group Testing and the rank of random matrices
Given a random Bernoulli matrix A∈{0,1}^m× n, an integer 0< k < n and th...
read it

How to hide a clique?
In the well known planted clique problem, a clique (or alternatively, an...
read it

Fair and Truthful Mechanisms for Dichotomous Valuations
We consider the problem of allocating a set on indivisible items to play...
read it

On the path partition number of 6regular graphs
A path partition (also referred to as a linear forest) of a graph G is a...
read it

A New Approach to Fair Distribution of Welfare
We consider transferableutility profitsharing games that arise from se...
read it

Target Set Selection for Conservative Populations
Let G = (V,E) be a graph on n vertices, where d_v denotes the degree of ...
read it

A randomized strategy in the mirror game
Alice and Bob take turns (with Alice playing first) in declaring numbers...
read it

Tighter bounds for online bipartite matching
We study the online bipartite matching problem, introduced by Karp, Vazi...
read it

Finding cliques using few probes
Consider algorithms with unbounded computation time that probe the entri...
read it

A Polynomial Time Constant Approximation For Minimizing Total Weighted Flowtime
We consider the classic scheduling problem of minimizing the total weigh...
read it

MaxMin Greedy Matching
A bipartite graph G(U,V;E) that admits a perfect matching is given. One ...
read it

Why are images smooth?
It is a well observed phenomenon that natural images are smooth, in the ...
read it
Uriel Feige
is this you? claim profile
Professor.at Department of Computer Science and Applied Mathematics, the Weizmann Institute, Coinventing the Feige–Fiat–Shamir identification scheme, Gödel Prize in 2001 "for the PCP theorem and its applications to hardness of approximation".