|
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.
| 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.
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 reservations@mail.aux.umass.edu. 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.
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.
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
Please see the local arrangements web site.
The conference is sponsored by the IEEE Computer Society Technical Committee for Mathematical Foundations of Computing in cooperation with ACM, SIGACT and EATCS.
Please see the local arrangements web site.
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.
Welcome reception: 8:00pm to 10:00pm, Top of the Campus Center
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
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
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
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
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
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
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
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
2:00pm to 3:05pm
Consequences and Limits of Nonlocal Strategies (Cleve, Høyer, Toner, Watrous)
Multiparty Quantum Coin Flipping (Ambainis, Buhrman, Dodis, and Roehrig)
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
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
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.