6 papers
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…
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…
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…