Anna Gál
Kristoffer Arnsfelt Hansen
ABSTRACT
We bound the minimum number w of wires needed to compute any (asymptotically good) error-correcting code C:{0,1}Ω(n) -> {0,1}n with minimum distance Ω(n), using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are: (1) If d=2 then w = Θ(n ({log n/ log log n})2). (2) If d=3 then w = Θ(n lg lg n). (3) If d=2k or d=2k+1 for some integer k ≥ 2 then w = Θ(n λk(n)), where λ1(n)=⌈ log n⌉, λi+1(n)= λi*(n), and the * operation gives how many times one has to iterate the function λi to reach a value at most 1 from the argument n. (4) If d=log* n then w=O(n).
For depth d=2, our Ω(n (log n/log log n)2) lower bound gives the largest known lower bound for computing any linear map.
Using a result by Ishai, Kushilevitz, Ostrovsky, and Sahai (2008), we also obtain similar bounds for computing pairwise-independent hash functions.
Our lower bounds are based on a superconcentrator-like condition that the graphs of circuits computing good codes must satisfy. This condition is provably intermediate between superconcentrators and their weakenings considered before.
Supplemental Material
- M. Ajtai, J. Komlós, and E. Szemerédi. Deterministic simulation in LOGSPACE. In 19th Annual ACM Symposium on Theory of Computing (STOC'87), pages 132--140. ACM Press, 1987. Google Scholar
Digital Library
- N. Alon, J. Bruck, J. Naor, M. Naor, and R. M. Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38(2):509--516, 1992. Google ScholarDigital Library
- N. Alon and P. Pudlák. Superconcentrators of depth 2 and 3; odd levels help (rarely). Journal of Computer and System Sciences, 48(1):194--202, 1994. Google ScholarDigital Library
- L. Bazzi, M. Mahdian, and D. A. Spielman. The minimum distance of turbo-like codes. IEEE Transactions on Information Theory, 55(1):6--15, 2009. Google ScholarDigital Library
- L. Bazzi and S. K. Mitter. Encoding complexity versus minimum distance. IEEE Transactions on Information Theory, 51(6):2103--2112, 2005. Google ScholarDigital Library
- R. Boppana. The average sensitivity of bounded-depth circuits. Information Processing Letters, 63(5):257--261, 1997. Google ScholarDigital Library
- H. Buhrman, P. B. Miltersen, J. Radhakrishnan, and S. Venkatesh. Are bitvectors optimal? SIAM Journal on Computing, 31(6):1723--1744, 2002. Google ScholarDigital Library
- A. K. Chandra, S. Fortune, and R. J. Lipton. Lower bounds for constant depth circuits for prefix problems. In 10th Colloquium on Automata, Languages and Programming (ICALP'83), volume 154 of LNCS, pages 109--117. Springer, 1983. Google ScholarDigital Library
- A. K. Chandra, S. Fortune, and R. J. Lipton. Unbounded fan-in circuits and associative functions. Journal of Computer and System Sciences, 30(2):222--234, 1985.Google ScholarCross Ref
- B. Chor, O. Goldreich, J. Håstad, J. Friedman, S. Rudich, and R. Smolensky. The bit extraction problem or t-resilient functions. In 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS'85), pages 396--407. IEEE Computer Society Press, 1985. Google ScholarDigital Library
- D. Dolev, C. Dwork, N. Pippenger, and A. Wigderson. Superconcentrators, generalizers and generalized connectors with limited depth. In 15th Annual ACM Symposium on Theory of Computing (STOC'83), pages 42--51. ACM Press, 1983. Google ScholarDigital Library
- C. Dutta and J. Radhakrishnan. Tradeoffs in depth-two superconcentrators. In 23rd Annual Symposium on Theoretical Aspects of Computer Science (STACS'06), volume 3884 of LNCS, pages 372--383. Springer, 2006. Google ScholarDigital Library
- L. R. Ford and D. R. Fulkerson. Flows in networks. Princeton University Press, 1962.Google Scholar
- S. Gelfand, R. Dobrushin, and M. Pinsker. On the complexity of coding. In 2nd International Symposium on Information Theory, pages 177--184. Akademiai Kiado, 1973.Google Scholar
- V. Guruswami and P. Indyk. Expander-based constructions of efficiently decodable codes. In 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS'01), pages 658--667. IEEE Computer Society Press, 2001. Google ScholarDigital Library
- G. Hansel. Nombre minimal de contacts de fermature nécessaires pour réaliser une fonction booléenne symétrique de n variables. C. R. Acad. Sci. Paris, 258:6037--6040, 1964.Google Scholar
- Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai. Cryptography with constant computational overhead. In 14th Annual ACM Symposium on Theory of Computing (STOC'08), pages 433--442. ACM Press, 2008. Google ScholarDigital Library
- S. Jukna. Boolean Function Complexity: Advances and Frontiers, volume 27 of Algorithms and Combinatorics. Springer, 2012. Google ScholarDigital Library
- N. Kahale. Eigenvalues and expansion of regular graphs. Journal of the ACM, 42(5):1091--1106, 1995. Google ScholarDigital Library
- N. Linial, Y. Mansour, and N. Nisan. Constant depth circuits, Fourier transform, and learnability. Journal of the ACM, 40(3):607--620, 1993. Google ScholarDigital Library
- S. Lovett and E. Viola. Bounded-depth circuits cannot sample good codes. In 25th Annual IEEE Conference on Computational Complexity (CCC'10), pages 243--251. IEEE Computer Society Press, 2010. Google ScholarDigital Library
- Y. Mansour, N. Nisan, and P. Tiwari. The computational complexity of universal hashing. Theoretical Computer Science, 107(1):121--133, 1993. Google ScholarDigital Library
- P. B. Miltersen. Error correcting codes, perfect hashing circuits, and deterministic dynamic dictionaries. In 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'98), pages 556--563. ACM Press, 1998. Google ScholarDigital Library
- J. G. Oxley. Matroid theory. Oxford University Press, 1992.Google Scholar
- H. Perfect. Applications of Menger's graph theorem. Journal of Mathematical Analysis and Applications, 22:96--111, 1968.Google ScholarCross Ref
- P. Pudlák. Communication in bounded depth circuits. Combinatorica, 14(2):203--216, 1994.Google ScholarCross Ref
- P. Pudlák and V. Rödl. Some combinatorial-algebraic problems from complexity theory. Discrete Mathematics, 136(1--3):253--279, 1994. Google ScholarDigital Library
- J. Radhakrishnan and A. Ta-Shma. Bounds for dispersers, extractors, and depth-two superconcentrators. SIAM Journal on Discrete Mathematics, 13(1):2--24, 2000. Google ScholarDigital Library
- D. Spielman. Computationally Efficient Error-Correcting Codes and Holographic Proofs. PhD thesis, Massachusetts Institute of Technology, 1995. Google ScholarDigital Library
- D. A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723--1731, 1996. Google ScholarCross Ref
- L. Valiant. On non-linear lower bounds in computational complexity. In 7th Annual ACM Symposium on Theory of Computing (STOC'75), pages 45--53. ACM Press, 1975. Google ScholarDigital Library
- E. Viola. The complexity of constructing pseudorandom generators from hard functions. Computational Complexity, 13(3--4):147--188, 2004. Google ScholarDigital Library
- D. J. Welsh. Matroid theory. Academic Press, London, 1976.Google Scholar
Index Terms
- Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
Recommendations
Tight Bounds on Computing Error-Correcting Codes by Bounded-Depth Circuits With Arbitrary Gates
We bound the minimum number $w$ of wires needed to compute any (asymptotically good) error-correcting code $C:\{0,1\}^{\Omega (n)}\to\{0,1\}^{n}$ with minimum distance $\Omega (n)$, using unbounded fan-in circuits of depth $d$ with arbitrary gates. Our ...
Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates
We prove superlinear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth ...
Tight Bounds for Adopt-Commit Objects
We give matching upper and lower bounds of $\varTheta(\min(\frac{\log m}{\log \log m},\, n))$ for the individual step complexity of a wait-free m -valued adopt-commit object implemented using multi-writer registers for n anonymous processes. While the upper bound is deterministic, the lower bound ...
Comments