Algebrization

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algebrization: A New Barrier in Complexity Theory

Full text

Pdf (405 KB)

Source

ACM Transactions on Computation Theory (TOCT) archive
Volume 1 , Issue 1 (February 2009) table of contents

Article No. 2

Year of Publication: 2009

ISSN:1942-3454

Authors

Scott Aaronson	MIT
Avi Wigderson	Institute for Advanced Study

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 61, Downloads (12 Months): 417, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1490270.1490272 What is a DOI?

ABSTRACT

Any proof of P ≠ NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (e.g., that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier to progress on the central questions in complexity theory.

In this article, we present such a barrier, which we call algebraic relativization or algebrization. The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to a low-degree extension of A over a finite field or ring.

We systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. First, we show that all known nonrelativizing results based on arithmetization---both inclusions such as IP = PSPACE and MIP = NEXP, and separations such as MA_EXP ⊄ P/poly---do indeed algebrize. Second, we show that almost all of the major open problems---including P versus NP, P versus RP, and NEXP versus P/poly---will require non-algebrizing techniques. In some cases, algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for PromiseMA but not for NP.

Our second set of results follows from lower bounds in a new model of algebraic query complexity, which we introduce in this article and which is interesting in its own right. Some of our lower bounds use direct combinatorial and algebraic arguments, while others stem from a surprising connection between our model and communication complexity. Using this connection, we are also able to give an MA-protocol for the Inner Product function with O (√nlogn) communication (essentially matching a lower bound of Klauck), as well as a communication complexity conjecture whose truth would imply NL ≠ NP.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Scott Aaronson, Oracles Are Subtle But Not Malicious, Proceedings of the 21st Annual IEEE Conference on Computational Complexity, p.340-354, July 16-20, 2006 [doi>10.1109/CCC.2006.32]
	2	Arora, S., Impagliazzo, R., and Vazirani, U. 1992. Relativizing versus nonrelativizing techniques: The role of local checkability. (http://www.cs.berkeley.edu/~vazirani/pubs/relativizing.ps).
	3	Babai, L., Fortnow, L., and Lund, C. 1991. Nondeterministic exponential time has two-prover interactive protocols. Computat. Complex. 1, 1, 3--40.
	4	Baker, T., Gill, J., and Solovay, R. 1975. Relativizations of the P=?NP question. SIAM J. Comput. 4, 431--442.
	5	Bennett, C. H. and Gill, J. 1981. Relative to a random oracle A, P^A ≠ NP^A ≠ coNP^A with probability 1. SIAM J. Comput. 10, 1, 96--113.
	6	H. Buhrman , L. Fortnow , T. Thierauf, Nonrelativizing Separations, Proceedings of the Thirteenth Annual IEEE Conference on Computational Complexity, p.8, June 15-18, 1998
	7	Harry Buhrman , Nikolay Vereshchagin , Ronald de Wolf, On Computation and Communication with Small Bias, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.24-32, June 13-March 16, 2007 [doi>10.1109/CCC.2007.18]
	8	Harry Buhrman , Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoretical Computer Science, v.288 n.1, p.21-43, 9 October 2002 [doi>10.1016/S0304-3975(01)00144-X]
	9	Uriel Feige , Joe Kilian, Making games short (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.506-516, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258644]
	10	Fortnow, L. 1994. The role of relativization in complexity theory. Bull. EATCS 52, 229--244.
	11	Furst, M., Saxe, J. B., and Sipser, M. 1984. Parity, circuits, and the polynomial time hierarchy. Math. Syst. Theory 17, 13--27.
	12	Oded Goldreich , Silvio Micali , Avi Wigderson, Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems, Journal of the ACM (JACM), v.38 n.3, p.690-728, July 1991 [doi>10.1145/116825.116852]
	13	Hartmanis, J., Chang, R., Chari, S., Ranjan, D., and Rohatgi, P. 1992. Relativization: A revisionistic perspective. Bull. EATCS 47, 144--153.
	14	Hartmanis, J. and Stearns, R. E. 1965. On the computational complexity of algorithms. Trans. Amer. Math. Soc. 117, 285--306.
	15	John Hopcroft , Wolfgang Paul , Leslie Valiant, On Time Versus Space, Journal of the ACM (JACM), v.24 n.2, p.332-337, April 1977 [doi>10.1145/322003.322015]
	16	Russell Impagliazzo , Valentine Kabanets , Avi Wigderson, In search of an easy witness: exponential time vs. probabilistic polynomial time, Journal of Computer and System Sciences, v.65 n.4, p.672-694, December 2002 [doi>10.1016/S0022-0000(02)00024-7]
	17	Juma, A., Kabanets, V., Rackoff, C., and Shpilka, A. 2007. The black-box query complexity of polynomial summation. ECCC TR07-125.
	18	Bala Kalyanasundaram , Georg Schintger, The probabilistic communication complexity of set intersection, SIAM Journal on Discrete Mathematics, v.5 n.4, p.545-557, Nov. 1992 [doi>10.1137/0405044]
	19	Kannan, R. 1982. Circuit-size lower bounds and non-reducibility to sparse sets. Inf. Cont. 55, 40--56.
	20	Karchmer, M. and Wigderson, A. 1990. Monotone circuits for connectivity require super-logarithmic depth. SIAM J. Comput. 3, 255--265.
	21	Klauck, H. 2003. Rectangle size bounds and threshold covers in communication complexity. In Proceedings of the IEEE Conference on Computational Complexity. IEEE Computer Society Press, Los Alamitos, CA. 118--134. cs.CC/0208006.
	22	Adam R. Klivans , Dieter van Melkebeek, Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.659-667, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301428]
	23	Carsten Lund , Lance Fortnow , Howard Karloff, Algebraic methods for interactive proof systems, Journal of the ACM (JACM), v.39 n.4, p.859-868, Oct. 1992 [doi>10.1145/146585.146605]
	24	Wolfgang J. Paul , Nicholas Pippenger , Endre Szemeredi , William T. Trotter, On determinism versus non-determinism and related problems, Proceedings of the 24th Annual Symposium on Foundations of Computer Science, p.429-438, November 07-09, 1983 [doi>10.1109/SFCS.1983.39]
	25	Ran Raz, Exponential separation of quantum and classical communication complexity, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.358-367, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301343]
	26	Ran Raz , Amir Shpilka, On the Power of Quantum Proofs, Proceedings of the 19th IEEE Annual Conference on Computational Complexity, p.260-274, June 21-24, 2004 [doi>10.1109/CCC.2004.21]
	27	Razborov, A. A. 1987. Lower bounds for the size of circuits of bounded depth with basis {&,⊕⊕}. Mathematicheskie Zametki 41, 4, 598--607. (English translation in Math. Notes. Acad. Sci. USSR 41, 4, 1987) 333--338.
	28	A. A. Razborov, On the distributional complexity of disjointness, Theoretical Computer Science, v.106 n.2, p.385-390, Dec. 1992 [doi>10.1016/0304-3975(92)90260-M]
	29	Razborov, A. A. 2003. Quantum communication complexity of symmetric predicates. Izvestiya Math. (English version) 67, 1, 145--159. quant-ph/0204025.
	30	Alexander A. Razborov , Steven Rudich, Natural proofs, Journal of Computer and System Sciences, v.55 n.1, p.24-35, Aug. 1997 [doi>10.1006/jcss.1997.1494]
	31	Rahul Santhanam, Circuit lower bounds for Merlin-Arthur classes, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250832]
	32	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	33	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]
	34	Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.20 n.5, p.865-877, Oct. 1991 [doi>10.1137/0220053]
	35	Luca Trevisan , Salil Vadhan, Pseudorandomness and Average-Case Complexity via Uniform Reductions, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.129, May 21-24, 2002
	36	Dieter van Melkebeek, A survey of lower bounds for satisfiability and related problems, Foundations and Trends® in Theoretical Computer Science, v.2 n.3, p.197-303, January 2006 [doi>10.1561/0400000012]
	37	Vinodchandran, N. V. 2004. A note on the circuit complexity of PP. ECCC TR04-056.
	38	Wigderson, A. 1990. Information theoretic reasons for computational difficulty. In Proceedings of the International Congress of Mathematicians. 1537--1548.
	39	Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States
	40	Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science, p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]