20.04.2018
Venue: Lecture room 0.016 in the new computer science building
| 15:45 | Coffee and Tee (room 2.075) |
| 16:15 | Thomas Kesselheim: Prophet Inequalities and Posted Prices for Stochastic Combinatorial Optimization |
| 17:00 | Coffee break (room 2.075) |
| 17:30 | Ulrich Brenner: Faster Adder Circuits for Inputs with Prescribed Arrival Times |
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 And-Or path (i.e., a formula of type t0∧(t1∨(t2∧(…tm−1)…) or t0∨(t1∧(t2∨(…tm−1)…))) 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 log2W + log2log2m + log2log2log2m + 5 where ⌈log2W⌉ is a lower bound on the delay of any circuit depending on inputs t0,…,tm−1 with prescribed arrival times. Fast realizations of And-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 And-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 And-Or paths and adders in terms of delay known so far.