194
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
Submodular function maximization is a central problem in combinatorial optimization, generalizing many important problems including Max Cut in directed/undirected graphs and in hy...
185
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We present an improved oracle for the distance sensitivity problem. The goal is to preprocess a directed graph G = (V, E) with non-negative edge weights to answer queries of the f...
167
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We analyze the mixing time of a natural local Markov chain (the Glauber dynamics) on configurations of the solid-onsolid model of statistical physics. This model has been proposed...
175
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We consider the problem of MaxMin allocation of indivisible goods. There are m items to be distributed among n players. Each player i has a nonnegative valuation pij for an item j...
145
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
A distributed task T on n processors is an input/output relation between a collection of processors' inputs and outputs. While all tasks are solvable if no processor may ever...
184
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
A function on n variables is called a k-junta if it depends on at most k of its variables. In this article, we show that it is possible to test whether a function is a k-junta or ...
156
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
Let K be a polytope in Rn defined by m linear inequalities. We give a new Markov Chain algorithm to draw a nearly uniform sample from K. The underlying Markov Chain is the first t...
168
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
In this paper we study a fundamental open problem in the area of probabilistic checkable proofs: What is the smallest s such that NP naPCP1,s[O(log n), 3]? In the language of har...
183
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
The quantum analog of a constraint satisfaction problem is a sum of local Hamiltonians - each (term of the) Hamiltonian specifies a local constraint whose violation contributes to...
146
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
Some, but not all, extractors resist adversaries with limited quantum storage. In this paper we show that Trevisan's extractor has this property, thereby showing an extractor...