[Colloquium] TTI-C Guest Speaker, Ran Raz 10/17/05 @

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE TALK
 
Speaker:  Ran Raz, Weizmann Institute
 
Speaker's homepage: http://www.wisdom.weizmann.ac.il/~ranraz/ 
 
Time:  Monday, October 17, 2005 3:00pm
 
Location:  TTI-C Conference Room 
 
 
Title: Quantum Information and the PCP Theorem
 
 
Abstract:
 
I will discuss the following two results. I will assume no prior knowledge
of quantum information or the PCP theorem.
 
1) The membership of $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$ a verifier only needs to read ONE of
the blocks of the classical proof. This shows that if a short quantum
witness is available then a (classical) PCP with only one query is possible.
 
2) The class $QIP/qpoly$ contains ALL languages. That is: for any language
$L$ (even non-recursive), the membership of $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$).
 
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 verifier can
also be replaced by a classical probabilistic advice, as long as this advice
is kept as a secret from the prover. The second result can hence be
interpreted as: The class $IP/rpoly$ contains all languages.
 
For the proof of the second result, we introduce the "quantum
low-degree-extension" of a string of bits. The first result requires an
additional machinery of "quantum low-degree-test". 
 
-----------------------------------------------------------------
 
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.   For information on future
TTI-C talks and events, please go to the TTI-C Events page:
http://www.tti-c.org/events.html.  TTI-C (1427 East 60th Street, Chicago, IL
60637)
 
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20051010/5910e4aa/attachment.htm