Deutsch
 
Hilfe Datenschutzhinweis Impressum
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT
  On the Complexity of Hazard-free Circuits

Ikenmeyer, C., Komarath, B., Lenzen, C., Lysikov, V., Mokhov, A., & Sreenivasaiah, K. (2017). On the Complexity of Hazard-free Circuits. Retrieved from http://arxiv.org/abs/1711.01904.

Item is

Basisdaten

einblenden: ausblenden:
Genre: Forschungspapier

Dateien

einblenden: Dateien
ausblenden: Dateien
:
arXiv:1711.01904.pdf (Preprint), 310KB
Name:
arXiv:1711.01904.pdf
Beschreibung:
File downloaded from arXiv at 2018-01-31 10:23
OA-Status:
Sichtbarkeit:
Öffentlich
MIME-Typ / Prüfsumme:
application/pdf / [MD5]
Technische Metadaten:
Copyright Datum:
-
Copyright Info:
-

Externe Referenzen

einblenden:

Urheber

einblenden:
ausblenden:
 Urheber:
Ikenmeyer, Christian1, Autor           
Komarath, Balagopal2, Autor
Lenzen, Christoph1, Autor           
Lysikov, Vladimir2, Autor
Mokhov, Andrey2, Autor
Sreenivasaiah, Karteek2, Autor
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Inhalt

einblenden:
ausblenden:
Schlagwörter: Computer Science, Computational Complexity, cs.CC,
 Zusammenfassung: The problem of constructing hazard-free Boolean circuits dates back to the
1940s and is an important problem in circuit design. Our main lower-bound
result unconditionally shows the existence of functions whose circuit
complexity is polynomially bounded while every hazard-free implementation is
provably of exponential size. Previous lower bounds on the hazard-free
complexity were only valid for depth 2 circuits. The same proof method yields
that every subcubic implementation of Boolean matrix multiplication must have
hazards.
These results follow from a crucial structural insight: Hazard-free
complexity is a natural generalization of monotone complexity to all (not
necessarily monotone) Boolean functions. Thus, we can apply known monotone
complexity lower bounds to find lower bounds on the hazard-free complexity. We
also lift these methods from the monotone setting to prove exponential
hazard-free complexity lower bounds for non-monotone functions.
As our main upper-bound result we show how to efficiently convert a Boolean
circuit into a bounded-bit hazard-free circuit with only a polynomially large
blow-up in the number of gates. Previously, the best known method yielded
exponentially large circuits in the worst case, so our algorithm gives an
exponential improvement.
As a side result we establish the NP-completeness of several hazard detection
problems.

Details

einblenden:
ausblenden:
Sprache(n): eng - English
 Datum: 2017-11-062017
 Publikationsstatus: Online veröffentlicht
 Seiten: 21 p.
 Ort, Verlag, Ausgabe: -
 Inhaltsverzeichnis: -
 Art der Begutachtung: -
 Identifikatoren: arXiv: 1711.01904
URI: http://arxiv.org/abs/1711.01904
BibTex Citekey: Ikenmeyer_Komarath2017
 Art des Abschluß: -

Veranstaltung

einblenden:

Entscheidung

einblenden:

Projektinformation

einblenden: ausblenden:
Projektname : ToRH
Grant ID : 716562
Förderprogramm : Horizon 2020 (H2020)
Förderorganisation : European Commission (EC)

Quelle

einblenden: