Michael Kaminski (Technion, Haifa, Israel):
A lower bound on the complexity of polynomial multiplication over finite fields
Abstract: 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)$.
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:
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.
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 broadcasted
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].
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.
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.
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.
Abstract: We show that any randomized Logspace algorithm
(running in polynomial time, with bounded twosided 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 stconnectivity
problem on undirected graphs.
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.
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.
