• DocumentCode
    2722174
  • Title

    Perfect hashing, graph entropy, and circuit complexity

  • Author

    Newman, Ilan ; Ragde, Prabhakar ; Wigderson, Avi

  • Author_Institution
    Hebrew Univ., Jerusalem, Israel
  • fYear
    1990
  • fDate
    8-11 July 1990
  • Firstpage
    91
  • Lastpage
    99
  • Abstract
    It is shown that approximate compaction can be efficiently performed in constant parallel time using perfect hash functions. This allows it to be shown that polylogarithmic-threshold functions are in linear ACo. Next, it is shown that the information-theoretic notion of graph entropy captures some aspect of the difficulty of computing Boolean functions. This is used to derive superlinear lower bounds on the formula size of threshold and other simple Boolean functions
  • Keywords
    Boolean functions; circuit layout CAD; computational complexity; file organisation; graph theory; threshold logic; Boolean functions; approximate compaction; circuit complexity; constant parallel time; formula size; graph entropy; information theory; perfect hash functions; polylogarithmic-threshold functions; superlinear lower bounds; Boolean functions; Circuits; Compaction; Complexity theory; Entropy; History; Phase change random access memory; Polynomials; Size measurement; Testing;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1990, Proceedings., Fifth Annual
  • Conference_Location
    Barcelona
  • Print_ISBN
    0-8186-6072-4
  • Type

    conf

  • DOI
    10.1109/SCT.1990.113958
  • Filename
    113958
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2722174