some hits of focs'07

(UW theory reading group -- fall'07)

Place: CSE 503
Time: Wednesday 3:00pm - 4:30pm

Future meeting(s):

Any AND-OR formula of size N can be evaluated in time N^{1/2+o(1)} time on a quantum computer [pdf]

(by Ambainis, Childs, Reichardt, Spalek, and Zhang)

date: October 24th, 2007
speaker: Dave

Towards sharp inapproximability for any 2-CSP [pdf]

(by Austrin)

date: October 31st, 2007
speaker: Punya

possible list of other papers

Pseudorandom bits for polynomials via the Gowers norm (Bogdanov and Viola)
On the Complexity of Nash Equilibria and Other Fixed Points (Etessami and Yannakakis)
The Computational Hardness of Estimating Edit Distance (Andoni and Krauthgamer)
Identity Based Encryption Without Pairings (Boneh, Gentry, and Hamburg)
Hardness of Reconstructing Multivariate Polynomials over Finite Fields (Gopalan, Khot, and Saket)

Previous meetings:

One-way multi-party communication lower bound for pointer jumping with applications [pdf]

(by Viola and Wigderson)

date: October 3rd, 2007
speaker: Paul

A Primal-Dual Randomized Algorithm for Weighted Paging [pdf]

(by Bansal, Buchbinder, and Naor)

date: October 10th, 2007
speaker: Ben

Organizer: james