Joanna Ochremiak Photo Joanna Ochremiak Photo


My name is Joanna Ochremiak.

I am a Marie Skłodowska-Curie research fellow at the Computer Laboratory, University of Cambridge.


I am mainly interested in applications of logic to the study of algorithms and complexity. Especially in the areas of constraint satisfaction problems, finite model theory, proof complexity, database theory & computation over infinite structures.


Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem | with Albert Atserias

LICS 2018  ||  full↓

Proof Complexity Meets Algebra | with Albert Atserias

ICALP 2017  ||  download↓  ||  full↓

Homomorphism Problems for First-Order Definable Structures | with Bartek Klin, Sławek Lasota, Szymon Toruńczyk

FSTTCS 2016  ||  download↓  ||  full↓

Extended Constraint Satisfaction Problems

PhD thesis  ||  download↓

Eliminating Recursion from Monadic Datalog Programs on Trees | with Filip Mazowiecki, Adam Witkowski

MFCS 2015  ||  download↓

Locally Finite Constraint Satisfaction Problems | with Bartek Klin, Eryk Kopczyński, Szymon Toruńczyk

LICS 2015  ||  download↓

Algebraic Properties of Valued Constraint Satisfaction Problem | with Marcin Kozik

ICALP 2015  ||  download↓  ||  full↓

Turing Machines with Atoms, Constraint Satisfaction Problems, and Descriptive Complexity | with Bartek Klin, Sławek Lasota, Szymon Toruńczyk

LICS 2014  ||  download↓

Nominal Sets over Algebraic Atoms

RAMiCS 2014  ||  download↓


Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem

13.11.2018  Theory Group Research Seminar Queen Mary University of London
19.09.2018  HIGHLIGHTS 2018 Berlin
12.07.2018  LICS 2018 Oxford  ||  download↓
15.06.2018  Logique et Vérification Laboratoire d'Informatique de Paris Nord

Algebraic and Semi-Algebraic Proof Systems | 19.07.2018

invited talk at Autobóz 2018 Gèdre, France

Sum-of-Squares, Counting Logics and Graph Isomorphism

27.03.2018  Séminaire Algo Université Paris Est
30.01.2018  Proof Complexity Dagstuhl Seminar
26.01.2018  Valda Seminar ENS Paris

Proof Complexity Meets Algebra

13.12.2017  Logical Structures in Computation Simons Institute, UC Berkeley
17.08.2017  Proof Complexity and Beyond Oberwolfach Workshop
11.07.2017  ICALP 2017 Warsaw  ||  download↓

Proof Complexity of Constraint Satisfaction Problems

03.11.2017  Links' Seminar Lille
31.10.2017  DIMAP Seminar University of Warwick
03.10.2017  Séminaire de l'équipe Méthodes Formelles LaBRI, Bordeaux
15.09.2017  HIGHLIGHTS 2017 London
07.09.2017  Finite and Algorithmic Model Theory Dagstuhl Seminar  ||  download↓
03.05.2017  Current Topics in Logic and Database Theory Berlin  ||  download↓
12.04.2017  Automata Seminar University of Warsaw

FO-Definable Constraint Satisfaction Problems

15.05.2017  Séminaire Général de Logique Institut de Mathématiques de Jussieu
9.11.2016  {Symmetry, Logic, Computation} Simons Institute, UC Berkeley  ||  download↓

Computation in Sets with Atoms | 19.09.2016

guest lecture at QuantLA workshop  ||  download↓

Homomorphism Problems for First-Order Definable Structures

21.04.2016  Logic & AI Seminar Imperial College London
12.04.2016  ALGA 2016 Marseille  ||  download↓

Extended Constraint Satisfaction Problems | 24.02.2016

PhD defence  ||  download↓

Algebraic Necessary Condition for Tractability of Valued CSP | 18.09.2015

HIGHLIGHTS 2015 Prague  ||  download↓

Deciding FO-definable CSP instances | 24.07.2015

The Constraint Satisfaction Problem Dagstuhl Seminar  ||  download↓

Locally Finite Constraint Satisfaction Problems

08.07.2015  LICS 2015 Kyoto
02.06.2015  Verification Seminar Oxford  ||  download↓
22.05.2015  ToCAI Seminar Middlesex University, London
15.05.2015  Logic and Semantics Seminar Cambridge
09.01.2015  Seminar “Automata” LIAFA, Paris

Algebraic Properties of Valued Constraint Satisfaction Problem

06.07.2015  ICALP 2015 Kyoto  ||  download↓
20.05.2015  Algorithms Seminar Oxford

Turing Machines with Atoms and Constraint Satisfaction Problems | 3.09.2014

HIGHLIGHTS 2014 Paris  ||  download↓

Nominal Sets over Algebraic Atoms | 29.04.2014

RAMiCS 2014  ||  download↓


MSCA Individual Fellowship InfCSP

ANR grant AGGREG led by Joachim Niehren

ERC grant AUTAR led by Albert Atserias

NCN grant New Notion of Finiteness in Theory of Computation led by Mikołaj Bojańczyk

Blog on computation with atoms


joanna.ochremiak (at) gmail (dot) com

Created by ZN - Copyright 2014