5 citations · 8 across the 9 of their papers we have counts for
20 papers
Two-Sided Product Expanding Codes via Rademacher Matrices
Eshan Chattopadhyay, Noam Ringach, Nicholas Spooner
We give a proof of the existence of two-sided product expanding codes which, unlike the earlier result of Kalachev and Panteleev (FOCS, 2025), does not rely on explicit constructio…
Frustration Free Stoquastic Local Hamiltonian with Sub-Constant Gap is in NP
Eshan Chattopadhyay, Oren Renard, Nicholas Spooner
We continue the study of the Stoquastic Local Hamiltonian problem, a physically motivated restriction of the QMA-complete Local Hamiltonian problem (Kitaev, Shen, and Vyalyi, 2002)…
Exponential Correlation Bounds for Polynomials
Eshan Chattopadhyay, Pooya Hatami, Chin Ho Lee +3
We prove that the XOR of majorities on disjoint blocks of bits has correlation at most with every Boolean-valued degree- polynomial over an arbit…
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 …
Multipass Linear Sketches for Geometric LP-Type Problems
N. Efe Çekirge, William Gay, David P. Woodruff
LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinat…
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…
On the Existence of Seedless Condensers: Exploring the Terrain
Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach
We prove several new results for seedless condensers in the context of three related classes of sources: Non-Oblivious Symbol Fixing (NOSF) sources, online NOSF (oNOSF) sources [AO…
Extractors for Polynomial Sources over
Eshan Chattopadhyay, Jesse Goodman, Mohit Gurumukhani
We explicitly construct the first nontrivial extractors for degree polynomial sources over . Our extractor requires min-entropy $k\geq n - \tildeΩ(\sqrt{\…
Low-Degree Polynomials Extract from Local Sources
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman +2
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…
Extractors for Sum of Two Sources
Eshan Chattopadhyay, Jyun-Jie Liao
We consider the problem of extracting randomness from \textit{sumset sources}, a general class of weak sources introduced by Chattopadhyay and Li (STOC, 2016). An -sumset…
Fractional Pseudorandom Generators from Any Fourier Level
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee +2
We prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay {et al.} [CHHL19,CHLT19] that exploit Fourier tail bounds for classes…
Improved Extractors for Small-Space Sources
Eshan Chattopadhyay, Jesse Goodman
We study the problem of extracting random bits from weak sources that are sampled by algorithms with limited memory. This model of small-space sources was introduced by Kamp, Rao,…
Optimal Error Pseudodistributions for Read-Once Branching Programs
Eshan Chattopadhyay, Jyun-Jie Liao
In a seminal work, Nisan (Combinatorica'92) constructed a pseudorandom generator for length and width read-once branching programs with seed length $O(\log n\cdot \log(nw)+…
Non-Malleable Extractors and Codes for Composition of Tampering, Interleaved Tampering and More
Eshan Chattopadhyay, Xin Li
Non-malleable codes were introduced by Dziembowski, Pietrzak, and Wichs (JACM 2018) as a generalization of standard error correcting codes to handle severe forms of tampering on co…
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols
Eshan Chattopadhyay, Xin Li
We make progress in the following three problems: 1. Constructing optimal seeded non-malleable extractors; 2. Constructing optimal privacy amplification protocols with an active ad…
Non-Malleable Extractors and Codes, with their Many Tampered Extensions
Eshan Chattopadhyay, Vipul Goyal, Xin Li
Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the con…
On Low Discrepancy Samplings in Product Spaces of Motion Groups
Chandrajit Bajaj, Abhishek Bhowmick, Eshan Chattopadhyay +1
Deterministically generating near-uniform point samplings of the motion groups like SO(3), SE(3) and their n-wise products SO(3)^n, SE(3)^n is fundamental to numerous applications…