17 citations · 54 across the 24 of their papers we have counts for
5 papers · 1 filter
Biased halfspaces, noise sensitivity, and local Chernoff inequalities
Nathan Keller, Ohad Klein
A halfspace is a function of the form , where . We show that if is a halfspace with $\mathb…
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 -uniform hypergraph on vertices that does not contain an `enlarged' copy of a fi…
Tight Bounds on Online Checkpointing Algorithms
Achiya Bar-On, Itai Dinur, Orr Dunkelman +4
The problem of online checkpointing is a classical problem with numerous applications which had been studied in various forms for almost 50 years. In the simplest version of this p…
Approximation of biased Boolean functions of small total influence by DNF's
Nathan Keller, Noam Lifshitz
The influence of the 'th coordinate on a Boolean function is the probability that flipping changes the value . The total influence…
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 of a set $A…