IEEE Conference on

Computational Complexity

The Twentieth Annual Conference
Sponsored by
The IEEE Computer Society Technical Committee
on Mathematical Foundations of Computing


NB: Most of the information about local arrangements appearing here was copied verbatim from the local arrangements web site


The registration for CCC 2005 is web based. Please see the local arrangements web site for fees, deadlines, and other local information.


The conference will take place in Hotel Hyatt Sainte Claire located at 302 S. Market St. This historic hotel is located in the heart of downtown and is about 4 miles away from the San Jose airport.  Parking information for downtown is available here. There is a convenient Light Rail that services downtown and nearby areas, while Caltrain provides services to San Francisco. 

The hotel room rates for conference attendees is $119, single or double occupancy, plus applicable sales and room taxes.  While making reservations, mention that you are attending the IEEE CCC’05 --- Conference on Computational Complexity.

The hotel is within walking distance of a number of good restaurants, coffee shops, and bars.  Free wireless is available in some cafes and here. Nearby attractions include museums, theaters, and a cinematheque.


San Jose, the capital of Silicon Valley, is about 50 miles south of San Francisco. From within North America the best choice is the Mineta San Jose International Airport (SJC); another option is Oakland International Airport (OAK) that is an hour by car from the hotel. From Europe it might be easier to fly to the San Francisco International Airport (SFO), about an hour by car from the hotel.

