192
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
The "direct product code" of a function f gives its values on all k-tuples (f(x1), . . . , f(xk)). This basic construct underlies "hardness amplification" in c...
176
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We consider matrix groups, specified by a list of generators, over finite fields. The two most basic questions about such groups are membership in and the order of the group. Even...
184
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
Locally Decodable Codes (LDC) allow one to decode any particular symbol of the input message by making a constant number of queries to a codeword, even if a constant fraction of t...
194
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
The price of anarchy (POA) is a worst-case measure of the inefficiency of selfish behavior, defined as the ratio of the objective function value of a worst Nash equilibrium of a g...
162
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We show by means of several examples that robust statistical estimators present an excellent starting point for differentially private estimators. Our algorithms use a new paradig...
157
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We initiate a systematic study of a special type of property testers. These testers consist of repeating a basic test for a number of times that depends on the proximity parameter...
193
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. ? We show that for every code, the rat...
179
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
d Abstract] Virginia Vassilevska School of Mathematics Institute for Advanced Study Princeton, NJ 08540 USA virgi@math.ias.edu Ryan Williams School of Mathematics Institute for Adv...
173
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
The paper concerns graph spanners that are resistant to vertex or edge failures. Given a weighted undirected n-vertex graph G = (V, E) and an integer k 1, the subgraph H = (V, E ...
138
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
One of the most fundamental problems in web search is how to re-rank result web pages based on user logs. Most traditional models for re-ranking assume each query has a single int...