Monday, October 26, 2009
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
room 4.112
Lecture - 14:15
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
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.