# TE-ETH: Lower Bounds for QBFs of Bounded Treewidth

# TE-ETH: Lower Bounds for QBFs of Bounded Treewidth

*Talk by Markus Hecher*

- Location: APB 3027
- Start: 28. November 2019 at 1:00 pm
- End: 28. November 2019 at 2:30 pm
- Event series: KBS Seminar
- iCal

A natural question is whether one can significantly improve these results and decrease the tower while assuming the Exponential Time Hypothesis (ETH). In the last years, there has been a growing interest in the quest of establishing lower bounds under ETH, showing mostly problem-specific lower bounds up to the third level of the polynomial hierarchy. Still, an important question is to settle this as general as possible and to cover the whole polynomial hierarchy.

In this work, we show lower bounds based on the ETH for arbitrary QBFs parameterized by treewidth (and quantifier depth). More formally, we establish lower bounds for QSAT and treewidth, namely, that under ETH there cannot be an algorithm that solves QSAT of quantifier depth i in runtime significantly better than i-fold exponential in the treewidth and polynomial in the input size. In doing so, we provide a versatile reduction technique to compress treewidth that encodes the essence of dynamic programming on arbitrary tree decompositions. Further, we describe a general methodology for a more fine-grained analysis of problems parameterized by treewidth that are at higher levels of the polynomial hierarchy.

**Authors:**Johannes Klaus Fichte, Markus Hecher, Andreas Pfandler