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.