7 papers · 1 filter
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…