Number of the records: 1  

Communication complexity towards lower bounds on circuit depth

  1. 1.
    0175225 - MU-W 20020113 RIV CH eng J - Journal Article
    Edmonds, J. - Impagliazzo, R. - Rudich, S. - Sgall, Jiří
    Communication complexity towards lower bounds on circuit depth.
    Computational Complexity. Roč. 10, č. 3 (2001), s. 210-246. ISSN 1016-3328. E-ISSN 1420-8954
    R&D Projects: GA AV ČR IAA1019602; GA AV ČR IAA1019901; GA ČR GA201/97/P038; GA ČR GA201/01/1195; GA MŠMT ME 103
    Keywords : communication complexity%lower bounds
    Subject RIV: BA - General Mathematics
    Impact factor: 0.448, year: 2001

    Karchmer, Raz, and Wigderson, 1995, discuss the circuit depth complexity of $n$ bit Boolean functions constructed by composing up to $d = log n /log log n$ levels of $k = log n$ bit Boolean functions. In order to develop techniques for using communication complexity to prove circuit lower bounds, they suggest an intermediate communication complexity problem which they call the Universal Composition Relation. We give an almost optimal lower bound of $dk - 0 (d
    Permanent Link: http://hdl.handle.net/11104/0072210

     
    FileDownloadSizeCommentaryVersionAccess
    Sgall1.pdf1556.3 KBPublisher’s postprintrequire
     

Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.