Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

Monday, October 26, 2009

Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room 4.112

Lecture - 14:15

Susanne Albers - HU Berlin

Energy-Efficient Algorithm

Energy has become a scarce and expensive resource. There is a growing awareness in society that energy saving is a critical issue. In this lecture we survey algorithmic solutions to reduce energy consumption in computing environments. We focus on the system and device level. More specifically, we study power-down mechanisms as well as dynamic speed scaling techniques in modern microprocessors.

Colloquium - 16:00

Holger Dell - HU Berlin

Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small cost, where the cost measure is the number of bits of communication from the first player to the second player.

For any integer $d \geq 3$ and positive real $\epsilon$ we show that if satisfiability for $n$-variable $d$-CNF formulas has a protocol of cost $O(n^{d-\epsilon})$ then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to the third level. The result even holds for conondeterministic protocols, and is tight as there exists a trivial deterministic protocol for $\epsilon = 0$. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, including sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs.

By reduction, the above statement holds for the vertex-cover problem on $n$-vertex $d$-uniform hypergraphs for any integer $d \geq 2$.

This is joint work with Dieter van Melkebeek.

Letzte Aktualisierung: 02.11.2009