Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > RANDOMNESS EXTRACTORS:
Reports tagged with Randomness Extractors:
TR04-083 | 8th September 2004
Boaz Barak, Yehuda Lindell, Salil Vadhan

Lower Bounds for Non-Black-Box Zero Knowledge

We show new lower bounds and impossibility results for general (possibly <i>non-black-box</i>) zero-knowledge proofs and arguments. Our main results are that, under reasonable complexity assumptions:
<ol>
<li> There does not exist a two-round zero-knowledge <i>proof</i> system with perfect completeness for an NP-complete language. The previous impossibility result for two-round zero ... more >>>


TR05-145 | 5th December 2005
Ronen Shaltiel

How to get more mileage from randomness extractors

Let $\cal C$ be a class of distributions over $\B^n$. A deterministic randomness extractor for $\cal C$ is a function $E:\B^n \ar \B^m$ such that for any $X$ in $\cal C$ the distribution $E(X)$ is statistically close to the uniform distribution. A long line of research deals with explicit constructions ... more >>>


TR06-026 | 27th February 2006
Ronen Gradwohl, Salil Vadhan, David Zuckerman

Random Selection with an Adversarial Majority

We consider the problem of random selection, where $p$ players follow a protocol to jointly select a random element of a universe of size $n$. However, some of the players may be adversarial and collude to force the output to lie in a small subset of the universe. We describe ... more >>>


TR06-126 | 2nd October 2006
Piotr Indyk

Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1

We give an explicit construction of a constant-distortion embedding of an n-dimensional L_2 space into an n^{1+o(1)}-dimensional L_1 space.

more >>>

TR06-134 | 18th October 2006
Venkatesan Guruswami, Chris Umans, Salil Vadhan

Extractors and condensers from univariate polynomials

Revisions: 1

We give new constructions of randomness extractors and lossless condensers that are optimal to within constant factors in both the seed length and the output length. For extractors, this matches the parameters of the current best known construction [LRVW03]; for lossless condensers, the previous best constructions achieved optimality to within ... more >>>


TR07-015 | 1st March 2007
Oded Goldreich, Or Sheffet

On the randomness complexity of property testing

We initiate a general study of the randomness complexity of
property testing, aimed at reducing the randomness complexity of
testers without (significantly) increasing their query complexity.
One concrete motovation for this study is provided by the
observation that the product of the randomness and query complexity
of a tester determine ... more >>>


TR07-057 | 11th July 2007
Oded Goldreich

On the Average-Case Complexity of Property Testing

Revisions: 1

Motivated by a recent study of Zimand (22nd CCC, 2007),
we consider the average-case complexity of property testing
(focusing, for clarity, on testing properties of Boolean strings).
We make two observations:

