3 papers
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…
cs.DS2019
Settling the relationship between Wilber's bounds for dynamic optimality
Victor Lecomte, Omri Weinstein
In FOCS 1986, Wilber proposed two combinatorial lower bounds on the operational cost of any binary search tree (BST) for a given access sequence . Both bounds play a c…