4 papers · 1 filter
The Switching Lemma shows what the Switching Lemma cannot prove: an unconditional natural-proofs barrier
Bruno Loff, Suhail Sherif, Navid Talebanfard +1
Razborov and Rudich (JCSS'97) observed that all known lower-bound proofs follow a certain pattern: when showing that a function is hard, along the way the proof provides us wit…
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…
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 …