Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MOHIT GURUMUKHANI:
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

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


TR23-210 | 22nd December 2023
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

On the Existence of Seedless Condensers: Exploring the Terrain

Revisions: 2

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


TR23-140 | 20th September 2023
Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani

Extractors for Polynomial Sources over $\mathbb{F}_2$

Revisions: 1

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




ISSN 1433-8092 | Imprint