Szymon Torunczyk

According to our database, Szymon Torunczyk authored at least 49 papers between 2009 and 2024.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2024

Twin-Width IV: Ordered Graphs and Matrices.

Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, Pierre Simon, Stéphan Thomassé, Szymon Torunczyk

J. ACM, June, 2024

Flip-Breakability: A Combinatorial Dichotomy for Monadically Dependent Graph Classes.

Jan Dreier, Nikolas Mählmann, Szymon Torunczyk

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Structurally Tractable Graph Classes (Invited Talk).

Szymon Torunczyk

Proceedings of the 41st International Symposium on Theoretical Aspects of Computer Science, 2024

Elementary first-order model checking for sparse graphs.

Jakub Gajarský, Michal Pilipczuk, Marek Sokolowski, Giannos Stamoulis, Szymon Torunczyk

Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science, 2024

2023

First-Order Model Checking on Monadically Stable Graph Classes.

Jan Dreier, Ioannis Eleftheriadis, Nikolas Mählmann, Rose McCarty, Michal Pilipczuk, Szymon Torunczyk

CoRR, 2023

Canonical Decompositions in Monadically Stable and Bounded Shrubdepth Graph Classes.

Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Szymon Torunczyk

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Flipper Games for Monadically Stable Graph Classes.

Jakub Gajarský, Nikolas Mählmann, Rose McCarty, Pierre Ohlmann, Michal Pilipczuk, Wojciech Przybyszewski, Sebastian Siebertz, Marek Sokolowski, Szymon Torunczyk

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Indiscernibles and Flatness in Monadically Stable and Monadically NIP Classes.

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Flip-width: Cops and Robber on dense graphs.

Szymon Torunczyk

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Register Automata with Extrema Constraints, and an Application to Two-Variable Logic.

Szymon Torunczyk, Thomas Zeume

Log. Methods Comput. Sci., 2022

Indiscernibles and Wideness in Monadically Stable and Monadically NIP Classes.

Jan Dreier, Nikolas Mählmann, Sebastian Siebertz, Szymon Torunczyk

CoRR, 2022

Stable graphs of bounded twin-width.

Jakub Gajarský, Michal Pilipczuk, Szymon Torunczyk

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Treelike Decompositions for Transductions of Sparse Graphs.

Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michal Pilipczuk, Szymon Torunczyk

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Model Checking on Interpretations of Classes of Bounded Local Cliquewidth.

Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon, Szymon Torunczyk

Proceedings of the LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science, Haifa, Israel, August 2, 2022

Algorithms and Data Structures for First-Order Logic with Connectivity Under Vertex Failures.

Michal Pilipczuk, Nicole Schirrmacher, Sebastian Siebertz, Szymon Torunczyk, Alexandre Vigny

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Twin-Width and Types.

Jakub Gajarský, Michal Pilipczuk, Wojciech Przybyszewski, Szymon Torunczyk

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Ordered graphs of bounded twin-width.

Pierre Simon, Szymon Torunczyk

CoRR, 2021

Nondeterministic and co-Nondeterministic Implies Deterministic, for Data Languages.

Bartek Klin, Slawomir Lasota, Szymon Torunczyk

Proceedings of the Foundations of Software Science and Computation Structures, 2021

2020

First-Order Interpretations of Bounded Expansion Classes.

Jakub Gajarský, Stephan Kreutzer, Jaroslav Nesetril, Patrice Ossona de Mendez, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

ACM Trans. Comput. Log., 2020

Aggregate Queries on Sparse Databases.

Szymon Torunczyk

Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2020

Uniformisations of Regular Relations Over Bi-Infinite Words.

Grzegorz Fabianski, Michal Skrzypczak, Szymon Torunczyk

Proceedings of the LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 2020

2019

Definable isomorphism problem.

Khadijeh Keshvardoost, Bartek Klin, Slawomir Lasota, Joanna Ochremiak, Szymon Torunczyk

Log. Methods Comput. Sci., 2019

Progressive Algorithms for Domination and Independence.

Grzegorz Fabianski, Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

Parameterized circuit complexity of model checking first-order logic on sparse structures.

Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

CoRR, 2018

On the number of types in sparse graphs.

Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

Parameterized circuit complexity of model-checking on sparse structures.

Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

On computability and tractability for infinite sets.

Mikolaj Bojanczyk, Szymon Torunczyk

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

2017

On Wideness and Stability.

Michal Pilipczuk, Sebastian Siebertz, Szymon Torunczyk

CoRR, 2017

LOIS: syntax and semantics.

Eryk Kopczynski, Szymon Torunczyk

Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages, 2017

Entropy Bounds for Conjunctive Queries with Functional Dependencies.

Tomasz Gogacz, Szymon Torunczyk

Proceedings of the 20th International Conference on Database Theory, 2017

2016

On Ultralimits of Sparse Graph Classes.

Michal Pilipczuk, Szymon Torunczyk

Electron. J. Comb., 2016

Cost Functions Definable by Min/Max Automata.

Thomas Colcombet, Denis Kuperberg, Amaldev Manuel, Szymon Torunczyk

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

The MSO+U Theory of (N, <) Is Undecidable.

Mikolaj Bojanczyk, Pawel Parys, Szymon Torunczyk

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

Homomorphism Problems for First-Order Definable Structures.

Bartek Klin, Slawomir Lasota, Joanna Ochremiak, Szymon Torunczyk

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Models of Lambda-Calculus and the Weak MSO Logic.

Pawel Parys, Szymon Torunczyk

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

Non-Homogenizable Classes of Finite Structures.

Albert Atserias, Szymon Torunczyk

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

LOIS: an Application of SMT Solvers.

Eryk Kopczynski, Szymon Torunczyk

Proceedings of the 14th International Workshop on Satisfiability Modulo Theories affiliated with the International Joint Conference on Automated Reasoning, 2016

2015

Locally Finite Constraint Satisfaction Problems.

Bartek Klin, Eryk Kopczynski, Joanna Ochremiak, Szymon Torunczyk

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

2014

Turing machines with atoms, constraint satisfaction problems, and descriptive complexity.

Bartek Klin, Slawomir Lasota, Joanna Ochremiak, Szymon Torunczyk

Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014

2013

Report on Highlights 2013.

Szymon Torunczyk

Bull. EATCS, 2013

Verification of database-driven systems via amalgamation.

Mikolaj Bojanczyk, Luc Segoufin, Szymon Torunczyk

Proceedings of the 32nd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2013

Turing Machines with Atoms.

Mikolaj Bojanczyk, Bartek Klin, Slawomir Lasota, Szymon Torunczyk

Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, 2013

2012

Weak MSO+U over infinite trees.

Mikolaj Bojanczyk, Szymon Torunczyk

Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Languages of Profinite Words and the Limitedness Problem.

Szymon Torunczyk

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Imperative Programming in Sets with Atoms.

Mikolaj Bojanczyk, Szymon Torunczyk

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

Automata based verification over linearly ordered data domains.

Luc Segoufin, Szymon Torunczyk

Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

2010

On the Topological Complexity of MSO+U and Related Automata Models.

Szczepan Hummel, Michal Skrzypczak, Szymon Torunczyk

Proceedings of the Mathematical Foundations of Computer Science 2010, 2010

Energy and Mean-Payoff Games with Imperfect Information.

Aldric Degorre, Laurent Doyen, Raffaella Gentilini, Jean-François Raskin, Szymon Torunczyk

Proceedings of the Computer Science Logic, 24th International Workshop, 2010

2009

Deterministic Automata and Extensions of Weak MSO.

Mikolaj Bojanczyk, Szymon Torunczyk

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009