## 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)

A lower bound on the complexity of polynomial multiplication over finite fields

Abstract:

$[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)

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)

(referuje David Kronus)

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:

- The decision tree complexity of f .
- The degree of the polynomial representing f .
- The smallest degree of a polynomial approximating f in the Lmax norm.

28. 4., 5. 5. 2004(středa [Wednesday],14.30, MÚ Žitná 25,3. patro)

(referuje Tomáš Ebenlendr)

21. 4. 2004(středa [Wednesday],14.30, MÚ Žitná 25,3. patro)

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)

7. 4. 2004(středa [Wednesday],14.30, MÚ Žitná 25,3. patro)

(referuje Petr Matyáš)

17. 3. 2004(středa [Wednesday],14.30, MÚ Žitná 25,3. patro)

(referuje Daniel Král')

25. 2., 10. 3. 2004(středa [Wednesday],14.30, MÚ Žitná 25,3. patro)

(referuje David Kronus)

3. 3. 2004(středa [Wednesday],14.30, MÚ Žitná 25,3. patro)

**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?