Search open problems

Determine whether the graph induced by any simple arrangement of great circles on the sphere is vertex 3-colorable.

First postulated by Hoffmann-Ostenhof (approx. 2010). conjecture: Every connected cubic graph can be decomposed into a spanning tree, a disjoint union of cycles, and a matching.

Determine whether every graph of maximum degree at most six has a crossing-free three-dimensional orthogonal drawing with at most two bends per edge.

The 3SUM decision problem asks whether three integer sets contain elements a, b, and c satisfying a+b=c. The open question is whether 3SUM and the problems to which it reduces admit algorithms with a polynomial saving over quadratic time. Algorithms with logarithmic-factor improvements are known, but such an exponent saving is conjectured to be impossible even in expectation.

Does the combinatory basis consisting only of $B$ and $\omega$ contain a fixed-point combinator? The stronger requirement that the fixed-point equation hold by reduction is known to be impossible, while the equational version remains open in the source.

The class of polyregular functions corresponds to the class of functions accepted by reversible, two-way pebble transducers. The question therefore is to come up with a streaming model with "controlled copying" which will be closed under composition, and which can define squaring as well as iterated reverse.

Construct a direct and suitably simple ordinal assignment to simply typed lambda terms that strictly decreases under every beta-reduction step, thereby proving strong normalization.

Determine whether a nonconstant stepsize schedule can accelerate gradient descent on smooth convex functions while providing a uniform guarantee for every stopping time and for the current iterate, rather than only selected horizons or the best previous iterate.

Are context unification and linear second order unification decidable?

Are the existential fragment or the positive fragment of the theory of one-step rewriting decidable?

Are there hyper-recurrent combinators?

Are universality and inclusion of AC-recognizable languages decidable?

Is combinatorial completeness decidable for finite sets of proper combinators? The unrestricted finite normal-combinator problem is undecidable, whereas the linear proper case is decidable.

The design of efficient differentially private learning algorithms with dimension-independent learning guarantees is a central challenge in privacy-preserving machine learning. A recent work gives confidence-margin guarantees for linear and kernel-based classification and for certain classes of neural networks. Despite these positive results, two fundamental questions remain open: whether the linear and kernel algorithms can have more favorable computational cost, and whether neural-network margin guarantees can avoid explicit dependence on network size.

Petri nets with ordered data is an extension of Petri nets where tokens carry values from the set of rational numbers Q , and executability of transitions is conditioned by inequalities between data values. Question: Is the following problem decidable?

Design a black-box reduction from stochastic nonconvex optimization to online convex optimization whose stationarity guarantee is controlled by the regret of the supplied online algorithm. Such a reduction would transfer adaptive, dimension-sensitive regret bounds to nonconvex optimization.

By the classic Rackoff argument in d-dimensional Vector Addition System with States (d-VASS) V if there is a path starting in configuration s and covering configuration t then there is also a covering path of length at most M k , where M is the maximal number occurring on transitions of VASS and in configurations s and t, while k 2^d . conjecture is hard to prove despite of a simple formulation and progress on it could led to a deep understanding of runs of VASS.

Determine whether every bounded-error randomized polynomial-time algorithm can be replaced by a deterministic polynomial-time algorithm.

Recently [arXiv:2206.09619], an approach for analyzing Büchi automata using graph neural networks (GNN) was proposed. Thus far, the analysis has been limited to the emptiness problem and simple properties like "does the automaton accept a word containing at least one/infinitely many b ?". My immediate question was what the limits of learning-based approaches are and whether one can identify certain properties which cannot be learned GNNs.

Can completion always be made terminating when limiting the depth of occurrences of critical pairs?

Is local regularization sufficiently expressive to learn every learnable multiclass hypothesis class, and can it do so with optimal or nearly optimal sample complexity? A particular learnable class H_ is proposed as a possible counterexample.

Can strong normalization of the typed lambda calculus be proved by a reasonably straightforward mapping from typed terms to a well-founded ordering?

Can the application condition on the Merge rule in the computation of dag-solved forms of unification problems be improved?

Can we use the dependency pair method to prove relative termination?

Determine the minimum number of colors needed to color the Euclidean plane so that points at unit distance receive different colors.

We start from the following fact: Given a two-player game arena $G$ labelled with an alphabet $\Sigma$, and an objective $W \subseteq \Sigma^\omega$ for Player 1, if $W$ is closed by subwords then if Player 1 has a winning strategy, she has one using memory $\leq |G|!$. The problem is to characterise classes of languages with this property, or at least identify some non-trivial examples. A first step could be to show that for all $k$, the class $C_k$ of languages recognised by automata with SCCs of size at most $k$ has this property, and identify some classes that have that property but are not subsumed by some $C_k$.

Is every pure lambda term typable in System $F_\omega$ already typable using only type constructors of order at most one?

A series f : ^* Q is commutative if the output does not depend on the order of the symbols in the input. Given a polynomial automaton recognising a commutative series, does there exist an equivalent polynomial automaton where all control states recognise commutative series? The answer for weighted automata is yes.

Determine whether any two planar point sets of the same size and with the same number of hull vertices admit combinatorially compatible triangulations.

Take the setting of probabilistic Turing machines with nondeterminism. Consider the decision problem of deciding if a probabilistic nondeterministic Turing machine terminates with probability 1 under all fair schedulers. What is the recursion-theoretic complexity of this problem? Note this this problem is trivially undecidable, and that the corresponding decision problem for non-probabilistic Turing machines is known to be $\Pi^1_1$-complete.

Problem Definition: Let $A = (Q, \Sigma, \delta)$ be a (complete) deterministic finite automaton (DFA) where $Q$ is a finite set of states, $\Sigma$ is a finite alphabet and $\delta \colon Q \times \Sigma \to Q$ is a (totally defined) transition function (we neglect start and final states). We generalize $\delta$ to words $w= w_1w_2 \dots w_n$, $w_i \in \Sigma$ by setting $\delta(q, w) = \delta(\delta(q, w_1)w_2\dots w_n)$. We further generalize it to sets $S$ of states by $\delta(S, w) = \cup_{q\in S}\{\delta(q, w)\}$. We say that a word $w\in \Sigma^*$ is synchronizing for $A$ if $|\delta(Q, w)| = 1$, i.e., regardless from which state we read $w$, we end up in the same state.

The conjugacy problem for rational relations can be stated as follows: Question: Is it true that for every accepting run of T , the concatenation a_1a_2 a_n of the first components of the labels is a cyclic shift of the concatenation b_1b_2 b_n of the second components? That is, does there exist 1 j n such that: 1) a_i = b_i+j for all 1 i n-j , and 2) a_i = b_i+j-n for all n-j < i n .

Definitions: A temporal graph is a graph where in addition to set of vertices and edges, for each edge, a set of times at which times it can be traversed is specified. Question: Given a temporal arena with edge availability specified using existential Presburger formula, checking if Eve has a winning strategy for the explorability objective is known to be PSPACE-hard (even if all vertices are controlled by Eve) and in EXPTIME. Can we find matching upper or lower bound?

A vector addition system is a finite set of vectors $V = \{ v_1,v_2,\ldots,v_n \} \in \mathbb{Z}^d$ with $d \in \mathbb{N}$. Conjecture: For every vector addition system $V$, there exists a constant $C_V$ such that for every pair of positions $s$ and $t$, if there exists at least one run of $V$ from $s$ to $t$, one of these runs has a length smaller than $C_V \cdot \big(||s|| + ||t|| \big)$.

