Nathan Keller

activity

20062026

most citedGeometric influences

17 citations · 54 across the 24 of their papers we have counts for

collaborators

Showing 2017 · math.COShow all

4 papers · 2 filters

math.CO2017

Biased halfspaces, noise sensitivity, and local Chernoff inequalities

Nathan Keller, Ohad Klein

A halfspace is a function $f : {- 1, 1}^{n} \to {0, 1}$ of the form $f (x) = 1 (a \cdot x > t)$ , where $\sum_{i} a_{i}^{2} = 1$ . We show that if $f$ is a halfspace with $\mathb…

math.CO2017★ 3 cited

The Junta Method for Hypergraphs and the Erdős-Chvátal Simplex Conjecture

Nathan Keller, Noam Lifshitz

Numerous problems in extremal hypergraph theory ask to determine the maximal size of a $k$ -uniform hypergraph on $n$ vertices that does not contain an `enlarged' copy $H^{+}$ of a fi…

math.CO2017★ 5 cited

Approximation of biased Boolean functions of small total influence by DNF's

Nathan Keller, Noam Lifshitz

The influence of the $k$ 'th coordinate on a Boolean function $f : {0, 1}^{n} \to {0, 1}$ is the probability that flipping $x_{k}$ changes the value $f (x)$ . The total influence…

math.CO2017

On a biased edge isoperimetric inequality for the discrete cube

David Ellis, Nathan Keller, Noam Lifshitz

The `full' edge isoperimetric inequality for the discrete cube (due to Harper, Bernstein, Lindsay and Hart) specifies the minimum size of the edge boundary $\partial A$ of a set $A…