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

Pavel Pudlák, Jiří Sgall

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)

Abstract: We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i,j)=C(i,j). We complement the known EXP-hardness of computing the exact value of a succinct zero-sum game by several results on approximating the value.
(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.

In the end of the talk I will mention a number of open problems and describe possible direction for further research.

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.