39 citations · 65 across the 14 of their papers we have counts for
5 papers · 1 filter
Improved Monotonicity Testers via Hypercube Embeddings
Mark Braverman, Subhash Khot, Guy Kindler +1
We show improved monotonicity testers for the Boolean hypercube under the -biased measure, as well as over the hypergrid . Our results are: 1. For any , for t…
An analogue of Bonami's Lemma for functions on spaces of linear maps, and 2-2 Games
David Ellis, Guy Kindler, Noam Lifshitz
We prove an analogue of Bonami's (hypercontractive) lemma for complex-valued functions on , where and are vector spaces over a finite field. This inequali…
The success probability in Levine's hat problem, and independent sets in graphs
Noga Alon, Ehud Friedgut, Gil Kalai +1
Lionel Levine's hat challenge has players, each with a (very large, or infinite) stack of hats on their head, each hat independently colored at random black or white. The playe…
Forbidden intersection problems for families of linear maps
David Ellis, Guy Kindler, Noam Lifshitz
We study an analogue of the Erdős-Sós forbidden intersection problem, for families of linear maps. If and are vector spaces over the same field, we say a family $\mathcal{F…
Isoperimetric Inequalities Made Simpler
Ronen Eldan, Guy Kindler, Noam Lifshitz +1
We give an alternative, simple method to prove isoperimetric inequalities over the hypercube. In particular, we show: 1. An elementary proof of classical isoperimetric inequalities…