Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/1007352.1007353acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Multi-linear formulas for permanent and determinant are of super-polynomial size

Published: 13 June 2004 Publication History

Abstract

An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear. We prove that any multi-linear arithmetic formula for the permanent or the determinant of an n x n matrix is of size super-polynomial in n.Previously, super-polynomial lower bounds were not known (for any explicit function) even for the special case of multi-linear formulas of constant depth.

References

[1]
S. Aaronson. Multilinear Formulas and Skepticism of Quantum Computing. STOC 2004
[2]
N. Alon, J.H. Spencer, P.Erdos. The Probabiliatic Method. John Wiley and Sons, Inc., (1992)
[3]
P. Burgisser, M. Clausen, M. A. Shokrollahi. Algebraic Complexity Theory. Springer-Verlag New York, Inc., (1997)
[4]
J. von zur Gathen. Feasible Arithmetic Computations: Valiant's Hypothesis. J. Symbolic Computation 4(2): 137--172 (1987)
[5]
J. von zur Gathen. Algebraic Complexity Theory. Ann. Rev. Computer Science 3: 317--347 (1988)
[6]
D. Grigoriev, M. Karpinski. An Exponential Lower Bound for Depth 3 Arithmetic Circuits. STOC 1998: 577--582
[7]
D. Grigoriev, A. A. Razborov. Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields. Applicable Algebra in Engineering, Communication and Computing 10(6): 465--487 (2000) (preliminary version in FOCS 1998)
[8]
R. Impagliazzo, V. Kabanets. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds. STOC 2003: 355--364
[9]
A. Kalorkoti. The Formula Size of the Determinant. SIAM Journal of Computing 14: 678--687 (1995)
[10]
N. Nisan. Lower Bounds for Non-Commutative Computation. STOC 1991: 410--418
[11]
N. Nisan, A. Wigderson. Lower Bounds on Arithmetic Circuits Via Partial Derivatives. Computational Complexity 6(3): 217--234 (1996) (preliminary version in FOCS 1995)
[12]
R. Raz, A. Shpilka. Deterministic Polynomial Identity Testing in Non Commutative Models. Conference on Computational Complexity 2004 (to appear)
[13]
C. P. Schnorr. A Lower Bound on the Number of Additions in Monotone Computations. Theoretical Computer Science 2(3): 305--315 (1976)
[14]
E. Shamir, M. Snir. On the Depth Complexity of Formulas. Mathematical Systems Theory 13: 301--322 (1980)
[15]
A. Shpilka, A. Wigderson. Depth-3 Arithmetic Circuits Over Fields of Characteristic Zero. Computational Complexity 10(1): 1--27 (2001) (preliminary version in Conference on Computational Complexity 1999)
[16]
L. G. Valiant. Negation can be Exponentially Powerful. Theoretical Computer Science 12: 303--314 (1980)
[17]
L. G. Valiant. Why is Boolean Complexity Theory Difficult? In Boolean Function Complexity (M. S. Paterson, ed.) Lond. Math. Soc. Lecture Note Ser. Vol. 169, Cambridge Univ. Press 84--94 (1992)

Cited By

View all

Index Terms

  1. Multi-linear formulas for permanent and determinant are of super-polynomial size

    Recommendations

    Comments

    Please enable JavaScript to view thecomments powered by Disqus.

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '04: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing
    June 2004
    660 pages
    ISBN:1581138520
    DOI:10.1145/1007352
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 13 June 2004

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. algebraic complexity
    2. arithmetic formulas
    3. circuit complexity
    4. computational complexity
    5. lower bounds

    Qualifiers

    • Article

    Conference

    STOC04
    Sponsor:
    STOC04: Symposium of Theory of Computing 2004
    June 13 - 16, 2004
    IL, Chicago, USA

    Acceptance Rates

    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 28 Nov 2024

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)Lower Bounds for Monotone q-Multilinear Boolean CircuitsSOFSEM 2023: Theory and Practice of Computer Science10.1007/978-3-031-23101-8_20(301-312)Online publication date: 1-Jan-2023
    • (2020)On $$\epsilon$$-sensitive monotone computationscomputational complexity10.1007/s00037-020-00196-629:2Online publication date: 25-Jul-2020
    • (2019)Lower bounds for Sum and Sum of Products of Read-once FormulasACM Transactions on Computation Theory10.1145/331323211:2(1-27)Online publication date: 2-Apr-2019
    • (2016)Functional lower bounds for arithmetic circuits and connections to boolean circuit complexityProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982478(1-19)Online publication date: 29-May-2016
    • (2016)Proof complexity lower bounds from algebraic circuit complexityProceedings of the 31st Conference on Computational Complexity10.5555/2982445.2982477(1-17)Online publication date: 29-May-2016
    • (2012)Об одном методе получения нижних оценок сложности монотонных арифметических схем, вычисляющих действительные многочленыA method for obtaining lower bounds for complexity of monotone arithmetic circuits computing real polynomialsМатематический сборникMatematicheskii Sbornik10.4213/sm7904203:10(33-70)Online publication date: 2012
    • (2012)Separating multilinear branching programs and formulasProceedings of the forty-fourth annual ACM symposium on Theory of computing10.1145/2213977.2214034(615-624)Online publication date: 19-May-2012
    • (2012)A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomialsSbornik: Mathematics10.1070/SM2012v203n10ABEH004270203:10(1411-1447)Online publication date: 13-Dec-2012
    • (2011)Non-commutative circuits and the sum-of-squares problemJournal of the American Mathematical Society10.1090/S0894-0347-2011-00694-224:3(871-898)Online publication date: 2-Feb-2011
    • (2011)Multilinear formulas, maximal-partition discrepancy and mixed-sources extractorsJournal of Computer and System Sciences10.1016/j.jcss.2010.06.01377:1(167-190)Online publication date: 1-Jan-2011
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media