39 citations · 180 across the 62 of their papers we have counts for
4 papers · 1 filter
A stability result for balanced dictatorships in
David Ellis, Yuval Filmus, Ehud Friedgut
We prove that a balanced Boolean function on whose Fourier transform is highly concentrated on the first two irreducible representations of , is close in structure t…
A quasi-stability result for dictatorships in
David Ellis, Yuval Filmus, Ehud Friedgut
We prove that Boolean functions on whose Fourier transform is highly concentrated on the first two irreducible representations of , are close to being unions of cosets…
The Complexity of the Comparator Circuit Value Problem
Stephen A. Cook, Yuval Filmus, Dai Tri Man Le
In 1990 Subramanian defined the complexity class CC as the set of problems log-space reducible to the comparator circuit value problem (CCV). He and Mayr showed that NL \subseteq C…
A Tight Combinatorial Algorithm for Submodular Maximization Subject to a Matroid Constraint
Yuval Filmus, Justin Ward
We present an optimal, combinatorial 1-1/e approximation algorithm for monotone submodular optimization over a matroid constraint. Compared to the continuous greedy algorithm (Cali…