160
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
208
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We consider the following question: given a two-argument boolean function f, represented as an N ? N binary matrix, how hard is to determine the (deterministic) communication comp...
191
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We describe the first algorithm to compute maximum flows in surface-embedded graphs in near-linear time. Specifically, given a graph embedded on a surface of genus g, with two spe...
208
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Publishing fully accurate information ...
167
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We show how to compute the edit distance between two strings of length n up to a factor of 2 ~O( log n) in n1+o(1) time. This is the first sub-polynomial approximation algorithm f...
164
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
The continuous-time query model is a variant of the discrete query model in which queries can be interleaved with known operations (called "driving operations") continuo...
205
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We study the question of basing symmetric key cryptography on weak secrets. In this setting, Alice and Bob share an n-bit secret W, which might not be uniformly random, but the ad...
190
click to vote
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we...
158
Voted
STOC
2009
ACM
16 years 7 months ago
2009
ACM
We study integrality gaps for SDP relaxations of constraint satisfaction problems, in the hierarchy of SDPs defined by Lasserre. Schoenebeck [25] recently showed the first integra...