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.