#
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

*Abstract:*

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

*Abstract:*

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