Daniel Kleber

collaborators

2 papers

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…