IEEE Conference on

Computational Complexity

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



The registration for CCC'04 is web based. Please register at the registration web site.  For information about local arrangements, visit the local arrangements web site.

Registration Fees (In US dollars)

Advance (by June 4th) Late (after June 4th)
Members US$320 US$385
Non-members US$405 US$475
Student members US$100 US$120
Student non-members US$125 US$145

Please Note: The non-student conference fee includes a copy of the proceedings, the Sunday evening reception, the Wednesday banquet, and lunches Monday, Tuesday and Wednesday.

The student conference fee includes a copy of the proceedings and the Sunday evening reception.   

Extra banquet tickets are US$40 each.  Extra proceedings are US$45 each.

A member is someone belonging to the ACM, EATCS, IEEE, or SIGACT.

Alternative registration

If electronic registration is not possible, please see the registration web site for an address to which mail your registration and a FAX number to which you can transmit it. 


The University of Massachusetts (UMass) has reserved a block of hotel rooms for Complexity 2004 at the UMASS Campus Center Hotel. Reservations should be made by June 6, 2004 to secure the rates of $75 for a single room and $85 for a double room. To make reservations at the Campus Center Hotel call them directly at 413-549-6000 or email them at Rooms are available in University Residence Halls for the nights of June 20 through 24 (departure on the 25th). Residence Hall Rooms are part of student housing on campus. Rooms provide each resident with a twin bed, dresser, desk, and chair. Linens are provided at check-in. Bathrooms are centrally located on each floor. Residence Halls are not air conditioned. You may reserve a residence hall room by going to the registration web site

Conference Information


Lectures will take place from Monday, June 21st, through Thursday, June 24th.  Breakout rooms and computer access will be made available.  We will have a Dagstuhl-style hike on the nearby Holyoke range on one of the afternoons.

The Sunday night reception (June 20th) will be on campus, probably in the Computer Science building.  Lunches will be at the Campus Center.  There will be a banquet at a local restaurant to be decided, and there are many fine restaurants available in Amherst and nearby Northampton for dinners.

Rooms will be available at the Campus Center Hotel on the UMass campus, only a few minutes walk from the lecture hall.  Alternate housing will be available in campus dormitories for the budget-conscious and in nearby commercial lodgings.

Social Program

Welcome reception: Sunday evening, 8:00pm to 10:00pm, Top of the Campus Center

Rump Session: Monday evening, 8:45pm, Polymer Science Auditorium

Hike: Tuesday afternoon, busses leave for the Notch Visitor Center at 2:30pm and return by 6:00pm

Business meeting: Tuesday evening, 8:30pm, Polymer Science Auditorium

Banquet: Wednesday evening, 7:00pm to 10:00pm, Lord Jeffrey Inn, Amherst

Getting There and Getting Around

Please see the local arrangements web site.

Additional Information


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

Local Arrangements

Please see the local arrangements web site.

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.  Details about submissions format and deadline will be posted here shortly.  


Local Arrangements: David Mix Barrington, U. of Massachusetts, Amherst; Neil Immerman, U. of Massachusetts, Amherst.

Program Committee: Russell Impagliazzo (chair), U. of California at San Diego; Eric Allender, Rutgers U.; Richard Beigel, Temple U.; Al Borodin, U. of Toronto; Shafi Goldwasser, MIT; Subhash Khot, Georgia Tech and IAS; Steven Rudich, CMU; Chris Umans, Caltech; Avi Wigderson, Hebrew U. and IAS.

Conference Committee: Lance Fortnow (chair), U. of Chicago; Manindra Agrawal, Indian Inst. of Tech., Kanpur; Harry Buhrman, CWI and U. of Amsterdam; Peter Bro Miltersen, U. of Aarhus; Toni Pitassi, U. of Toronto; John Rogers, DePaul U.; Michael Saks, Rutgers U.; Avi Widgerson, Hebrew U. and IAS.

Conference Program

SUNDAY, June 20th

Welcome reception: 8:00pm to 10:00pm, Top of the Campus Center

