MFCS 2023: 48TH INTERNATIONAL SYMPOSIUM ON MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE

This page contains an index consisting of author-provided keywords.

#
#P	Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes
3
3SUM problem	Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator
A
Agda	Inductive Continuity via Brouwer Trees
algebraic algorithms	Deterministic Constrained Multilinear Detection
algebraic branching programs	Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
algorithmic game theory	Relaxed core stability for hedonic games with size-dependent utilities
Algorithmic graph theory	Some Algorithmic Problems on Temporal Graphs
Algorithmic information theory	Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals
algorithms under uncertainty	Graph Connectivity with Noisy Queries
Analog Computations	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
Approximation	Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games
approximation algorithms	Exact and approximation algorithms for routing a convoy through a graph
Arithmetic circuits	Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
arithmetic theories	On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract)
asynchronous automata	String Diagrammatic Trace Theory
automata	Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
Automatic relations	Separating Automatic Relations
B
Backreferences	On the Expressive Power of Regular Expressions with Backreferences
Bayesian	The Compositional Structure of Bayesian Inference
Beyond Worst-case Analysis	Rényi-Ulam Games and Online Computation with Imperfect Advice
binary rank	On Property Testing of the Binary Rank
bipartite graphs	Spartan Bipartite Graphs are Essentially Elementary
Bipartiteness	Dynamic constant-time parallel graph algorithms with sub-linear work
Boolean Function	An iterative approach for counting reduced ordered binary decision diagrams
Boolean functions	Query Complexity of Search Problems
Boolean Hierarchy	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
C
Canadian Traveller Problem	The Covering Canadian Traveller Problem Revisited
Category Theory	The Compositional Structure of Bayesian Inference
chordal graphs	A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
Circuit complexity	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy Depth-3 Circuits for Inner Product
clique graphs	A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
clique-width	Tight Algorithmic Applications of Clique-Width Generalizations
Competitive analysis	Competitive Search in the Line and the Star with Predictions
Complexity	Some Algorithmic Problems on Temporal Graphs
complexity dichotomy	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Complexity Trichotomy	Dependent k-Set Packing on Polynomoids
Computability	Realizing finitely presented groups as projective fundamental groups of SFTs
Computable Analysis	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
Computational Complexity	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
computational social choice	Relaxed core stability for hedonic games with size-dependent utilities
Concurrent games	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
connectivity problems	Tight Algorithmic Applications of Clique-Width Generalizations
Consistency and robustness	Competitive Search in the Line and the Star with Predictions
constraint satisfaction	On the complexity dichotomy for the satisfiability of systems of term equations over finite algebras Short definitions in constraint languages
Constructive Type Theory	Inductive Continuity via Brouwer Trees
Context-free grammars	Parallel enumeration of parse trees
Continued fractions	Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals
Continuity	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation Inductive Continuity via Brouwer Trees
continuous approximation	The Geometry of Reachability in Continuous Vector Addition Systems with States
convoy routing	Exact and approximation algorithms for routing a convoy through a graph
Cops and Robber	Parameterized Analysis of the Cops and Robber Game
Coq	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
core stability	Relaxed core stability for hedonic games with size-dependent utilities
Cost register automata	Universality and Forall-Exactness of Cost Register Automata with Few Registers
counter automata	Parikh One-Counter Automata
counting logics	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
Counting problems	Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes
Cryptanalysis	Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator
Cryptography	Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator
Cut-free LK	A super-polynomial separation between resolution and cut-free sequent calculus
D
Data Languages	Positive Data Languages
decidability	Universality and Forall-Exactness of Cost Register Automata with Few Registers Parikh One-Counter Automata
Decidable fragment	On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation
decision procedures	Deciding Predicate Logical Theories of Real-Valued Functions
Decision trees	Query Complexity of Search Problems
Decomposition	Decomposing Finite Languages
depth of proofs	OBDD(join) Proofs Cannot be Balanced
Depth-3 circuit	Depth-3 Circuits for Inner Product
descriptive complexity	Descriptive complexity for distributed computing with circuits Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes
descriptive complexity theory	Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits
Deterministic finite automaton (DFA)	Decomposing Finite Languages
Dialogue trees	Inductive Continuity via Brouwer Trees
diameter	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
Dirac graphs	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
Directed Acyclic Graph	An iterative approach for counting reduced ordered binary decision diagrams
Discrete ordinary differential equations	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
disjointness function	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
Distributed algorithms	Checking Presence Reachability Properties on Parameterized Shared-Memory Systems
distributed computing	Descriptive complexity for distributed computing with circuits
distributed quantum Merlin-Arthur	Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
distributed verification	Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
distribution testing	Support Size Estimation: The Power of Conditioning
Domination problems	Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
Dynamic complexity	On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages Dynamic Planar Embedding is in DynFO
Dynamic parallel algorithms	Dynamic constant-time parallel graph algorithms with sub-linear work
dynamic programming	A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
Dynamical Systems	Realizing finitely presented groups as projective fundamental groups of SFTs
E
edge subdivision	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Effective Hausdorff dimension	Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals
elementary graphs	Spartan Bipartite Graphs are Essentially Elementary
emptiness	Parikh One-Counter Automata
Energy Games	Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games
entropic risk	Entropic Risk for Turn-Based Stochastic Games
Entropy games	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
Enumeration problems	Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
Enumerative Combinatorics	An iterative approach for counting reduced ordered binary decision diagrams
eqaulity function	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
eternal vertex cover	Spartan Bipartite Graphs are Essentially Elementary
ETH	On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric Parameterized Max Min Feedback Vertex Set
Exact real computation	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
Exponential sums	A Weyl Criterion for Finite-State Dimension and Applications
Expressive power	On the Expressive Power of Regular Expressions with Backreferences
expressiveness	Parikh One-Counter Automata
Extensional Type Theory	Inductive Continuity via Brouwer Trees
F
Fairness	Fixed-Parameter Algorithms for Fair Hitting Set Problems
Feedback Vertex Set	Parameterized Max Min Feedback Vertex Set Parameterized Approximation Scheme for Feedback Vertex Set
few subpowers	Short definitions in constraint languages
fine-grained complexity	Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification
Finite automata	Probabilistic Input-driven Pushdown Automata Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification
finite colorability	Separating Automatic Relations
Finite Differences	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
Finite languages	Decomposing Finite Languages
Finite model theory	Locality Theorems in Semiring Semantics Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits
Finite multisets	Ordinal measures of the set of finite multisets
Finite-state compression	A Weyl Criterion for Finite-State Dimension and Applications
Finite-state dimension	A Weyl Criterion for Finite-State Dimension and Applications
First-order logic	Locality Theorems in Semiring Semantics On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation
first-order predicate logical theories	Deciding Predicate Logical Theories of Real-Valued Functions
first-order theories	On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract)
Fixed Parameter Tractability	Parameterized Analysis of the Cops and Robber Game Fixed-Parameter Algorithms for Fair Hitting Set Problems
Fixed parameterized algorithms	A FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular Width
fixed-parameter tractability	On Polynomial-Time Decidability of k-Negations Fragments of FO Theories (Extended Abstract)
fixed-parameter tractable	Modification Problems toward Proper (Helly) Circular-arc Graphs
Forall-exact problem	Universality and Forall-Exactness of Cost Register Automata with Few Registers
forbidden subgraph	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
FPT Approximation	FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Fundamental Group	Realizing finitely presented groups as projective fundamental groups of SFTs
G
G-modular cardinality	Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
Games on graphs	Rational Verification for Nash and Subgame-perfect Equilibria in Graph Games
general algebra	On the complexity dichotomy for the satisfiability of systems of term equations over finite algebras
Graph classes	Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
Graph colouring	Exploring the space of colourings with Kempe changes
graph connectivity	Graph Connectivity with Noisy Queries
graph drawing	On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
Graph Exploration	The Covering Canadian Traveller Problem Revisited
graph minor	Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
graph modification problem	Modification Problems toward Proper (Helly) Circular-arc Graphs
graph motif	Deterministic Constrained Multilinear Detection
Graph Searching	Recontamination helps a lot to hunt a rabbit Parameterized Analysis of the Cops and Robber Game
Graph theory	Exploring the space of colourings with Kempe changes
graph-algorithms	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
guarded logics	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
H
H-free graph	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
H-graphs	Recognizing H-graphs – beyond circular-arc graphs
Hamiltonian Cycle	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
Hamiltonian Path	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
hedonic games	Relaxed core stability for hedonic games with size-dependent utilities
Helly Property	Recognizing H-graphs – beyond circular-arc graphs
Hereditary Systems	Dependent k-Set Packing on Polynomoids
Hilbert projective metric	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
Hitting Set	Fixed-Parameter Algorithms for Fair Hitting Set Problems
homomorphism counting	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
homomorphism indistinguishability	Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
Hunter and Rabbit Game	Recontamination helps a lot to hunt a rabbit
Hyperbolic graphs	Isometric path complexity of graphs
Hypergraph Matchings	Dependent k-Set Packing on Polynomoids
hypergraphs	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
Hyperproperties	Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity
Hyperspaces	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
hypertree decompositions	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
I
Implicit complexity	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
incidence graphs	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
independent feedback vertex set	Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
information theory	Support Size Estimation: The Power of Conditioning
inner product	Depth-3 Circuits for Inner Product
input-driven automata	Probabilistic Input-driven Pushdown Automata
Intersection Graphs	Recognizing H-graphs – beyond circular-arc graphs
Intuitionistic Logic	Inductive Continuity via Brouwer Trees
Isometric path complexity	Isometric path complexity of graphs
Isometric Path Cover	Isometric path complexity of graphs
K
kernel	MaxCut Above Guarantee
Kernelization	Parameterized Analysis of the Cops and Robber Game
Kolmogorov complexity	Effective Continued Fraction Dimension versus Effective Hausdorff Dimension of Reals
Krasnoselskii-Mann fixed point iteration	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
L
Linear and star search	Competitive Search in the Line and the Star with Predictions
Linear Temporal Logic	Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity
Locality	Locality Theorems in Semiring Semantics
logic	Descriptive complexity for distributed computing with circuits Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
logics for PTIME	Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits
loop invariants	Algebraic Reasoning for (Un)Solvable Loops
lower bound	Support Size Estimation: The Power of Conditioning
lower bounds	OBDD(join) Proofs Cannot be Balanced
M
Markov chains	Entropic Risk for Turn-Based Stochastic Games
Markov decision processes	Entropic Risk for Turn-Based Stochastic Games
Markov kernel	The Compositional Structure of Bayesian Inference
matching cut	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
matrix multiplication	Parallel enumeration of parse trees
Matroid intersection	Deterministic Constrained Multilinear Detection Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids
Matroids	Finding a Highly Connected Steiner Subgraph and its Applications
Max Cut	FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
MaxCut	MaxCut Above Guarantee
maximum cardinality search	A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
maximum cut	MaxCut Above Guarantee
Mazurkiewicz traces	String Diagrammatic Trace Theory
Median String	On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric
Minimality	Decomposing Finite Languages
Models of computation	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
Modular width	A FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular Width
Modular-width	Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
Monadic Second-Order Logic	Positive Data Languages
monochromatic rectangles	On Property Testing of the Binary Rank
Monoid	On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation
Monotonicity	Recontamination helps a lot to hunt a rabbit
N
Nash equilibria	Rational Verification for Nash and Subgame-perfect Equilibria in Graph Games
neural networks	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
noisy queries	Graph Connectivity with Noisy Queries
Nominal Sets	Positive Data Languages
noncommutative polynomial ring	Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
Normal numbers	A Weyl Criterion for Finite-State Dimension and Applications
O
OBDD	OBDD(join) Proofs Cannot be Balanced
Online Algorithm	The Covering Canadian Traveller Problem Revisited
online algorithms	The Online Simple Knapsack Problem with Reservation and Removability Graph Connectivity with Noisy Queries
Online Computation	Rényi-Ulam Games and Online Computation with Imperfect Advice
opacity	Speed Me up if You Can: Conditional Lower Bounds on Opacity Verification
Oracle Construction	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
Ordinary differential equations	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
Ore graphs	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
Outerstring graphs	Isometric path complexity of graphs
P
p-Edge-Connected Graphs	Finding a Highly Connected Steiner Subgraph and its Applications
parallel algorithms	Parallel enumeration of parse trees
parallel constant time	On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages
Parameterized Algorithms	Deterministic Constrained Multilinear Detection Parameterized Complexity of Domination Problems Using Restricted Modular Partitions Parameterized Max Min Feedback Vertex Set Parameterized Approximation Scheme for Feedback Vertex Set Fixed-Parameter Algorithms for Fair Hitting Set Problems
Parameterized Approximation	Parameterized Approximation Scheme for Feedback Vertex Set
Parameterized Complexity	On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric Finding a Highly Connected Steiner Subgraph and its Applications Tight Algorithmic Applications of Clique-Width Generalizations On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
Parameterized models	Checking Presence Reachability Properties on Parameterized Shared-Memory Systems
Parikh automata	Parikh One-Counter Automata
Parity Games	Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games
parsing	Parallel enumeration of parse trees
partial search order	A Polynomial-Time Algorithm for MCS Partial Search Order on Chordal Graphs
Partial Vertex Cover	FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Planar Embedding	Dynamic Planar Embedding is in DynFO
Planar Graphs	Dynamic Planar Embedding is in DynFO
polynomial factorization	Multivariate to Bivariate Reduction for Noncommutative Polynomial Factorization
Polynomial-delay enumeration	Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids
polynomially expressive	Short definitions in constraint languages
Predictions	Competitive Search in the Line and the Star with Predictions
Presheaves	Positive Data Languages
price of anarchy	Relaxed core stability for hedonic games with size-dependent utilities
Primality	Decomposing Finite Languages
primitive positive definability	Short definitions in constraint languages
probabilistic automata	Probabilistic Input-driven Pushdown Automata
Probability	The Compositional Structure of Bayesian Inference
program analysis	Algebraic Reasoning for (Un)Solvable Loops
Program Extraction	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
Program verification	Ordinal measures of the set of finite multisets
Proof complexity	A super-polynomial separation between resolution and cut-free sequent calculus OBDD(join) Proofs Cannot be Balanced Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
Proof Systems	Upward Translation of Optimal and P-Optimal Proof Systems in the Boolean Hierarchy over NP
proper circular-arc graph	Modification Problems toward Proper (Helly) Circular-arc Graphs
proper Helly circular-arc graph	Modification Problems toward Proper (Helly) Circular-arc Graphs
property testing	On Property Testing of the Binary Rank
Pseudo-random generator	Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator
Pseudodeterminism	Query Complexity of Search Problems
Q
quantitative logics	Counting Computations with Formulae: Logical Characterisations of Counting Complexity Classes
quantum computation	Distributed Merlin-Arthur Synthesis of Quantum States and Its Applications
quantum graphs	Counting Homomorphisms from Hypergraphs of Bounded Generalised Hypertree Width: A Logical Characterisation
query complexity	Support Size Estimation: The Power of Conditioning
Query models	Rényi-Ulam Games and Online Computation with Imperfect Advice
R
radius	Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
Randomness	Query Complexity of Search Problems
Ranked Enumeration	Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids
reachability	The Geometry of Reachability in Continuous Vector Addition Systems with States
real functions	Deciding Predicate Logical Theories of Real-Valued Functions
real numbers	Deciding Predicate Logical Theories of Real-Valued Functions
Realizability	Inductive Continuity via Brouwer Trees
recognizable relations	Separating Automatic Relations
Reconfiguration	Exploring the space of colourings with Kempe changes
Recursion scheme	A characterization of functions computable in polynomial time and space over the reals with discrete ordinary differential equations. Simulation of Turing machines with analytic discrete ordinary differential equations.
Reduced Ordered Binary Decision Diagram	An iterative approach for counting reduced ordered binary decision diagrams
Register Automata	Positive Data Languages
Regular expressions	On the Expressive Power of Regular Expressions with Backreferences
Regular languages	Decomposing Finite Languages
Relation algebra	On the Finite Variable-Occurrence Fragment of the Calculus of Relations with Bounded Dot-Dagger Alternation
relational clone	Short definitions in constraint languages
Relative value iteration	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
ReLU cicuits	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
Removability	The Online Simple Knapsack Problem with Reservation and Removability
Representative Families	Finding a Highly Connected Steiner Subgraph and its Applications
Resolution	A super-polynomial separation between resolution and cut-free sequent calculus
Reverse search	Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids
risk-aversion	Entropic Risk for Turn-Based Stochastic Games
Roman domination	Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
Rényi-Ulam Games	Rényi-Ulam Games and Online Computation with Imperfect Advice
S
Search problems	Query Complexity of Search Problems Competitive Search in the Line and the Star with Predictions
Semiring semantics	Locality Theorems in Semiring Semantics
separability	Separating Automatic Relations
shortest path problem	Exact and approximation algorithms for routing a convoy through a graph
Shortest paths	Isometric path complexity of graphs
sigmoid circuits	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
Simple Knapsack	The Online Simple Knapsack Problem with Reservation and Removability
Simple Stochastic Games	Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games
Spaces of subsets	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
spanning tree	Graph Connectivity with Noisy Queries A FPT Algorithm for Spanning Trees with Few Branch Vertices Parameterized by Modular Width
Special graph classes	Roman Census: Enumerating and Counting Roman Dominating Functions on Graph Classes
sprase activity	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
st-orientations	On the Parameterized Complexity of Computing st-Orientations with Few Transitive Edges
state complexity	Probabilistic Input-driven Pushdown Automata
Stateful computations	Inductive Continuity via Brouwer Trees
Steiner Subgraph Extension	Finding a Highly Connected Steiner Subgraph and its Applications
stochastic games	Entropic Risk for Turn-Based Stochastic Games
Stochastic mean-payoff games	Solving irreducible stochastic mean-payoff games and entropy games by relative Krasnoselskii-Mann iteration
Strategy complexity	Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games
string diagrams	String Diagrammatic Trace Theory
subexponential	MaxCut Above Guarantee
Subexponential algorithms	FPT Approximation and Subexponential Algorithms for Covering Few or Many Edges
Subgame-perfect equilibria	Rational Verification for Nash and Subgame-perfect Equilibria in Graph Games
subpower membership	Short definitions in constraint languages
Subset-sum problem	Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator
Subshift of Finite Type	Realizing finitely presented groups as projective fundamental groups of SFTs
Subshifts	Realizing finitely presented groups as projective fundamental groups of SFTs
support size	Support Size Estimation: The Power of Conditioning
symbolic computation	Algebraic Reasoning for (Un)Solvable Loops
symmetric computation	Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits
symmetric monoidal categories	String Diagrammatic Trace Theory
systems of equations	On the complexity dichotomy for the satisfiability of systems of term equations over finite algebras
T
TBA1	Online Algorithms with Predictions Modern Parallel Algorithms
TBA2	Online Algorithms with Predictions Modern Parallel Algorithms
TBA3	Online Algorithms with Predictions Modern Parallel Algorithms
Team Semantics	Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity
Temporal Graphs	Some Algorithmic Problems on Temporal Graphs
Termination	Ordinal measures of the set of finite multisets
the CONGEST model	Distributed CONGEST Algorithm for Finding Hamiltonian Paths in Dirac Graphs and Generalizations
Theorem proving	Inductive Continuity via Brouwer Trees
threshold circuits	Exponential Lower Bounds for Threshold Circuits of Sub-Linear Depth and Energy
Time Series	On the Complexity of Computing Time Series Medians under the Move-Split-Merge Metric
Topology	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
traveling salesperson problem	Exact and approximation algorithms for routing a convoy through a graph
Travelling Salesperson Problem	The Covering Canadian Traveller Problem Revisited
Treewidth	Parameterized Max Min Feedback Vertex Set Complexity Framework for Forbidden Subgraphs III: When Problems are Tractable on Subcubic Graphs
Truemper Configurations	Isometric path complexity of graphs
Type Theory	Formalizing Hyperspaces for Extracting Efficient Exact Real Computation
U
Undirected connectivity	Dynamic constant-time parallel graph algorithms with sub-linear work
Universality	Universality and Forall-Exactness of Cost Register Automata with Few Registers
V
Vector addition system with states	The Geometry of Reachability in Continuous Vector Addition Systems with States
Verification	Checking Presence Reachability Properties on Parameterized Shared-Memory Systems
vertex cover	Spartan Bipartite Graphs are Essentially Elementary
visibly pushdown automata	Probabilistic Input-driven Pushdown Automata
W
W-hardness	Parameterized Complexity of Domination Problems Using Restricted Modular Partitions
Wang tiles	Realizing finitely presented groups as projective fundamental groups of SFTs
Weighted automata	Universality and Forall-Exactness of Cost Register Automata with Few Registers
weighted grammars	Parallel enumeration of parse trees
Well-partial order	Ordinal measures of the set of finite multisets
Weyl’s criterion	A Weyl Criterion for Finite-State Dimension and Applications
work	On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages

Disclaimer | Powered by EasyChair Smart Program