The Complexity of Forecast Testing
Lance Fortnow
Thursday, January 25, 4:30-5:30pm, CSE 3725
Abstract
Consider a weather forecaster predicting a probability of rain for the
next day. We consider tests that given a finite sequence of forecast
predictions and outcomes will either pass or fail the forecaster. Sandroni
(2003) shows that for any test that passes a forecaster that knows the
distribution of nature can be probabilistically passed by a forecaster
that has no knowledge of future events. We look at how complex the
forecaster needs to be to pass the tests. A good tester is one that passes
the truth, i.e., any forecaster that gives the true probabilities of
future events will pass the test with high probability. An ignorant
forecaster bases his predictions solely on previous outcomes. We show 1)
For any reasonable time-bound t(n), there are good testers that run in
time t^2(n) that will fail with high probability all ignorant forecasters
running in time t(n) for a specific distribution. 2) We create a
linear-time good tester and such that any ignorant forecaster that passes
the test with high probability on all distributions can be used to factor
arbitrary integers efficiently. 3) We extend the previous result so that
any ignorant forecaster can solve arbitrary NP search problems like
traveling salesperson and graph coloring and even PSPACE-hard problems
like playing a perfect game of chess on an arbitrary size board. Joint
work with Rakesh Vohra (Northwestern/Kellogg)
Biography
Lance Fortnow received
his Ph.D. in Applied Mathematics at MIT in 1989 and has spent his academic
career in Computer Science at the University of Chicago with the exception
of a senior research scientist position at the NEC Research Institute from
1999-2003. In 1992 he received the NSF Presidential Faculty Fellowship and
was a Fulbright Scholar visiting CWI in Amsterdam 1996-97. Fortnow studies
computational complexity and its applications to electronic commerce,
quantum computation, bioinformatics, learning theory and cryptography.
Fortnow also writes the popular scientific and academic weblog
Computational Complexity (http://weblog.fortnow.com)
Zero-Knowledge Proof Systems Secure
against Quantum Attacks
Shengyu Zhang
Thursday, November 30, 4:30-5:30pm, CSE 3941
Abstract
In this talk, I will discuss the recent breakthrough of the
Zero-Knowledge proofs against quantum attacks. After briefly reviewing
the concepts of zero-knowledge, I will introduce the main idea of the
recent result by Watrous [STOC'06] that two particular classical ZK
protocols (those for Graph Isomorphism and Graph 3 Coloring) are also
zero-knowledge against quantum verifiers. Then I will show how to
transform a classical Honest Verifier SZK proof to a classical protocol
which is also SZK against both arbitrary classical and arbitrary quantum
verifiers. This answers the main open question in Watrous' [STOC'06]
paper.
Short Bio
Shengyu Zhang received the B.S. in Mathematics at Fudan University in
1999, a M.S. in Computer Science at Tsinghua University in 2002 (under
the supervision of Mingsheng Ying), and the Ph.D. in Computer Science at
Princeton University in 2006 (under the supervision of Andrew Yao). He
is currently a postdoc at California Institute of Technology.
Recent results in the search for new quantum
algorithms
Wim van Dam
Friday, October 26, 2-3pm, Room TBA
Abstract
A central role in the the theory of quantum algorithms is played by the
Hidden Subgroup Problem where one tries to find the hidden symmetry of a
function that is defined over a group. For different groups this problem
relates to various standard computational problems such as factoring,
counting solutions of finite field equations, lattice problems and graph
isomorphism. In 1994 Peter Shor showed that there exists an efficient
quantum algorithm for the Hidden Subgroup Problem over Abelian groups,
which allowed him to construct his famous algorithm for discrete
logarithms and factoring. Finding similar quantum algorithms for
non-Abelian groups has turned out to be much more difficult.
In this talk I will first give an overview of the Hidden Subgroup
Problem and the quantum algorithm for the Abelian case. After that, I
will describe some of the recent progress on the non-Abelian Hidden
Subgroup Problem, some positive, some negative. Special attention will
be paid to the need to find average case classical algorithms for
problems such as Subset Sum, which are useful as subroutines for quantum
algorithms for Shortest Vector Problems.
Short Bio
Wim van Dam is an assistant professor in computer science and physics at
the University of California, Santa Barbara. His research focuses on the
theory of quantum computation and all things related, with an emphasis
on the development of new quantum algorithms that give an exponential
speed-up when compared with traditional, classical algorithms.
Van Dam received his Ph.D. in Physics from the University of Oxford, UK
in 2000 and in 2002 he received his Ph.D. in Computer Science from the
University of Amsterdam, The Netherlands. Before joining the Computer
Science Department at UCSB in July 2004 and the Physics Department in
July 2005, he was a postdoc at UC Berkeley, HP Labs Palo Alto, The
Mathematical Sciences Research Institute and MIT.