Fijalkow and Horn studied generalised reachability games on graphs, which requires Player 1 to visit at least one vertex from each given target set. the problem is solvable in PTIME. However when all target sets are of size at most 2, the complexity is currently unknown. Hence, the best known upper bound is PSPACE and the best known lower bound is PTIME. Can we obtain better upper or lower bounds for this case?

Fijalkow and Horn studied generalised reachability games on graphs, which requires Eve (Player 1) to visit vertices from several different target sets. the problem is solvable in PTIME. We are interested in the complexity of determining how many target sets Eve can guarantee to visit, i.e, given an arena, target vertices v_1, v_2, , v_n , and a k n , does Eve have a strategy that ensures at least k targets are visited? This is known to be in PSPACE and NP-hard. Can we obtain better upper or lower bounds?

A d -dimesional continuous VASS is a counter system, which consists of a finite set of states and d counters, each of which can hold a non-negative rational number. the problem of deciding whether a given source configuration of a continuous VASS can reach a given target configuration. It is known that this problem is NP-complete. When the dimension d is fixed and all vectors are encoded in binary, it is known that the problem is NL-complete if d = 1 and NP-complete if d 2 . However when d is fixed and all vectors are encoded in unary, the complexity is unknown, which leads to the following question: What is the complexity of reachability in continuous VASS when the dimension d is fixed?

For a polygon and a prescribed number of pieces, find mutually congruent pieces that leave the least uncovered area and characterize when a perfect congruent partition exists.

A choice function over a set E is a function f that assigns to every non-empty subset of E one of its elements (of the subset). Conjecture : Let be a signature. There exists a procedure that inputs an MSO[ ] formula (X,x) and outputs another one, (x,y), such that for every -structure E, if (X,x) is a regular choice function over E then (x,y) is a regular well order over E.

Data VAS is a finite set of finitely supported functions from ordered data set D to Z^k, where k is a dimension. Continuous reachability is a continuous version of the reachability. First, markings are finitely/supported functions from D to Q_ 0^k. Further there is a continuous step from m to m' if there are: x VAS, an order preserving data permutation , and a factor a Q_ 0 such that m+a x =m'. A transitive closure of continuous step is a continuous reachability relation.

Does a continuously complete CPO model of lambda calculus have equational theory exactly lambda-beta, or, in the extensional case, exactly lambda-beta-eta?

Does simultaneous mean-field Langevin descent--ascent converge for every smooth entropy-regularized two-player zero-sum game? If convergence holds, the limit is already known to be the unique saddle point; the missing step is convergence of the unmodified single-timescale flow itself.

Determine the asymptotic growth constant and sharper enumeration bounds for fixed polyominoes of order n.

Let us assume a distributed system with an unknown number of participants. The problem asking, given a protocol and a state of this protocol, if there exists a number of agents with which we can find a run leading to a configuration in which at least one agent is on this state is called the coverability problem and is EXPSPACE-complete. We consider a restriction on protocols namely Wait-Only protocol: in a Wait-Only protocol, each state is either an action state (all its outgoing transitions are broadcast transitions or sending transitions) or a waiting state (all its outgoing transitions are reception transitions). The complexity of the coverability problem is unknown in that case.

Given a dataset $D$ of $N$ examples, a selection budget $n\leq N$, and a fixed natural learning rule $A$, how well can $A$ perform when trained only on $n$ examples from $D$, in terms of the loss on the full dataset? Concrete instances of this question are posed for mean estimation and linear regression.

Is the following problem decidable: Given A, a weighted automaton (WA) over the ( ,+) semiring, answer whether A has an equivalent deterministic WA?

Is Horn-style entailment decidable for finite sets of simple subtyping constraints over non-structurally ordered trees?

A cost register automaton (CRA) over $(\mathbb{Z}, \min, +)$ is a DFA equipped with a finite number of registers that take values in $\mathbb{Z}$. Question: Is it decidable, given a $\mathbb{Z}$-CCRA, whether the function it expresses is upper-bounded? That is, whether $(\exists c)(\forall w)[f(w) \leq c]$.

Design a framework for combining constraint solving algorithms.

Design a notion of automata for graphs.

Design new termination methods based on the gap-embedding theorems of Friedman and Kriz.

Design pattern-matching algorithms for graphs.

Input: two timed languages L, M represented as nondeterministic timed automata. Question: decide whether there exists a deterministic timed automaton recognising a timed language S which separates L, M, in the sense that L is included in S and S is disjoint from M.

Develop effective methods to decide whether a system decreases with respect to some exponential interpretation.

Determine how learning curves, list-learning resources, compression resources, and standard combinatorial dimensions behave under products of concept classes. The questions seek tight direct-sum laws rather than bounds obtained by learning each coordinate independently.

Determine tight extremal bounds for the number of unit-distance pairs and the minimum number of distinct distances among finite point sets in two and three dimensions.

Consider a nondeterministic parity automaton $A = (Q, \Sigma, \Delta, q_0, \Omega),$ where: $Q$ is a finite set of states, $\Sigma$ is the input alphabet, $\Delta \subseteq Q \times \Sigma \times Q$ is the transition relation, $q_0 \in Q$ is the initial state, and $\Omega : Q \to \mathbb{N}$ is the parity acceptance condition. This leads to the question: If a nondeterministic parity automaton $A$ is stochastically resolvable using a memoryless resolver, is it always possible to construct such a resolver using uniform distributions?

Online learning in the mistake-bound model and differential privacy are fundamental concepts in learning theory. We ask whether every hypothesis class that is online learnable is also privately online learnable: is privacy free in the online-learning framework? A resolution would either separate the two learnability classes or give a general transformation from an online learner to a private online learner, together with the privacy level under which a finite mistake bound remains possible.

We are interested in functions realized by weighted automata over the semiring $\mathbb N_{\mathsf{ min}}=\langle \mathbb N\cup\left\{ \infty \right\} , \mathsf{ min}, +, \infty,0\rangle$. Question: Does it hold that for all $S\subseteq \mathbb N$ semilinear, $[\![ \mathcal A ]\!]^{-1}(S)$ is regular?

Does a system that is nonoverlapping under unification with infinite terms have unique normal forms?

Does AC unification terminate under more flexible control?

What is the optimal sample complexity of differentially private PAC learning? A concept class is learnable under approximate differential privacy if and only if it is online learnable. For finite classes, $O(\log|\mathcal C|)$ samples suffice, while non-private learning is characterized by $\operatorname{VC}(\mathcal C)$, which can be much smaller. We ask for a combinatorial characterization of private sample complexity and, more concretely, whether there are finite classes for which privacy forces sample complexity of order $\log|\mathcal C|$ even though this quantity is superpolynomial in VC dimension.

Does every automatic group have a presentation through some finite convergent string-rewriting system? Does every automatic monoid have an automatic structure such that the set of representatives is a prefix-closed cross-section?

Does surjective pairing conservatively extend -conversion?

Does the Church-Rosser property of abstract reduction systems imply decreasing Church-Rosser?

Does there exist a semigroup theory for which there is a reduced canonical term-rewriting system that is not length decreasing?

Maintain a dynamic planar point set under insertions and deletions while supporting nearest-neighbor queries, with logarithmic time for every operation.

Determine the minimum number of colors required to color all edges of a complete geometric graph so that crossing edges receive different colors.

The open problem asks whether every convex polyhedron can be cut along its edges and unfolded into a single simple polygon in the plane without overlap. The answer is conjectured to be affirmative, but no general result is known.

Determine whether every genus-zero polycube can be cut along its unit-square edges and unfolded into one nonoverlapping planar piece.

Consider a linear recurrence sequence $f : \mathbb N \to \mathbb Q$. Given an input index $n \in \mathbb N$ in binary encoding, decide whether $f(n) = 0$. Can this be done in polynomial time?

