LICS 2022 Accepted Papers

Daniel Gratzer. Normalization for Multimodal Type Theory
Edon Kelmendi. Computing the Density of the Positivity Set for Linear Recurrence Sequences
Junyi Liu, Li Zhou, Gilles Barthe and Mingsheng Ying. Quantum Weakest Preconditions for Reasoning about Expected Runtimes of Quantum Programs
Richard Lipton, Florian Luca, Joris Nieuwveld, Joel Ouaknine, David Purser and James Worrell. On the Skolem Problem and the Skolem Conjecture
C. Aiswarya, Soumodev Mal and Prakash Saivasan. On the Satisfiability of Context-free String Constraints with Subword Ordering
Nathanael Ackerman, Julian Asilis, Jieqi Di, Cameron Freer and Jean-Baptiste Tristan. Computable PAC Learning of Continuous Features
Nikhil Balaji, Klara Nosan, Mahsa Shirmohammadi and James Worrell. Identity testing for radical expressions
Jiri Adamek. Varieties of quantitative algebras and their monads
Martin Avanzini, Georg Moser, Romain Péchoux, Simon Perdrix and Vladimir Zamdzhiev. Quantum Expectation Transformers for Cost Analysis
Arka Ghosh, Piotr Hofman and Sławomir Lasota. Solvability of orbit-finite systems of linear equations
Benedikt Ahrens, Paige North and Niels van der Weide. Semantics for two-dimensional type theory
Yoàv Montacute and Nihil Shah. The Pebble-Relation Comonad in Finite Model Theory
Thomas Place. The amazing mixed polynomial closure and its applications to two-variable first-order logic
Wojciech Czerwiński, Engel Lefaucheux, Filip Mazowiecki, David Purser and Markus Whiteland. The boundedness and zero isolation problems for weighted automata over nonnegative rationals
Francesco Dagnino and Fabio Pasquali. Logical Foundations of Quantitative Equality
Remi Delannoy and Kuldeep S. Meel. On Almost-Uniform Generation of SAT Solutions: The power of 3-wise independent hashing
Clemens Kupke, Johannes Marti and Yde Venema. Size measures and alphabetic equivalence in the mu-calculus
Gianluca Curzi and Anupam Das. Cyclic Implicit Complexity
Michael Blondin, Filip Mazowiecki and Philip Offtermatt. The complexity of soundness in workflow nets
Anca Muscholl and Igor Walukiewicz. Active learning for sound negotiations
Pierre Ohlmann. Characterizing Positionality in Games of Infinite Duration over Infinite Graphs
Bart Jacobs. Partitions and Ewens Distributions in element-free Probability Theory
R. Govind, Frédéric Herbreteau, B Srivathsan and Igor Walukiewicz. Abstractions for the local-time semantics of timed automata: a foundation for partial-order methods
Ilario Bonacina and Maria Luisa Bonet. On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems
Moses Ganardi, Rupak Majumdar and Georg Zetzsche. The complexity of bidirected reachability in valence systems
Davide Barbarossa. Resource approximation for the lambda-mu-calculus
Pascal Bergsträßer, Moses Ganardi, Anthony W. Lin and Georg Zetzsche. Ramsey Quantifiers over Automatic Structures: Complexity and Applications to Verification
Kristina Sojakova and G. A. Kavvos. Syllepsis in Homotopy Type Theory
Moritz Lichter and Pascal Schweitzer. Choiceless Polynomial Time with Witnessed Symmetric Choice
Jan Dreier, Jakub Gajarský, Sandra Kiefer, Michał Pilipczuk and Szymon Toruńczyk. Treelike decompositions for transductions of sparse graphs
Paweł Idziak, Piotr Kawałek and Jacek Krzaczkowski. Complexity of Modular Circuits
Guanyan Li, Andrzej Murawski and Luke Ong. Probabilistic Verification Beyond Context-Freeness
Clemens Grabmayer. Milner's Proof System for Regular Expressions Modulo Bisimilarity is Complete
Lukas Heidemann, David Reutter and Jamie Vicary. Zigzag normalisation for associative n-categories
Antoine Mottet and Michael Pinsker. Smooth approximations and CSPs over finitely bounded homogeneous structures
Diego Figueira and Anthony Widjaja Lin. Reasoning on Data Words over Numeric Domains
Sean Moss and Paolo Perrone. Probability monads with submonads of deterministic states
Jakub Gajarský, Michał Pilipczuk and Szymon Toruńczyk. Stable graphs of bounded twin-width
Wojciech Czerwiński and Łukasz Orlikowski. Lower Bounds for the Reachability Problem in Fixed Dimensional VASSes
Erich Grädel, Hayyan Helal, Matthias Naaf and Richard Wilke. Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics
Magnus Baunsgaard Kristensen, Rasmus Ejlers Møgelberg and Andrea Vezzosi. Greatest HITs: Higher inductive types in coinductive definitions via induction under clocks
Laurent Doyen. Stochastic Games with Synchronizing Objectives
Jens Oliver Gutsfeld, Arne Meier, Christoph Ohrem and Jonni Virtema. Temporal Team Semantics Revisited
Melissa Antonelli, Ugo Dal Lago and Paolo Pistone. Curry and Howard Meet Borel
Aliaume Lopez. When Locality Meets Preservation
Beniamino Accattoli, Ugo Dal Lago and Gabriele Vanoni. Reasonable Space for the Lambda-Calculus, Logarithmically
Eric Finster, David Reutter, Jamie Vicary and Alex Rice. A Type Theory for Strictly Unital Infinity-Categories
Beniamino Accattoli. Exponentials as Substitutions and the Cost of Cut Elimination in Linear Logic
Luc Dartois, Paul Gastin, Govind R and Krishna S. Efficient Construction of Reversible Transducers from Regular Transducer Expressions
Elena Di Lavore, Giovanni de Felice and Mario Román. Monoidal Streams for Dataflow Programming
Matteo Mio, Ralph Sarkis and Valeria Vignudelli. Beyond Nonexpansive Operations in Quantitative Algebraic Reasoning
Guillaume Geoffroy. A first-order completeness result about characteristic Boolean algebras in classical realizability
Édouard Bonnet, Jan Dreier, Jakub Gajarský, Stephan Kreutzer, Nikolas Mählmann, Pierre Simon and Szymon Toruńczyk. Model Checking on Interpretations of Classes of Bounded Local Cliquewidth
Anuj Dawar and Felipe Ferreira Santos. Separating LREC from LFP
Raven Beutner, David Carral, Bernd Finkbeiner, Jana Hofmann and Markus Krötzsch. Deciding Hyperproperties Combined with Functional Specifications
Cristina Matache, Sean Moss and Sam Staton. Concrete categories and higher-order recursion (with applications including probability, differentiability, and full abstraction)
Corentin Barloy, Michaël Cadilhac, Charles Paperman and Thomas Zeume. The Regular Languages of First-Order Logic with One Alternation
Dmitry Chistikov, Christoph Haase and Alessio Mansutti. Geometric decision procedures and the VC dimension of linear arithmetic theories
Takeshi Tsukada and Kazuyuki Asada. Linear-Algebraic Models of Linear Logic as Categories of Modules over Sigma-Semirings
Chase Ford, Stefan Milius, Lutz Schröder, Harsh Beohar and Barbara König. Graded Monads and Behavioural Equivalence Games
Valentin Blot. A direct computational interpretation of second-order arithmetic via update recursion
David Baelde, Amina Doumane, Denis Kuperberg and Alexis Saurin. Bouncing threads for circular and non-wellfounded proofs
Paul-André Melliès. A functorial excursion between algebraic geometry and linear logic

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.