• DocumentCode
    3268204
  • Title

    A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent

  • Author

    Koiran, Pascal ; Perifel, Sylvain

  • Author_Institution
    LIP, Ecole Normale Super. de Lyon, Lyon, France
  • fYear
    2009
  • fDate
    15-18 July 2009
  • Firstpage
    35
  • Lastpage
    40
  • Abstract
    We show that the permanent cannot be computed by DLOGTIME-uniform threshold or arithmetic circuits of depth o(log log n) and polynomial size.
  • Keywords
    computational complexity; polynomials; DLOGTIME-uniform threshold; arithmetic circuits; polynomial size; superpolynomial lower bound; uniform nonconstant-depth threshold circuits; Arithmetic; Circuits; Complexity theory; Computational complexity; Dark states; Polynomials; Turing machines; arithmetic circuits; lower bound; non-constant depth circuits; permanent; threshold circuits; uniform circuits;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 2009. CCC '09. 24th Annual IEEE Conference on
  • Conference_Location
    Paris
  • ISSN
    1093-0159
  • Print_ISBN
    978-0-7695-3717-7
  • Type

    conf

  • DOI
    10.1109/CCC.2009.19
  • Filename
    5231205
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=3268204