3 citations · 3 across the 6 of their papers we have counts for
13 papers · 1 filter
Exponential Correlation Bounds for Polynomials
Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee +3
We prove that the XOR of majorities on disjoint blocks of \(\ell\) bits has correlation at most \((2d/\sqrt{\ell})^k\) with every degree-\(d\) polynomial over \(\mathbb F_2\).…
A Resolution of Friedgut's Conjecture on Influential Coalitions
Eshan Chattopadhyay, Mohit Gurumukhani
We prove that, for every constant and every function , there is a coalition of coordinates and a target output …
Leakage-Resilient Extractors against Number-on-Forehead Protocols
Eshan Chattopadhyay, Jesse Goodman
Given a sequence of independent sources , how many of them must be good (i.e., contain some min-entropy) in order to…
Improved Bounds for Coin Flipping, Leader Election, and Random Selection
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach +1
Random selection, leader election, and collective coin flipping are fundamental tasks in fault-tolerant distributed computing. We study these problems in the full-information model…
Condensing and Extracting Against Online Adversaries
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach +1
We study the tasks of deterministically condensing and extracting from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model of defective randomness where extraction…
Two-Sided Lossless Expanders in the Unbalanced Setting
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach +1
We present the first explicit construction of two-sided lossless expanders in the unbalanced setting (bipartite graphs that have polynomially many more nodes on the left than on th…