## Předchozí program semináře, zimní semestr 2005 [Previous program, Fall 2005]

**27. 1. 2006 **(pátek [Friday], **13.00, MÚ Žitná 25**,
zadní budova, přízemí)

Two Exponential Separations in Communication Complexity Through Quantum State Indistinguishability

(joint work with Julia Kempe, Oded Regev, and Ronald de Wolf)

Abstract: We consider the problem of bounded-error quantum state identification: given one of two known states, what is the optimal probability a with which we can identify the given state, subject to our guess being correct with high probability (but we are permitted to output "don't know" instead of a guess). We prove a direct product theorem for this problem. Our proof is based on semidefinite programming duality and may be of wider interest.

Using this result, we present two new exponential separations in the simultaneous message passing model of communication complexity. Both are shown in the strongest possible sense:

- we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared randomness, but needs n^(1/3) communication if the parties don't share randomness, even if communication is quantum;
- we describe a relation that can be computed with O(log n) classical bits of communication in the presence of shared entanglement, but needs (almost) n^(1/3) communication if the parties share randomness but no entanglement, even if communication is quantum.

The talk will be very non-technical, understanding does not require any background in quantum computing.

Here is a link to slides of the talk: http://pages.cpsc.ucalgary.ca/~gavinsky/talks/qbeqs.pdf

**3. 1. 2006 **(úterý [Tuesday], **14.20, MÚ Žitná 25**,
zadní budova, přízemí)

Abstract: Suppose A and B are families of subsets of an n-element set and L is a set of s numbers. We say that the pair (AA,BB) is L-cross-intersecting if |A intersection B|\in L for every A\in AA and B\in BB. Among such pairs (A, B) we write P_L(n) for the maximum possible value of |AA|*|BB|. In this paper we find an exact bound for P_L(n) when n is sufficiently large, improving earlier work of Sgall. We also determine P_{2}(n) and P_{1,2}(n) exactly, which respectively confirm special cases of a conjecture of Ahlswede, Cai and Zhang and a conjecture of Sgall.

**13. 12. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**,
zadní budova, přízemí)

**P. Pudlak: Quantum deduction rules**

**Abstract: **We shall define a quantum version of Frege
systems. We
shall prove that the proofs in these systems are not shorter, but
assuming a plausible conjecture, it is hard to extract a classical
proof from a quantum one.

**6. 12. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**,
zadní budova, přízemí)

**Noga Alon, Ilan Newman, Alexander Shen, Gabor Tardos, and Nikolai
Vereshchagin:
Partitioning multidimensional sets in a small number of ``uniform''
parts
**(referuje Tomáš Ebenlendr)

**Abstract:**
Our main result implies the following easily formulated statement. The
set of edges E of every finite bipartite graph can be split into
poly(log |E|) subsets so that all the resulting bipartite graphs are
almost regular. The latter means that the ratio between the maximal and
minimal nonzero degree of the left nodes is bounded by a constant and
the same condition holds for the right nodes. Stated differently, every
finite 2 dimensional set S \subset N^2 can be partitioned into
poly(log |S|) parts so that in every part the ratio between the maximal
size and the minimal size of nonempty horizontal section is bounded by
a constant and the same condition holds for vertical sections. We prove
a similar statement for ndimensional sets for any n and show how it
can be used to relate information inequalities for Shannon entropy of
random variables to inequalities between sizes of sections and their
projections of multidimensional finite sets.

**29. 11. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**,
zadní budova, přízemí)

**Dan Gutfreund,
Ronen Shaltiel,
and Amnon TaShma:
If NP languages are hard on the worstcase then it is easy to find
their hard instances** (CCC'05)

(referuje Ondřej Zajíček)

**Abstract:** We prove that if NP \not\subseteq BPP, i.e., if
some NPcomplete language is worst-case hard, then for every
probabilistic algorithm trying to decide the language, there exists
some polynomially samplable distribution that is hard for it. That is,
the algorithm often errs on inputs from this distribution. This is the
first worst-case to average-case reduction for NP of any kind. We
stress however, that this does not mean that there exists one fixed
samplable distribution that is hard for all probabilistic polynomial
time algorithms, which is a prerequisite assumption needed for OWF and
cryptography (even if not a sufficient assumption). Nevertheless, we do
show that there is a fixed distribution on instances of NPcomplete
languages, that is samplable in quasipolynomial time and is hard for
all probabilistic polynomial time algorithms (unless NP is easy in the
worstcase). Our results are based on the following lemma that may be
of independent interest: Given the description of an efficient
(probabilistic) algorithm that fails to solve SAT in the worstcase, we
can efficiently generate at most three Boolean formulae (of increasing
lengths) such that the algorithm errs on at least one of them.

**22. 11. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**,
zadní budova, přízemí)

**Zeev Dvir and Amir Shpilka: Locally Decodable Codes with 2
queries and Polynomial Identity Testing for depth 3 circuits
**(referuje Pavel Nejedlý)

**8. 11., 15. 11. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**,
zadní budova, přízemí)

**Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower bounds for Lovasz-Schrijver systems and beyond, using multiparty
communication complexity** (ICALP'05)

(referuje Martin Pergel)

**Abstract:** We prove that an omega(log^3 n) lower bound for the
three-party number-on-the-forehead (NOF) communication complexity of
the set-disjointness function implies an n^omega(1) size lower bound
for
tree-like Lovasz-Schrijver systems that refute unsatisfiable
CNFs. More generally, we prove that an n^Omega(1) lower bound for the
(k+1)party NOF communication complexity of set-disjointness implies a
2^n^Omega(1) size lower bound for all tree-like proof systems whose
formulas
are degree k polynomial inequalities.

**25. 10., 1. 11. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná 25**,
zadní budova, přízemí)

**Jeff Ford and Anna Gál: Hadamard Tensors and Lower bounds on
Multiparty Communication Complexity **(ICALP'05)

(referuje David Kronus)

**11. 10., 18. 10. 2005 **(úterý [Tuesday], **14.20, MÚ Žitná
25**,
zadní budova, přízemí)

**Pavel Pudlák: A lower bound on constant depth circuits **

**Robert Špalek (CWI Amsterdam): Quantum Random Walk Algorithms **

**Abstract:** Quantum
computers can search an unsorted database of size N in time
sqrt(N) [Grover, 1996]. This search algorithm is very universal and one
can use
it as a subroutine for solving a number of other problems, for example
element distinctness, that is testing whether all number in a sequence
of length N are distinct in time N^{3/4}. Ambainis [2004] published a
very elegant algorithm based on quantum random walks solving this
problem in time N^{2/3}, which is optimal. Szegedy [2004] generalized
this technique to
all symmetric Markov chains and simplified the proof. The resulting
algorithm is almost as universal as the unsorted search, and it was
successfully applied on triangle finding in time N^{1.3} [Magniez,
Santha, Szegedy, 2005], group commutativity testing in time N^{2/3}
[Magniez, Nayak, 2005], and verification of matrix products [Buhrman,
Špalek, 2006].