Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Metastability-Containing Circuits, Parallel Distance Problems, and Terrain Guarding
Speaker:Stephan Friedrichs
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Promotionskolloquium
Visibility:D1, D2, D3, D4, D5, RG1, SWS, MMCI
We use this to send out email in the morning.
Level:Public Audience
Language:English
Date, Time and Location
Date:Monday, 11 September 2017
Time:15:30
Duration:60 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
We study three problems. The first is the phenomenon of metastability in digital circuits. This is a state of bistable storage elements, such as registers, that is neither logical 0 nor 1 and breaks the abstraction of Boolean logic. We propose a time- and value-discrete model for metastability in digital circuits and show that it reflects relevant physical properties. Further, we propose the fundamentally new approach of using logical masking to perform meaningful computations despite the presence of metastable upsets and analyze what functions can be computed in our model. Additionally, we show that circuits with masking registers grow computationally more powerful with each available clock cycle.

The second topic are parallel algorithms, based on an algebraic abstraction of the Moore-Bellman-Ford algorithm, for solving various distance problems. Our focus are distance approximations that obey the triangle inequality while at the same time achieving polylogarithmic depth and low work.

Finally, we study the continuous Terrain Guarding Problem. We show that it has a rational discretization with a quadratic number of guard
candidates, establish its membership in NP and the existence of a PTAS, and present an efficient implementation of a solver.

Contact
Name(s):Stephan Friedrichs
EMail:sfriedri@mpi-inf.mpg.de
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):

Created:
Stephan Friedrichs, 08/29/2017 11:17 AM
Last modified:
Uwe Brahm/MPII/DE, 09/11/2017 07:01 AM
  • Stephan Friedrichs, 08/29/2017 11:17 AM -- Created document.