Fall 2016

Logical Structures in Computation

Aug. 17Dec. 16, 2016

Logic has played a fundamental role throughout the development of Computer Science, profoundly influencing such areas as programming languages, verification, databases, descriptive complexity, and knowledge representation and reasoning. These interactions have led to the emergence of the field of Logic in Computer Science, which spans a vast range of specialized topics, and has led to deep and conceptually innovative research. Within this broad area, one can distinguish two main underlying themes: the first is the interaction of logic with the analysis of algorithms and computational complexity, and the second is the study of the semantics of programs and processes. While one can identify some specific pieces of recent research that bring these themes together, such examples are still rather rare.

The aim of this program is to bring together, for the first time on a significant scale, researchers from selected areas of logic in computer science, but at different ends of the spectrum.  The focus will be on four different strands: finite and algorithmic model theory; logic and probability; logic and quantum mechanics; and logic and databases. We envision two-way and three-way interactions between these four strands, which may both create bridges between the strands and advance the state-of-the-art in each of them. The program will be complemented by three workshops with themes that underlie all four strands: compositionality in computation; symmetry in computation; and uncertainty in computation.

We believe that this program may have a significant and lasting impact in advancing logic in computer science, bringing different communities together and stimulating the fruitful cross-fertilization of ideas. The focus and critical mass of key participants over the duration of the program will allow a common technical language and awareness of cross-cutting themes and ideas to be developed within the various communities at different ends of the spectrum of logic in computer science. These should lead both to advances on existing problems, and to greater cohesiveness and collaboration in future work.


Samson Abramsky (University of Oxford), Anuj Dawar (University of Cambridge), Phokion G. Kolaitis (UC Santa Cruz and IBM Research - Almaden), Prakash Panangaden (McGill University)

Long-Term Participants (including Organizers):

Samson Abramsky (University of Oxford), Albert Atserias (Universitat Politècnica de Catalunya), Nathalie Bertrand (INRIA), Andreas Blass (University of Michigan), Achim Blumensath (Masaryk University), Mikołaj Bojańczyk (University of Warsaw), Sam Buss (UC San Diego), Thomas Colcombet (CNRS), Vincent Danos (University of Edinburgh), Anupam Das (École Normale Supérieure de Lyon), Anuj Dawar (University of Cambridge), Kousha Etessami (University of Edinburgh), Sara Faridi (Dalhousie University), Diego Figueira (CNRS), Mai Gehrke (Universite Paris Diderot - Paris 7), Erich Grädel (RWTH Aachen), André Hernich (University of Liverpool), Chris Heunen (University of Edinburgh), Jane Hillston (University of Edinburgh), Wesley Holliday (UC Berkeley), Dominic Horsman (Durham University), Bart Jacobs (University of Nijmegen), Bartek Klin (University of Warsaw), Phokion G. Kolaitis (UC Santa Cruz and IBM Research - Almaden), Marta Kwiatkowska (University of Oxford), Johann Makowsky (Technion Israel Institute of Technology), Shane Mansfield (Universite Paris Diderot - Paris 7), Michael Mislove (Tulane University), Antonio Montalban (UC Berkeley), Ugo Montanari (University of Pisa), Jaroslav Nešetřil (Charles University), Martin Otto (TU Darmstadt), Prakash Panangaden (McGill University), Simon Perdrix (CNRS, Loria), Daniela Petrisan (Université Paris Diderot), Gordon Plotkin (University of Edinburgh), Stuart Russell (UC Berkeley), Thomas Scanlon (UC Berkeley), Dana Scott (Carnegie Mellon University), Peter Selinger (Dalhousie University), Simone Severini (University College London), Alexandra Silva (University College London), Theodore Slaman (UC Berkeley), Val Tannen (University of Pennsylvania), Jouko Väänänen (University of Helsinki), Franck van Breugel (York University), Jamie Vicary (University of Oxford), Thomas Zeume (TU Dortmund)

Research Fellows:

Matthew Anderson (Union College), Christoph Berkholz (Humboldt University of Berlin), Nathanaël Fijalkow (University of Oxford), Tomer Kotek (Vienna University of Technology), Joanna Ochremiak (Universitat Politecnica de Catalunya), R. Ramyaa (New Mexico Institute of Mining and Technology), Miguel Romero (University of Chile), Rui Soares Barbosa (University of Oxford)

Visiting Graduate Students and Postdocs:

Alexis Bernadet (Dalhousie University), Xiaoning Bian (Dalhousie University), Giovanni Caru (University of Oxford), Kenta Cho (Radboud University), Nadish de Silva (University College London), Andru Gheorgiu (University of Edinburgh), Marijana Lazić (Technische Universität Wien), Bert Lindenhovius (Tulane University), Daniel Mills (University of Oxford), Nick Ramsey (UC Berkeley), Matteo Sammartino (University College London), Pengming Wang (University of Cambridge), Linde Wester (University of Oxford), Gregory Wilsenach (University of Cambridge), Kentarô Yamamoto (UC Berkeley), Vladimir Zamdzhiev (University of Oxford), Octavio Zapata (University College London)


Aug. 29Sep. 2, 2016


Samson Abramsky (University of Oxford), Anuj Dawar (University of Cambridge), Phokion G. Kolaitis (UC Santa Cruz and IBM Research - Almaden), Prakash Panangaden (McGill University)
Oct. 4Oct. 7, 2016


Prakash Panangaden (McGill University; chair), Dan Roy (University of Toronto), Dan Suciu (University of Washington), Eli Upfal (Brown University)
Nov. 7Nov. 10, 2016


Anuj Dawar (University of Cambridge; chair), Neil Immerman (University of Massachusetts, Amherst), Alexandra Silva (University College London)
Dec. 5Dec. 9, 2016


Samson Abramsky (University of Oxford; chair), Lucien Hardy (Perimeter Institute), Michael Mislove (Tulane University)
Dec. 11Dec. 14, 2017


Samson Abramsky (University of Oxford), Anuj Dawar (University of Cambridge), Phokion G. Kolaitis (UC Santa Cruz and IBM Research - Almaden), Prakash Panangaden (McGill University)

Program image: "Engine of Logic" by Phokion Kolaitis et al.