Seminář z výpočetní složitosti

Pavel Pudlák, Jiří Sgall

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)

Andrej Bogdanov, Emanuele Viola: Pseudorandom bits for polynomials. ECCC Report TR07-081.
(referuje Pavel Nejedlý)

Abstract: We present a new approach to constructing pseudorandom generators that fool low-degree polynomials over finite fields, based on the Gowers norm. Using this approach, we obtain the following main constructions of explicitly computable generators $G : F^s to F^n$ that fool polynomials over a prime field $F$: begin{enumerate} item a generator that fools degree-$2$ (i.e., quadratic) polynomials to within error $1/n$, with seed length $s = O(log n)$, item a generator that fools degree-$3$ (i.e., cubic) polynomials to within error $eps$, with seed length $s = O(log_{abs{F}} n) + f(eps,F)$ where $f$ depends only on $eps$ and $F$ (not on $n$), item assuming the ``Gowers inverse conjecture,'' for every $d$ a generator that fools degree-$d$ polynomials to within error $eps$, with seed length $s = O(d cdot log_{abs{F}} n) + f(d,eps,F)$ where $f$ depends only on $d,eps,$ and $F$ (not on $n$). end{enumerate} We stress that the results in (1) and (2) are unconditional, i.e. do not rely on any unproven assumption. Moreover, the results in (3) rely on a special case of the conjecture which may be easier to prove.

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

Abstrakt: Chci ukazat, ze jista zobecneni Chrapcenkovy miry mohou dat nejvyse kvadraticke dolni odhady na formulovou slozitost.

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

Michal Koucký: Product-Sum Theorem

Abstrakt: Na tomto seminari probereme tzv. "Product-Sum Theorem", tvrzeni, ze pro kazdou dostatecne malou podmnozinu A konecneho telesa, bud mnozina A+A={a+b; a,b in A} nebo A*A={ab; a,b in A} musi byt podstatne vetsi nez A. Toto tvrzeni bylo dokazano relativne nedavavno, ma vsak zajimave aplikace. Ukazeme dukaz Boaze Baraka, coz je zjednoduseni puvodniho dukazu.

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

Petr Savický: O derandomizaci branching programů

Abstrakt: Hitting set pro branching programy sirky 2 s prijimajicimi hranami, ktere mohou vstup prijmout kdykoli behem vypoctu
a zamitnout pouze na konci.

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

Úvodní seminář

První dva semináře jsme věnovali prezentaci zajímavých otevřených problémů. Výběr článků pro referování a případně i následný společný výzkum bychom chtěli soustředit okolo těchto problémů.

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:

Answers to these questions  bring out unexpected connections with  classical areas of mathematics.