A super-polynomial lower bound for regular arithmetic formulas
From MaRDI portal
Recommendations
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
- Tensor-rank and lower bounds for arithmetic formulas
- An exponential lower bound for homogeneous depth four arithmetic formulas
- Tensor-rank and lower bounds for arithmetic formulas
- The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
Cites work
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(30)- Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits
- Multi-k-ic depth three circuit lower bound
- Lower bounds for arithmetic circuits via the Hankel matrix
- Depth-4 lower bounds, determinantal complexity: a unified approach
- Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
- Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees
- On the limits of depth reduction at depth 3 over small finite fields
- Arithmetic circuits: a chasm at depth 3
- A Selection of Lower Bounds for Arithmetic Circuits
- The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
- Lower bounds for depth-4 formulas computing iterated matrix multiplication
- An exponential lower bound for homogeneous depth four arithmetic formulas
- On the power of homogeneous depth 4 arithmetic circuits
- Lower bounds for depth-three arithmetic circuits with small bottom fanin
- Subexponential size hitting sets for bounded depth multilinear formulas
- Lower bounds for sums of powers of low degree univariates
- The limits of depth reduction for arithmetic formulas: it's all about the top fan-in
- On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
- The computational power of depth five arithmetic circuits
- On the Symmetries of and Equivalence Test for Design Polynomials.
- A super-quadratic lower bound for depth four arithmetic circuits
- Lower bounds by Birkhoff interpolation
- scientific article; zbMATH DE number 7204375 (Why is no real title available?)
- scientific article; zbMATH DE number 7250153 (Why is no real title available?)
- Approaching the chasm at depth four
- Multi-linear formulas for permanent and determinant are of super-polynomial size
- Lower bounds for set-multilinear branching programs
- Towards deterministic algorithms for constant-depth factors of constant-depth circuits
- On the existence of algebraic natural proofs
- Lower bounds for set-multilinear branching programs
This page was built for publication: A super-polynomial lower bound for regular arithmetic formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259548)
