Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors
From MaRDI portal
Publication:5025767
DOI10.1137/19M1257792zbMath1499.94078arXiv1803.10868WikidataQ114074255 ScholiaQ114074255MaRDI QIDQ5025767
Publication date: 3 February 2022
Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1803.10868
Related Items
Randomized numerical linear algebra: Foundations and algorithms, Marchenko–Pastur law with relaxed independence conditions, A theory of capacity and sparse neural encoding, Computing characteristic polynomials of hyperplane arrangements with symmetries, The quarks of attention: structure and capacity of neural attention building blocks, Exact hyperplane covers for subsets of the hypercube, Sparse random tensors: concentration, regularization and applications, On neuronal capacity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Tensor Decompositions and Applications
- Adjacency matrices of random digraphs: singularity and anti-concentration
- Inverse Littlewood-Offord problems and the singularity of random symmetric matrices
- On the least singular value of random symmetric matrices
- The limit of the smallest singular value of random matrices with i.i.d. entries
- On the singularity of adjacency matrices for random regular digraphs
- Invertibility of sparse non-Hermitian matrices
- Optimal inverse Littlewood-Offord theorems
- No-gaps delocalization for general random matrices
- Perceptrons of large weight
- Hanson-Wright inequality and sub-Gaussian concentration
- The threshold order of a Boolean function
- Random symmetric matrices are almost surely nonsingular.
- Smallest singular value of random matrices with independent columns
- The least singular value of a random square matrix is O\((n ^{- 1/2})\)
- Random matrices: The distribution of the smallest singular values
- On the singularity probability of discrete random matrices
- Group actions and learning for a family of automata
- On subspaces spanned by random selections of \(\pm 1\) vectors
- Solution of the Littlewood-Offord problem in high dimensions
- Computing Boolean functions by polynomials and threshold circuits
- The expressive power of voting polynomials
- Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- PP is closed under intersection
- Classification by polynomial surfaces
- A new look at independence
- Bilinear and quadratic variants on the Littlewood-Offord problem
- A structure theorem for poorly anticoncentrated polynomials of Gaussians and applications to the study of polynomial threshold functions
- The capacity of feedforward neural networks
- Dimension reduction by random hyperplane tessellations
- Singularity of random Bernoulli matrices
- Invertibility of random matrices: norm of the inverse
- Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
- Extremal properties of polynomial threshold functions
- The Littlewood-Offord problem and invertibility of random matrices
- Rademacher series and decoupling
- The smallest singular value of random rectangular matrices with no moment assumptions on entries
- Discrete Mathematics of Neural Networks
- Rank-One Approximation to High Order Tensors
- Anti-concentration for polynomials of independent random variables
- Reed–Muller Codes for Random Erasures and Errors
- A sharp inverse Littlewood-Offord theorem
- Non-asymptotic theory of random matrices: extreme singular values
- On random ±1 matrices: Singularity and determinant
- On the singularity probability of random Bernoulli matrices
- On minimal singular values of random matrices with correlated entries
- Harmonic Analysis of Polynomial Threshold Functions
- An enumerative problem in threshold logic
- Decoupling and Partial Independence
- Smallest singular value of a random rectangular matrix
- Separating ${AC}^0$ from Depth-2 Majority Circuits
- Neural networks, orientations of the hypercube, and algebraic threshold functions
- A Problem in Geometric Probability.
- Methods OI geometry and probabilistic combinatorics in threshold logic
- Facing up to arrangements: face-count formulas for partitions of space by hyperplanes
- Estimates for the concentration function of combinatorial number theory and probability
- Asymptotic expansions for bivariate von Mises functionals
- On the number of threshold functions
- On the Size of Weights for Threshold Gates
- Sample Covariance Matrices of Heavy-Tailed Distributions
- High-Dimensional Probability
- On the Probability That a Random ± 1-Matrix Is Singular
- Analysis of Boolean Functions
- On the Singularity of Random Combinatorial Matrices
- Symmetric Tensors and Symmetric Tensor Rank
- From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
- Über ein Problem von Erdös und Moser
- Polynomial bounds for decoupling, with applications
- Invertibility of random matrices: Unitary and orthogonal perturbations
- Invertibility of symmetric random matrices
- Singular 0/1-Matrices, and the Hyperplanes Spanned by Random 0/1-Vectors
- On Complete Sets of Logic Primitives
- Enumeration of Seven-Argument Threshold Functions
- Partitions ofN-Space by Hyperplanes
- [https://portal.mardi4nfdi.de/wiki/Publication:5731810 On the foundations of combinatorial theory I. Theory of M�bius Functions]
- Partition of Space
- On a lemma of Littlewood and Offord
- A logical calculus of the ideas immanent in nervous activity
- New degree bounds for polynomial threshold functions
- Arrangements of hyperplanes and the number of threshold functions
