37 citations · 101 across the 43 of their papers we have counts for
4 papers · 2 filters
Tradeoffs for small-depth Frege proofs
Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan
We study the complexity of small-depth Frege proofs and give the first tradeoffs between the size of each line and the number of lines. Existing lower bounds apply to the overall p…
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…
Fooling Gaussian PTFs via Local Hyperconcentration
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan +1
We give a pseudorandom generator that fools degree- polynomial threshold functions over -dimensional Gaussian space with seed length . All previ…
On the Power and Limitations of Branch and Cut
Noah Fleming, Mika Göös, Russell Impagliazzo +4
The Stabbing Planes proof system was introduced to model the reasoning carried out in practical mixed integer programming solvers. As a proof system, it is powerful enough to simul…