20 citations · 69 across the 36 of their papers we have counts for
5 papers · 1 filter
Constant Degree Direct Product Testers with Small Soundness
Mitali Bafna, Noam Lifshitz, Dor Minzer
Let be a -dimensional simplicial complex. A function is said to be a direct product function if there exists a function …
Hypercontractivity on High Dimensional Expanders: Approximate Efron-Stein Decompositions for -Product Spaces
Tom Gur, Noam Lifshitz, Siqi Liu
We prove hypercontractive inequalities on high dimensional expanders. As in the settings of the p-biased hypercube, the symmetric group, and the Grassmann scheme, our inequalities…
An Invariance Principle for the Multi-slice, with Applications
Mark Braverman, Subhash Khot, Noam Lifshitz +1
Given an alphabet size thought of as a constant, and whose entries sum of up , the -multi-slice is the set of vectors $x\i…
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…
On the sum of the L1 influences of bounded functions
Yuval Filmus, Hamed Hatami, Nathan Keller +1
Let have degree as a multilinear polynomial. It is well-known that the total influence of is at most . Aaronson and Ambainis asked whethe…