On the structure of Boolean functions with small spectral norm (Q2012184): Difference between revisions

Latest revision as of 04:22, 14 July 2024

scientific article; zbMATH DE number 6721558

On the structure of boolean functions with small spectral norm

Language	Label	Description	Also known as
English	On the structure of Boolean functions with small spectral norm	scientific article; zbMATH DE number 6721558	On the structure of boolean functions with small spectral norm

Statements

instance of

scholarly article

0 references

title

On the structure of Boolean functions with small spectral norm (English)

0 references

On the structure of boolean functions with small spectral norm (English)

0 references

0 references

0 references

0 references

Computational Complexity

0 references

Proceedings of the 5th conference on Innovations in theoretical computer science

0 references

publication date

28 July 2017

0 references

19 May 2017

0 references

full work available at URL

https://arxiv.org/abs/1304.0371

0 references

zbMATH Keywords

analysis of Boolean functions

0 references

parity decision trees

0 references

spectral norm

0 references

decision trees

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Q4526993

0 references

Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)

0 references

Bounds for Width Two Branching Programs

0 references

Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP

0 references

(Leveled) fully homomorphic encryption without bootstrapping

0 references

Efficient Fully Homomorphic Encryption from (Standard) LWE

0 references

Fully homomorphic encryption using ideal lattices

0 references

Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness

0 references

Trapdoors for hard lattices and new cryptographic constructions

0 references

Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based

0 references

Evaluating Branching Programs on Encrypted Data

0 references

Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions

0 references

Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller

0 references

Public-key cryptosystems from the worst-case shortest vector problem

0 references

New lattice-based cryptographic constructions

0 references

On lattices, learning with errors, random linear codes, and cryptography

0 references

On lattices, learning with errors, random linear codes, and cryptography

0 references

A hierarchy of polynomial time lattice basis reduction algorithms

0 references

The complexity of properly learning simple concept classes

0 references

Linearity testing in characteristic two

0 references

Self-testing/correcting with applications to numerical problems

0 references

Complexity measures and decision tree complexity: a survey.

0 references

Boolean functions with low average sensitivity depend on few coordinates

0 references

On the power of circuits with gates of low \(L_{1}\) norms.

0 references

Testing Fourier Dimensionality and Sparsity

0 references

Boolean functions with small spectral norm

0 references

A quantitative version of the idempotent theorem in harmonic analysis

0 references

Some optimal inapproximability results

0 references

A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.

0 references

Learning Decision Trees Using the Fourier Spectrum

0 references

Constant depth circuits, Fourier transform, and learnability

0 references

Communication is Bounded by Root of Rank

0 references

Q4839061

0 references

Analysis of Boolean Functions

0 references

On the structure of Boolean functions with small spectral norm

0 references

Q5827965

0 references

On the parity complexity measures of Boolean functions

0 references

Identifiers

zbMATH Open document ID

1371.94704

0 references

1365.94682

0 references

DOI

10.1007/s00037-015-0110-y

0 references

10.1145/2554797.2554803

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2012184

@@ Property / cites work @@
+The complexity of properly learning simple concept classes
+Normal rank
@@ Property / cites work @@
+Linearity testing in characteristic two
@@ Property / cites work: Linearity testing in characteristic two / rank @@
+Normal rank
@@ Property / cites work @@
+Self-testing/correcting with applications to numerical problems
+Normal rank
@@ Property / cites work @@
+Complexity measures and decision tree complexity: a survey.
+Normal rank
@@ Property / cites work @@
+Boolean functions with low average sensitivity depend on few coordinates
+Normal rank
@@ Property / cites work @@
+On the power of circuits with gates of low \(L_{1}\) norms.
+Normal rank
@@ Property / cites work @@
+Testing Fourier Dimensionality and Sparsity
@@ Property / cites work: Testing Fourier Dimensionality and Sparsity / rank @@
+Normal rank
@@ Property / cites work @@
+Boolean functions with small spectral norm
@@ Property / cites work: Boolean functions with small spectral norm / rank @@
+Normal rank
@@ Property / cites work @@
+A quantitative version of the idempotent theorem in harmonic analysis
+Normal rank
@@ Property / cites work @@
+Some optimal inapproximability results
@@ Property / cites work: Some optimal inapproximability results / rank @@
+Normal rank
@@ Property / cites work @@
+A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
+Normal rank
@@ Property / cites work @@
+Learning Decision Trees Using the Fourier Spectrum
+Normal rank
@@ Property / cites work @@
+Constant depth circuits, Fourier transform, and learnability
+Normal rank
@@ Property / cites work @@
+Communication is Bounded by Root of Rank
@@ Property / cites work: Communication is Bounded by Root of Rank / rank @@
+Normal rank
@@ Property / cites work @@
+Q4839061
@@ Property / cites work: Q4839061 / rank @@
+Normal rank
@@ Property / cites work @@
+Analysis of Boolean Functions
@@ Property / cites work: Analysis of Boolean Functions / rank @@
+Normal rank
@@ Property / cites work @@
+On the structure of Boolean functions with small spectral norm
+Normal rank
@@ Property / cites work @@
+Q5827965
@@ Property / cites work: Q5827965 / rank @@
+Normal rank
@@ Property / cites work @@
+On the parity complexity measures of Boolean functions
+Normal rank