MONDAY, June 21st

Session 1

8:50am to 10:30am

Compression of Sampleable Sources (Trevisan, Vadhan, Zuckerman)

Language Compression and Pseudo-random Generators (Buhrman, Lee, van Melkebeek)

On Pseudoentropy vs. compressibility (Wee)

10:30am to 10:50am: Break

Session 2

10:50am to 12:30pm

Reductions between disjoint NP-pairs (Glasser, Selman, Sengupta)

Relativized NP search problems and propositional proof systems (Buresh-Oppenheim, Morioka)

The complexity of tree-lime Systems over k-Local Formulae (Galesi, Thapen)

12:30pm to 2:00pm: Lunch

Session 3

2:00pm to 3:05pm

Lower bounds for testing Bipartiteness in Dense Graphs (Bogdanov, Trevisan)

Polylogarithmic-round Interactive Proofs for Co-NP Collapse the Exponential Hierarchy (Selman, Sengupta)

3:05pm to 3:20pm: Break

Session 4

3:25pm to 4:30pm

Solvable group isomorphism is (almost) in NP \cap Co-NP (Arvind, Toran)

Small Spans in Scaled Dimensions (Hitchcock)

Rump Session: 8:45pm, Polymer Science Auditorium

TUESDAY, June 22nd

8:50am to 10:30am

Computing in fault-tolerance broadcast networks (Newman)

Some results on majority quantifiers over words (Lange)

Separating complexity classes using structural properties (Buhrman, Torenvliet)

10:30am to 10:50am: Break

Session 5

10:50am to 12:30pm

Parameterized complexity of constraint satisfaction problems (Marx)

Tight Lower Bounds for Certain Parameterized NP-hard Problems (Chen, Chor, Fellows, Huang, Juedes, Kanj, Xia)

The Complexity of the Covering Radius Problem on Lattices and Codes (Guruswami, Micciancio, Regev)

Tuesday afternoon: 2:30pm, depart by bus for a trip to the Notch Nature Center, which will include a hike

Business Meeting: 8:30pm, Polymer Science Auditorium

WEDNESDAY, June 23rd

Session 6

8:50am to 10:30am

Dimension, Entropy Rates, and Compression (Hitchcock, Vinodchandran)

Properties of NP-Complete sets (Glasser, Pavan, Selman, Sengupta)

Partial bi-immunity and NP-completeness (Hitchcock, Pavan, Vinodchandran)

10:30am to 10:50am: Break

Session 7

10:50am to 12:30pm

Abelian Permutation Group Problems and Logspace Counting Classes (Arvind, Vijayaraghavan)

Deterministic Polynomial Identity Testing in Non-Commutative Models (Raz, Shpilka)

Polynomials that Sign-Represent Parity and Descartes' Rule of Signs (Basu, Bhatmagar, Gopalan, Lipton)

12:30pm to 2:00pm: Lunch

Session 8

2:00pm to 3:05pm

Consequences and Limits of Nonlocal Strategies (Cleve, Hyer, Toner, Watrous)

Multiparty Quantum Coin Flipping (Ambainis, Buhrman, Dodis, and Roehrig)

Session 9

3:25pm to 4:30pm

On the Power of Quantum Proofs (Raz, Shpilka)

Quantum Arthur-Merlin Games (Marriott, Watrous)

Banquet: 7:00pm to 10:00pm, Lord Jeffrey Inn, Amherst

THURSDAY, June 24th

Session 10

9:15am to 10:20am

Graph properties and circular functions: How low can quantum query complexity go? (Sun, Yao, Zhang)

Lower bounds for randomized and quantum query complexity using Kolmogorov arguments (Laplante, Magniez)

10:20am to 10:40am: Break

Session 11

10:40am to 11:45am

Towards the classical communication complexity of entanglement distillation protocols with incomplete information (Ambainis, Yang)

Limitations of Quantum Advice and One-way Communication (Aaronson)

This document was last updated on Tuesday, April 27th, 2004.