Joanna Fijalkow Photo Joanna Fijalkow Photo

Hello

My name is Joanna Fijalkow (Ochremiak).

I am a CNRS researcher at LaBRI, a computer science research lab in Bordeaux.




Research

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.

News

15 - 17 Nov. 2023   ||   2nd Workshop on Logic, Graphs, and Algorithms LoGAlg 2023 in Warsaw

13 - 14 Dec. 2023   ||   Complexity Days in Paris

29 Jan. - 2 Feb. 2024   ||   Research School in Discrete Mathematics and Computer Science at CIRM in Marseille

Papers

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

SIAM Journal on Computing (SICOMP) 2023  ||  download↓

On the Power of Symmetric Linear Programs | with Albert Atserias, Anuj Dawar

Journal of the ACM (JACM) 2021  ||  ACM DL Author-ize service download↓

Definable Isomorphism Problem | with Khadijeh Keshvardoost, Bartek Klin, Sławek Lasota, Szymon Toruńczyk

Logical Methods in Computer Science (LMCS) 2019  ||  download↓

On the Power of Symmetric Linear Programs | with Albert Atserias, Anuj Dawar

LICS 2019  ||  download↓  ||  full↓

Proof Complexity Meets Algebra | with Albert Atserias

ACM Transactions on Computational Logic (TOCL) 2019  ||  ACM DL Author-ize service download↓

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

LICS 2018  ||  ACM DL Author-ize service download↓  ||  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

CSL-LICS 2014  ||  ACM DL Author-ize service download↓

Nominal Sets over Algebraic Atoms

RAMiCS 2014  ||  download↓

Talks

On the Power of Symmetric Linear Programs

29.06.2022  invited talk at Logic Colloquium 2022 (special session on Computer Science Logic), Reykjavik
20.03.2019  Automata Theory Seminar, University of Warsaw

A Brief Introduction to Proof Complexity | 28.06.2021

Logic Mentoring Workshop

Proof Complexity meets Finite Model Theory

07.06.2021  MIAO Video Seminar, University of Copenhagen & Lund University
03.03.2021  Theoretical Foundations of SAT/SMT Solving, Simons Institute, UC Berkeley

Understanding the Power of Linear and Semidefinite Programming Using Logic | 04.04.2019

invited talk at Complexité et Algorithmes, Roscoff, France

Proof Complexity of the Graph Isomorphism Problem | 13.03.2019

Journées Nationales du GdR Informatique Mathématique, Orléans

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

15.04.2021  Fellows Talk, Simons Institute, UC Berkeley
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 Theory 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, Marienstatt im Westerwald  ||  download↓

PROJECTS

ERC grant BOBR led by Michał Pilipczuk


ANR grant QUID led by Claire David


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




contact

joanna.fijalkow (at) gmail (dot) com




Created by ZN - Copyright 2014