Call for Papers

Computational Complexity

Nineteenth Annual IEEE Conference

http://computationalcomplexity.org

June 21–24, 2004

Amherst, Massachussets

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

Program Committee Russell Impagliazzo (chair), U. of

California, 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 Widgerson, Hebrew U. and IAS

Important Dates Submissions Due: Nov. 26th, 2003 Notification: Feb. 13th, 2004 Final Copies Due: Apr. 9th, 2004

Local Arrangements David Mix Barrington, U. of

Massachussets, Amherst Neil Immerman, U. of Massachussets,

Amherst

The conference seeks original research papers in all areas of computational complexity theory. We also encourage results from other areas of computer science and mathematics motivated by topics in complexity theory. The following list of possible topics is not exhaustive:

Complexity classes  Reducibility
Algebraic Complexity  Communication complexity
Proof complexity  Complexity and logic
Interactive proof systems  Nonapproximability
Circuits and other concrete Cryptographic complexity
computational models  Complexity and learning
Kolmogorov complexity  Quantum computation

A submission must be received by November 26th, 2003, 23:59 EST, for consideration. The paper should not exceed 20 pages. For instructions on submitting, please see the web site computationalcomplexity.org.

Authors of accepted papers are expected to present their work at the conference. The program committee will determine time allocations for presentations (between 15 and 45 minutes). Conference proceedings will be published by the IEEE Computer Society. Publication in the conference proceedings does not preclude subsequent journal publication.

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

More Information Get more information at the web site, computationalcomplexity.org, or at this year’s local arrangements web site, www.cs.umass.edu/∼barring/ccc2004/. You may also contact the publicity chair: John Rogers, De-Paul University, 243 S. Wabash, Chicago IL 60604, USA; E-mail: jrogers@cs.depaul.edu.

The next page has more details.

Electronic Submissions We prefer electronic submissions. Instructions can be found at the permanent conference web site computationalcomplexity.org.

Submissions to other conferences Abstract material which has been previously published in another conference proceedings or journal or which is simultaneously submitted to another conference with published proceedings may not be submitted to Computational Complexity 2004 and will not be considered for acceptance. Authors are encouraged to submit their papers to the Electronic Colloquium on Computational Complexity, found at the web site www.eccc.uni-trier.de/eccc/.

Submission Guidelines The conference has imposed a firm limitation of twenty pages (in 11 point or larger fonts) on submissions. This limit includes the bibliography and any technical appendices. Submissions deviating from these guidelines risk summary rejection. In your abstract (i) explain what the paper’s major contributions are, (ii) convey why these contributions are interesting, and (iii) tell how these contributions relate to prior work.

Authors with no access to electronic submissions may contact Russell Impagliazzo, the program committee chair, by e-mail to russell@cs.ucsd.edu or by telephone at +1-858-534-1332.

Final Copies The instructions for final copies will be communicated to authors of accepted papers.

Ronald V. Book Prize for Best Student Paper This award will be given to the best paper written solely by one or more students. An abstract is eligible if all authors are full-time students at the time of submission. This should be indicated in the submission registration message or cover letter. The program committee may decline to make the award or may split it among several papers.

Best Paper Award This award will be given to the best paper submitted to the conference. This will be awarded by the program committee. The program committee may decline to make the award or may split it among several papers.

Conference Abstracts In conjunction with the conference, contributed short research abstracts will be collected and will be made available a few days before the conference. Attendance at the conference is not required to submit an abstract. For more details, check the conference web site or contact the abstracts editor: Stephen Fenner, Dept. of Computer Science and Engineering, U. of South Carolina, Columbia SC 29208 USA; E-mail: fenner@cse.sc.edu.

The Conference Site The conference will be held on the campus of the University of Massachusetts Amherst, in the beautiful Pioneer Valley of western Massachusetts. Amherst and nearby Northampton, each with a year-round population of about 20,000, are the centers of a region famous both for education (with four well-known undergraduate colleges as well as UMass) and agriculture. Historical sites, good restaurants, and recreational opportunities abound. Access by air is from Logan Airport in Boston (two hours drive) and Bradley Airport in Connecticut (one hour drive). Access by rail and bus is also possible.