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

Formale Metadaten

Titel
Sparse Kindler-Safra Theorem via agreement theorems
Alternativer Titel
Kindler-Safra Theorem on the p-biased hypercube via agreement theorems
Serientitel
Anzahl der Teile
17
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
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.