Call for Papers

Computational Complexity

Eighteenth Annual IEEE Conference

http://computationalcomplexity.org

July 7–10, 2003

Aarhus, Denmark

Conference Committee Lance Fortnow (chair), NEC Research Manindra Agrawal, Indian Inst. of

Tech., Kanpur Pierre McKenzie, U. of Montréal Peter Bro Miltersen, U. of Aarhus Toni Pitassi, U. of Toronto Alexander Razborov, Steklov Math.

Inst. John Rogers, DePaul U. Michael Saks, Rutgers U.

Program Committee Harry Buhrman (chair), CWI and U.

of Amsterdam David Barrington, U. of

Massachusetts Maria Luisa Bonet, UPC Barcelona Oded Goldreich, Weizmann Institute

of Science Johan Håstad, Royal Institute of

Technology, Stockholm Steve Homer, Boston U. Ilan Newman, Haifa U. Marcus Schaefer, DePaul U. Gábor Tardos, Rényi Institute,

Budapest Nikolai Vereshchagin, Moscow State

U.

Important Dates Submissions Due: Nov. 27th, 2002 Notification: Mar. 4th, 2003 Final Copies Due: Apr. 18th, 2003

Local Arrangements Peter Bro Miltersen (chair), U. of

Aarhus Gerth Stølting Brodal, U. of Aarhus Ulrich Kohlenbach, U. of Aarhus Karen K. Møller, U. of Aarhus Sven Skyum, U. of Aarhus

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 27th, 2002, 23:59 EST, for consideration. The paper should not exceed 10 pages. See submission instructions on the next page.

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 through our complexity web site (http://computationalcomplexity.org) or at (http://www.brics.dk/Complexity2003/), this year’s conference web site. You may also contact the publicity chair: John Rogers, CTI, DePaul University, 243 S. Wabash, Chicago IL 60604, USA; Email: jrogers@cs.depaul.edu.

The next page has more details.

Electronic Submissions We prefer electronic submissions. Please read the instructions on the world-wide web at http://sigact.csci.unt.edu/∼ccc03/CCC03.html or send e-mail to ccc03@sigact.acm.org with subject “HELP”.

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 2003 and will not be considered for acceptance. Authors are encouraged to submit their papers to the Electronic Colloquium on Computational Complexity (http://www.eccc.uni-trier.de/eccc/)

Submission Guidelines The conference has imposed a firm limitation of ten pages (in 11 point or larger fonts) on submissions. The ten-page limit excludes the following: cover page, bibliography, and 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. Use appendices to substantiate your major technical results.

Authors with no access to electronic submissions please contact the program committee chair by e-mail to Harry.Buhrman@cwi.nl, by telephone at +31-20-5924076, or by mail to

Harry Buhrman CWI, INS 4 Kruislaan 413 1098 SJ Amsterdam The Netherlands

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

Ron 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.

Special Kolmogorov Session On Sunday, July 6th, a one-day session in honor of the 100th anniversary of the birth of A. N. Kolmogorov will be held in Aarhus. The session is titled “Complexity, Information, and Randomness: The Legacy of Andrei Kolmogorov.” All who are attending the conference are welcome and encouraged to come.

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 take place at the University of Aarhus. The city of Aarhus (Århus) is located on the eastern shore of the Jutland peninsula, and is the second largest city in Denmark with approximately 280,000 inhabitants (including suburbs). Aarhus is both a metropolis and a village: it offers cultural activities, shopping, and commerce, but still the countryside is reachable within twenty minutes from the city centre. Aarhus is served by Aarhus and Billund airports and can also be reached by train from Copenhagen or Hamburg.