Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity.

*(English)*Zbl 1006.68051Summary: The rigidity of a matrix measures the number of entries that must be changed in order to reduce its rank below a certain value. The known lower bounds on the rigidity of explicit matrices are very weak. It is known that stronger lower bounds would have important consequences in complexity theory. We consider some restricted variants of the rigidity problem over the complex numbers. Using spectral methods, we derive lower bounds on these variants. Two applications of such restricted variants are given. First, we show that our lower bound on a variant of rigidity implies lower bounds on size-depth trade-offs for arithmetic circuits with bounded coefficients computing linear transformations. These bounds generalize a result of Nisan and Wigderson. The second application is conditional; we show that it would suffice to prove lower bounds on certain restricted forms of rigidity to conclude several separation results such as separating the analogs of PH and PSPACE in the model of two-party communication complexity. Our results complement and strengthen a result of Razborov.

We introduce a combinatorial complexity measure, called AC\(^0\)-dimension, of sets of Boolean functions. While high rigidity implies large AC\(^0\)-dimension, large AC\(^0\)-dimension for explicit sets would already give explicit languages outside the analog of PH in two-party communication complexity. Moreover, the concept of AC\(^0\)-dimension allows us to formulate interesting combinatorial problems which may be easier than rigidity and which would still have consequences to separation questions in communication complexity.

We introduce a combinatorial complexity measure, called AC\(^0\)-dimension, of sets of Boolean functions. While high rigidity implies large AC\(^0\)-dimension, large AC\(^0\)-dimension for explicit sets would already give explicit languages outside the analog of PH in two-party communication complexity. Moreover, the concept of AC\(^0\)-dimension allows us to formulate interesting combinatorial problems which may be easier than rigidity and which would still have consequences to separation questions in communication complexity.

Reviewer: Reviewer (Berlin)

##### MSC:

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

PDF
BibTeX
XML
Cite

\textit{S. V. Lokam}, J. Comput. Syst. Sci. 63, No. 3, 449--473 (2001; Zbl 1006.68051)

Full Text:
DOI

##### References:

[1] | N. Alon, On the rigidity of an Hadamard matrix, manuscript, 1994. |

[2] | N. Alon, P. Frankl, and V. Rödl, Geometric realizations of set systems and probabilistic communication complexity, in 26th IEEE FOCS (1985), pp. 277-280. |

[3] | L. Babai, Trading group theory for randomness, in, 17th ACM STOC (1985), pp, 421, -, 429. |

[4] | Babai, L.; Moran, S., Arthur-merlin games: A randomized proof system, and a hierarchy of complexity classes, J. comput. system sci., 36, 254-276, (1988) · Zbl 0652.03029 |

[5] | Bürgisser, P.; Clausen, M.; Shokrollahi, M.A., Algebraic complexity theory, Grundlehren der mathematischen wissenschaften, (1997), Springer-Verlag New York · Zbl 1087.68568 |

[6] | Babai, L.; Fortnow, L., Arithmetization: A new method in structural complexity theory, Comput. complexity, 1, 41-66, (1991) · Zbl 0774.68040 |

[7] | L. Babai, P. Frankl, and J. Simon, Complexity classes in communication complexity theory, in 27th IEEE FOCS (1986), pp. 337-347. |

[8] | Borodin, A.; Munro, I., The computational complexity of algebraic and numeric problems, (1975), American Elsevier New York · Zbl 0404.68049 |

[9] | Borodin, A.; Razborov, A.; Smolensky, R., On lower bounds for Read-k-times branching programs, Comput. complexity, 3, 1-18, (1993) · Zbl 0777.68043 |

[10] | Beigel, R.; Tarui, T., On acc, 32nd IEEE FOCS, (1991), p. 783-792 |

[11] | B. Chazelle, A spectral approch to lower bounds, in, 35th IEEE FOCS (1994), pp, 674, -, 682. |

[12] | Friedman, J., A note on matrix rigidity, Combinatorica, 13, 235-239, (1993) · Zbl 0848.15005 |

[13] | F. Green, J. Köbler, and J. Torán, The power of the middle bit, in Proc. 7th IEEE Structure in Complexity Theory, 1992, pp. 111-117. |

[14] | Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proof systems, SIAM J. comput., 18, 186-208, (1989) · Zbl 0677.68062 |

[15] | Golub, G.H.; Van Loan, C.F., Matrix computations, (1983), Johns Hopkins Univ. Press · Zbl 0559.65011 |

[16] | Håstad, J., Computational limitations of small depth circuits, ACM doctoral dissertation awards, (1986), M.I.T. Press Cambridge |

[17] | Halstenberg, B.; Reischuk, R., Relations between communication complexity classes, J. comput. system sci., 41, 402-429, (1990) · Zbl 0715.68029 |

