Structure Of Boolean Almost Low Degree Functions On The Biased Cube

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,600
Published on ● Video Link: https://www.youtube.com/watch?v=4Rd11uLCVro


Duration: 57:20
525 views
7

Yuval Filmus (Technion - Israel Institute of Technology)
https://simons.berkeley.edu/talks/yuval-filmus-technion-israel-institute-technology-2023-07-28
Structural Results

The FKN theorem states that if a Boolean function on the Boolean cube is close to degree 1, then it is close to a dictator.
Similarly, the Kindlerโ€“Safra theorem states that if a Boolean function on the Boolean cube is close to degree d, then it is close to a junta.

The picture becomes more interesting when we study functions on the p-biased Boolean cube.
If a Boolean function is ๐œ€-close to degree 1, then (up to negation) it is O(๐œ€)-close to a maximum of O(โˆš๐œ€/p+1) coordinates, and so O(โˆš๐œ€+p)-close to a constant function.
A similar statement holds for functions close to degree d, but the corresponding structure is more complicated.

Another setting we might discuss is functions on the symmetric group.
If a Boolean function is ๐œ€-close to degree 1, then it is O(โˆš๐œ€)-close to a dictator (suitably defined), and O(๐œ€)-close (up to negation) to a union of โ€œmostly disjointโ€ cosets.
A similar statement should hold for degree d, where the function ought to be close to a (suitably defined) decision tree of depth poly(d).

Joint work with Irit Dinur (Weizmann Institute) and Prahladh Harsha (TIFR).



Other Videos By Simons Institute for the Theory of Computing


2023-08-15Panel Discussion
2023-08-14An observation on Generalization
2023-08-14Towards Reliable Use of Large Language Models: Better Detection, Consistency, and Instruction-Tuning
2023-08-14Possible Impossibilities and Impossible Possibilities
2023-08-14Sparks of Artificial General Intelligence
2023-08-10Generating Approximate Ground States of Molecules Using Quantum Machine Learning
2023-08-10Quantum-Classical Cross-Correlations and the Post-selection Problem
2023-08-10Industry Applications of Hamiltonian Simulation and Beyond
2023-08-10What Can I Do With a Noisy Quantum Computer?
2023-08-10Quantum Machine Learning in the NISQ Era
2023-07-29Structure Of Boolean Almost Low Degree Functions On The Biased Cube
2023-07-29Correspondence Colouring of Random Graphs
2023-07-28Structures in Random Graphs: New Connections
2023-07-28Noncommutativity and Rounding Schemes for Combinatorial Optimization Parts 1 & 2
2023-07-28Some Remarks About Quantum and Classical Local Hamiltonian Optimization and SDP Rounding
2023-07-28Structure of Communication | Richard M. Karp Distinguished Lecture
2023-07-28Randomized versus Deterministic Decision Tree Size
2023-07-28Fourier Growth of XOR-Fibers of Communication Protocols
2023-07-27Sign-rank vs Margin
2023-07-27Tight Space Complexity of the Coin Problem
2023-07-27A New Upper Bound for the Heilbronn Triangle Problem


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Structural Results
Yuval Filmus