All reports by Author Jesse Goodman:

__
TR23-140
| 20th September 2023
__

Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani#### Extractors for Polynomial Sources over $\mathbb{F}_2$

Revisions: 1

__
TR22-082
| 27th May 2022
__

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro#### Low-Degree Polynomials Extract from Local Sources

__
TR21-106
| 22nd July 2021
__

Eshan Chattopadhyay, Jesse Goodman, David Zuckerman#### The Space Complexity of Sampling

Revisions: 1

__
TR21-075
| 4th June 2021
__

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao#### Affine Extractors for Almost Logarithmic Entropy

__
TR20-106
| 15th July 2020
__

Eshan Chattopadhyay, Jesse Goodman#### Explicit Extremal Designs and Applications to Extractors

Revisions: 5

__
TR20-060
| 23rd April 2020
__

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li#### Leakage-Resilient Extractors and Secret-Sharing against Bounded Collusion Protocols

__
TR19-184
| 13th December 2019
__

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li#### Extractors for Adversarial Sources via Extremal Hypergraphs

Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani

We explicitly construct the first nontrivial extractors for degree $d \ge 2$ polynomial sources over $\mathbb{F}_2^n$. Our extractor requires min-entropy $k\geq n - \frac{\sqrt{\log n}}{(d\log \log n)^{d/2}}$. Previously, no constructions were known, even for min-entropy $k\geq n-1$. A key ingredient in our construction is an input reduction lemma, which allows ... more >>>

Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, João Ribeiro

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

Eshan Chattopadhyay, Jesse Goodman, David Zuckerman

Recently, there has been exciting progress in understanding the complexity of distributions. Here, the goal is to quantify the resources required to generate (or sample) a distribution. Proving lower bounds in this new setting is more challenging than in the classical setting, and has yielded interesting new techniques and surprising ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Jyun-Jie Liao

We give an explicit construction of an affine extractor (over $\mathbb{F}_2$) that works for affine sources on $n$ bits with min-entropy $k \ge~ \log n \cdot (\log \log n)^{1 + o(1)}$. This improves prior work of Li (FOCS'16) that requires min-entropy at least $\mathrm{poly}(\log n)$.

Our construction is ...
more >>>

Eshan Chattopadhyay, Jesse Goodman

An $(n,r,s)$-design, or $(n,r,s)$-partial Steiner system, is an $r$-uniform hypergraph over $n$ vertices with pairwise hyperedge intersections of size $0$, we extract from $(N,K,n,k)$-adversarial sources of locality $0$, where $K\geq N^\delta$ and $k\geq\text{polylog }n$. The previous best result (Chattopadhyay et al., STOC 2020) required $K\geq N^{1/2+o(1)}$. As a result, we ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

In a recent work, Kumar, Meka, and Sahai (FOCS 2019) introduced the notion of bounded collusion protocols (BCPs), in which $N$ parties wish to compute some joint function $f:(\{0,1\}^n)^N\to\{0,1\}$ using a public blackboard, but such that only $p$ parties may collude at a time. This generalizes well studied models in ... more >>>

Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li

Randomness extraction is a fundamental problem that has been studied for over three decades. A well-studied setting assumes that one has access to multiple independent weak random sources, each with some entropy. However, this assumption is often unrealistic in practice. In real life, natural sources of randomness can produce samples ... more >>>