Timed automata are finite-state automata extended with finite real-valued variables called clocks. Question: Is the emptiness-checking decidable for timed automata with additive constraints for 3 clocks?

Equational axiomatization of graph operations

For each integer k, identify or construct all polyhedra whose generic orthogonal projections always have exactly k sides.

Consider the model introduced in this problem . conjecture that it is decidable is the CRA is ordered ; this means that the registers can be ordered, say x_1, x_2, , x_n, such that for all updates, x_i is only updated with registers x_j for j i.

Question: Given a non-deterministic timed automata with 1 clock(1-NTA) and reachability acceptance condition, decide whether there exists an equivalent history deterministic timed automata with k clocks (k-HDTA), where k can be fixed or arbitrary?

The open problem asks whether the Euclidean minimum spanning tree of n points in ℝ^d can be computed in time close to the Ω(n log n) lower bound. The difficulty is most pronounced in large dimension, where the reported upper bounds approach quadratic time.

Consider the problem: given a matrix M over integers, does there exist a natural number n such that M^n has only non-negative entries? the problem: given a matrix M over integers, does there exist a natural number n such that M^n has only non-negative entries? Is this question as hard as ultimate positivity? Note that if you consider two matrices M, N and ask if there exists n such that M^n+ N^n has only non-negative entries, that problem is indeed equivalent to ultimate positivity, but with a single matrix, we do not know. Note also that if we ask strict positivity of entries, the single matrix case becomes easy!

Moran Birth-death processes are stochastic processes defined as follows. Open problem: Does there exist a connected graph $G$ with $n \in \mathbb{N}$ vertices such that the fixation probability of each vertex of $G$ is strictly greater than $p_n$?

Does Expansion Postponement hold for every Pure Type System? That is, can expansion always be postponed to at most one final inference step?

Determine whether two dense square matrices over a field can be multiplied using essentially quadratic arithmetic operations.

Extend combination results on rewrite orderings to systems involving reductions.

ession types are constructs to define protocol interactions and automatically verify if an implementation meets its specifications. Can we relax the widening condition for the regular expressions in order to capture more examples while retaining the simplicity of the construction?

Determine the minimum worst-case number of subdivision vertices needed to extend an arrangement of pseudosegments into a pseudoline arrangement.

Determine whether every convex polygon can be partitioned into any prescribed number of convex pieces having equal areas and equal perimeters.

The problem concerns the update-time complexity of computing the L_1 difference between two vectors specified by data streams. The standard approach described by the source uses projections onto pseudorandom vectors whose entries are drawn from the Cauchy distribution, but sufficient accuracy requires many independent inner products and can make each update costly. The open directions are to obtain faster L_1-difference algorithms through large-frequency or sparse-projection techniques and to prove nontrivial worst-case or amortized lower bounds for stream-update time.

Find an embedding theorem for directed graphs.

Find more restrictive strategies in Boolean-ring based methods for resolution-like first-order theorem proving.

A ($d$-dimensional) Vector Addition System is a set of vectors $T \subseteq \mathbb Z^d$ and induces a single-step transition relation $\mathrm\rightarrow\ \subseteq \mathbb N^d \times \mathbb N^d$ by $\mathbf u \rightarrow \mathbf v \Leftrightarrow \mathbf v = \mathbf u + \mathbf t$ for some $\mathbf t \in T$. The boundedness problem for VAS asks if, given a vector $\mathbf u$, the set $R(\mathbf u)$ is finite. It has been long known that the boundedness problem for VAS is EXPSPACE-complete. A more careful analysis reveals an upper bound of $\mathcal O(n^{2^{d \log d}})$. A similar upper bound for VAS coverability was recently tightened to $\mathcal O(n^{2^d})$. Can we tighten the upper bound for boundedness too?

