39 citations · 180 across the 62 of their papers we have counts for
5 papers · 1 filter
Sparse juntas on the biased hypercube
Irit Dinur, Yuval Filmus, Prahladh Harsha
We give a structure theorem for Boolean functions on the -biased hypercube which are -close to degree in , showing that they are close to sparse juntas. Our structur…
Agreement tests on graphs and hypergraphs
Irit Dinur, Yuval Filmus, Prahladh Harsha
Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreemen…
A comment on Intersecting Families of Permutations
Yuval Filmus
Ellis, Friedgut and Pilpel proved that for large enough , a -intersecting family of permutations contains at most permutations. Their main theorem also states that e…
On the Bhattacharya-Mesner rank of third order hypermatrices
Edinah K. Gnang, Yuval Filmus
We introduce the Bhattacharya-Mesner rank of third order hypermatrices as a relaxation to the tensor rank and devise from it some bounds for the tensor rank. We use the Bhattachary…
Information complexity of the AND function in the two-Party, and multiparty settings
Yuval Filmus, Hamed Hatami, Yaqiao Li +1
In a recent breakthrough paper [M. Braverman, A. Garg, D. Pankratov, and O. Weinstein, From information to exact communication, STOC'13] Braverman et al. developed a local characte…