12 papers
Sumset Structure in Local Computation
Alexander Golovnev, Mohit Gurumukhani
We introduce and study a new model of decision trees that lies at the frontier of provable circuit lower bounds. We study -local decision trees, in which each internal node q…
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 …
Optimal Depth-Three Circuits for Inner Product
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +2
We show that Inner Product in variables, , can be computed by depth-3 bottom fan-in 2 circuits of size $\mathsf{poly}…
Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +3
Gurumuhkani et al. (CCC'24) introduced the local enumeration problem as follows: for a natural number and a parameter , given an -variate -CNF with no sat…
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…
Local Enumeration: The Not-All-Equal Case
Mohit Gurumukhani, Ramamohan Paturi, Michael Saks +1
Gurumukhani et al. (CCC'24) proposed the local enumeration problem Enum(k, t) as an approach to break the Super Strong Exponential Time Hypothesis (SSETH): for a natural number …
On Extremal Properties of k-CNF: Capturing Threshold Functions
Mohit Gurumukhani, Marvin Künnemann, Ramamohan Paturi
We consider a basic question on the expressiveness of -CNF formulas: How well can -CNF formulas capture threshold functions? Specifically, what is the largest number of assig…
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…
Local Enumeration and Majority Lower Bounds
Mohit Gurumukhani, Ramamohan Paturi, Pavel Pudlák +2
Depth-3 circuit lower bounds and -SAT algorithms are intimately related; the state-of-the-art -circuit lower bound and the -SAT algorithm are based on the same combina…
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{\…