Lower bounds for depth 4 formulas computing iterated matrix multiplication

DOI10.1145/2591796.2591824zbMath1315.68137OpenAlexW2136589970MaRDI QIDQ5259546

Nutan Limaye, Srikanth Srinivasan, Hervé Fournier, Guillaume Malod

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.2591824

zbMATH Keywords

lower boundsarithmetic circuitsshifted partial derivatives

Mathematics Subject Classification ID

Related Items (22)

Geometric aspects of iterated matrix multiplication ⋮ Lower Bounds for Sums of Powers of Low Degree Univariates ⋮ Lower bounds for depth-three arithmetic circuits with small bottom fanin ⋮ Lower bounds for the circuit size of partially homogeneous polynomials ⋮ On the limits of depth reduction at depth 3 over small finite fields ⋮ Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. ⋮ The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials ⋮ An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas ⋮ On the Power of Homogeneous Depth 4 Arithmetic Circuits ⋮ Unbalancing sets and an almost quadratic lower bound for syntactically multilinear arithmetic circuits ⋮ The Computational Power of Depth Five Arithmetic Circuits ⋮ Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications ⋮ Lower bounds by Birkhoff interpolation ⋮ Depth-4 lower bounds, determinantal complexity: a unified approach ⋮ Lower bounds for arithmetic circuits via the Hankel matrix ⋮ Arithmetic Circuits: A Chasm at Depth 3 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Algebraic Complexity Classes ⋮ A Selection of Lower Bounds for Arithmetic Circuits ⋮ On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models ⋮ Approaching the Chasm at Depth Four

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Lower bounds for depth 4 formulas computing iterated matrix multiplication