×
Borodin, A.; Razborov, A.; Smolensky, R.

On lower bounds for read-\(k\)-times branching programs. (English) Zbl 0777.68043

Comput. Complexity 3, No. 1, 1-18 (1993).
Proving nontrivial lower bounds for read-\(k\)-times switching networks (called also, nondeterministic branching programs) is a long standing problem. Such bounds were obtained only for oblivious read-\(k\)-times schemes. The authors consider another restriction: they require that no variable occurs more than \(k\) times on any path (whether or not consistent). An explicit Boolean function is exhibited which requires such “syntactic” read-\(k\)-times contact schemes of size \(\exp\left(\Omega\left({n\over 4^ kk^ 3}\right)\right)\). The proof is based on the following combinatorial result concerning Sylvester matrices, i.e. \(n\times n\) matrices \(A=\{a_{S,T}\}\) over \(GF(3)\) with rows and columns indexed by the subsets \(T,S\subseteq\{1,2,\dots,\log n\}\) and entries \(a_{S,T}=(-1)^{| S\cap T|}\).
It is proved that the rank of any \(u\times t\) submatrix of \(A\) is at least \(ut/(2n\ln(2n/u))\). For nonsyntactic read-\(k\)-times networks (with no restrictions on inconsistent paths) the problem remains open even for \(k=2\).
Reviewer: S.P.Yukna (Dortmund)

Cited in 3 Reviews
Cited in 55 Documents

MSC:

68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

read-\(k\)-times networks; generalized Fourier transforms; lower bounds; branching programs
Cite Review PDF
Full Text: DOI

References:

[1] K. Abrahamson, Generalized string matching.SIAM Journal on Computing 16 (1987), 1039-1051. · Zbl 0646.68079 · doi:10.1137/0216067
[2] K. Abrahamson, Time-space tradeoffs for algebraic problems on general sequential machines.JCSS 43 (1991), 269-289. · Zbl 0776.68052
[3] N. Alon andW. Maass, Meanders and their applications in lower bounds arguments.JCSS 37 (1988), 118-129. · Zbl 0664.68045
[4] L. Babai, P. Hajnal, E. Szemerédi, andG. Turan, A lower bound for read-once branching programs.JCSS 35 (1987), 153-162. · Zbl 0652.68062
[5] L. Babai, N. Nisan, and M. Szegedy, Multiparty protocols and logspacehard pseudorandom sequences. InProceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989, 1-11.
[6] L. Babai, P. Pudlák, V. Rödl, andE. Szemerédi, Lower bounds to the complexity of symmetric boolean functions.Theoretical Computer Science 74 (1990), 313-324. · Zbl 0701.68044 · doi:10.1016/0304-3975(90)90080-2
[7] D. Barrington and H. Straubing, Superlinear lower bounds for bounded-width branching programs. In6th Structure in Complexity Theory, 1991, 305-313. To appear inJCSS. · Zbl 0837.68056
[8] P. Beame, A general sequential time-space tradeoff for finding unique elements.SIAM Journal on Computing 20 (1991), 270-277. · Zbl 0722.68062 · doi:10.1137/0220017
[9] A. Borodin andS. Cook, A time-space tradeoff for sorting on a general sequential model of computation.SIAM Journal on Computing 11 (1982), 287-297. · Zbl 0478.68061 · doi:10.1137/0211022
[10] A. Chandra, M. Furst, and R. Lipton, Multiparty protocols. InProceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983, 94-99.
[11] P.E. Dunne, Lower bounds on the complexity of 1-time only branching programs. InProceedings of the FCT, Lecture Notes in Computer Science, 199, New York, 1985, Springer-Verlag, 90-99.
[12] M.A. Gavrilov,The Theory of Relay and Switching Circuits. Nauka, 1950. In Russian.
[13] N. Immerman, Nondeterministic space is closed under complementation.SIAM J. Comput. 17 (1988), 935-938. · Zbl 0668.68056 · doi:10.1137/0217058
[14] N. Jacobson,Basic Algebra I. W.H. Freeman and Company, New York, second edition, 1985.
[15] S. Jukna,A Note on Read-k Times Branching Programs. Technical Report 448, Universität Dortmund, 1992. · Zbl 0889.68021
[16] M. Krause, C. Meinel, and S. Waack, Separating complexity classes related to certain input oblivious logarithmic space bounded Turing machines. In4th Structure in Complexity Theory Conference, 1989, 240-259. · Zbl 0768.68017
[17] M. Krause, C. Meinel, andS. Waack, Separating the eraser turing machine classesL e ,N L e ,co-N L e andP e .Theoretical Computer Science 86 (1991), 267-275. · Zbl 0749.68036 · doi:10.1016/0304-3975(91)90021-S
[18] C. Y. Lee, Representation of switching cirucits by binary-decision programs.Bell System Technical Journal 38 (1959), 985-999.
[19] Y. Mansour, N. Nisan, and P. Tiwari, The computational complexity of universal hashing. InProceedings of the 22nd Annual ACM Symposium on the Theory of Computing, 1990, 235-243. · Zbl 0764.68080
[20] W. Masek,A Fast Algorithm for the String Editing Problem and Decision Graph Complexity. M.Sc. Thesis, Massachusetts Institute of Technology, Cambridge, 1976.
[21] E. A. Okolnishnikova, Lower bounds for branching programs computing characteristic functions of binary codes.Metody discretnogo analiza 51 (1991), 61-83, In Russian.
[22] C. H. Papadimitriou andM. Sipser, Communication complexity.JCSS 28 (1984), 260-269.
[23] P. Pudlák, On bounded depth circuits with arbitrary gates. Preprint.
[24] A. Razborov, Lower bounds for deterministic and nondeterministic branching programs. InProceedings of the 8th FCT, Lecture Notes in Computer Science, 529, New York/Berlin, 1991, Springer-Verlag, 47-60.
[25] W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities.JCSS 4 (1970), 177-192. · Zbl 0188.33502
[26] C. Shannon, A symbolic analysis of relay and switching networks.Transactions of American Institute of Electrical Engineers 57 (1938), 713-723. · doi:10.1109/T-AIEE.1938.5057767
[27] J. Simon and M. Szegedy, Lower bound techniques for read only once branching programs. Preprint, 1990. · Zbl 0801.68077
[28] R. Szelepcsényi, The method of forcing for nondeterministic automata.Bull. European Assoc. Theoret. Comput. Sci. 33 (1987), 96-100. · Zbl 0664.68082
[29] I. Wegener,The Complexity of Boolean Functions. Wiley-Teubner Series in Comp. Sci., New York/Stuttgart, 1987. · Zbl 0623.94018
[30] Y. Yesha, Time-space tradeoffs for matrix multiplication and the discrete Fourier transform on any general sequential random-access computer.SIAM Journal on Computing 29 (1984), 183-197. · Zbl 0577.68060
[31] S. ?ák, An exponential lower bound for one-time-only branching programs. InProceedings of the 11th MFCT, Lecture Notes in Computer Science, 176, New York/Berlin, 1984, Springer-Verlag, 562-566.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.