Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > RANDOMNESS EXTRACTION:
Reports tagged with Randomness Extraction:
TR09-004 | 15th January 2009
Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan

Extensions to the Method of Multiplicities, with applications to Kakeya Sets and Mergers

Revisions: 2

We extend the method of multiplicities'' to get the following results, of interest in combinatorics and randomness extraction.
\begin{enumerate}
\item We show that every Kakeya set in $\F_q^n$, the $n$-dimensional vector space over the finite field on $q$ elements, must be of size at least $q^n/2^n$. This bound is tight ... more >>>

TR10-044 | 12th March 2010
Eli Ben-Sasson, Swastik Kopparty

{\em Dispersers} and {\em extractors} for affine sources of dimension $d$ in $\mathbb F_p^n$ --- where $\mathbb F_p$ denotes the finite field of prime size $p$ --- are functions $f: \mathbb F_p^n \rightarrow \mathbb F_p$ that behave pseudorandomly when their domain is restricted to any particular affine space $S \subseteq ... more >>> TR10-150 | 19th September 2010 Bjørn Kjos-Hanssen A strong law of computationally weak subsets We show that in the setting of fair-coin measure on the power set of the natural numbers, each sufficiently random set has an infinite subset that computes no random set. That is, there is an almost sure event$\mathcal A$such that if$X\in\mathcal A$then$X\$ has an infinite ... more >>>

TR11-106 | 6th August 2011
Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil Vadhan

The Limits of Two-Party Differential Privacy

We study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and ... more >>>

ISSN 1433-8092 | Imprint