Theory and Algorithms for Parallel Computation

Topic 13


The goal of algorithm design and complexity theory in parallel/distributed computing is to study efficient algorithms for (and limitations on the complexity of) problems, taking into account such parallel complexity measures as the number of processing nodes, the amount of communication or other resources in addition to classical measures such as time and space. Research areas such as development of efficient parallel algorithms including new techniques on randomization and approximation, on realistic parallel computation models, communication complexity, parallel complexity classes, and lower bounds for specific problems have received a lot of attention in recent years, but many important problems remain open. We invite papers concerning investigations in these areas.


  • static algorithms and lower bounds for key computational problems in specific applications
  • models of parallel  and distributed computing (e.g., BSP, CGM, LogP, PRAM,  fixed processor networks, Boolean circuits, BDDs, ...)
  • deterministic, randomized or approximation algorithms for these problems
  • communication complexity
  • parallel complexity classes
  • emerging new paradigms of parallel computing (quantum computing, optical computing, biocomputing, ...)   

Global Chair

Prof. Christos Kaklamanis

Computer Technology Institute and

Department of Computer Engineering & Informatics

University of Patras, Greece


Vice Chairs

Prof. Danny Krizanc

Computer Science Group

Mathematics Department

Wesleyan University, USA


Dr. Pierre Fraigniaud

Laboratoire de Recherche en Informatique   

Université Paris-Sud, France


Local Chair

Prof. Michael Kaufmann

Wilhelm-Schickard-Institut für Informatik

Universität Tübingen, Germany