CALL FOR PAPERS COMPUTATIONAL COMPLEXITY Seventeenth Annual IEEE Conference May 21-24, 2002 Montreal, Quebec, Canada 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 12th, 2001, 23:59 EST**, for consideration. The paper should not exceed 10 pages. See below for submission instructions. 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. JOINT SESSION WITH STOC'02 The STOC and Complexity Program Committees decided to schedule a Joint Session for 2002. See below for details. CONFERENCE COMMITTEE Lance Fortnow (chair), NEC Research Manindra Agrawal, Indian Inst. of Tech. Kanpur Luc Longpre, U.\ of Texas at El Paso Jack Lutz, Iowa State Univ. Pierre McKenzie, U. Montreal Toni Pitassi, U. of Toronto Alexander Razborov, Steklov Math. Inst. Madhu Sudan, MIT PROGRAM COMMITTEE Anne Condon (chair), U. British Columbia Harry Buhrman, CWI, Amsterdam Sam Buss, U. C. San Diego Jin-Yi Cai, U. Wisconsin Sophie Laplante, U. Paris-Sud Dieter van Melkebeek, U. Wisconsin Amit Sahai, Princeton Michael Saks, Rutgers Univ. John Watrous, U. of Calgary IMPORTANT DATES Submissions Due: Nov. 12, 2001 Notification: Jan. 19, 2002 Final Copies due: Mar. 6, 2002 LOCAL ARRANGEMENTS CO-CHAIRS Pierre McKenzie, U. Montreal Denis Therien, McGill U. SPONSORS The conference is sponsored by the IEEE Computer Society Technical Committee for Mathematical Foundations of Computing in cooperation with ACM SIGACT and EATCS, with support from the Centre de Recherches Mathematiques de l'Universite de Montreal. FOR MORE INFORMATION Get more information through our complexity web site: http://www.cs.utep.edu/longpre/complexity.html or at this year's conference web site: http://www.CRM.UMontreal.CA/CCC You may also contact the publicity chair: Luc Longpr\'{e}; Computer Science Department, University of Texas at El Paso, El Paso, TX 79968, USA; E-mail: longpre@cs.utep.edu. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ COMPUTATIONAL COMPLEXITY: ADDITIONAL DETAILS ELECTRONIC SUBMISSIONS We prefer electronic submissions. Please read the instructions on the world-wide web at http://sigact.acm.org/~coco2002/Complexity02.html or send e-mail to coco2002@sigact.acm.org with subject "HELP". 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: the 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, condon@cs.ubc.ca, (604) 822-8175, or at Anne Condon The Department of Computer Science 2366 Main Mall University of British Columbia Vancouver, B.C. V6T 1Z4 CONFERENCE PAPER AWARDS An award will be given to the **best paper** submitted to the conference. In addition, the **Ron Book Prize for Best Student Paper** 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. For each respective award, the program committee may decline to make the award or may split it among several papers. JOINT SESSION WITH STOC'02 Abstract material which has been previously published in another conference proceedings or journal or which is simultaneously submitted to another conference with published proceedings, will not be considered for acceptance at Complexity'02. This year, there will be an exception to this rule for submissions to the STOC Conference. In particular, the STOC and Complexity Program Committees decided to schedule a Joint Session for 2002. Authors who wish to have their abstract considered for the Joint Session should submit their abstract to both conferences and so notify both Program Committee Chairs. STOC dates are May 19--21 and the STOC submissions deadline is also Nov. 12. See http://sigact.acm.org/stoc02/ for updates. Abstracts that are accepted for the Joint Session will appear in the STOC'02 proceedings, and a 1-page version of the abstract will appear in the Complexity proceedings. Abstracts not accepted for the Joint Session will still be eligible for acceptance for an ordinary session. Authors are also encouraged to submit their papers to the Electronic Colloquium on Computational Complexity: http://www.eccc.uni-trier.de/eccc/ 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: William Gasarch Dept. of Computer Science Univ. of Maryland College Park, MD 20742 USA Email: gasarch@cs.umd.edu THE CONFERENCE SITE The conference will take place on the campus of Universite de Montreal, and accommodations will be available at both the University residences and a nearby hotel. There is a subway station in front of the University, which gives access to all parts of the city.