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

**11. 7. 2005 **(pondělí [Monday], **13.00, MÚ Žitná 25**, **nová
posluchárna v přízemí zadní budovy**)

**Valentine Kabanets (SFU, Vancouver): Complexity of succinct
zero-sum
games**

(joint work with Lance Fortnow, Russell Impagliazzo, and Chris Umans)

(1) We prove that approximating the value of a succinct zero-sum game to within an additive factor is complete for the class promise-S_2^p, the ``promise'' version of S_2^p. To the best of our knowledge, it is the first natural problem shown complete for this class.

(2) We describe a ZPP^{NP} algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct zero-sum game. As a corollary, we obtain, in a uniform fashion, several complexity-theoretic results, e.g., a ZPP^{NP} algorithm for learning circuits for SAT~\cite{BCGKT96} and a recent result by Cai~\cite{Cai01} that S_2^p\subseteq ZPP^{NP}.

Joint work with Lance Fortnow, Russell Impagliazzo, and Chris Umans.

**11. 7. 2005 **(pondělí [Monday], **14.30, MÚ Žitná 25**, **nová
posluchárna v přízemí zadní budovy**)

**Dmitry Gavinsky (Univ. of Calgary, Canada): Auxiliary Shared
Resources in Quantum and
Classical Communication**

**Abstract: **Quantum computers are being intensively studied in
the last decade,
it is widely believed that the laws of Nature described by quantum
mechanics give rise to significantly more powerful model of
computation than that of (classical) Turing Machine. The notion of
(classical) communication complexity was first
studied by Yao in 1979, since then this complexity measure has found
many application in different areas of Computer Sciences. In 1993 Yao
defined the notion of quantum communication complexity. More recently
it has been shown that using the laws of quantum mechanics it is
sometimes possible to construct considerably more efficient
communication protocols.

In this talk I will try to compare communication efficiency of several classical and quantum models. I will describe the following results:

- We demonstrate a communication problem where 0-error
classical
simultaneous message passing with public coin is exponentially more
efficient than 0-error quantum simultaneous message passing. Together
with a separation in the other direction due to BarYossef et al.,
this shows that the quantum SMP model is, in some sense, incomparable
with the classical public coin SMP model.

- We "almost separate" the models of quantum simultaneous message passing with shared entanglement and the model of quantum simultaneous message passing with shared randomness. We define a relation which can be efficiently exactly solved in the first model but cannot be solved efficiently, either exactly or in 0-error setup in the second model.
- We strengthen a result by Yao that a "very short" protocol from
the model of classical simultaneous message passing with shared
randomness can be simulated in the model of quantum simultaneous
message passing with at most exponential slowdown. We show a similar
result for protocols from the (stronger) model of classical 1-way
message passing with shared randomness.

**24. 5. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**, **3.
patro**)

**Laszlo Babai, Satyanarayana V. Lokam:****
A Quadratic Lower Bound on Rigidity
**(referuje Pavel Pudlák)

**Abstract:** The rigidity of a matrix A is the minimum number of
entries of A that must be changed to reduce the rank of A to or below a
given value r. It is a major unsolved problem (Valiant, 1977) to
construct “explicit” n × n matrices of rigidity > n^{1+eps}for rank
bound r=Cn where eps and C are positive constants. In fact, no
superlinear lower bounds are known for explicit families of matrices
for rank bound r=Cn.

In this paper we give an optimal, cn^2, lower bound on the rigidity of
a “somewhat explicit” family of matrices with respect to the rank bound
r=n/17. The entries of our matrices are the square roots of the first
n^2 prime numbers. The result follows by a slight modification of an
argument by Lokam (2000) based on the Shoup–Smolensky dimension of
matrices (1997).

**17. 5. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**, **3.
patro**)

**
Miroslava Sotáková: Reversible circuits consisting of small gates**

**Abstract:** This paper deals with the $n$-tuples of boolean
functions, which are computable by reversible circuits with $n$ input
nodes, consisting of ``small", i.e. unary, binary resp. ternary
gates. Such an $n$-tuple determines a bijection on the set
$\{0,1\}^n$. At first, we introduce the rewrite rules which enable us
to recognize, whether the two given binary-gate circuits are
equivalent, i.e. they compute the same $n$-tuple of boolean
functions. Furthermore we determine the $n$-tuples which are really
computable by at most ternary-gate circuits. We will show that we can
compute all bijections on the set of $n$-bit strings using one
auxiliary bit. In fact, if we allow to use binary quantum
(i.e. non-classical) gates instead of classical ternary gates, no
additional qubit is needed.

**15. 3., 22. 3., 5. 4., 12. 4., 19. 4., 26. 4., 12. 5. 2005 **(úterý
[Tuesday],
**14.20,
MÚ
Žitná 25**, **3. patro**)

**Luca Trevisan: Some Applications of Coding Theory in
Computational Complexity **(ECCC
Report TR04-043)

(referuje Pavel Pudlák, Ondřej Zajíček, Martin Pergel, Lada Vronková,
Miroslava Sotáková)

Jde o přehledový článek, který bychom v tomto semestru chtěli
postupně probrat podrobněji.

**Abstract: **Error-correcting codes and related combinatorial
constructs play an important role in several recent (and old) results
in computational complexity theory. In this paper we survey results on
locally-testable and locally-decodable error-correcting codes, and
their applications to complexity theory and to cryptography. Locally
decodable codes are error-correcting codes with sub-linear time
error-correcting algorithms. They are related to private information
retrieval (a type of cryptographic protocol), and they are used in
average-case complexity and to construct ``hard-core predicates'' for
one-way permutations. Locally testable codes are error-correcting codes
with sub-linear time error-detection algorithms, and they are the
combinatorial core of probabilistically checkable proofs.

**8. 3. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**, **3.
patro**)

**Daniel Kral (TU Berlin): Polynomial-size binary decision diagrams
for
the Exactly half-d-hyperclique
problem reading each input bit twice**

**Abstract: **
A binary decision diagram (BDD) is a graph-based data structure
representing
Boolean functions; k-BDDs are BDDs with an additional restriction that
each
input bit can be tested at most k times. A d-uniform hypergraph H on N
vertices
is an exactly half-d-hyperclique if N/2 of its vertices form a
hyperclique
and
the remaining vertices are isolated. Wegener [J. ACM 35(2) (1988),
461-471]
conjectured that there is no polynomial-size (d-1)-BDD for the Exactly
half-d-hyperclique problem. We refute this conjecture by constructing
polynomial-size (syntactic) 2-BDDs for the Exactly half-d-hyperclique
problem
for every d>=2.

**1. 3. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**, **3.
patro**)

**N. Goyal, M. Saks: ****Rounds vs Queries Trade-off in Noisy
Computation **(SODA 2005)

(referuje Jiří Sgall)

**Abstract: **We show that a noisy parallel decision tree
making O(n) queries needs O(log^* n) rounds to compute OR of n bits.
This answers a question of Newman. We prove more general trade-offs
between the number of queries and rounds. We also completely settle a
similar question for computing MAX in the noisy comparison tree
model; these results bring out interesting differences among the
noise models.