Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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.
\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

Affine Dispersers from Subspace Polynomials

{\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 >>>

TR19-183 | 21st December 2019
Marshall Ball, Oded Goldreich, Tal Malkin

Randomness Extraction from Somewhat Dependent Sources

Revisions: 1

We initiate a comprehensive study of the question of randomness extractions from two somewhat dependent sources of defective randomness.
Specifically, we present three natural models, which are based on different natural perspectives on the notion of bounded dependency between a pair of distributions.
Going from the more restricted model ... more >>>

TR20-054 | 22nd April 2020
Marshall Ball, Oded Goldreich, Tal Malkin

Communication Complexity with Defective Randomness

Revisions: 3

Starting with the two standard model of randomized communication complexity, we study the communication complexity of functions when the protocol has access to a defective source of randomness.
Specifically, we consider both the public-randomness and private-randomness cases, while replacing the commonly postulated perfect randomness with distributions over $\ell$ bit ... more >>>

TR21-090 | 14th June 2021
Divesh Aggarwal, Eldon Chung, Maciej Obremski, Joao Ribeiro

On Secret Sharing, Randomness, and Random-less Reductions for Secret Sharing

Secret-sharing is one of the most basic and oldest primitives in cryptography, introduced by Shamir and Blakely in the 70s. It allows to strike a meaningful balance between availability and confidentiality of secret information. It has a host of applications most notably in threshold cryptography and multi-party computation. All known ... more >>>

TR22-010 | 18th January 2022
Marshall Ball, Dana Dachman-Soled, Julian Loss

(Nondeterministic) Hardness vs. Non-Malleability

We present the first truly explicit constructions of \emph{non-malleable codes} against tampering by bounded polynomial size circuits. These objects imply unproven circuit lower bounds and our construction is secure provided E requires exponential size nondeterministic circuits, an assumption from the derandomization literature.

Prior works on NMC ... more >>>

ISSN 1433-8092 | Imprint