A super-polynomial lower bound for regular arithmetic formulas

DOI10.1145/2591796.2591847zbMath1315.68140OpenAlexW2069546133MaRDI QIDQ5259548

Ramprasad Saptharishi, Chandan Saha, Neeraj Kayal

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsarithmetic circuitsVPVNPdepth-4 circuits

Mathematics Subject Classification ID

Related Items (25)

Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits ⋮ Lower Bounds for Sums of Powers of Low Degree Univariates ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ Subexponential size hitting sets for bounded depth multilinear formulas ⋮ The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In ⋮ On the limits of depth reduction at depth 3 over small finite fields ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ Lower Bounds for Depth-4 Formulas Computing Iterated Matrix Multiplication ⋮ Multi-\(k\)-ic depth three circuit lower bound ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ Lower bounds by Birkhoff interpolation ⋮ Depth-4 lower bounds, determinantal complexity: a unified approach ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Unnamed Item ⋮ On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree ⋮ Lower bounds for arithmetic circuits via the Hankel matrix ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Unnamed Item ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ On the Symmetries of and Equivalence Test for Design Polynomials. ⋮ A super-quadratic lower bound for depth four arithmetic circuits ⋮ Lower bounds and PIT for non-commutative arithmetic circuits with restricted parse trees ⋮ Approaching the Chasm at Depth Four

Uses Software

• SuLQ

Cites Work

• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography
• Unnamed Item
• Unnamed Item

This page was built for publication: A super-polynomial lower bound for regular arithmetic formulas