9th Colloquium of Research Area KL

Date: April 20, 2018

Venue: Lecture room 0.016 in the new computer science building

Homepage: Research Institute for Discrete Mathematics


Thomas Kesselheim: Prophet Inequalities and Posted Prices for Stochastic Combinatorial Optimization

The prophet inequality [Samuel-Cahn, 1984] is a famous result from stopping theory. One is presented a random sequence of rewards. Whenever a prize is presented, one can choose to pick this reward and to stop the sequence or to discard this reward and to continue. This setting has the intriguing interpretation of selling one item among multiple buyers. As optimal strategies are based on thresholds, they naturally correspond to posting a price for the item.
We go beyond this setting and consider combinatorial allocation problems. For example, we might have multiple items to allocate. We show that as long as there is a suitable way to set prices for the respective allocation problem without stochastic input, there is also a generalization of the prophet-inequality result.

Ulrich Brenner: Faster Adder Circuits for Inputs with Prescribed Arrival Times

Joint work with Anna Hermann

We present an algorithm that computes a Boolean circuit for an \textsc{And}-\textsc{Or} path (i.e., a formula of type $t_0 \land (t_1 \lor (t_2 \land ( \dots t_{m-1}) \dots )$ or $t_0 \lor (t_1 \land (t_2 \lor ( \dots t_{m-1}) \dots )$) with given arrival times for the input signals. Our objective function is delay, a generalization of depth. The maximum delay of the circuit we compute is $\log_2 W + \log_2 \log_2 m + \log_2 \log_2 \log_2 m + 5$, where $\lceil \log_2 W \rceil$ is a lower bound on the delay of any circuit depending on inputs $t_0, \dots, t_{m-1}$ with prescribed arrival times. Fast realizations of \textsc{And}-\textsc{Or} paths play an important role for optimizing the cycle time of modern logic chips. Moreover, since the carry bit computation in adders reduces to evaluating \textsc{And}-\textsc{OR} paths, up to a small additive constant, an adder with the same delay can be constructed. Our method yields the fastest circuits both for \textsc{And}-\textsc{Or} paths and adders in terms of delay known so far.