39 citations · 180 across the 62 of their papers we have counts for
5 papers · 1 filter
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for
Yuval Filmus, Or Meir, Avishay Tal
Håstad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of under a random restriction…
Hypercontractivity on the symmetric group
Yuval Filmus, Guy Kindler, Noam Lifshitz +1
The hypercontractive inequality is a fundamental result in analysis, with many applications throughout discrete mathematics, theoretical computer science, combinatorics and more. S…
Complexity Measures on the Symmetric Group and Beyond
Neta Dafni, Yuval Filmus, Noam Lifshitz +2
We extend the definitions of complexity measures of functions to domains such as the symmetric group. The complexity measures we consider include degree, approximate degree, decisi…
Explicit SoS lower bounds from high-dimensional expanders
Irit Dinur, Yuval Filmus, Prahladh Harsha +1
We construct an explicit family of 3XOR instances which is hard for levels of the Sum-of-Squares hierarchy. In contrast to earlier constructions, which involve a…
MaxSAT Resolution and Subcube Sums
Yuval Filmus, Meena Mahajan, Gaurav Sood +1
We study the MaxRes rule in the context of certifying unsatisfiability. We show that it can be exponentially more powerful than tree-like resolution, and when augmented with weaken…