We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Sparse Kindler-Safra Theorem via agreement theorems

Formal Metadata

Title
Sparse Kindler-Safra Theorem via agreement theorems
Alternative Title
Kindler-Safra Theorem on the p-biased hypercube via agreement theorems
Title of Series
Number of Parts
17
Author
Contributors
License
CC Attribution - NonCommercial - NoDerivatives 4.0 International:
You are free to use, copy, distribute and transmit the work or content in unchanged form for any legal and non-commercial purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Identifiers
Publisher
Release Date
Language

Content Metadata

Subject Area
Genre
Abstract
Nisan and Szegedy showed that low degree Boolean functions are juntas, namely, they depend only on a constant number of their variables. Kindler and Safra showed a robust version of the above: low degree functions which are almost Boolean are close to juntas. We study the same question on the p-biased hypercube, for very small p. The p-biased hypercube is a product probability space in which each coordinate is 1 with probability p and 0 otherwise. In this space most of the measure is on n-bit strings whose Hamming weight about pn << n. It turns out that here new phenomena emerge. For example, the function x_1 + ... + x_n=p (where x_i \in {0,1}) is close to Boolean but not close to a junta. We characterize low degree functions that are almost Boolean and show that they are close to a new class of functions which we call sparse juntas. An interesting aspect of our proof is a new proof paradigm that relies on a local to global agreement theorem. We cover the p-biased hypercube by many smaller dimensional copies of the uniform hypercube, and approximate our function locally via the standard Kindler-Safra theorem for constant p. We then stitch the local approximations together into one global function that is a sparse junta. The stitching is made feasible via a new local-to-global agreement theorem, which is an extension of the classical direct product results to larger dimensions. Time permitting, I'll show another application of this paradigm: extending the classical AKKLR low-degree tests to the p-biased hypercube.