Topic 12: Theory and Algorithms for Parallel Computation


Parallelism permeates all levels of current computing systems, from single CPU machines, to large server farms, to geographically dispersed "volunteers" who collaborate over the Internet. The effective use of parallelism depends crucially on the availability of faithful, yet tractable, models of computation for algorithm design and analysis and of efficient strategies for solving key computational problems on prominent classes of computing platforms. No less important are good models of the way the different components/subsystems of a platform are interconnected. With the development of new genres of computing platforms, such as multicore parallel machines, desktop grids, and hybrid GPU/CPU-based systems, new models and paradigms are needed, that will allow parallel programming to advance into mainstream computing. High-quality, original, papers are solicited, that contribute new results on foundational issues regarding parallelism in computing and/or proposing improved approaches to the solution of specific algorithmic problems. Topics of interest include, but are not limited to, the following:


  • Foundations, Models, and Emerging paradigms for parallel, distributed, multiprocessor and network computation
  • Deterministic and randomized parallel algorithms
  • Lower bounds for key computational problems
  • Models and algorithms for parallelism in memory hierarchies
  • Models and algorithms for real networks (scale-free, small world, wireless networks)
  • Theoretical aspects of routing

Topic Committee

Global chair

Arnold Rosenberg, Colorado State University, USA

Local chair

Frédéric Vivien, INRIA, France


Kunal Agrawal, Washington University in St Louis, USA
Panagiota Fatourou, University of Crete, Greece