Karchmer-Wigderson games for hazard-free computation

Show simple item record

dc.contributor.author Ikenmeyer, Christian
dc.contributor.author Komarath, Balagopal
dc.contributor.author Saurabh, Nitin
dc.date.accessioned 2012-09-26T07:22:32Z
dc.date.available 2012-09-26T07:22:32Z
dc.date.issued 2021-07
dc.identifier.citation Ikenmeyer, Christian; Komarath, Balagopal and Saurabh, Nitin, "Karchmer-Wigderson games for hazard-free computation", arXiv, Cornell University Library, DOI: arXiv:2107.05128, Jul. 2021. en_US
dc.identifier.uri http://arxiv.org/abs/2107.05128
dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/6656
dc.description.abstract We present a Karchmer-Wigderson game to study the complexity of hazard-free formulas. This new game is both a generalization of the monotone Karchmer-Wigderson game and an analog of the classical Boolean Karchmer-Wigderson game. Therefore, it acts as a bridge between the existing monotone and general games. Using this game, we prove hazard-free formula size and depth lower bounds that are provably stronger than those possible by the standard technique of transferring results from monotone complexity in a black-box fashion. For the multiplexer function we give (1) a hazard-free formula of optimal size and (2) an improved low-depth hazard-free formula of almost optimal size and (3) a hazard-free formula with alternation depth 2 that has optimal depth. We then use our optimal constructions to obtain an improved universal worst-case hazard-free formula size upper bound. We see our results as a significant step towards establishing hazard-free computation as an independent missing link between Boolean complexity and monotone complexity.
dc.description.statementofresponsibility by Christian Ikenmeyer, Balagopal Komarath and Nitin Saurabh
dc.language.iso en_US en_US
dc.publisher Cornell University Library en_US
dc.title Karchmer-Wigderson games for hazard-free computation en_US
dc.type Pre-Print en_US
dc.relation.journal arXiv


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account