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.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2722174
بازگشت