Call for Papers

Computational Complexity

Fifteenth Annual IEEE Conference

July 4-7, 2000

Florence, Italy

Conference Committee

Eric Allender (chair), Rutgers Univ.
Richard Beigel, U. Illinois at Chicago
Harry Buhrman, CWI, Amsterdam
Lance Fortnow, U. Chicago and NEC Research
Russell Impagliazzo, U.C. San Diego
Luc Longpré, U. of Texas at El Paso
Madhu Sudan, Mass. Inst. Tech.
Jacobo Torán, U. of Ulm

Program Committee

Pavel Pudlák (chair), Acad. Science Czech. Rep.
Ricard Gavaldà, U. Polit. de Catalunya
Russell Impagliazzo, U. C. San Diego
Ran Raz, Weizmann Inst.
Alexander Razborov, Steklov Math. Inst.
Uwe Schoening, U. Ulm
Denis Thérien, McGill U.
Luca Trevisan, Columbia U.
R. Venkatesan, Microsoft Research

Invited Speaker

Paul Beame, U. Washington


Luca Trevisan, Columbia U.
Russell Impagliazzo, U. C. San Diego

Important Dates

Submissions Due: Jan. 19, 2000
Notification: Mar. 24, 2000

Local Arrangements

Pierluigi Crescenzi

The conference seeks original research papers in all areas of 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


Algebraic Complexity

Communication complexity

Proof complexity

Complexity and logic

Interactive proof systems


Circuits and other concrete

Cryptographic complexity

computational models

Complexity and learning

Kolmogorov complexity

Quantum computation

A submission must be received by January 19th, 2000 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.


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

For More Information

Get more information through our complexity web site, or at this year's conference web site. You may also contact the publicity chair: Luc Longpré; Computer Science Department, University of Texas at El Paso, El Paso, TX 79968, USA; E-mail:

The next page has more details.