Showing cs.CCShow all
2 papers · 1 filter
cs.CC2022
The composition complexity of majority
Victor Lecomte, Prasanna Ramakrishnan, Li-Yang Tan
We study the complexity of computing majority as a composition of local functions: \[ \text{Maj}_n = h(g_1,\ldots,g_m), \] where each is an arbitrary…
cs.CC2021
Sharper bounds on the Fourier concentration of DNFs
Victor Lecomte, Li-Yang Tan
In 1992 Mansour proved that every size- DNF formula is Fourier-concentrated on coefficients. We improve this to where is the read num…