Computational Complexity

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

Tutorials

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

ccc2000@dsi.unifi.it

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

Sponsors

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: longpre@utep.edu

The next page has more details.