A nonlinear lower bound for constant depth arithmetical circuits via the discrete uncertainty principle
| Autor: | Kenneth W. Regan, Maurice J. Jansen |
|---|---|
| Rok vydání: | 2008 |
| Předmět: |
Uncertainty principle
General Computer Science Arithmetical circuits 010102 general mathematics Cyclic group 0102 computer and information sciences Lower bounds 01 natural sciences Upper and lower bounds Matrix multiplication Convolution Constant depth bilinear circuits Theoretical Computer Science Combinatorics Computational complexity 010201 computation theory & mathematics Bounded function Arithmetic function 0101 mathematics Circulant matrix Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 409(3):617-622 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2008.09.029 |
| Popis: | We prove a superlinear lower bound on the size of a bounded depth bilinear arithmetical circuit computing cyclic convolution. Our proof uses the strengthening of the Donoho–Stark uncertainty principle [D.L. Donoho, P.B. Stark, Uncertainty principles and signal recovery, SIAM Journal of Applied Mathematics 49 (1989) 906–931] given by Tao [T. Tao, An uncertainty principle for cyclic groups of prime order, Mathematical Research Letters 12 (2005) 121–127], and a combinatorial lemma by Raz and Shpilka [R. Raz, A. Shpilka, Lower bounds for matrix product, in arbitrary circuits with bounded gates, SIAM Journal of Computing 32 (2003) 488–513]. This combination and an observation on ranks of circulant matrices, which we use to give a much shorter proof of the Donoho–Stark principle, may have other applications. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect