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

Pavel Pudlák, Jiří Sgall

Předchozí program semináře, letní semestr 2004 [Previous program, spring 2004]

26. 5. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
Michael Kaminski (Technion, Haifa, Israel):
A lower bound on the complexity of polynomial multiplication over finite fields

It is shown that computing the coefficients of the product of two degree-$n$ polynomials over a $q$-element field requires at least
$[3 + (q-1)^2 / (q^5+(q-1)^3) ] n - o(n)$ multiplications, whereas the best lower bound known from the literature is $3n - o(n)$.
19. 5. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
Pavel Pudlák: Linearni kody a expandery

Pripomeneme si znamy vysledek, jak z expanderu sestrojit dobre kody a ukazeme si mene znamou vec, ze to jde i naopak.
12. 5. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
Noam Nisan, Mario Szegedy: On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4: 301-313 (1994)
(referuje David Kronus)

Abstract: Every boolean function may be represented as a real polynomial. In this paper we characterize the degree of this polynomial in terms of certain combinatorial properties of the boolean function.
Our first result is a tight lower bound of \Omega\Gammalog n) on the degree needed to represent any boolean function that depends on n variables.
Our second result states that for every boolean function f the following measures
are all polynomially related:
28. 4., 5. 5. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
Ilan Newman. Computing in fault tolerance broadcast networks. (Complexity 2004)
(referuje Tomáš Ebenlendr)

Abstract: We consider a fault tolerance broadcast network of n processors each holding one bit of information. The goal is to compute a given Boolean function on the n bits. In each step, a processor may broadcast one bit of information. Each listening processor receives the bit that was broad­casted with error probability bounded by a fixed contant. The errors in different steps, as well as for different receiving processors in the same step, are mutually independent. The protocols that are considered in this model are oblivi­ ous protocols: At each step, the processors that broadcast are fixed in advanced and independent of the input and the outcome of previous steps. The primal complexity measure in this model is the total number of broadcasts that is per­ formed by the protocol. We present here the first linear complexity protocols for several classes of Boolean functions, including the OR function, functions that have O(1) ­minterm (maxterm) size, functions that have linear size AC_0 formulae and some other functions. This answer an open question of Yao [22], considering this fault tolerance model of El Gamal [2] and Gallager [8].
21. 4. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
Martin Aigner, Gianluca De Marco,  and Manuela Montangero. The Plurality Problem with Three Colors. (STACS 2004)

Abstract: The plurality problem with three colors is a game between two participants: Paul and Carol. Suppose we are given n balls colored with three colors. At any step of the game, Paul chooses two balls and asks whether they are of the same color, whereupon Carol answers yes or no. The game ends when Paul either produces a ball a of the plurality color (meaning that the number of balls colored like a exceeds those of the other colors), or when Paul states that there is no plurality. How many questions L(n) does Paul have to ask in the worst case? We show that 3n/2-2 <= L(n) <= 5n/3-2.
14. 4. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)

Jan Johannsen. Satisfiability problems complete for deterministic logarithmic space.  (STACS 2004).
(referuje Martin Pergel)

Abstract: The satisfiability and not-all-equal satisfiability problems for boolean formulas in CNF with at most two occurrences of each variable are complete for deterministic logarithmic space.
7. 4. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
D. Sivakumar: Algorithmic derandomization via complexity theory. STOC 2002.
(referuje Petr Matyáš)

Abstract: We point out how the methods of Nisan, originally developed for derandomizing space-bounded computations, may be applied to obtain polynomial-time and NC derandomizations of several probabilistic algorithms. Our list includes the randomized rounding steps of linear and semi-definite programming relaxations of optimization problems, parallel derandomization of discrepancy-type problems, and the Johnson--Lindenstrauss lemma, to name a few. A fascinating aspect of this style of derandomization is the fact that we often carry out the derandomizations directly from the statements about the correctness of probabilistic algorithms, rather than carefully mimicking their proofs.
17. 3. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
Noam Nisan: RL <= SC. Computational Complexity 4: 1-11 (1994).
(referuje Daniel Král')

Abstract: We show that any randomized Logspace algorithm (running in polynomial time, with bounded two­sided error) can be simulated deterministically in polynomial time and O(log 2 n) space. This puts RL in SC, ``Steve's Class''. In particular, we get a polynomial time O(log 2 n) space algorithm for the st­connectivity problem on undirected graphs.
25. 2., 10. 3. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
Gabor Tardos: Optimal probabilistic fingerprint codes
(referuje David Kronus)

Abstract: We construct binary codes for fingerprinting. Our codes for n users that are eps-secure against c pirates have length O(c2 log(n/eps)). This improves the codes proposed by Boneh and Shaw [3] whose length is approximately the square of this length. Our codes are probabilistic. By proving matching lower bounds we establish that the length of these codes is best within a constant factor for reasonable error probabilities. This lower bound generalizes the bound found independently by Peikert, Shelat, and Smith [10] that applies to a limited class of codes. Our results also imply that randomized fingerprint codes over a binary alphabet are as powerful as over an arbitrary alphabet, and also the equal strength of two distinct models for fingerprinting.
3. 3. 2004 (středa [Wednesday], 14.30, MÚ Žitná 25, 3. patro)
Manuel Bodirsky (Humboldt Univ., Berlin): Constraint Satisfaction with Countably Categorical Templates

Abstract: Many constraint satisfaction problems can be formulated as *homomorphism problems*. These problems are specified by a fixed structure T, called the *template*, and the computational problem is to determine for a given finite structure S of the same signature as T whether there is a homomorphism from S to T. This problem is called the *constraint satisfaction problem for T* and was intensively studied for finite templates T. It is possible to formalize many interesting tractable, and many interesting hard problems in this way.

Guiding -- and mostly open -- research questions in this area are: Which homomorphism problems are tractable, which problems are NP-hard? Are there problems that are of intermediate complexity? When are constraint satisfaction problems tractable via *constraint propagation*? How can we determine the expressive power of the corresponding constraint languages? Which computational problems can be formalized as homomorphism problems? Which parts of the theory of constraint satisfaction for finite templates generalize to which classes of infinite templates?

I will give a survey on constraint satisfaction and techniques to study the complexity of constraint satisfaction problems. Finally I will report on some results that generalize these techniques to infinite structures. This will be illustrated by problems that are motivated in computational linguistics and bioinformatics.