Date:		April 12, 2007
Topic:		China Theory Day (II)
	Title:	Counting Homomorphisms to Directed Acyclic Graphs
	Speaker:	Mike Paterson, University of Warwick
	Biography:	Professor of Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom.
	Abstract:	We give a dichotomy theorem for the problem of counting homomorphisms to directed acyclic graphs. $H$ is a fixed directed acyclic graph. The problem is, given an input digraph $G$, to determine how many homomorphisms there are from $G$ to $H$. We give a graph-theoretic classification, showing that for some digraphs $H$, the problem is in P and for the rest of the digraphs $H$ the problem is \#P-complete. An interesting feature of the dichotomy, which is absent from related dichotomy results, is the rich supply of tractable graphs~$H$ with complex structure. (This is joint work with Martin Dyer and Leslie Goldberg.)

	Title:	Quantum Information and the PCP Theorem
	Speaker:	Ran Raz, Weizmann Institute
	Biography:	I am a faculty member in the faculty of mathematics and computer science at the Weizmann Institute. My main research area is complexity theory, with emphasize on proving lower bounds for computational models. More specifically, I am interested in:Boolean circuit complexity, Arithmetic circuit complexity, Communication complexity, Propositional proof theory, Probabilistic checkable proofs, Quantum computation and communication and Randomness and derandomization.
	Abstract:	Our main result is that the membership $x \in SAT$ (for $x$ of length $n$)can be proved by a logarithmic-size quantum state $\Psi$, together with a polynomial-size classical proof consisting of blocks of length $polylog(n)$ bits each, such that after measuring the state $\Psi$ the verifier only needs to read ONE block of the classical proof. This shows that if a short quantum witness is available then a (classical) PCP with only one query is possible. Our second result is that the class $QIP/qpoly$ contains ALL languages. That is, for any language $L$ (even non-recursive), the membership $x \in L$ (for $x$ of length $n$) can be proved by a polynomial-size quantum interactive proof, where the verifier is a polynomial-size quantum circuit with working space initiated with some quantum state $\Psi_{L,n}$ (depending only on $L$ and $n$). Moreover, the interactive proof that we give is of only one round, and the messages communicated are classical. The advice $\Psi_{L,n} $ given to the verifiercan also be replaced by a classical probabilistic advice, as long as this advice is kept as a secret from the prover. Our result can hence be interpreted as: the class $IP/rpoly$ contains all languages. For the proof of the second result, we introduce the {\em quantum low-degree-extension}of a string of bits. The main result requires an additional machinery of "quantum low-degree-test".

	Title:	Parallel Repetition of the Odd Cycle Game
	Speaker:	Mario Szegedy, Rutgers University
	Biography:	Mario Szegedy has graduated from the University of Chicago, and now he is a professor in Rutgers University, New Jersey. His research interests include complexity theory, combinatorics, combinatorial geometry and quantum computing, but he also has an interest in algebra. He received the Goedel Prize twice: in 2001 for his part in the PCP Theorem and its connection to inapproximability and in 2005 for the analysis of data streams using limited memory.
	Abstract:	The Odd Cycle Game is a two-prover game where the provers, Alice and Bob, both color their own copy of the odd cycle C_n with two colors. They optimize their coloring for the following verification procedure: The verifier picks a random 0 <= i <= n and a random type from {1,2}. In the type 1 test the verifier checks if Alice and Bob colored node $i$ in the same way. In the type 2 test the verifier checks if the color Alice gave to node i is different from the color Bob gave to node i+1 (mod n). The colorings of Alice and Bob has to be chosen before the verification procedure starts and it cannot be changed. It is easy to see that under the optimal coloring strategy Alice and Bob win the game against the verifier with probability 1-1/2n. This is the value of the Odd Cycle Game. If Alice and Bob players play several instances of the game in parallel, one might expect that the probability that they win in ALL copies (no matter what strategy they use) is not bigger than (1-1/2n)^N, where N is the number of copies. This is however not true, and we give the exact game value for two repeated copies (N=2). We also give estimates for for the game value for more repeated copies and also study the situation when the players are allowed to communicate a limited amount. Joint with Kooshiar Azimian

[Close]