Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests

DOI10.1137/1.9781611975482.128MaRDI QIDQ5236315zbMATH OpenOpenAlexFDO

Authors Irit Dinur, Yuval Filmus, Prahladh Harsha

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.128

Mathematics Subject Classification ID

Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• FKN theorem on the biased cube
• A structure theorem for almost low-degree functions on the slice
• A simple reduction from a biased measure on the discrete cube to the uniform measure
• Approximation of biased Boolean functions of small total influence by DNFs
• Friedgut-Kalai-Naor theorem for slices of the Boolean cube

Cited in

(11)

• A structure theorem for almost low-degree functions on the slice
• Boolean constant degree functions on the slice are juntas
• FKN theorem on the biased cube
• A simple reduction from a biased measure on the discrete cube to the uniform measure
• Boolean function analysis on high-dimensional expanders
• Boolean functions on \(S_n\) which are nearly linear
• On approximability of satisfiable k-CSPs. III
• Boolean function analysis on high-dimensional expanders
• Sparse juntas on the biased hypercube
• Baby PIH: Parameterized inapproximability of min CSP
• Agreement tests on graphs and hypergraphs

This page was built for publication: Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236315)