English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
  Small Hazard-free Transducers

Bund, J., Lenzen, C., & Medina, M. (2018). Small Hazard-free Transducers. Retrieved from http://arxiv.org/abs/1811.12369.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/21.11116/0000-0002-9FAD-9 Version Permalink: http://hdl.handle.net/21.11116/0000-0002-9FAE-8
Genre: Paper

Files

show Files
hide Files
:
arXiv:1811.12369.pdf (Preprint), 417KB
Name:
arXiv:1811.12369.pdf
Description:
File downloaded from arXiv at 2018-12-06 14:27
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Bund, Johannes1, Author              
Lenzen, Christoph1, Author              
Medina, Moti2, Author              
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Computational Complexity, cs.CC
 Abstract: Recently, an unconditional exponential separation between the hazard-free complexity and (standard) circuit complexity of explicit functions has been shown. This raises the question: which classes of functions permit efficient hazard-free circuits? Our main result is as follows. A \emph{transducer} is a finite state machine that transcribes, symbol by symbol, an input string of length $n$ into an output string of length $n$. We prove that any function arising from a transducer with $s$ states, that is input symbols which are encoded by $\ell$ bits, has a hazard-free circuit of size $2^{\BO(s+\ell)}\cdot n$ and depth $\BO(\ell+ s\cdot \log n)$; in particular, if $s, \ell\in \BO(1)$, size and depth are asymptotically optimal. We utilize our main result to derive efficient circuits for \emph{$k$-recoverable addition}. Informally speaking, a code is \emph{$k$-recoverable} if it does not increase uncertainty regarding the encoded value, so long as it is guaranteed that it is from $\{x,x+1,\ldots,x+k\}$ for some $x\in \NN_0$. We provide an asymptotically optimal $k$-recoverable code. We also realize a transducer with $\BO(k)$ states that adds two codewords from this $k$-recoverable code. Combined with our main result, we obtain a hazard-free adder circuit of size $2^{\BO(k)}n$ and depth $\BO(k\log n)$ with respect to this code, i.e., a $k$-recoverable adder circuit that adds two codewords of $n$ bits each. In other words, $k$-recoverable addition is fixed-parameter tractable with respect to $k$.

Details

show
hide
Language(s): eng - English
 Dates: 2018-11-292018
 Publication Status: Published online
 Pages: 35 p.
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: arXiv: 1811.12369
URI: http://arxiv.org/abs/1811.12369
BibTex Citekey: Bund_arXiv1811.12369
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show