159
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
The classical zero-one law for first-order logic on random graphs says that for every first-order property in the theory of graphs and every p (0, 1), the probability that the r...
171
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We prove lower bounds on the redundancy necessary to represent a set S of objects using a number of bits close to the information-theoretic minimum log2 |S|, while answering vario...
165
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We prove that for any positive integer k, there is a constant ck such that a randomly selected set of cknk log n Boolean vectors with high probability supports a balanced k-wise i...
198
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
Linear programming decoding for low-density parity check codes (and related domains such as compressed sensing) has received increased attention over recent years because of its p...
161
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We consider and analyze a new algorithm for balancing indivisible loads on a distributed network with n processors. The aim is minimizing the discrepancy between the maximum and m...
161
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
Algebraic codes that achieve list decoding capacity were recently constructed by a careful "folding" of the Reed-Solomon code. The "low-degree" nature of this f...
188
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We design a linear time approximation scheme for the GaleBerlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest C...
191
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
This paper studies constant-time approximation algorithms for problems on degree-bounded graphs. Let n and d be the number of vertices and the degree bound, respectively. This pap...
155
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We give explicit constructions of epsilon nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dime...