Constant depth circuits, Fourier transform, and learnability

DOI10.1145/174130.174138zbMath0781.94006OpenAlexW2042194938WikidataQ105824818 ScholiaQ105824818MaRDI QIDQ3140018

Nathan Linial, Yishay Mansour, Noam Nisan

Publication date: 9 December 1993

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/174130.174138

zbMATH Keywords

Fourier transformBoolean functionsharmonic analysislearning functions

Mathematics Subject Classification ID

Related Items (only showing first 100 items - show all)

Separation results for Boolean function classes ⋮ Uniform-distribution attribute noise learnability ⋮ Expander-based cryptography meets natural proofs ⋮ Boolean functions: influence, threshold and noise ⋮ On learning monotone DNF under product distributions ⋮ Spatio-spectral limiting on Boolean cubes ⋮ Polynomial-time algorithms for checking some properties of Boolean functions given by polynomials ⋮ The average sensitivity of bounded-depth circuits ⋮ Pseudo-average block sensitivity equals average sensitivity ⋮ On (Not) Computing the Möbius Function Using Bounded Depth Circuits ⋮ Learning functions of \(k\) relevant variables ⋮ Exploring crypto dark matter: new simple PRF candidates and their applications ⋮ Toward efficient agnostic learning ⋮ On the Fourier transform of a quantitative trait: implications for compressive sensing ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ On automorphic analogues of the Möbius randomness principle ⋮ Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)] ⋮ Approximating Boolean Functions with Depth-2 Circuits ⋮ Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ On the degree of Boolean functions as real polynomials ⋮ On small depth threshold circuits ⋮ Bounds on the Fourier coefficients of the weighted sum function ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Learning juntas in the presence of noise ⋮ On PAC learning algorithms for rich Boolean function classes ⋮ On the nonlinearity of the sequence of signs of Kloosterman sums ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ DNF sparsification and a faster deterministic counting algorithm ⋮ Learning intersections and thresholds of halfspaces ⋮ Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky ⋮ \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product ⋮ Proofs of Work from worst-case assumptions ⋮ An efficient membership-query algorithm for learning DNF with respect to the uniform distribution ⋮ On the power of circuits with gates of low \(L_{1}\) norms. ⋮ The Fourier spectrum of critical percolation ⋮ A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions ⋮ The learnability of quantum states ⋮ Learning random monotone DNF ⋮ Unnamed Item ⋮ Learning Boolean functions in \(AC^0\)on attribute and classification noise -- estimating an upper bound on attribute and classification noise ⋮ BKW meets Fourier new algorithms for LPN with sparse parities ⋮ Polynomial regression under arbitrary product distributions ⋮ Approximate location of relevant variables under the crossover distribution. ⋮ Computing Walsh coefficients from the algebraic normal form of a Boolean function ⋮ Quantitative relation between noise sensitivity and influences ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ Isomorphism testing of Boolean functions computable by constant-depth circuits ⋮ On polynomial approximations to AC ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration ⋮ Fourier analysis and large independent sets in powers of complete graphs ⋮ Decision Trees and Influences of Variables Over Product Probability Spaces ⋮ Pseudo-Derandomizing Learning and Approximation ⋮ Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates ⋮ Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity ⋮ Noise stability and correlation with half spaces ⋮ Local restrictions from the Furst-Saxe-Sipser paper ⋮ The communication complexity of addition ⋮ Existence and efficient construction of fast Fourier transforms on supersolvable groups ⋮ On the measure of intersecting families, uniqueness and stability ⋮ Bounded-depth circuits cannot sample good codes ⋮ On the structure of Boolean functions with small spectral norm ⋮ Fourier concentration from shrinkage ⋮ Unnamed Item ⋮ Exploring learnability between exact and PAC ⋮ On the Fourier spectrum of symmetric Boolean functions ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Testing monotone high‐dimensional distributions ⋮ Homomorphic Evaluation Requires Depth ⋮ On extremal \(k\)-CNF formulas ⋮ Sums with the Möbius function twisted by characters with powerful moduli ⋮ A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus$ via the Coin Problem] ⋮ Efficient learning algorithms yield circuit lower bounds ⋮ Learning large-alphabet and analog circuits with value injection queries ⋮ Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\). ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ Unnamed Item ⋮ Variable Influences in Conjunctive Normal Forms ⋮ Ehrenfeucht-Fraïssé Games on Random Structures ⋮ Learning with restricted focus of attention ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ Criticality of regular formulas ⋮ Prediction from partial information and hindsight, with application to circuit lower bounds ⋮ Fine-Grained Cryptography ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Cryptography with constant input locality ⋮ Proper learning of \(k\)-term DNF formulas from satisfying assignments ⋮ Synthesizers and their application to the parallel construction of pseudo-random functions ⋮ Average-Case Lower Bounds for Noisy Boolean Decision Trees ⋮ Quantum Hardness of Learning Shallow Classical Circuits ⋮ Learning DNF from random walks ⋮ Harmonicity and invariance on slices of the Boolean cube ⋮ Probability set functions ⋮ Circuit and decision tree complexity of some number theoretic problems ⋮ On the isomorphism problem for decision trees and decision lists ⋮ Pseudorandom Functions: Three Decades Later ⋮ A slight sharpening of LMN ⋮ Agnostically Learning Boolean Functions with Finite Polynomial Representation ⋮ Mining circuit lower bound proofs for meta-algorithms

This page was built for publication: Constant depth circuits, Fourier transform, and learnability