LICS 2021 Accepted Papers

Fusible numbers and Peano Arithmetic – Jeff EricksonGabriel 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 DawarTomáš 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 HughesLutz 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 AmorimDexter KozenRadu MardarePrakash 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 ChatterjeeWolfgang DvořákMonika 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 BlondinTim LeysFilip MazowieckiPhilip 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 FordStefan Milius and Lutz Schröder.

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

Finite Model Theory of the Triguarded Fragment and Related LogicsEmanuel 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 GlabbeekPeter 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 De Meo and Antoine Mottet.

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

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

GC6del-McKinsey-Tarski and Blok-Esakia for Lewis-Brouwer Implication – Jim de GrootTadeusz 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 KomoridaShin-Ya KatsumataClemens KupkeJurriaan 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 BruniRoberto Giacobazzi, Roberta Gori and Francesco Ranzato.

Efficient Local Computation of Differential Bisimulations via Coupling and Up-to Methods – Giorgio Bacci, Giovanni Bacci, Kim Guldstrand LarsenMirco TribastoneMax 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ńczykBartek 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 AtseriasPhokion 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 AccattoliUgo 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 LazicAndrzej 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 BulatovMarcin Kozik and Dmitriy Zhuk.

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

Session Logical Relations for Noninterference – Farzaneh DerakhshanStephanie 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.