A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle
From MaRDI portal
Publication:2378541
DOI10.1016/j.tcs.2008.09.029zbMath1156.68024OpenAlexW2027797312MaRDI QIDQ2378541
Maurice Jansen, Kenneth W. Regan
Publication date: 8 January 2009
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2008.09.029
Cites Work
- Unnamed Item
- The complexity of partial derivatives
- Communication in bounded depth circuits
- Chebotarëv and his density theorem
- Lower bounds for polynomial evaluation and interpolation problems
- An uncertainty principle for cyclic groups of prime order
- Uncertainty Principles and Signal Recovery
- Lower bounds on the bounded coefficient complexity of bilinear maps
- On the Complexity of Matrix Product
- Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
- An Algorithm for the Machine Calculation of Complex Fourier Series
- Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform