163
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We give near-optimal space bounds in the streaming model for linear algebra problems that include estimation of matrix products, linear regression, low-rank approximation, and app...
152
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We put forward a new approach to mechanism design, and exemplify it via a new mechanism guaranteeing significant revenue in unrestricted combinatorial auctions. Our mechanism ? su...
177
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
Consider the edge-connectivity survivable network design problem: given a graph G = (V, E) with edge-costs, and edgeconnectivity requirements rij Z0 for every pair of vertices i,...
141
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We describe a new approximation algorithm for Max Cut. Our algorithm runs in ~O(n2 ) time, where n is the number
171
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
An affine disperser over Fn 2 for sources of dimension d is a function f : Fn 2 F2 such that for any affine space S Fn 2 of dimension at least d, we have {f(s) : s S} = F2. Aff...
147
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We study the Sherali-Adams lift-and-project hierarchy of linear programming relaxations of the matching polytope. Our main result is an asymptotically tight expression 1 + 1/k for...
199
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We prove strong lower bounds on integrality gaps of Sherali?Adams relaxations for MAX CUT, Vertex Cover, Sparsest Cut and other problems. Our constructions show gaps for Sherali?A...
202
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We study a general sub-class of concave games, which we call socially concave games. We show that if each player follows any no-external regret minimization procedure then the dyn...
183
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We study the topological simplification of graphs via random embeddings, leading ultimately to a reduction of the Gupta-Newman-Rabinovich-Sinclair (GNRS) L1 embedding conjecture t...
161
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
Non-relativization of complexity issues can be interpreted as giving some evidence that these issues cannot be resolved by "black-box" techniques. In the early 1990'...