{Symmetry, Logic, Computation}

Program

Logical Structures in Computation

Location

Calvin Lab Auditorium

Date

Monday, Nov. 7 – Thursday, Nov. 10, 2016

Back to calendar

Click on the titles of individual talks for abstract, slides and archived video.

9 – 9:20 a.m.

Coffee and Check-In

9:20 – 9:30 a.m.

Opening Remarks

9:30 – 10:30 a.m.

Orbit-Finite Sets

Mikolaj Bojanczyk, University of Warsaw

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

The Power of Two Variables

Howard Straubing, Boston College

11:30 a.m. – 12 p.m.

Towards Capturing Order-Independent P

Neil Immerman, University of Massachusetts

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

New Results on Register Automata

Andrzej Murawski, University of Warwick

2:30 – 3 p.m.

Simulation and Bisimulations for Probabilistic Systems, and their Logical Contents

Nathanaël Fijalkow, University of Oxford

3 – 3:30 p.m.

Operations on Languages and Codensity Monads

Daniela Petrisan, Université Paris Diderot

3:30 – 4 p.m.

Break

4 – 4:30 p.m.

Fibred Categories of Tree Automata

Colin Riba, ENS Lyon

4:30 – 5 p.m.

Pro-Aperiodic Monoids via Saturated Models

Sam Van Gool, City College of New York

5 – 6 p.m.

Reception

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

Lower Bounds for Subgraph Isomorphism and Consequences in First-Order Logic

Benjamin Rossman, University of Toronto

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

A Dichotomy Structure Theorem for the Resilience Problem

Cibele Freire, University of Massachusetts

11:30 a.m. – 12 p.m.

Symmetric Circuits and Fixed-Point Logics

Matthew Anderson, Union College

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

One Eilenberg Theorem to Rule Them All

Stefan Milius, Universität Erlangen-Nürnberg

2:30 – 3 p.m.

A Finite Alternation Result for Reversible Boolean Circuits

Peter Selinger, Dalhousie University

3 – 3:30 p.m.

Graph Isomorphism Via Non-Local Games

Simone Severini, University College London

3:30 – 4 p.m.

Break

4 – 4:30 p.m.

Extending Symmetric Circuits

Gregory Wilsenach, University of Cambridge

4:30 – 5 p.m.

Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps

Christoph Berkholz, Humboldt-Universität zu Berlin

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10:30 a.m.

{Symmetry, Logic, Constraint Satisfaction Problem}

Libor Barto, Charles University

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Combinatorial Properties of the Weisfeiler-Leman Algorithm

Sandra Kiefer,,
RWTH,
Aachen

11:30 a.m. – 12 p.m.

Approximating Graph Isomorphism through Linear Maps

Anuj Dawar, University of Cambridge

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

Power and Limits of LP and SDP Relaxations

Stanislav Zivny, University of Oxford

2:30 – 3 p.m.

Reducts of Finitely Bounded Homogeneous Structures, and Lifting Tractability from Finite-Domain Constraint Satisfaction

Antoine Mottet, TU Dresden

3 – 3:30 p.m.

Finite Duality, Connectivity of Homomorphisms, Spatial Mixing and Gibbs Measures

Andrei Bulatov, Simon Fraser University

3:30 – 4 p.m.

Break

4 – 4:30 p.m.

FO-Definable Constraint Satisfaction Problems

Joanna Ochremiak, Universitat Politecnica de Catalunya

4:30 – 5 p.m.

Braid Groups, Hecke Algebras, Representations, and Anyons

Andreas Blass, University of Michigan

9 – 9:30 a.m.

Coffee and Check-In

9:30 – 10 a.m.

Functional Programming Over Sets with Atoms

Bartek Klin, University of Warsaw

10 – 10:30 a.m.

Logic and Bisimulation for Guarded Teams

Erich Grädel, RWTH Aachen University

10:30 – 11 a.m.

Break

11 – 11:30 a.m.

Logic in Computer Science, Engineering and Industry

Yuri Gurevich, Microsoft Research

11:30 a.m. – 12 p.m.

Symmetry-Preserving Finite Synthesis and Amalgamation

Martin Otto, Technische Universität Darmstadt

12 – 2 p.m.

Lunch

2 – 2:30 p.m.

Logics of Finite Hankel Rank

Johann Makowsky, Technion Israel Institute of Technology

2:30 – 3 p.m.

The Logic of Counting Query Answers

Hubie Chen, Universidad del,
País,
Vasco

3 – 3:30 p.m.

Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

Prajakta Nimbhorkar, Chennai Mathematical Institute

3:30 – 4 p.m.

Break

4 – 4:30 p.m.

Testing Assignments to Constraint Satisfaction Problems

Matt Valeriote, McMaster University

4:30 – 5 p.m.

The Expressiveness of Recognizability by Orbite Finite Nominal Monoids

Thomas,
Colcombet, IRIF