Mohit Gurumukhani

activity

20232026

collaborators

Showing 2026Show all

4 papers · 1 filter

cs.CC2026

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…

cs.CC2026

A Resolution of Friedgut's Conjecture on Influential Coalitions

Eshan Chattopadhyay, Mohit Gurumukhani

We prove that, for every constant $ε > 0$ and every function $f : Σ^{n} \to {0, 1}$ , there is a coalition of $O (n / lo g n)$ coordinates and a target output $b \in {0, 1}$ …

cs.CC2026

Optimal Depth-Three Circuits for Inner Product

Mohit Gurumukhani, Daniel Kleber, Ramamohan Paturi +2

We show that Inner Product in $2 n$ variables, $IP_{n} (x, y) = x_{1} y_{1} \oplus \dots \oplus x_{n} y_{n}$ , can be computed by depth-3 bottom fan-in 2 circuits of size $\mathsf{poly}…

cs.CC2026

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 $E n u m (k, t)$ as follows: for a natural number $k$ and a parameter $t$ , given an $n$ -variate $k$ -CNF with no sat…