Constant depth circuits, Fourier transform, and learnability
From MaRDI portal
Recommendations
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
- Hardness amplification and the approximate degree of constant-depth circuits
- On the Fourier spectrum of monotone functions
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^0\)
- Learning and lower bounds for AC\(^{0}\) with threshold gates
Cited in
(only showing first 100 items - show all)- Learning large-alphabet and analog circuits with value injection queries
- Cryptography with constant input locality
- Learning with restricted focus of attention
- Synthesizers and their application to the parallel construction of pseudo-random functions
- Probability set functions
- Toward efficient agnostic learning
- On the degree of Boolean functions as real polynomials
- Reflections on ``Representations of sets of Boolean functions by commutative rings by Roman Smolensky
- 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.
- Approximate location of relevant variables under the crossover distribution.
- A slight sharpening of LMN
- Boolean functions: influence, threshold and noise
- Exploring crypto dark matter: new simple PRF candidates and their applications
- On automorphic analogues of the Möbius randomness principle
- \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
- Proofs of Work from worst-case assumptions
- Noise stability and correlation with half spaces
- Exploring learnability between exact and PAC
- Interpolation of the discrete logarithm in \(\mathbb{F}_{q}\) by Boolean functions and by polynomials in several variables modulo a divisor of \(q-1\).
- Circuit and decision tree complexity of some number theoretic problems
- Uniform-distribution attribute noise learnability
- On learning monotone DNF under product distributions
- Learning functions of \(k\) relevant variables
- Evaluating spectral norms for constant depth circuits with symmetric gates
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
- Polynomial regression under arbitrary product distributions
- \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration
- Fourier concentration from shrinkage
- Separation results for Boolean function classes
- Expander-based cryptography meets natural proofs
- On the Fourier transform of a quantitative trait: implications for compressive sensing
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Prediction from partial information and hindsight, with application to circuit lower bounds
- Proper learning of \(k\)-term DNF formulas from satisfying assignments
- Harmonicity and invariance on slices of the Boolean cube
- On the isomorphism problem for decision trees and decision lists
- Mining circuit lower bound proofs for meta-algorithms
- Bounds on the Fourier coefficients of the weighted sum function
- Learning juntas in the presence of noise
- On PAC learning algorithms for rich Boolean function classes
- Quantitative relation between noise sensitivity and influences
- Fourier analysis and large independent sets in powers of complete graphs
- On extremal \(k\)-CNF formulas
- Efficient learning algorithms yield circuit lower bounds
- Learning DNF from random walks
- Alternation, sparsity and sensitivity: bounds and exponential gaps
- Exact learning from an honest teacher that answers membership queries
- A quantum algorithm to estimate the Gowers \(U_2\) norm and linearity testing of Boolean functions
- BKW meets Fourier new algorithms for LPN with sparse parities
- Homomorphic evaluation requires depth
- Pseudorandom generators and learning algorithms for \(\mathrm{AC}^0\)
- Fine-Grained Cryptography
- 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
- Learning \(\mathrm{AC}^0\) under \(k\)-dependent distributions
- Locality of Queries Definable in Invariant First-Order Logic with Arbitrary Built-in Predicates
- Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
- On (not) computing the Möbius function using bounded depth circuits
- Fast pseudorandom functions based on expander graphs
- Approximating Boolean functions with depth-2 circuits
- The learnability of quantum states
- DNF sparsification and a faster deterministic counting algorithm
- Decision Trees and Influences of Variables Over Product Probability Spaces
- Learning and lower bounds for AC\(^{0}\) with threshold gates
- Testing monotone high‐dimensional distributions
- Variable Influences in Conjunctive Normal Forms
- Ehrenfeucht-Fraïssé Games on Random Structures
- Average-Case Lower Bounds for Noisy Boolean Decision Trees
- Breaking the Minsky--Papert Barrier for Constant-Depth Circuits
- Submodular functions: learnability, structure, and optimization
- Average-case lower bounds and satisfiability algorithms for small threshold circuits
- Computing Walsh coefficients from the algebraic normal form of a Boolean function
- On polynomial approximations to \(\mathrm{AC}^0\)
- What circuit classes can be learned with non-trivial savings?
- PAC learning depth-3 \(\mathrm{AC}^0\) circuits of bounded top fanin
- Isomorphism testing of Boolean functions computable by constant-depth circuits
- scientific article; zbMATH DE number 774007 (Why is no real title available?)
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- Quantum hardness of learning shallow classical circuits
- Agnostic Learning from Tolerant Natural Proofs
- Randomness extraction in \(\mathsf{AC}^0\) and with small locality
- Pseudo-derandomizing learning and approximation
- Pseudorandom functions: three decades later
- On small depth threshold circuits
- AC0 unpredictability
- scientific article; zbMATH DE number 7528580 (Why is no real title available?)
- Expander-Based Cryptography Meets Natural Proofs
- Criticality of regular formulas
- Joint data and key distribution of simple, multiple, and multidimensional linear cryptanalysis test statistic and its impact to data complexity
- Tight bounds on the Fourier spectrum of \(\mathsf{AC}^0\)
- scientific article; zbMATH DE number 7250141 (Why is no real title available?)
- Agnostically learning Boolean functions with finite polynomial representation
- Local restrictions from the Furst-Saxe-Sipser paper
- The communication complexity of addition
- Sums with the Möbius function twisted by characters with powerful moduli
- On the nonlinearity of the sequence of signs of Kloosterman sums
- scientific article; zbMATH DE number 7053345 (Why is no real title available?)
This page was built for publication: Constant depth circuits, Fourier transform, and learnability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3140018)
