## Předchozí program semináře, zimní semestr 2007 [Previous program, Fall 2007]

**8. 1. 2008 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**)

**Michal Koucký: ** Amplifying Lower Bounds by Means of
Self-Reducibility

**Abstract: **We observe that many important computational
problems in $NC^1$ share a
simple self-reducibility property. We then show that, for any problem
$A$
having this self-reducibility property, $A$ has polynomial size $TC^0$
circuits if and only if it has $TC^0$ circuits of size $n^{1+\epsilon}$
for
every $\epsilon > 0$ (counting the number of wires in a circuit as
the size
of the circuit). As an example of what this observation yields,
consider
the Boolean Formula Evaluation problem (BFE), which is complete for
$NC^1$.
It follows from a lower bound of Impagliazzo, Paturi, and Saks, that
BFE
requires $TC^0$ circuits of size $n^{1+\Omega(1)}$. If one were able to
improve this lower bound to show that there is some constant $c>0$
such that
every $TC^0$ circuit family recognizing BFE has size $n^{1+c}$, then it
would follow that $TC^0 \neq NC^1$.

We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth $d$ $TC^0$ and $AC[6]^0$ circuits of size $n^{1+c}$ for some constant $c$ depending on $d$. Joint work with Eric Allender.

**11. 12., 18. 12. 2007 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**)

(referuje Pavel Nejedlý)

**4. 12. 2007 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**)

**Emanuele Viola, Avi Wigderson: One-way
multi-party communication lower bound for pointer jumping with
applications.** ECCC Report TR07-079.

(referuje Ondřej Zajíček)**
**

**Abstract: ** In this paper we study the one-way
multi-party communication model,
in which every party speaks exactly once in its turn. For every
fixed $k$, we prove a tight lower bound of
$Omega{n^{1/(k-1)}}$ on the probabilistic communication
complexity of pointer jumping in a $k$-layered tree, where the
pointers of the $i$-th layer reside on the forehead of the $i$-th
party to speak. The lower bound remains nontrivial even for $k =
(log n)^{1/2 - Omega(1)}$ parties. Previous to our work a lower bound
was
known only for $k=3$ cite{BabaiHayesKimmel01},
and in very restricted models for $k>3$ cite{DJS98,Cha07}. Our
results have the following consequences to other models and
problems, extending previous work in several directions.
The one-way model is strong enough to capture {em general} (non
one-way) multi-party protocols of bounded rounds. Thus we generalize
to this multi-party model results on two directions studied in the
classical 2-party model (e.g.~cite{PaS84,NiW93}).
The first is a round hierarchy: We give an exponential separation
between the power of $r$ and $2 r$ rounds in general
probabilistic $k$-party protocols, for any fixed $k$ and $r$. The
second is the relative power of determinism and nondeterminism: We
prove an exponential separation between nondeterministic and
deterministic communication complexity for general $k$-party
protocols with $r$ rounds, for any fixed $k,r$.
The pointer jumping function is weak enough to be a special case of the
well-studied disjointness function. Thus we obtain a lower bound of
$Omegarb{n^{1/(k-1)}}$ on the probabilistic complexity of
$k$-set disjointness in the one-way model, which was known only
for $k=3$ parties. Our result also extends a similar lower bound
for the weaker simultaneous model, in which parties simultaneously
send one message to a referee cite{BPSW05}.
Finally, we infer an exponential separation between the power of
different orders in which parties send messages in the one-way
model, for every fixed $k$. Previous to our work such a separation
was only known for $k=3$ cite{NiW93}.
Our lower bound technique, which handles functions of high
discrepancy, may be of independent interest. It provides a
``party-elimination'' induction, based on a restricted form of a
direct-product result, specific to the pointer jumping function.

**27. 11. 2007 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**)

**Emanuele Viola: Selected
Results in Additive Combinatorics: An Exposition**. ECCC Report
TR07-103.

(referuje Tomáš Ebenlendr)**
**

**Abstrakt: **
We give a self-contained exposition of selected results in additive
combinatorics over the group {0,1}^n. In particular, we prove the
celebrated theorems known as the Balog-Szemeredi-Gowers theorem ('94
and '98) and
the
Freiman-Ruzsa theorem ('73 and '99), leading to the remarkable result
by Samorodnitsky ('07) that linear transformations are efficiently
testable.
No new result is proved here. However, we strip down the available
proofs to the bare
minimum needed to derive the efficient testability of linear
transformations over
{0,1}^n, thus hoping to provide a computer science-friendly
introduction to the marvelous
field of additive combinatorics.

**13. 11. 2007 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**)

**Pavel Hrubeš: Formulová složitost a aditivní míry**

**30. 10., 6. 11. 2007 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**)

**Michal Koucký: Product-Sum Theorem**

**23. 10. 2007 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**)

Abstrakt:

a zamitnout pouze na konci.

**9. 10., 16. 10. 2007 **(úterý [Tuesday], **14:00,
MÚ Žitná 25**)

**Úvodní seminář
**

24. 9. 2007** **** **(pondělí
[Monday], 13:00, posluchárna
v přízemí zadní budovy **MÚ Žitná 25**)

**Ed Coffman (Columbia University, NY, U.S.A.): **

MOLECULAR COMPUTING: ALGORITHMIC SELF ASSEMBLY

Abstract: Advances in
chemical synthesis have laid the groundwork for computation at
nanoscale, where self assembly becomes the core process, either as a
computation itself, or as a mechanism for fabricating nanodevices. By
such processes, elementary particles, such as DNA molecules, combine
into large complexes following built-in bonding rules. We study
self
assembly viewed as a random growth process, addressing such as
questions as:

- How long does a given structure take to self-assemble?'

- How does one optimize the yield of a particular self-assembly
process?'

- What are the trade-offs between the reliability (error tolerance) and speed of self assembly?