On the structure of Boolean functions with small spectral norm
From MaRDI portal
Publication:2012184
DOI10.1007/s00037-015-0110-yzbMath1371.94704arXiv1304.0371OpenAlexW1951009694MaRDI QIDQ2012184
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)
Full work available at URL: https://arxiv.org/abs/1304.0371
Related Items (16)
Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity ⋮ On (simple) decision tree rank ⋮ Generic framework for key-guessing improvements ⋮ Structure of Protocols for XOR Functions ⋮ Dimension-free bounds and structural results in communication complexity ⋮ Self-Predicting Boolean Functions ⋮ Property testing lower bounds via a generalization of randomized parity decision trees ⋮ Fourier Sparsity of GF(2) Polynomials ⋮ On the structure of Boolean functions with small spectral norm ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ A generalization of a theorem of Rothschild and van Lint ⋮ Unnamed Item ⋮ Bounds in Cohen's idempotent theorem ⋮ Boolean functions with small spectral norm, revisited ⋮ Coset decision trees and the Fourier algebra ⋮ On the decision tree complexity of threshold functions
Cites Work
- On the parity complexity measures of Boolean functions
- A hierarchy of polynomial time lattice basis reduction algorithms
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Boolean functions with low average sensitivity depend on few coordinates
- Self-testing/correcting with applications to numerical problems
- On the power of circuits with gates of low \(L_{1}\) norms.
- Complexity measures and decision tree complexity: a survey.
- A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
- On the structure of Boolean functions with small spectral norm
- A quantitative version of the idempotent theorem in harmonic analysis
- Boolean functions with small spectral norm
- The complexity of properly learning simple concept classes
- (Leveled) fully homomorphic encryption without bootstrapping
- Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
- Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
- Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
- Linearity testing in characteristic two
- Constant depth circuits, Fourier transform, and learnability
- Communication is Bounded by Root of Rank
- Trapdoors for hard lattices and new cryptographic constructions
- Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
- Evaluating Branching Programs on Encrypted Data
- Bounds for Width Two Branching Programs
- Learning Decision Trees Using the Fourier Spectrum
- Analysis of Boolean Functions
- Fully homomorphic encryption using ideal lattices
- Public-key cryptosystems from the worst-case shortest vector problem
- Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
- New lattice-based cryptographic constructions
- Some optimal inapproximability results
- Efficient Fully Homomorphic Encryption from (Standard) LWE
- Testing Fourier Dimensionality and Sparsity
- On lattices, learning with errors, random linear codes, and cryptography
- On lattices, learning with errors, random linear codes, and cryptography
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: On the structure of Boolean functions with small spectral norm