[18] | Hoffman, A.J.; Wielandt, H.W., The variation of the spectrum of a normal matrix, Duke math. J., 20, 37-39, (1953) · Zbl 0051.00903 |

[19] | B. S. Kashin, and, A. A. Razborov, Improved lower bounds on the rigidity of Hadamard matrices, manuscript, Dec. 1997. · Zbl 0917.15013 |

[20] | M. Krause and S. Waack, Variation ranks of communication matrices and lower bounds for depth-two circuits having symmetric gates with unbounded fan-in, in Proc. 32nd IEEE FOCS, 1991, pp. 777-782. |

[21] | Kimmel, P.; Settle, A., Univ. of Chicago tech. report, (1992) |

[22] | Lund, C.; Fortnow, L.; Karloff, H.; Nisan, N., Algebraic methods in interactive proof systems, J. assoc. comput. Mach., 39, 859-868, (1992) · Zbl 0799.68097 |

[23] | S. V. Lokam, Matrix rigidity and communication complexity, manuscript, Nov. 28, 1994. |

[24] | S. V. Lokam, Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity, in Proc. 36th IEEE symp. Foundations of Comp. Sci. (FOCS), 1995, pp. 6-15. · Zbl 0937.68515 |

[25] | Lokam, S.V., On the rigidity of Vandermonde matrices, Theoret. comput. sci., 237, 477-483, (2000) · Zbl 0943.68072 |

[26] | Morgenstern, J., Note on a lower bound of the linear complexity of the fast Fourier transform, J. assoc. comput. Mach., 20, 305-306, (1973) · Zbl 0258.65120 |

[27] | N. Nisan and A. Wigderson, On the complexity of bilinear forms, in ACM STOC 1995, pp. 723-732. · Zbl 1059.68577 |

[28] | Pudlák, P., Large communication in constant depth circuits, Combinatorica, 14, 203-216, (1994) · Zbl 0819.68090 |

[29] | P. Pudlák, A note on the use of determinant for proving lower bounds on the size of linear circuits, Electron. Colloquium Comput. Complexity (ECCC), Report, 42, July 2, 1998. |

[30] | Pudlák, P.; Rödl, V., Some combinatorial-algebraic problems from complexity theory, Discrete math., 136, 253-279, (1994) · Zbl 0824.68053 |

[31] | Pudlák, P.; Rödl, V.; Sgall, J., Boolean circuits, tensor ranks and communication complexity, SIAM J. comput., 26, 605-633, (1997) · Zbl 0870.68068 |

[32] | Paturi, R.; Simon, J., Probabilistic communication complexity, J. comput. system sci., 33, 106-123, (1986) · Zbl 0625.68029 |

[33] | Pudlák, P.; Vavrin, Z., Computation of rigidity of order n2/r for one simple matrix, Comment. math. univ. carolinae, 32, 213-218, (1991) · Zbl 0753.15011 |

[34] | A. A. Razborov, On rigid matrices, manuscript, 1989. [In Russian] |

[35] | Razborov, A.A., Comment published in electron. colloquium comput. complexity (ECCC), Report, (1998) |

[36] | J. Radhakrishnan and A. Ta-Shma, Bounds on Depth-2 superconcentrators, in Proc. 38th IEEE Symp. Foundations of Computer Science (FOCS), 1997, pp. 585-594. |

[37] | Shen, A., IP=PSPACE, a simplified proof, J. assoc. comput. Mach., 39, 878-880, (1992) · Zbl 0799.68098 |

[38] | Shamir, A., Ip=pspace, J. assoc. comput. Mach., 39, 869-877, (1992) |

[39] | V. Shoup and R. Smolensky, Lower bounds for polynomial evaluation and interpolation, in Proc. IEEE FOCS (1991), pp. 378-383. · Zbl 0895.68075 |

[40] | Shokrollahi, M.A.; Spielman, D.A.; Stemann, V., A remark on matrix rigidity, Inform. process. lett., 64, 283-285, (1997) · Zbl 1337.15004 |

[41] | Tarui, J., Randomized polynomials, threshold circuits and polynomial hierarchy, Theoret. comput. sci., 113, 167-183, (1993) · Zbl 0783.68047 |

[42] | Toda, S., PP is as hard as the polynomial hierarchy, SIAM J. comp., 20, 865-877, (1991) · Zbl 0733.68034 |

[43] | Valiant, L., Graph-theoretic arguments in low-level complexity, Proc. 6th math. foundations of comp. sci., Lecture notes in computer science, 53, (1977), Springer-Verlag New York, p. 162-176 |

[44] | A. C.-C. Yao, Some complexity questions related to distributive computing, in Proc. ACM STOC 1979, pp. 209-213. |

[45] | A. C.-C. Yao, On ACC and threshold circuits, in Proc. of 31st IEEE FOCS, 1990, pp. 619-627. |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.