1) In the context of average-case analysis with respect to
the uniform distribution (on all strings of ... more >>>


TR09-071 | 1st September 2009
John Hitchcock, A. Pavan, N. V. Vinodchandran

Kolmogorov Complexity in Randomness Extraction

We clarify the role of Kolmogorov complexity in the area of randomness extraction. We show that a computable function is an almost randomness extractor if and only if it is a Kolmogorov complexity
extractor, thus establishing a fundamental equivalence between two forms of extraction studied in the literature: Kolmogorov extraction
more >>>


TR13-121 | 4th September 2013
Mahdi Cheraghchi, Venkatesan Guruswami

Non-Malleable Coding Against Bit-wise and Split-State Tampering

Revisions: 1

Non-malleable coding, introduced by Dziembowski, Pietrzak and Wichs (ICS 2010), aims for protecting the integrity of information against tampering attacks in situations where error-detection is impossible. Intuitively, information encoded by a non-malleable code either decodes to the original message or, in presence of any tampering, to an unrelated message. Non-malleable ... more >>>


TR15-003 | 3rd January 2015
Oded Goldreich, Emanuele Viola, Avi Wigderson

On Randomness Extraction in AC0

We consider randomness extraction by AC0 circuits. The main parameter, $n$, is the length of the source, and all other parameters are functions of it. The additional extraction parameters are the min-entropy bound $k=k(n)$, the seed length $r=r(n)$, the output length $m=m(n)$, and the (output) deviation bound $\epsilon=\epsilon(n)$.

For $k ... more >>>


TR17-187 | 3rd December 2017
Roei Tell

A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization

The quantified derandomization problem of a circuit class $\mathcal{C}$ with a function $B:\mathbb{N}\rightarrow\mathbb{N}$ is the following: Given an input circuit $C\in\mathcal{C}$ over $n$ bits, deterministically distinguish between the case that $C$ accepts all but $B(n)$ of its inputs and the case that $C$ rejects all but $B(n)$ of its inputs. ... more >>>


TR18-082 | 21st April 2018
Xin Li, Shachar Lovett, Jiapeng Zhang

Sunflowers and Quasi-sunflowers from Randomness Extractors

The Erdos-Rado sunflower theorem (Journal of Lond. Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding sunflower conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which ... more >>>


TR18-116 | 18th June 2018
Xue Chen, David Zuckerman

Existence of Simple Extractors

Revisions: 1

We show that a small subset of seeds of any strong extractor also gives a strong extractor with similar parameters when the number of output bits is a constant. Specifically, if $Ext: \{0,1\}^n \times \{0,1\}^t \to \{0,1\}^m$ is a strong $(k,\epsilon)$-extractor, then for at least 99% of choices of $\tilde{O}(n ... more >>>


TR19-173 | 28th November 2019
Divesh Aggarwal, Siyao Guo, Maciej Obremski, Joao Ribeiro, Noah Stephens-Davidowitz

Extractor Lower Bounds, Revisited

Revisions: 1

We revisit the fundamental problem of determining seed length lower bounds for strong extractors and natural variants thereof. These variants stem from a ``change in quantifiers'' over the seeds of the extractor: While a strong extractor requires that the average output bias (over all seeds) is small for all input ... more >>>


TR20-055 | 22nd April 2020
Ashutosh Kumar, Raghu Meka, David Zuckerman

Bounded Collusion Protocols, Cylinder-Intersection Extractors and Leakage-Resilient Secret Sharing

In this work we study bounded collusion protocols (BCPs) recently introduced in the context of secret sharing by Kumar, Meka, and Sahai (FOCS 2019). These are multi-party communication protocols on $n$ parties where in each round a subset of $p$-parties (the collusion bound) collude together and write a function of ... 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 >>>


TR21-117 | 11th August 2021
Divesh Aggarwal, Bhavana Kanukurthi, SaiLakshmiBhavana Obbattu, Maciej Obremski, Sruthi Sekar

Simplicity Meets Near-Optimal Rate: Non-malleable Codes and Non-malleable Two-source Extractors via Rate Boosters

Revisions: 3

At ITCS 2010, Dziembowski, Pietrzak, and Wichs introduced Non-malleable Codes (NMCs). Non-malleability is one of the strongest and most challenging notions of security considered in cryptography and protects against tampering attacks. In the context of coding schemes, non-malleability requires that it be infeasible to tamper the codeword of a message ... more >>>


TR22-082 | 27th May 2022
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

Low-Degree Polynomials Extract from Local Sources

We continue a line of work on extracting random bits from weak sources that are generated by simple processes. We focus on the model of locally samplable sources, where each bit in the source depends on a small number of (hidden) uniformly random input bits. Also known as local sources, ... more >>>


TR23-169 | 14th November 2023
Marshall Ball, Dana Dachman-Soled, Eli Goldin, Saachi Mutreja

Extracting Randomness from Samplable Distributions, Revisited

Randomness extractors provide a generic way of converting sources of randomness that are
merely unpredictable into almost uniformly random bits. While in general, deterministic randomness
extraction is impossible, it is possible if the source has some structural constraints.
While much of the literature on deterministic extraction has focused on sources ... more >>>


TR24-040 | 29th February 2024
Kuan Cheng, Ruiyang Wu

Randomness Extractors in $\mathrm{AC}^0$ and $\mathrm{NC}^1$: Optimal up to Constant Factors

We study extractors computable in uniform $\mathrm{AC}^0$ and uniform $\mathrm{NC}^1$.

For the $\mathrm{AC}^0$ setting, we give a construction such that for every $k \ge n/ \mathrm{poly} \log n, \eps \ge 2^{-\mathrm{poly} \log n}$, it can extract $(1-\gamma)k$ randomness from an $(n, k)$ source for an arbitrary constant ... more >>>




ISSN 1433-8092 | Imprint