The Library
Karchmer-Wigderson games for hazard-free computation
Tools
Tools
Tools
Ikenmeyer, Christian, Komarath, Balagopal and Saurabh, Nitin (2022) Karchmer-Wigderson games for hazard-free computation. In: 14th Innovations in Theoretical Computer Science (ITCS), MIT in Cambridge, Massachusetts, 11-13 Jan 2023. Published in: Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), 251 ISBN 9783959772631. doi:10.4230/LIPIcs.ITCS.2023.74 ISSN 1868-8969.
|
PDF
WRAP-Karchmer-Wigderson-games-hazard-free-computation-Ikenmeyer-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (801Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.ITCS.2023.74
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.
| Item Type: | Conference Item (Paper) | ||||||
|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science Faculty of Science, Engineering and Medicine > Science > Mathematics |
||||||
| Library of Congress Subject Headings (LCSH): | Computational complexity, Algebra, Boolean , Combinational circuits , Combinatorial analysis -- Data processing | ||||||
| Journal or Publication Title: | Proceedings of the 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) | ||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fur Informatik | ||||||
| ISBN: | 9783959772631 | ||||||
| ISSN: | 1868-8969 | ||||||
| Official Date: | 2022 | ||||||
| Dates: |
|
||||||
| Volume: | 251 | ||||||
| Article Number: | 74 | ||||||
| DOI: | 10.4230/LIPIcs.ITCS.2023.74 | ||||||
| Status: | Peer Reviewed | ||||||
| Publication Status: | Published | ||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||
| Date of first compliant deposit: | 8 November 2022 | ||||||
| Date of first compliant Open Access: | 9 November 2022 | ||||||
| RIOXX Funder/Project Grant: |
|
||||||
| Conference Paper Type: | Paper | ||||||
| Title of Event: | 14th Innovations in Theoretical Computer Science (ITCS) | ||||||
| Type of Event: | Conference | ||||||
| Location of Event: | MIT in Cambridge, Massachusetts | ||||||
| Date(s) of Event: | 11-13 Jan 2023 | ||||||
| Related URLs: | |||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
