LICS 2021 Accepted Papers

Fusible numbers and Peano Arithmetic – Jeff Erickson, Gabriel Nivasch and Junyan Xu.

Asynchronous Template Games – Paul-André Melliès

First-Order Reasoning and Efficient Semi-Algebraic Proofs – Fedor Part, Neil Thapen and Iddo Tzameret.

PTAS for Sparse General-Valued CSPs – BalCizs F. Mezei, Marcin Wrochna and Stanislav Živný.

Higher lenses – Paolo Capriotti, Nils Anders Danielsson and Andrea Vezzosi.

Forbidden Induced Subgraphs and the Los-Tarski Theorem – Yijia Chen and Jörg Flum

Positive first-order logic on words – Denis Kuperberg.

Graphical Language with Delayed Trace: Picturing Quantum Computing with Finite Memory – Titouan Carette, Simon Perdrix and Marc De Visme.

A Constructive Logic with Classical Proofs and Refutations – Pablo Barenbaum and Teodoro Freund.

The smash product of monoidal theories – Amar Hadzihasanovic.

Jade Master and Michael Shulman. Categories of Nets – John Baez, Fabrizio Romano Genovese.

LovaLsz-type Theorems and Game Comonads – Anuj Dawar, Tomáš Jakl and Luca Reggio.

Living without Beth and Craig: Definitions and Interpolants in the Guarded and Two-Variable Fragments – Jean Christoph Jung and Frank Wolter.

Inapproximability of Unique Games in Fixed-Point Logic with Counting – Jamie Tucker-Foltz.

Internal b‑-Categorical Models of Dependent Type Theory: Towards 2LTT Eating HoTT – Nicolai Kraus.

From Multisets over Distributions to Distributions over Multisets – Bart Jacobs.

Combinatorial Proofs and Decomposition Theorems for First-order Logic – Dominic Hughes, Lutz Straßburger and Jui-Hsuan Wu.

The Undecidability of System F Typability and Type Checking for Reductionists – Andrej Dudenhefner.

The Topological Mu-Calculus: completeness and decidability – Alexandru Baltag, Nick Bezhanishvili and David FernCindez-Duque.

Universal Semantics for the Stochastic Lambda-Calculus – Pedro H Azevedo de Amorim, Dexter Kozen, Radu Mardare, Prakash Panangaden and Michael Roberts.

Parikh’s theorem for infinite alphabets – Piotr Hofman, Marta Juzepczuk, Sławomir Lasota and Mohnish Pattathurajan.

Multi-Structural Games and Number of Quantifiers – Ronald Fagin, Jonathan Lenchner, Kenneth W. Regan and Nikhil Vyas.

Commutative Monads for Probabilistic Programming Languages – Xiaodong Jia, Bert Lindenhovius, Michael Mislove and Vladimir Zamdzhiev.

Zero-one laws for provability logic:Axiomatizing validity in almost all models and almost all frames – Rineke Verbrugge. 

Some constructive variants of S4 with the finite model property – Philippe Balbiani, Martín Diéguez and David FernC!ndez-Duque.

Symbolic Time and Space Tradeoffs for Probabilistic Verification – Krishnendu Chatterjee, Wolfgang Dvořák, Monika Henzinger and Alexander Svozil. 

No-Rainbow Problem and the Surjective Constraint Satisfaction Problem – Dmitriy Zhuk.

Evidenced Frames: A Unifying Framework Broadening Realizability Models – Liron Cohen, Etienne Miquey and Ross Tate.

Continuous One-Counter Automata – Michael Blondin, Tim Leys, Filip Mazowiecki, Philip Offtermatt and Guillermo Perez.

Combining nondeterminism, probability, and termination: equational and metric reasoning – Matteo Mio, Ralph Sarkis and Valeria Vignudelli.

Normalization for Cubical Type Theory – Jonathan Sterling and Carlo Angiuli.

Separating Rank Logic from Polynomial Time – Moritz Lichter.

Stochastic Processes with Expected Stopping Time – Krishnendu Chatterjee and Laurent Doyen.

Smart Choices and the Selection Monad – Martin Abadi and Gordon Plotkin.

A Quantum Interpretation of Bunched Logic & Quantum Separation Logic – Li Zhou, Gilles Barthe, Justin Hsu, Mingsheng Ying and Nengkun Yu.

Behavioural Preorders via Graded Monads – Chase Ford, Stefan Milius and Lutz Schröder.

Responsibility and verification: Importance value in temporal logics – Corto Mascle, Christel Baier, Florian Funke, Simon Jantsch and Stefan Kiefer.

Finite Model Theory of the Triguarded Fragment and Related Logics – Emanuel Kieronski and Sebastian Rudolph.

The Laplace Mechanism is optimal for differential privacy over continuous queries – Annabelle McIver, Natasha Fernandes and Carroll Morgan.

From Finite-Valued Nondeterministic Transducers to Deterministic Two-Tape Automata – Elisabet Burjons, Fabian Frei and Martin Raszyk. 

Deciding Differential Privacy for Programs with Unbounded Inputs – Rohit Chadha, A. Prasad Sistla and Mahesh Viswanathan.

Asynchronous extensions of HyperLTL – Laura Bozzelli, Adriano Peron and Cesar Sanchez.

Fast algorithms for the satisfiability of two-variable logic – Ting-Wei Lin, Chia-Hsuan Lu and Tony Tan.

Assuming Just Enough Fairness to make Session Types Complete for Lock-freedom – Rob van Glabbeek, Peter Höfner and Ross Horne.

SD-Regular Transducer Expressions for Aperiodic Transformations – Luc Dartois, Paul Gastin and Shankara Narayanan Krishna.