Input: A deterministic pushdown automaton P , with n states and constantly many input and stack letters. Output: Yes, if L(P) is empty. No, otherwise. Question: What is the fine-grained complexity of this problem? Can we obtain an improved upper bound (O(n^3- ) or an improved conditional lower bound ( (n^2 + )) for this problem?

The inclusion problem asks whether the language of an automaton A is included in that of an automaton B . Goal: Find upper and lower bounds on k such that the inclusion of deterministic parity automata can(not) be checked in time O(n^k) .

We consider the reachability problem for one-counter automata. Similar to the theory of NP-completeness which lets us prove that various problems do not admit polynomial-time algorithms under some plausible assumptions, in recent years, a theory of fine-grained complexity has emerged which lets us pinpoint the exact running time of various problems under plausible hypotheses. It would be interesting to see the applicability of techniques from this field for the reachability problem for one-counter automata.

Asymptotically optimal instance-dependent regret is known for stochastic online learning with fixed feedback graphs, but the finite-time component may dominate for exponentially many rounds in the number of actions. There are feedback graphs on which every algorithm fails to match the asymptotically optimal rate in finite time for a large class of instances. The open problems ask for a characterization of finite-time instance-dependent rates and for graph conditions under which the finite-time term is controlled by the asymptotic complexity.

Understanding the functions represented by ReLU networks is a major topic in current research. Several questions about properties of functions computed by ReLU neural networks can be answered by solving problems on special polytopes called zonotopes. These problems are NP-hard in general but polynomial-time solvable if the input dimension is constant. It is open whether they are fixed-parameter tractable with respect to the input dimension d.

For a finite point set in three-dimensional general position, determine whether all tetrahedralizations are connected by local bistellar flips.

For which equational theories is ground reducibility of extended rewriting decidable?

Determine the computational complexity and approximability of awakening sleeping robots in metric and planar geometric spaces as quickly as possible.

A string-to-string function is said to be rational (resp. regular) when it is computed by a functional nondeterministic one-way finite-state transducer (resp. a deterministic two-way transducer). (1) Is there a "simple" effective characterization in terms of local behaviors of two-way transducers that compute rational functions?

A vector addition system with states (VASS) is a finite graph (Q,E) with labels in Z^d and a designated initial state q_0 and final state q_f . Is 2^ x weakly-computable? It would be quite surprising, since x is not.

We aim to model the problem of networked control. Does the system have a strategy (with/without memory) to satisfy the specification?

Determine whether every closed nonconvex polyhedron has a connected cut set on its surface whose development is a single nonoverlapping planar polygon.

Give a complete (resource free) characterisation of rewrite systems with polynomial derivational complexity.

Give a definition of graph transduction that extends rational word transductions.

Give decidable criteria for left-linear rewriting systems to be Church-Rosser.

Given an automaton A, consider the following two games: Conjecture [1]: These two games are equivalent on nondeterministic parity automata.

Determine whether graph isomorphism has a deterministic polynomial-time algorithm for arbitrary finite graphs.

Determine whether every convex three-dimensional polytope has a tetrahedralization whose dual graph contains a Hamiltonian path.

Has any full, finitely-generated and Church-Rosser term-rewriting system (or system with bound variables) a recursive, one-step, normalizing reduction strategy?

Is higher-order matching decidable when simple types may contain arbitrarily many atomic type variables? Related many-atom retraction and polymorphic-retraction questions also remain open in the source.

How can termination orderings for term rewriting be adapted to cover those cases in which graph rewriting is terminating although term rewriting is not?

How can the notion of well-rewrite-ordering be used to as the basis for some new kind of ``recursive path ordering''?

Consider the language $a^*$. Open Problem: How can we formally make sense of additive and multiplicative inverses on words, such that $a^* = 1 + a + a^2 + {\dots} = \frac{1}{1 - a}$, i.e.\textbackslash{} such that $a^* \cdot (1 - a) = 1$?

We ask how much overparameterization is needed for simple iterative methods such as alternating least squares (ALS) and gradient descent to decompose a third-order tensor. For rank- r tensors, recent work shows that overparameterized rank k=O(r^2) suffices for a parallel variant of ALS with random initialization to converge to a global optimum. Is the quadratic dependence on r an inherent barrier for ALS-like methods? The open problems ask for subquadratic overparameterization guarantees, or for a polynomial lower bound showing that superlinear overparameterization is necessary.

How to compute finite and complete sets of unifiers for any finitary unification problem of a syntactic equational theory.

HyperLTL is an extension of LTL which allows quantification over traces. This motivates us to look for restrictions on parameters such as temporal depth, number of quantifier alternations or of universal quantifiers which would allow us to reach decidability. For the general problem, only very small fragments are decidable. However there is some hope in the other case. In particular, we do not know if it is decidable, given a HyperLTL formula of temporal depth one, whether is satisfied by the set of traces of some Kripke structure (the problem is TOWER-hard). If it is not, then which other restrictions would make it decidable?

In combinatory logic, is there a uniform universal generator?

In the $\lambda$-calculus, which sets have the form $\{M | Q \rightarrow^* PM\}$?

A one-counter MDP (OC-MDP) M is an MDP where each transition is labeled by an integer which is added to the counter whenever the transition is taken. The question is:

Determine decidability of inhabitation for the model-oriented intersection-type systems and recursive intersection-type variants that remain open in the TLCA source.

Characterize the finite sets of intersection-type equations whose induced conversion rule preserves strong normalization of typable lambda terms.

Investigate confluence and termination of combinations of typed lambda-calculi with term rewriting systems.

Investigate normalization by a canonical term rewrite system in the setting of second-order monadic logic

Investigate the exact difference between linear constant restrictions and arbitrary constant restrictions in unification problems.

Investigate the properties of spectri for special classes of rewrite systems.

Is a certain conditional rewrite system, which is a linearization of Combinatory Logic extended with surjective pairing, confluent?

Is any ``strongly'' non-overlapping right-linear term-rewriting system confluent?

Is confluence of ordered rewriting decidable when the (existential fragment of the) ordering is?

Is higher-order matching decidable?

We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optimal 1-bit minimax rate, and the same rate is attainable with general 1-bit queries using only one adaptive transition, that is, two stages of querying. In the non-adaptive setting, threshold and interval queries are known to be highly suboptimal, but the case of arbitrary non-adaptive quantizers remains unresolved. Can such quantizers match the adaptive rate, yielding an optimal one-shot protocol? Or is the known two-stage estimator stage-optimal, with a single adaptive transition being necessary and sufficient?

Is it true for non-orthogonal systems that decreasing redexes implies termination? If not, can some decent subclasses be delineated for which the implication does hold?

Is left-sequentiality a decidable property of orthogonal systems?

Given a Markov chain $M$, an initial distribution $u$ and target distribution $v$, and a rational number $r$, consider the problem of checking if there exists an $n$ such that $u M^n v =r$. This problem is known to be as hard as the Skolem problem of LRS. However, the reduction requires the Markov chain to be non-ergodic, in particular it is reducible and periodic. If we now assume the Markov chain to be irreducible and aperiodic (a natural assumption that is often used since forever!), does it remain hard?! Both yes or no answers would be very interesting and have consequences to model checking of probabilistic linear dynamical systems.

Is satisfiability of lpo or rpo ordering constraints decidable in case of non-total precedences?

Is strong sequentiality decidable for arbitrary rewrite systems?

Is termination of one linear rule decidable?

Is the decidability of strong sequentiality for orthogonal term rewriting systems NP-complete?

Is the extension of Combinatory Logic by Boolean constants confluent?

Starting from finite state automata, one can create a hierarchy of automata models by repeatedly applying one of the following constructions: A first avenue of investigation might be to consider the hierarchy created by building stacks and adding Z -counters.

We ask whether distribution-independent statistical-query learning implies low dimension complexity, and whether anything learnable with (stochastic) gradient descent on a benign neural network under every input distribution is also learnable with a comparably sized linear model. Equivalently, is the known power of deep learning over linear or kernel methods inherently distribution dependent, or can the dimension required by linear learning be much larger than the neural-network size and training time even in a distribution-independent guarantee?

Is the satisfiablity of ordering constraints (lpo) in conjunction with predicates like irreducibility by a fixed rewrite system or membership in a regular tree language decidable?

Is the system of Cohen and Watson for arithmetic terminating?

Is the union of two totally terminating rewrite systems, which do not share any symbols, totally terminating?

Is the word problem for all proper combinators of order smaller than 3 decidable?

Is the word problem for the S-combinator decidable?

Is there a calculus of explicit substitution that is confluent on open terms, simulates one-step beta-reduction and preserves beta-strong normalization?

Is there a convergent extended rewrite system for ternary boolean algebra, in which certain equations hold?

Is there a decidable uniform word problem for which there is no variant on the rewriting theme that can decide it---without adding new symbols?

Is there a finite term-rewriting system of some kind for free lattices?

For nonconvex--nonconcave minimax optimization, first-order methods may converge to stationary points that are locally optimal for the reverse maximin problem rather than for the intended minimax problem. This motivates the longstanding question of whether a first-order method can converge only to local minimax optima. Two-timescale extragradient gives the first convergence result to refined second-order stationary points, but a gap remains between its limit points and local minimax optima. The appropriate notion of local optimality itself may also require refinement.

Is there a notion of ``complete theory'' for which contextual deduction is complete for refutation of ground clauses?

Is there a one-rule string rewriting system that is non-terminating but also non-looping?

Is unification modulo the theory of allegories decidable?

Is unification of patterns modulo any set of variable-preserving equations decidable?

Given a set of points, a k-set is a subset of k points obtained by intersecting the point set with an open halfspace. The open problem is to determine the maximum possible number of k-sets. Even in two dimensions, the known upper and lower bounds remain separated.

Determine whether nondeterminism adds computational power when a machine is restricted to logarithmic working space.

Problem A: Given a deterministic one-counter automaton (a pushdown automaton with one stack alphabet) A and a nondeterministic one-counter net (a one-counter automaton with no zero-tests) N , decide if the language recognised by A is the same as the language recognised by N .

All known algorithms for learning deterministic one clock timed automata (1-DTA) using equivalence and membership queries and without making assumptions on the teacher, require an exponential number of membership queries in the worst case. Prove that it is not possible to do better than that.

The following is a problem inspired from quantitative program verification. the problem is: How can we learn / guess regular languages from positive examples (reasonably well)?

Sparse linear problems can be learned well with online multiplicative updates, whose regret grows only logarithmically with the feature dimension, but these updates lack closed-form batch solutions. Feature priming applies linear least squares, rescales each feature by a data-dependent prime factor, and applies least squares again. Experiments show behavior similar to multiplicative updates on sparse targets without hurting dense targets. The main open problem is whether such priming methods have provably competitive online regret bounds, together with related questions about optimal priming, sparse disjunctions, kernels, and spindly reparameterizations.

Given two regular languages $L_1$ and $L_2$, we can define the left language quotient operations as $L_2\backslash_lL_1 := \{ v \ \vert \ \exists u, uv \in L_1 \land u \in L_2 \}$. This leads to the following question: is there a purely inductive definition of the left quotient operation on regular expressions? i.e. a function $f : RE \times RE \to RE$ s.t. $\mathcal{L}(f(R_2,R_1))=\mathcal{L}(R_2)\backslash_l\mathcal{L}(R_1)$.

Linear loops (or linear dynamical systems) are an established computational model in our community. Question: Let p be an arbitrary polynomial in d variables. Does there exist an upper bound N such that if a non-trivial linear loop satisfying p=0 exists, then there exists a non-trivial linear loop with at most N variables satisfying the same invariant?

The open problem is whether linear programming admits a strongly polynomial algorithm. Linear programming is known to be weakly polynomial, meaning polynomial in the bit complexity of the input, and strongly polynomial linear-time algorithms are known when the dimension is fixed.

Determine whether every planar graph has a crossing-free straight-line three-dimensional grid drawing of linear volume.

Determine the maximum number of lines that are tangent to four balls in a set of n unit-radius balls in R^3 and miss all the others.

Nested-word automata (NWA) are essentially visibly pushdown automata with multiple stacks. In the general case (more than two stack, arbitrary nested words), the exact expressive power of NWA is not known. In particular, the following question is open: can every first-order formula be translated into an equivalent NWA ?

Deterministic Büchi register automata (DBRA) over infinite alphabets with equality tests have desirable algorithmic properties, including the decidability of synthesis, known to be EXPTIME [1]. Is there a temporal logic (or suitable logical fragment) that exactly characterises, or at least translates effectively into, deterministic Büchi register automata (DBRA) over infinite alphabets with equality tests?

Although quite natural, the problem of deciding if a weighted automaton can be determinized has only been solved in 2022 by Bell & Smertnig [arXiv:2209.02260]. Question: Can one obtain lower bounds for the decision problem of determinizability of weighted automata over Q ?

Guidable automata are a subclass of parity tree automata introduced by Colcombet and Löding [ICALP08], with a universal simulation property : An automaton A is guidable if, for all automata B recognizing a sublanguage of L(A) , there exists a finite "guiding function" for B that converts an accepting run of B over a tree t in an accepting run of A over t . conjecture that it is at least in EXPTIME.

In simply typed lambda calculus with finite products and sums, is beta-eta equality maximal among consistent typically ambiguous congruences containing beta equality?

Finite automata can be represented concisely in many way, including enriching their description with bounded-size stacks and registers, by allowing them to be two-way, etc For specific kind of concise representations, smarter algorithms could lead to only an exponential blowup.

Let A be an automaton and write, for any word w, f_w for the function that maps any state q to the state reached by reaching w from q. Question: Is there a word w such that f_w = f?

A VASS of dimension $d$ is an automaton where the transitions from states to states are given with a vector $\bar{v}\in\mathbb{Z}^d$, meant to be added coordinate-wise to the current counter. We would like to investigate the following class of problems, for F being a class of regular languages: is the language recognised by a given VASS in F?

Given a regular language L (on finite words), we consider the condition over omega-words "having a prefix in L". We want to characterize the optimal memory requirements for this condition over finite arenas. The memory requirements for the opponent were characterized by Colcombet, Fijalkow and Horn in the 2012 paper "Playing Safe" (that also holds for infinite arenas).

A subgame perfect equilibrium (SPE) is a formalisation of rational behaviour in multiplayer games that is a special case of Nash equilibria (NEs). Do finite-memory SPEs always exist in reachability games on infinite arenas?

Deterministic Suffix-reading Automata (DSA) are a model of automata over finite words introduced recently. This is a very recent model with plenty of open questions. Here is one concrete question: given a DSA, is it minimal?

For 2n points in the plane, the cost of a Euclidean matching is the total length of its edges. The open problem is to determine the computational complexity of finding a matching of minimum cost. An exact algorithm with running time O(n^1.5 ^5 n) is reported.

Determine whether a minimum-link path between two points in a planar polygonal domain can be computed in subquadratic time.

For a prescribed triangle, determine whether the plane admits a three-coloring containing no monochromatic congruent copy of that triangle.

A regular function is given by a deterministic 2way transducer: a deterministic 2way automaton with outputs. Question: Can every monotone regular function be realized by a sequential 2way transducer?

Partition a square into finitely many pieces so as to minimize the maximum ratio of circumradius to inradius among the pieces.

A RAAG (right-angled Artin group) or graph group is defined by a finite undirected graph $(V,E)$ as follows: The resulting group has a generator $x_v$ for every vertex $v \in V$. Question: Does this extend to $G$-VASS for $G$ being defined by a transitive forest, i.e. is every such $G$-VASS language nc-equivalent to a $\mathbb{Z}^n$-VASS language?

A 1-dimensional Vector Addition System with States (1-VASS) can be seen as an directed and integer weighted graph that is equipped with a non-negative integer counter. Does is there an o(n 2 )-time algorithm for coverability in 1-VASS?

Consider a safety automaton A , i.e., an automaton over infinite words where all but one rejecting sink state is accepting. Coming up with a more reasonable name is another open problem :p

The universality problem for context-free grammars is undecidable. While this problem reduces to the universality problem of unambiguous context-free grammars, a reduction in the other direction seems unlikely. The known complexity bounds are the same as for the more general problem.

Determine which effective one-step strategy constructions for combinatory logic transfer to lambda calculus. The requested cases concern cofinality, Church--Rosser joining, enumeration, and effective confluence.

Online optimization problems motivated by data-driven algorithm design often lie outside the classical convex Lipschitz regime: an algorithm's performance as a function of its hyperparameters can be highly volatile, with complex transition boundaries. Existing dispersion-based theory gives sublinear regret when these discontinuities are suitably well behaved. We ask for natural conditions that yield finite, preferably polynomial, root anti-concentration bounds for random polynomials, and for an analogous normalization condition for Pfaffian transition boundaries.

Best-arm identification asks an experimenter to adaptively allocate measurements among finitely many arms and identify the arm of largest mean. Instance-dependent asymptotic complexity is completely characterized in the fixed-confidence setting, while little is known in the apparently dual fixed-budget setting. The open problems are to identify a natural algorithm class and matching complexity function for fixed-budget error exponents, and to determine whether any adaptive algorithm performs uniformly no worse than uniform sampling.

What is the optimal instance-dependent sample complexity for identifying an approximate Nash equilibrium in a two-player zero-sum game with noisy observations? The problem asks which parameters of the payoff matrix govern the instance's inherent difficulty.

Determine the optimal gap-dependent pseudo-regret for stochastic full-information online learning with experts under pure differential privacy. Current upper and lower bounds do not match, and even the correct qualitative dependence on the individual action gaps remains unsettled.

For episodic reinforcement learning whose transition model lies in a reproducing kernel Hilbert space, determine whether no-regret learning is possible and identify the optimal dependence of regret on the number of episodes and the horizon.

For a set of n points in R^d whose convex hull has f faces, determine the optimal output-sensitive running time for constructing the hull.

Determine whether every decision problem whose solutions can be verified in polynomial time can also be solved in polynomial time.

Determine whether every problem solvable with polynomial working space is also solvable in polynomial time.

Consider a DFA A together with d pairs off counters (x_1,y_1), ,(x_d,y_d). Question: is the emptiness problem for this class of automata decidable?

Determine the computational complexity of deciding how many congruent axis-parallel rectangles, with rotations allowed, fit in a larger rectangle.

A strategy in a two player game on graphs is said to be "permissive" if it is winning and it allows all behaviours of all winning memoryless strategies. What is the complexity of the following problem:

Determine the computational complexity of finding a maximum-length traveling-salesperson tour through points in the Euclidean plane.

The open problem is to construct a linear-space data structure for point location in a three-dimensional subdivision that answers every query in logarithmic time. For a subdivision with $n$ faces, the reported known result uses $O(n\log n)$ space and answers queries in $O(\log^2 n)$ time.

Given a polygonal curve and an error tolerance, compute a simplification using the fewest original vertices and ask whether an optimal solution is possible in nearly linear time.

Given a triangulated surface in three dimensions and a tolerance, efficiently construct a simpler polyhedral surface within the prescribed error.

Determine whether every immersed spherical polyhedral surface made entirely of congruent regular pentagons is assembled from solid dodecahedra glued facet to facet.

Let $f$ be a Lipschitz geodesically convex function on a $d$-dimensional Riemannian manifold. Does there exist a deterministic first-order algorithm using only $O(\operatorname{poly}(d)\log(1/\epsilon))$ subgradient queries and $O(\operatorname{poly}(d))$ arithmetic operations per query? The Euclidean ellipsoid method has these properties. An ellipsoid-like method is known for constant-curvature spaces, but the question remains open for general Riemannian manifolds.

We present the model of populations of Markov decision processes, discuss our recent result on this model, and show an intriguing open question. The main open question is whether the first two cases are decidable (the third is what our paper above solves). To spell out the decision problem: given an MDP, is it true that for all $n \in \mathbb{N}$, there exists a strategy for the controller such that almost surely all tokens eventually end up in $t$, and the expected synchronisation time is bounded by $\log^{O(1)}(n)?$

We consider multi-player infinite duration games on graphs. Question: Do all reachability/Büchi/parity games admit a Nash equilibrium in which all strategies are positional?

Compare the term-typing power of simply typed lambda calculus with positive recursive types against System $F_\omega$. Is some term typable in the former but not in the latter?

A Deterministic One-Counter Automaton (DOCA) is a DPDA with single letter stack alphabet. The question is if it is decidable to check if a given a language (DOCA) is it prime. Notice that one can guess a decomposition into "smaller" automata, but not directly verify such a guess, because checking emptiness of intersections is undecidable for DOCA.

Decision trees are a canonical example of a highly interpretable model. We consider properly learning an unknown size-$s$ decision tree over $n$ Boolean variables under the uniform distribution, where the learner must return a decision-tree hypothesis. The fastest known algorithm runs in almost-polynomial time $n^{O(\log\log n)}$ in the standard regime $s=\operatorname{poly}(n)$. The open problem is to obtain a $\operatorname{poly}(n,s,1/\epsilon)$-time membership-query algorithm.

Weighted timed games (WTGs for short) are two-player zero-sum games played in a timed automaton equipped with integer weights into transitions and locations. I propose to study this function for all WTGs: for which class of WTGs, the value function is continuous and/or a fixed point of the local operator? In particular, I propose to start with WTGs that only use non-negative weights.

The problem concerns deterministic quantile summaries for insert-only data streams. Two known algorithms have incomparable space bounds: one applies to arbitrary input domains but has an involved analysis, while the other is easier to analyze and generalize but incurs a factor depending on the known domain size. The first open question asks for the optimal space bound and, in particular, whether O( ^-1) words suffice. The second asks whether the Greenwald--Khanna algorithm or a variation can receive a simpler analysis that supports generalizations with strict guarantees.

Determine whether approximating the ground-state energy of a local quantum Hamiltonian remains QMA-hard at constant precision.

Determine whether planar graphs have queue number bounded by an absolute constant.

Recall that a d-VASS is a finite automaton, where transitions are labelled with d-dimensional vectors over integers. This problem is also suggested by Michał Pilipczuk.

A $d$-dimensional Vector Addition System with States ($d$-VASS) is a finite automaton equipped with a finite set of states $\mathrm{Q}$ and $d$ non-negative counters. Each transition updates the counters by adding a vector $v \in \mathbb{Z}^d$ coordinate-wise, provided that no counter becomes negative in the process. The reachability problem asks whether a run exists from a given source configuration $s \in \mathrm{Q} \times \mathbb{N}^d$ to a target configuration $t \in \mathrm{Q} \times \mathbb{N}^d$. It is known that reachability is TOWER-hard when $d = 8$. An open question is whether this TOWER-hardness result can be achieved in a lower dimension.

Is the reachability problem decidable for reversible data VAS where the set of data values A satisfy the following properties: This question comes from the following paper with Sławomir Lasota: arXiv - LICS'24 proceedings link

The reachability problem for 1-dimensional Pushdown Vector Addition Systems (1-PVASS) is a big open problem. For thin 1-dimensional Grammar Vector Addition Systems, given a context-free grammar $G$ with integer terminals and two natural numbers $a,b$, determine whether there exists a witness word $w \in Z^*$ such that every prefix keeps the running value from $a$ nonnegative and the full word changes $a$ to $b$. The problem is decidable, but its complexity is high; the source conjectures polynomial witness length for two nonterminals and then any number of nonterminals, as well as a complexity below $F_d$ for $d$ nonterminals.

Reconfigurable broadcast networks (RBN) are networks consisting of finite-state, anonymous agents that communicate by broadcast. Formally, an RBN is $R = (Q, \Sigma, \delta)$ with $Q$ a finite set of states, $\Sigma$ a finite set of messages and $\delta \subseteq Q \times \{ !a, ?a | a \in \Sigma \} \times Q$ a finite set of transitions. Transitions are broadcasts of the form $(q, !a, q')$, or receives of the form $(q,?a, q')$. A configuration $C$ is a multiset over $Q$, which intuitively counts the number of agents in each state. Given a letter $a\in \Sigma$ and two configurations $C$ and $C'$ we say that there is a step $C \xrightarrow{a} C'$ if there exists a multiset $[ t, t_1, \ldots, t_k ]$ of $\delta$ for some $k\ge 0$ satisfying $t=(p, !a, q)$, each $t_i =(p_i, ?a, q_i)$, and in multiset notation $C \ge p + \sum_i p_i$, and $C' = C - p - \sum_i p_i + q + \sum_i q_i$. Intuitively it means that an agent at the state $p$ broadcasts the message $a$ and moves to $q$, and for each $1 \le i \le k$, there is an agent at the state $p_i$ which receives this message and moves to $q_i$. We denote by $\xrightarrow{*}$ the reflexive and transitive closure of the step relation. $C'$ is reachable from $C$ if $C \xrightarrow{*} C'$.

Determine whether a rectangle with rational side lengths can be tiled by finitely many rectangles of equal area whose perimeters are all distinct.

Can recursive types in Mendler's sense be defined in polymorphic System F with beta-eta conversion?

Determine the maximum, over planar point sets of size n, of the minimum number of reflex vertices in a polygonalization.

We consider sequential optimization of an unknown function belonging to a bounded ball of a reproducing kernel Hilbert space, with exact noise-free observations. While cumulative-regret rates are well developed in the noisy setting, directly setting the noise to zero gives loose bounds, and near-optimal simple-regret algorithms may incur linear cumulative regret. The open problem is to determine the lowest possible growth rate of cumulative regret, particularly for Matérn kernels of smoothness .

What is the best regret rate in heavy-tailed multi-armed bandits when no knowledge of the moment parameters is available and no additional assumptions are provided? A second question concerns the nature of the assumptions needed to compensate for the cost of adaptation.

This problem comes from a typing problem (non structural subtype assignment). conjecture that such language does not exist, though I don't find an approach to attack it. If such a language does exist, it would be interesting to know if there can be an infinite number of words such that the third point holds or not.

Consider a two letter alphabet $\Sigma = \{a, b\}$. Decide whether a rational series has a relative degree.

Determine the computational complexity of rolling a labeled die through every cell of a fully labeled rectangular board exactly once while matching each required top-face label.

Small probabilities in a personalized PageRank vector can be thresholded automatically through $\ell_1$-regularization or early termination. The fastest known method for $\ell_1$-regularized personalized PageRank uses proximal gradient descent and has graph-size-independent running time $\widetilde O((\alpha\rho)^{-1})$, where $\alpha$ is the teleportation parameter and $\rho$ controls sparsity. Accelerating the proximal method reduces its iteration complexity, but no corresponding sparsity bound is known. The open question is whether acceleration yields running time $\widetilde O((\sqrt\alpha\rho)^{-1})$.

An $\omega$-word language $L\subseteq \Sigma^\omega$ is a safety language if for all $w\not \in L$ there is a prefix $v\in \Sigma^*$ of $w$ such that for all $u\in \Sigma^\omega$, $vu\not \in L$. Open problem: Is there a (more) concise translation from LTL to safeLTL? Are there safety properties that are exponentially more concisely expressible in LTL than safeLTL?

By we denote the (scattered) subsequence relation between words. Input: A set C of subsequence constraints and a domain restriction d . Question:Is there a homomorphism h that respects the domain restriction d and satisfies every subsequence constraint in C ?

A $d$-dimensional Vector Addition System with States (VASS) is a finite automaton $V = (Q, \Delta)$ with transitions labeled by integer vectors: $\Delta \subseteq Q \times \mathbb{Z}^d \times Q$. A natural question that remains is whether the backward reachability sets of a two-dimensional BVASS are also semilinear. It is not too difficult to show that they are semilinear in dimension 1.

Given two words $u, v$ of length $n$ over $\{a, b\}$. Does there always exist an automaton of size $O(\log n)$ which distinguishes $u$ and $v$. Or bigger, like $O(n^{1/3})$? Best known bound is about $O(n^{2/5} \log(n))$.

Is there a 3-D VASS with shortest run from source to target, which is longer than exponential? Best lower bound is exponential, best upper bound is tower. The case of VASSes with finite reachability set is probably the core of the problem. In my point this is one of the problems we should attack if we want to push theory of VASSes further.

A deterministic linear-time algorithm for triangulating a simple polygon is known, but its construction is intricate. The open problem is to find a deterministic linear-time triangulation algorithm that is significantly simpler. Randomization yields simpler algorithms, including one with linear running time.

Given a planar point set, count the simple polygons whose vertex set is exactly the given set, and determine whether this count can be computed in polynomial time.

A Gap-order Constraint System (GCS) is a finite automaton with counters $(c_1,\dots c_n)$ where every transition bears conditions of the form $x-y\geq n$ where $n$ is a non-negative constant, and $x,y\in \{c_1,\dots,c_n,c'_1,\dots,c'_n\}\cup\mathbb{N}$ where $c_i$ denotes the value of counter $c_i$ before the transition, and $c'_i$ the value of $c_i$ after the transition. The problem that interests us is the simulation problem: Input: Two transition systems, one belonging to player Spoiler, the other to player Duplicator. Each time Spoiler makes a move on her GCS, Duplicator makes an equivalent move on his GCS. If the games goes on forever, Duplicator wins. If one player cannot make a move, the other player wins. Output: Does Duplicator have a winning strategy?

Determine whether there are linear-size universal planar point sets on which every planar graph of a given order has a crossing-free straight-line drawing.

Given two sets of n real numbers, determine whether all n^2 pairwise sums can be sorted in optimal quadratic time.

Population games involve two players, Laetitia and Terence, and an NFA with one initial and one final state. [2] Bertrand, Dewaskar, Genest, Gimbert, Godbole Controlling a population , LMCS-15(3), 2019

For each order at least two, characterize exactly the lambda terms typable in the corresponding stratum of a polymorphic type-assignment hierarchy.

Determine whether satisfiability for unbounded clause width fundamentally requires time approaching two to the number of variables.

A $k$-player (turn-based) game is given by a directed graph $G = (V, E)$ with each vertex owned by one of the $k$ players, and an objective $W_i \subseteq V^\omega$ for each player $i$. A strong subgame perfect equilibrium (SSPE) is a strategy profile that is a strong Nash equilibrium in every subgame. Does an SSPE always exist in $k$-player games with $\omega$-regular objectives? If so, can a maximal SSPE be computed?

What is the best structure-agnostic algorithm on top of black-box machine-learning models under the worst case? In particular, is the standard double-machine-learning rate the best possible when no structure of the nuisance functions, such as additivity or sparse linearity, is known?

Valiant showed that the succinctness gap between deterministic and nondeterministic pushdown automata (restricted to deterministic contextfree languages) is nonrecursive, i.e., there is no computable function f with the following property: If the language of a pushdown automaton A is deterministic contextfree, then there is a deterministic pushdown automaton of size f(|A|) recognizing L(A). The extent of these new gaps is open, but Valiant's result implies that at least one of the first two gaps has to be nonrecursive.

Determine polynomial separation bounds, and hence efficient exact comparison methods, for differences between sums of square roots of bounded integers.

Prove that some language in NP requires Boolean circuits of superpolynomial size, equivalently that NP is not contained in P/poly.

Reconstruct a surface from a sufficiently dense point sample with a guarantee that the output is homeomorphic to the sampled surface, including surfaces with sharp edges and corners.

Reconfigurable Broadcast Networks (RBN) are a model for large groups of identical agents communicating via unreliable broadcast. Is the Target problem for PRBN NP-hard? in PTIME?

An asynchronous shared-memory system is composed of n processes that interact by reading from and writing to a shared memory. Questions: Is TARGET XP with respect to r , i.e., is it solvable in polynomial time when r is fixed? Is it FPT with respect to r , i.e., can it be solved in time O(f(r) p(|P|)) with p a polynomial and P the protocol?

Population protocols are a model of distributed computation by indistinguishable agents, close to VASs. Give a bound on f(n) for protocols without leaders.

What information about solutions of an equation between arbitrary normal forms can be recovered from the associated equation between their injectively encoded deeds?

Let $Y_j$ be independent $\operatorname{Binomial}(n,p_j)$ variables for a sequence $p_j\to0$, and consider the expected uniform deviation of $Y_j/n$ from $p_j$. A finite-sample upper bound contains a $\log n$ factor, while matching asymptotic lower bounds do not. Is this factor necessary, or can it be removed?

Classify the possible numbers of fixed points of a closed term in lambda-beta calculus. If one fixed point is in normal form, the source records a dichotomy between exactly one and infinitely many.

Determine whether every planar point set has at least as many pointed pseudotriangulations as triangulations, with equality only in convex position.

We study a combinatorial property of the Parity language (the set of binary words with an even number of 1s). This property is useful while studying the expressive power of depth-3 boolean circuits in AC^0. A similar property has been proved for depth-3 circuits with bounded top fan-in in a recent LICS paper, and can be traced back to Hastad, Jukna and Pudlak. Here, the goal is to extend this combinatorial statement for a bigger class of languages, and for a more general notion of limit to describe precisely the regular languages definable thanks to depth-4 circuits with bounded top fan-in.

Multi-distribution learning generalizes agnostic learning to multiple data distributions. Given sample access to $k$ distributions, the goal is to output one possibly randomized hypothesis whose worst-case loss is within $\epsilon$ of the best hypothesis in the class. We ask whether a class of VC dimension $d$ can be learned with $O(\epsilon^{-2}(d\log k+k\log(k/\delta)))$ samples, and pose related questions about lower bounds, proper learning, and oracle-efficient learning.

The sequential flow problem (SFP) is a simple and natural reachability problem which was initially formalized for solving questions related to population protocols, but has independent interest. We now know that SFP is PSPACE-hard, and in EXPSPACE, but its precise complexity remains open. The following poster gives more background.

A 1-dimensional Vector Addition System with States (1-VASS) can be seen as an directed and integer weighted graph that is equipped with a non-negative integer counter. Is there an o(n^2) -time algorithm for coverability in 1-VASS?

Is the word problem decidable for the system of all proper combinators of order less than three? Order-one and restricted order-two cases are decidable, while sufficiently higher-order variants are undecidable.

Determine whether every drawing of a graph in which each pair of edges meets exactly once has at most as many edges as vertices.

Find a succinct functional that characterizes, up to constant factors, the sample complexity of identity testing for each reference distribution. Related questions ask for a direct relation between two existing characterizations and for a repair of a small gap in a foundational lower-bound proof.

A random-turn game is a graph game which is parameterized by a ratio p. My interest in random-turn games stems from the fact that they are equivalent to bidding games: a solution to a random-turn game can be used to construct optimal bidding strategies in a bidding game. Moreover, random-turn games have been extensively studied in the combinatorics community.

For every $n \in \mathbb{N}$, the full transformation monoid $T_n$ is the set of (total) functions from $\{1,2,\ldots,n\}$ to $\{1,2,\ldots,n\}$, equipped with the standard function composition. The symmetric group $S_n$ is the subroup of $T_n$ composed of all the permutations. What is the complexity of the following decision problems with respect to the parameter $n$:

Determine whether every polygon can be transformed into a regular polygon by finitely many moves that translate one vertex along the line through that vertex and the centroid of all vertices.

Determine whether a finite collection of pairwise disjoint planar segment mirrors can trap every ray emitted from a source point disjoint from the mirrors.

Determine the complexity of finding a shortest traveling-salesperson tour in a solid grid graph.

Fix a finite alphabet $A$. Denote by $T$ the set of $A$-labellings of the complete infinite binary tree, i.e. maps $\{0,1\}^*\rightarrow A$. Let $R \subseteq T \times T$ be an (equivalence) relation of such trees. A (binary) tree automaton with $R$-constraints consists of a finite state set $Q$, an initial state $q_0 \in Q$, and a transition relation $\Delta\subseteq (Q \times A\times \{R,\neg R\}) \times (Q \times Q)$. A run of a tree automaton on a tree labelling $\lambda:\{0,1\}^*\rightarrow A$ is a choice of states $q:\{0,1\}^*\rightarrow Q$ and transitions $t:\{0,1\}^*\rightarrow \Delta$ for each vertex such that $q(\epsilon)=q_0$ and $t(w)=(q(w),\lambda(w),X,q(w0),q(w1))$, where $X=R$ if the left and right subtree of $w$ are in $R$-relation and $X=\neg R$ otherwise. A tree automaton accepts a labelling if there is a run for it. This can be extended to different more intricate acceptance conditions (Büchi condition along paths, parity conditions, \ldots{}). The set of labellings accepted by an automaton is called its language. The following questions might depend to some extent on the nature of the relation $R$ and should be understood as "for your favourite/interesting $R$". Question: Is emptiness/universality decidable for these automata? Question: What are the closure properties for these language classes?

Find tree representations of lambda terms whose equality coincides with five contextual equivalences determined by weak-head, top-normal, strongly active, parameterized strongly active, and head-active observations.

Under what conditions does confluence of a normal semi-equational conditional term rewriting system imply confluence of the associated oriented system?

Does a uniform universal generator exist for weak combinatory reduction or for beta or beta-eta reduction in lambda calculus?

An object in three-dimensional space is called fat when the ratio of its circumradius to its inradius is bounded. The open problem is to determine the combinatorial complexity of the union of n such objects. This complexity is conjectured to be nearly quadratic in n.

Determine whether it is NP-hard to distinguish almost satisfiable unique constraint systems from instances in which only a small fraction can be satisfied.

An orthant is a region in R^d in which every vector in the orthant has the same sign in each dimension. Question: can this be extended to dimension 4+. Is it also undecidable in general?

Can one construct an infinite recursively enumerable set $S\subset \mathbb{N}$, for which one can decide: given any linear recurrence sequence $(u_n)$, whether $\exists n\in S$, s.t. $u_n<0$ ?

Determine the complexity of universality problem for unambiguous finite automata. Problem is known to be in PTIME and (as far as I understand) in NC^2, but is only known to be NL-hard.

Input: a context-free grammar for a language L a_1^* a_n^* (n is part of the input) Question: Is L = a_1^* a_n^*?

Problem 1: 1 Given a 1-VASS, let L_n be its language where acceptance is by reaching a final state from a fixed initial state and initial counter value n. Does there exist n such that ^* = L_n ?

Determine the worst-case number of inward-facing floodlights of aperture π, placed at polygon vertices, that suffice to illuminate every simple polygon.

Determine whether every closed polyhedron can be cut along edges into a connected, nonoverlapping planar unfolding whose faces may remain joined only at vertices.

Determine the worst-case combinatorial complexity of the vertical decomposition of an arrangement of n constant-complexity surfaces in R^d for d ≥ 5.

Given a graph and a specified Hamiltonian cycle, determine whether they are respectively the visibility graph and boundary cycle of a simple polygon.

For a unit-area convex planar region, choose a perimeter-halving fold and maximize the volume enclosed after identifying the two boundary chains.

For a set of lines or line segments in three-dimensional space, the open question is to determine the combinatorial complexity of its Voronoi diagram. In the Euclidean case, the known lower bound is quadratic in the number of input objects, while the upper bound is essentially cubic. The complexity is conjectured to be nearly quadratic.

The weak validation problem is an open problem stated in 2007 by Segoufin and Sirangelo. Eryk Kopczyński. 2016. Invisible Pushdown Languages. LICS '16

Must every weakly normalizing Pure Type System also be strongly normalizing? This is the Barendregt--Geuvers--Klop conjecture.

What are sufficient condition for the modularity of confluence?

What are the complexities of various term ordering decision problems?

Linear contextual bandits with private contexts and rewards are studied under $(\epsilon,\delta)$-Joint Differential Privacy (JDP), which constrains how changing one round's context--reward data may affect future actions. For adversarial contexts, the best stated regret upper bound is $O\!\left(d\sqrt{T}\log T+d^{3/4}\sqrt{T\log(1/\delta)}/\sqrt{\epsilon}\right)$, while the stated lower bound is $\Omega\!\left(\sqrt{dT\log K}+d/(\epsilon+\delta)\right)$. The lower bound already holds for stochastic contexts, leaving a gap in both the horizon dependence and the privacy dependence. The open questions are to obtain matching bounds, determine whether the price of JDP can be asymptotically negligible, and, if not, identify the minimal assumptions on context generation under which such a negligible privacy cost is possible.

Determine matching regret bounds for linear contextual bandits under joint differential privacy, especially when contexts are private and adversarial. The central issue is whether privacy can be obtained at asymptotically negligible regret cost and, if not, which assumptions on context generation make that possible.

What is the exact complexity of word unification?

What is the syntactic type of (mid-, three-way) distributivity?

What sufficient conditions make confluence of general (hyper-)graph rewriting decidable?

Which conditional rewrite systems are subcommutative?

Which is the coarsest relation such that its union with any rewrite relation preserves termination?

Which ordinals correspond to reduction graphs in the -calculus?

Which rewrite systems can be directly defined in lambda calculus?

Determine whether the Yao-Yao geometric graph has bounded stretch for a fixed number of cones.

Determine whether every convex polyhedron can be cut open along a single vertex-spanning path and unfolded without overlap.