From SJC, the most convenient way would be to take a shuttle (Bauer’s San Jose Airport Express) to reach the hotel and the cost is $10 (discount coupons are available on their website and might also be found in Hyatt Sainte Claire's lobby and presumably the airport).  Taxi might cost around $15.   From SFO, the options are to take SuperShuttle or South/East Bay Shuttle (1-800-548-4664, 408-225-4444, or 408-866-6660); the cost is roughly $35.  For a list of shuttle options from OAK, see here.  Taxi from SFO/OAK to the hotel will be an expensive option.

San Jose enjoys pleasant weather in June with an average high of 82° F (28.9° C) and an average low of 55° F (14.4° C).

Conference Information

Social Program

Welcome reception: Saturday evening, 7:00pm to 10:00pm

Business meeting: Sunday evening, 8:00pm to 10:00pm

Rump Session: Monday afternoon, 3:30pm to 5:30pm


The conference is sponsored by the IEEE Computer Society Technical Committee for Mathematical Foundations of Computing in cooperation with ACM, SIGACT and EATCS.

Complexity Abstracts

Each year, brief abstracts on current research on topics covered by the conference are made available electronically a week before the conference. Submission is open to all.  See the main Complexity web page for details. 


Local Arrangements: D. Sivakumar, IBM Almaden; Ravi Kumar, IBM Almaden

Program Committee: Scott Aaronson, IAS; Maria Bonet, Universidad Politécnica de Cataluña; Irit Dinur, UC Berkeley and Hebrew University; Anna Gal, UT Austin; Dieter van Melkebeek, U. of Wisconsin; Peter Bro Miltersen, U. of Aarhus; Ryan O'Donnell, Microsoft; Oded Regev, Tel Aviv University; Ronitt Rubinfeld, MIT; Luca Trevisan (chair), UC Berkeley

Conference Committee: Lance Fortnow (chair), U. of Chicago; Harry Buhrman, CWI and U. of Amsterdam; Anna Gál, U. of Texas; Peter Bro Miltersen, U. of Aarhus; John Rogers (publicity), DePaul U.; Michael Saks, Rutgers U.; Luca Trevisan, U. of California; Avi Widgerson, Hebrew U. and IAS.

Conference Program

Saturday, June 11, 2005

7.00 - 10.00 PM: Reception

Sunday, June 12, 2005

7.30 - 9.00 AM: Breakfast

9.00 - 10.30 AM: Session 1

On the Ring Isomorphism & Automorphism Problems by Neeraj Kayal, Nitin Saxena

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy by V. Arvind and Piyush P Kurur and T.C. Vijayaraghavan

The Complexity of the Inertia and some Closure Properties of GapL by Thanh Minh Hoang and Thomas Thierauf

10.30 - 11.00 AM: Break

11.00 - 11.45 AM: Session 2

Better Time-Space Lower Bounds for SAT and Related Problems by Ryan Williams

11:45 - 2.00 PM: Lunch (not provided)

2.00 - 3.30 PM: Session 3

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Disjointness by Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

Monotone Circuits for Weighted Threshold Functions by Amos Beimel and Enav Weinreb

The quantum adversary method and formula size lower bounds by S. Laplante, T. Lee, and M. Szegedy

3.30 - 4.00 PM: Break

4.00 - 5.00 PM: Session 4

More on noncommutative polynomial identity testing by Andrej Bogdanov and Hoeteck Wee

New Results on the Complexity of the Middle Bit of Multiplication by Ingo Wegener and Philipp Woelfel

8.00 - 10.00 PM: Business meeting

Monday, June 13, 2005

7.30 - 9.00 AM: Breakfast

9.00 - 10.30 AM: Session 5

On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas by Richard Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth Vishnoi

Short PCPs verifiiable in polylogarithmic time by Eli Ben-Sasson, Oded Goldriech, Prahladh Harsha, Madhu Sudan and Salil Vadhan

Tolerant Versus Intolerant Testing for Boolean Properties by Eldar Fischer and Lance Fortnow

10.30 - 11.00 AM: Break

11.00 - 12.00 PM: Session 6

Invited Lecture by Manuel Blum: Understanding "Understanding:" Steps toward a Mathematical Scientific Theory of Consciousness

12.00 - 2.00 PM: Lunch (not provided)

2.00 - 3.00 PM: Session 7

On the Hardness of Approximating Multicut and Sparsest-Cut by Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani and D.Sivakumar

Hardness of Max 3SAT with No Mixed Clauses by Venkatesan Guruswami, Subhash Khot

On the Sensitivity of Cyclically-Invariant Boolean Functions by Sourav Chakraborty

3.00 - 3.30 PM: Break

3.30 - 5:30 PM: Rump session

Tuesday, June 14, 2005

7.30 - 9.00 AM: Breakfast

9.00 - 10.30 AM: Session 8

On the Complexity of Hardness Amplification by Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu

On Constructing Parallel Pseudorandom Generators from One-Way Functions by Emanuele Viola

Pseudorandom Bits for Constant Depth Circuits with One Arbitrary Symmetric Gate by Emanuele Viola

10.30 - 11.00 AM: Break

11.00 - 11.45 AM: Session 9

Pseudorandomness for Approximate Counting and Sampling by Ronen Shaltiel and Chris Umans

11.45 - 2.00 PM: Lunch (not provided)

2.00 - 3.30 PM: Session 10

NP with Small Advice by Lance Fortnow and Adam Klivans

Average-Case Computations -- Comparing AvgP, HP, and Nearly-P by Arfst Nickelsen and Birgit Schelm

If NP languages are hard on the worst-case then it is easy to find their hard instances by Dan Gutfreund and Ronen Shaltiel and Amnon Ta-Shma

3.30 - 4.00 PM: Break

4.00 - 5.30 PM: Session 11

Computationally-Private Randomizing Polynomials and Their Applications by Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

A Geometric Approach to Information-Theoretic Private Information Retrieval by David Woodruff and Sergey Yekhanin

Prior entanglement, message compression and privacy in quantum communication by Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen

Wednesday, June 15, 2005

7.30 - 9.00 AM: Breakfast

9.00 - 10.30 AM: Session 12

Topology inside NC1 by Eric Allender, Samir Datta, Sambuddha Roy

Toward a Model for Backtracking and Dynamic Programming by M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, T. Pitassi

On the complexity of succinct zero-sum games by L. Fortnow and R. Impagliazzo and V. Kabanets and C. Umans

10.30 - 11.00 AM: Break

11.00 - 12.00 PM: Session 13

Upper Bounds for Quantum Interactive Proofs with Competing Provers by Gus Gutoski

On the hardness of distinguishing mixed-state quantum computations by Bill Rosgen and John Watrous

This document was last updated on Tuesday, June 7th, 2005.