U. Feige

activity

20032022

most citedQuantitative Group Testing and the rank of random matrices

12 citations · 38 across the 15 of their papers we have counts for

collaborators

Showing 2020Show all

3 papers · 1 filter

cs.IT2020★ 12 cited

Quantitative Group Testing and the rank of random matrices

Uriel Feige, Amir Lellouche

Given a random Bernoulli matrix $A \in {0, 1}^{m \times n}$ , an integer $0 < k < n$ and the vector $y := A x$ , where $x \in {0, 1}^{n}$ is of Hamming weight $k$ , the objective…

cs.DS2020

How to hide a clique?

Uriel Feige, Vadim Grinberg

In the well known planted clique problem, a clique (or alternatively, an independent set) of size $k$ is planted at random in an Erdos-Renyi random $G (n, p)$ graph, and the goal is…

cs.GT2020

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