29 citations · 99 across the 31 of their papers we have counts for
Showing 2005Show all
2 papers · 1 filter
math.CO2005
Edge-isoperimetric inequalities and influences
D. Falik, A. Samorodnitsky
We give a combinatorial proof of the result of Kahn, Kalai, and Linial, which states that every balanced boolean function on the -dimensional boolean cube has a variable with in…
math.CO2005
Gowers Uniformity, Influence of Variables, and PCPs
Alex Samorodnitsky, Luca Trevisan
Gowers introduced, for d\geq 1, the notion of dimension-d uniformity U^d(f) of a function f: G -> \C, where G is a finite abelian group and \C are the complex numbers. Roughly spea…