Types are Internal infinity-groupoids – Antoine Allioux, Eric Finster and Matthieu Sozeau.

Global Optimisation with Constructive Reals – Dan Ghica and Todd Waugh Ambridge.

Categorical models of Linear Logic with fixed points of formulas – Thomas Ehrhard and Farzad Jafarrahmani.

Parameterized Complexity of Elimination Distance to First-Order Logic Properties – Fedor Fomin, Petr Golovach and Dimitrios Thilikos.

Constraint Satisfaction Problems over Finite Structures – Libor Barto, William DeMeo and Antoine Mottet.

A compositional cost model for the lambda-calculus – James Laird.

Strong Call-by-Value is Reasonable, Implosively – Beniamino Accattoli, Andrea Condoluci and Claudio Sacerdoti Coen.

GC6del-McKinsey-Tarski and Blok-Esakia for Lewis-Brouwer Implication – Jim de Groot, Tadeusz Litak and Dirk Pattinson.

On Logics and Homomorphism Closure – Manuel Bodirsky, Thomas Feller, Simon Knaeuer and Sebastian Rudolph.

Lacon- and Shrub-Decompositions: A New Characterization of First-Order Transductions of Bounded Expansion Classes – Jan Dreier.

Expressivity of Quantitative Modal Logics: Categorical Foundations via Codensity and Approximation – Yuichi Komorida, Shin-Ya Katsumata, Clemens Kupke, Jurriaan Rot and Ichiro Hasuo.

On sequentiality and well-bracketing in the O-calculus – Daniel Hirschkoff, Enguerrand Prebet and Davide Sangiorgi.

On Generalized Metric Spaces for the Simply Typed Lambda-Calculus – Paolo Pistone.

Parametricity and Semi-Cubical Types – Hugo Moeneclaey.

A Logic for Locally Complete Abstract Interpretations – Roberto Bruni, Roberto Giacobazzi, Roberta Gori and Francesco Ranzato.

Efficient Local Computation of Differential Bisimulations via Coupling and Up-to Methods – Giorgio Bacci, Giovanni Bacci, Kim Guldstrand Larsen, Mirco Tribastone, Max Tschaikowski and Andrea Vandin.

Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property – Manuel Bodirsky and Bertalan Bodor.

Intersection Type Distributors – Federico Olimpieri.

Orbit-Finite-Dimensional Vector Spaces and Weighted Register Automata – Mikołaj Bojańczyk, Bartek Klin and Joshua Moerman.

A Bunched Logic for Conditional Independence – Jialu Bao, Simon Docherty, Justin Hsu and Alexandra Silva.

An Algebraic Characterisation of First-Order Logic with Neighbour – Amaldev Manuel and Dhruv Nevatia.

Fixed-Points for Quantitative Equational Logics – Radu Mardare, Gordon Plotkin and Prakash Panangaden.

Perspective Multi-Player Games – Orna Kupferman and Noam Shenwald.

On the Expressive Power of Homomorphism Counts – Albert Atserias, Phokion Kolaitis and Wei-Lin Wu.

Decidability and Complexity in Weakening and Contraction Hypersequent Substructural Logics – R. Balasubramanian, Timo Lang and Revantha Ramanayake.

Demonic Lattices and Semilattices in Relational Semigroups with Ordinary Composition – Robin Hirsch and Jas Semrl.

On Monadic Rewriting Systems, Part I – Francesco Gavazzo and Claudia Faggian.

The Space of Interaction – Beniamino Accattoli, Ugo Dal Lago and Gabriele Vanoni.

Universal Skolem Sets – Florian Luca, Joel Ouaknine and James Worrell.

Supermartingales, Ranking Functions and Probabilistic Lambda Calculus – Andrew Kenyon-Roberts and Luke Ong.

Compositional Semantics for Probabilistic Programs with Exact Conditioning – Dario Stein and Sam Staton.

Verifying higher-order concurrency with data automata – Alex Dixon, Ranko Lazic, Andrzej Murawski and Igor Walukiewicz.

Quantitative and Approximate Monitoring – Thomas A. Henzinger and N. Ege SaraC’.

Monomial-size vs. Bit-complexity in Sums-of-Squares and Polynomial Calculus – Tuomas Hakoniemi.

Axiomatizations and Computability of Weighted Monadic Second-Order Logic – Antonis Achilleos and Mathias Ruggaard Pedersen.

On the logical structure of choice and bar induction principles – Nuria Brede and Hugo Herbelin.

Initial limit Datalog: a new extensible class of decidable constrained Horn clauses – Toby Cathcart Burn, Luke Ong, Steven Ramsay and Dominik Wagner.

Compositional relational reasoning via operational game semantics – Guilhem Jaber and Andrzej Murawski.

Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP – Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik and Dmitriy Zhuk.

Alignment Completeness for Relational Hoare Logics – Ramana Nagasamudram and David Naumann.

Session Logical Relations for Noninterference – Farzaneh Derakhshan, Stephanie Balzer and Limin Jia.

Removing Redundant Refusals: Minimal Complete Test Suites for Failure Trace Semantics – Maciej Gazda and Rob Hierons.

A Complete Axiomatization for Divergence Preserving Branching Congruence of Finite-State Behaviours – Xinxin Liu and Tingting Yu.

A distributed operational view of Reversible Prime Event Structures – HernC!n Melgratti, Claudio Antares Mezzina and G. Michele Pinna.

Comonadic semantics for guarded fragments – Samson Abramsky and Daniel Marsden.

A Normal Form Characterization for Efficient Boolean Skolem Function Synthesis – Preey Shah, Aman Bansal, S. Akshay and Supratik Chakraborty.