5 citations · 6 across the 9 of their papers we have counts for
18 papers
Junta threshold for low degree Boolean functions on the slice
Yuval Filmus
We show that a Boolean degree function on the slice is a junta if , and that this bound is sharp. We prove a similar result for -valued degree $d…
Simple Algebraic Proofs of Uniqueness for Erdős-Ko-Rado Theorems
Yuval Filmus, Nathan Lindzey
We give simpler algebraic proofs of uniqueness for several Erdős-Ko-Rado results, i.e., that the canonically intersecting families are the only largest intersecting families. Using…
Approximate polymorphisms
Gilad Chase, Yuval Filmus, Dor Minzer +2
For a function , a function is called a -polymorphism if their actions commute: $f(g(\mathsf{row}_1(Z)),\ldots,g(\maths…
Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds
Ofir Gordon, Yuval Filmus, Oren Salzman
The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. Arguably, the state-of-the-art…
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…