LICS 2024 Accepted Papers

Victor Dalmau and Jakub Opršal. Local consistency as a reduction between constraint satisfaction problems
Lorenzo Ciardo, Marcin Kozik, Andrei Krokhin, Tamio-Vesa Nakajima and Stanislav Živný. 1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
Pierre-Marie Pédrot. “Upon This Quote I Will Build My Church Thesis”
Manuel Bodirsky, Žaneta Semanišinová and Carsten Lutz. The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems
Demian Banakh and Marcin Kozik. Injective hardness condition for PCSPs
Ismaël Jecker, Filip Mazowiecki and David Purser. Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
Arka Ghosh and Sławomir Lasota. Equivariant ideals of polynomials
Yoàv Montacute and Glynn Winskel. Concurrent Games over Relational Structures ---the origin of game comonads
Libor Barto, Silvia Butti, Alexandr Kazda, Caterina Viola and Stanislav Živný. Algebraic Approach to Approximation
Samuel Mimram and Emile Oleon. Delooping cyclic groups with lens spaces in homotopy type theory
Filippo Bonchi, Alessandro Di Giorgio, Nathan Haydon and Pawel Sobocinski. Diagrammatic Algebra of First Order Logic
Miroslav Chodil and Antonin Kucera. The Finite Satisfiability Problem for PCTL is Undecidable
Ali Asadi, Krishnendu Chatterjee, Jakub Svoboda and Raimundo Saona Urmeneta. Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights
Fabian Mitterwallner, Aart Middeldorp and René Thiemann. Linear Termination is Undecidable
Thomas Place and Marc Zeitoun. Dot-depth three, return of the J-class
Pierre Ohlmann and Mikołaj Bojańczyk. Rank-decreasing transductions
Wojciech Różowski and Alexandra Silva. A Completeness Theorem for Probabilistic Regular Expressions
Kirstin Peters and Nobuko Yoshida. Separation and Encodability in Mixed Choice Multiparty Sessions
Michael Blondin, Alain Finkel, Piotr Hofman, Filip Mazowiecki and Philip Offtermatt. Soundness of reset workflow nets
Antonio Casares and Pierre Ohlmann. Half-positional $\omega$-regular languages
Alexandre Clément, Noé Delorme and Simon Perdrix. Minimal Equational Theories for Quantum Circuits
Nicole Schirrmacher, Sebastian Siebertz, Giannos Stamoulis, Dimitrios M. Thilikos and Alexandre Vigny. Model Checking Disjoint-Paths Logic on Topological-Minor-Free Graph Classes
Udi Boker. Discounted-Sum Automata with Real-Valued Discount Factors
Chris Barrett, Willem Heijltjes and Daniel Castle. The Relational Machine Calculus
Pierre Clairambault and Simon Forest. An Analysis of Symmetry in Quantitative Semantics
Martin Grohe and Eran Rosenbluth. Are Targeted Messages More Effective?
Jakub Gajarský, Michał Pilipczuk, Szymon Toruńczyk, Giannos Stamoulis and Marek Sokołowski. Elementary first-order model checking for sparse graphs
Emmanuel Filiot, Ismaël Jecker, Christof Löding, Anca Muscholl, Gabriele Puppis and Sarah Winter. Finite-valued Streaming String Transducers
Sougata Bose, Rasmus Ibsen-Jensen and Patrick Totzke. Bounded-Memory Strategies in Partial-Information Games
Oskar Fiuk, Emanuel Kieronski and Vincent Michielini. On the complexity of Maslov’s class K
Masahito Hasegawa and Serge Lechenne. Braids, Twists, Trace and Duality in Combinatory Algebras
Sergey Goncharov, Stefan Milius, Stelios Tsampas and Henning Urbat. Bialgebraic Reasoning on Higher-order Program Equivalence
Emmanuel Hainry, Bruce Kapron, Jean-Yves Marion and Romain Péchoux. Declassification Policy for Program Complexity Analysis
Cameron Allett. Non-Elementary Compression of First-Order Proofs in Deep Inference Using Epsilon-Terms
Eric Finster, Alex Rice and Jamie Vicary. A Syntax for Strictly Associative and Unital ∞-Categories
Vasileios Koutavas, Yu-Yang Lin and Nikos Tzevelekos. Pushdown Normal-Form Bisimulation: A Nominal Context-Free Approach to Program Equivalence
Liron Cohen, Yannick Forster, Dominik Kirst, Bruno da Rocha Paiva and Vincent Rahli. Separating Markov's Principles
Thorsten Wißmann and Stefan Milius. Initial Algebras Unchained - A Novel Initial Algebra Construction Formalized in Agda
Marie Kerjean and Pierre-Marie Pédrot. ∂ is for Dialectica
Maximilian Pflueger, Johannes Marti and Egor V. Kostylev. A Characterisation Theorem for Two-Way Bisimulation-Invariant Monadic Least Fixpoint Logic Over Finite Structures
Zeinab Galal and Jean-Simon Pacaud Lemay. Combining fixpoint and differentiation theory
Benedict Bunting and Andrzej Murawski. Contextual Equivalence for State and Control via Nested Data
Bharat Adsul, Paul Gastin, Shantanu Kulkarni and Pascal Weil. An expressively complete local past propositional dynamic logic over Mazurkiewicz traces and its applications
Piotr Ostropolski-Nalewaja and Tim Lyon. Decidability of Quasi-Dense Modal Logics
Raheleh Jalali and Stefan Hetzl. On the Completeness of Interpolation Algorithms
Victor Arrial, Giulio Guerrieri and Delia Kesner. Genericity Through Stratification
Nathan Lhote, Vincent Michielini and Michał Skrzypczak. Uniformisation of Regular Relations in First-Order Logic with Two Variables
Pierre Cagne, Ulrik Buchholtz, Nicolai Kraus and Marc Bezem. On symmetries of spheres in univalent foundations
Eren Keskin and Roland Meyer. On the Separability Problem of VASS Reachability Languages
Tal Hershko and Maksim Zhukovskii. First order distinguishability of sparse random graphs
Lorenzo Ciardo. Quantum advantage and CSP complexity
Valérie Berthé, Toghrul Karimov, Joris Nieuwveld, Joel Ouaknine, Mihir Vahanwala and James Worrell. On the Decidability of Monadic Second-Order Logic with Arithmetic Predicates
Nadim Kasymov, Nadira Karimova and Bakh Khoussainov. Defining algorithmically presented structures in first order logic
Noah Abou El Wafa and André Platzer. Complete Game Logic with Sabotage
Sandra Kiefer and Daniel Neuen. Bounding the Weisfeiler--Leman Dimension via a Depth-Analysis of I/R-Trees
James Hefford and Matt Wilson. A Profunctorial Semantics for Quantum Supermaps
A. R. Balasubramanian. Decidability and Complexity of Decision Problems for Affine Continuous VASS
Harry Vinall-Smeeth. From Quantifier Depth to Quantifier Number: Separating Structures with k Variables
Pietro Di Gianantonio and Abbas Edalat. A Cartesian Closed Category for Random Variables
Danila Demin and Maksim Zhukovskii. First order complexity of finite random structures
Søren Brinck Knudstorp. Relevant S is Undecidable
Christian Sattler and David Wärn. Natural numbers from integers
Philip Saville and Hugo Paquet. Effectful semantics in bicategories: strong, commutative, and concurrent pseudomonads
Victor Blanchi and Hugo Paquet. Element-free probability distributions and random partitions
Alex Simpson. Equivalence and Conditional Independence in Atomic Sheaf Logic
Ashwani Anand, Sylvain Schmitz, Lia Schütze and Georg Zetzsche. Verifying Unboundedness via Amalgamation
Laura Ciobanu and Georg Zetzsche. Slice closures of indexed languages and word equations with counting constraints
John Li, Jon Aytac, Philip Johnson-Freyd, Amal Ahmed and Steven Holtzen. A Nominal Approach to Probabilistic Separation Logic
Ulrik Buchholtz and Johannes Schipp von Branitz. Primitive Recursive Dependent Type Theory
Nihil Shah and Amin Karamlou. No Go Theorems: Directed Containers That Do Not Distribute Over Distribution Monads
Anupam Das and Abhishek De. A proof theory of right-linear (omega-)grammars via cyclic proofs
Mayuko Kori, Kazuki Watanabe, Jurriaan Rot and Shin-Ya Katsumata. Composing Codensity Bisimulations

LICS Sponsorship

The symposium is sponsored by ACM SIGLOG and the IEEE Technical Committee on Mathematical Foundations of Computing.

  • ACM
  • IEEE

Website by Sam Staton based on a bootstrap design by Hartmut Eilers and Eric Koskinen.