On the structure of Boolean functions with small spectral norm

DOI10.1145/2554797.2554803zbMATH Open1371.94704arXiv1304.0371OpenAlexW1951009694MaRDI QIDQ2012184FDOQ2012184

Ben Lee Volk, Avishay Tal, Amir Shpilka

Publication date: 28 July 2017

Published in: Computational Complexity, Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Abstract: In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of f is $|hatf{|}_1=su{m}_{alpha}|hatf(alpha)|$). Specifically, we prove the following results for functions $f:{0,1}^{n}o0,1$ with $|hatf{|}_1=A$. 1. There is a subspace $V$ of co-dimension at most $A^2$ such that $f{|}_V$ is constant. 2. f can be computed by a parity decision tree of size $2^{A^2}{n}^{2A}$. (a parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.) 3. If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth $A^{2}logs$. 4. For every $0<epsilon$ there is a parity decision tree of depth $O(A^2+log(1/epsilon))$ and size $2^{O(A^2)}cdotmin1/epsilo{n}^2,O(log(1/epsilon){)}^{2A}$ that epsilon-approximates f. Furthermore, this tree can be learned, with probability $1-delta$, using $poly(n,exp(A^2),1/epsilon,log(1/delta))$ membership queries. All the results above also hold (with a slight change in parameters) to functions $f:Z_p^{n}o0,1$.

Full work available at URL: https://arxiv.org/abs/1304.0371

zbMATH Keywords

decision treesspectral normparity decision treesanalysis of Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (94D10)

Cites Work

• A hierarchy of polynomial time lattice basis reduction algorithms
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• Evaluating Branching Programs on Encrypted Data
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• Learning Decision Trees Using the Fourier Spectrum
• Trapdoors for hard lattices and new cryptographic constructions
• Title not available (Why is that?)
• Analysis of Boolean Functions
• Some optimal inapproximability results
• Boolean functions with low average sensitivity depend on few coordinates
• Self-testing/correcting with applications to numerical problems
• Linearity testing in characteristic two
• (Leveled) fully homomorphic encryption without bootstrapping
• Constant depth circuits, Fourier transform, and learnability
• On lattices, learning with errors, random linear codes, and cryptography
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Bounds for Width Two Branching Programs
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• Complexity measures and decision tree complexity: a survey.
• Testing Fourier Dimensionality and Sparsity
• Title not available (Why is that?)
• The complexity of properly learning simple concept classes
• New lattice-based cryptographic constructions
• On the structure of Boolean functions with small spectral norm
• Boolean functions with small spectral norm
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• A quantitative version of the idempotent theorem in harmonic analysis
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
• Title not available (Why is that?)
• On the parity complexity measures of Boolean functions
• On the power of circuits with gates of low \(L_{1}\) norms.
• Communication is Bounded by Root of Rank

Cited In (27)

• Structure of Protocols for XOR Functions
• Title not available (Why is that?)
• Generic framework for key-guessing improvements
• Self-Predicting Boolean Functions
• On Boolean functions with several flat spectra
• A generalization of a theorem of Rothschild and van Lint
• Dimension-free bounds and structural results in communication complexity
• Property testing lower bounds via a generalization of randomized parity decision trees
• A structure theorem for Boolean functions with small total influences
• Структура спектров булевых функций
• A geometrical representation of the Fourier transformation of Boolean functions
• On (simple) decision tree rank
• Title not available (Why is that?)
• Boolean functions with small spectral norm, revisited
• Evaluating spectral norms for constant depth circuits with symmetric gates
• Fourier Sparsity of GF(2) Polynomials
• On the Fourier spectrum of symmetric Boolean functions
• On the Fourier spectrum of functions on Boolean cubes
• Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity
• LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
• On the structure of Boolean functions with small spectral norm
• Coset decision trees and the Fourier algebra
• Some problems of spectral analysis of random Boolean functions with constraints
• Title not available (Why is that?)
• Bounds in Cohen's idempotent theorem
• A generalization of a theorem of Rothschild and van Lint
• On the decision tree complexity of threshold functions

This page was built for publication: On the structure of Boolean functions with small spectral norm

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