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

Pavel Pudlák, Jiří Sgall

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

Dmitry Gavinski (Univ. of Calgary):
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í)

Peter Keevash, Benny Sudakov: On a restricted cross-intersection problem
(referuje Jiří Sgall)

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

Abstract: In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions.

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)

Abstract: We develop a new method for estimating the discrepancy of tensors associated with muptiparty communication problems. We define an analgue of the Hadamard property of matrices for tensors in multiple dimensions and show that any such k-party problem needs Omega(n/2^k) communication. We also exhibit constructions of Hadamard tensors giving Omega(n/2^k) lower bounds for a new class of explicitely defined Boolean functions.

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

Abstract: We shall prove a combinatorial result on bounded depth graphs which enables us to show that AND cannot be computed by bounded depth modular circuits with constant number of wires.

5. 10. 2005 (středa [Wednesday], 13:00, MÚ Žitná 25, zadní budova, 1. patro)

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].