On the structure of Boolean functions with small spectral norm

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

Authors: Amir Shpilka, Avishay Tal, Ben Lee Volk 

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

Recommendations

• Boolean functions with small spectral norm, revisited
• Spectral norm of symmetric functions
• Boolean functions with small spectral norm
• On the Fourier spectrum of monotone functions

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

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)