1 citations · 1 across the 3 of their papers we have counts for
7 papers
Optimal Shallow Circuits for Majority
Victor Lecomte, Prasanna Ramakrishnan
Four decades on, Håstad's classical lower bound for depth- circuits computing Parity remains the best known circuit lower bound for any expl…
Hardness Amplification for Dynamic Binary Search Trees
Shunhua Jiang, Victor Lecomte, Omri Weinstein +1
We prove direct-sum theorems for Wilber's two lower bounds [Wilber, FOCS'86] on the cost of access sequences in the binary search tree (BST) model. These bounds are central to the…
Backdoor defense, learnability and obfuscation
Paul Christiano, Jacob Hilton, Victor Lecomte +1
We introduce a formal notion of defendability against backdoors using a game between an attacker and a defender. In this game, the attacker modifies a function to behave differentl…
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…
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…
The power of adaptivity in source identification with time queries on the path
Victor Lecomte, Gergely Ódor, Patrick Thiran
We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph…
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…