• DocumentCode
    2237070
  • Title

    BP(f)=O(L(f)1+ε)

  • Author

    Giel, Oliver

  • Author_Institution
    Fachbereich Inf., Dortmund Univ., Germany
  • fYear
    2000
  • fDate
    2000
  • Firstpage
    36
  • Lastpage
    43
  • Abstract
    Any B2-formula of size L can be transformed into a branching program of size O(eL1+ε)for arbitrary E>0. The presented proof is based on a technique due to R. Cleve (1991) to simulate balanced algebraic formulas of size s by algebraic straight-line programs that employ a constant number of registers and have length O(s1+ε). The best previously known simulation of B2-formulas of size C by branching programs achieves a branching program size of O(L1.195)
  • Keywords
    computational complexity; B2-formula; algebraic straight-line programs; balanced algebraic formulas; branching program; branching program size; simulation; Binary decision diagrams; Boolean functions; Registers;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 2000. Proceedings. 15th Annual IEEE Conference on
  • Conference_Location
    Florence
  • ISSN
    1093-0159
  • Print_ISBN
    0-7695-0674-7
  • Type

    conf

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