All reports by Author Mohit Gurumukhani:

__
TR24-133
| 7th September 2024
__

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Yunya Zhao#### Two-Sided Lossless Expanders in the Unbalanced Setting

Revisions: 1

__
TR23-210
| 22nd December 2023
__

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach#### On the Existence of Seedless Condensers: Exploring the Terrain

Revisions: 2

__
TR23-140
| 20th September 2023
__

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

Revisions: 1

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach, Yunya Zhao

We present the first explicit construction of two-sided lossless expanders in the unbalanced setting (bipartite graphs that have many more nodes on the left than on the right). Prior to our work, all known explicit constructions in the unbalanced setting achieved only one-sided lossless expansion.

Specifically, we show ... more >>>

Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

While the existence of randomness extractors, both seeded and seedless, has been thoroughly studied for many sources of randomness, currently, very little is known regarding the existence of seedless condensers in many settings. Here, we prove several new results for seedless condensers in the context of three related classes of ... more >>>

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