ABSTRACT. The Traveling Tournament Problem (TTP) is a well-known benchmark problem in the field of tournament timetabling, which asks us to design a double round-robin schedule such that each pair of teams plays one game in each other's home venue, minimizing the total distance traveled by all $n$ teams ($n$ is even). TTP-$k$ is the problem with one more constraint that each team can have at most $k$ consecutive home games or away games. The case where $k=3$, TTP-3, is one of the most investigated cases. In this paper, we improve the approximation ratio of TTP-3 from $(1.667+\epsilon)$ to $(1.598+\epsilon)$, for any $\epsilon>0$. Previous schedules were constructed based on a Hamiltonian cycle of the graph. We propose a novel construction based on triangle packing. Then, by combining our triangle packing schedule with the Hamiltonian cycle schedule, we obtain the improved approximation ratio. The idea of our construction can also be extended to $k\geq 4$. We demonstrate that the approximation ratio of TTP-4 can be improved from $(1.750+\epsilon)$ to $(1.700+\epsilon)$ by the same method. As an additional product, we also improve the approximation ratio of LDTTP-3 (TTP-3 where all teams are allocated on a straight line) from $4/3$ to $(6/5+\epsilon)$.

ABSTRACT. We consider a generalization of binary search in linear orders to the domain of weighted trees. The goal is to design an adaptive search strategy whose aim is to locate an unknown target vertex of a given tree. Each query to a vertex v incurs a non-negative cost ω(v) (that can be interpreted as the duration of the query) and returns feedback that either v is the target or the edge incident to v is given that is on the path towards the target. The goal of the algorithm is to find a strategy that minimizes the worst-case total cost. We propose a constant-factor approximation algorithm for trees with a monotonic cost function. Such function is defined as follows: there exists a vertex r such that for any two vertices u, v on any path connecting r with a leaf it holds that if u is closer to r than v, then ω(u) ≥ ω(v). The best-known approximation algorithm for general weight functions has the ratio of O(√log n) [Dereniowski et al. ICALP 2017] and it remains a challenging open question whether the constant-factor approximation is achievable in such a case. This gives our first motivation towards considering monotonic cost functions and the second one lies in the potential applications.

ABSTRACT. Valiant, in his seminal paper in 1979, showed an efficient simulation of algebraic formulas by determinants, showing that $\mathsf{VF}$, the class of polynomial families computable by polynomial-sized algebraic formulas, is contained in $\mathsf{VDet}$, the class of polynomial families computable by polynomial-sized determinants. Whether this containment is strict has been a long-standing open problem. We show that algebraic formulas can in fact be efficiently simulated by the determinant of tetradiagonal matrices, transforming the open problem into a problem about determinant of general matrices versus determinant of tetradiagonal matrices with just three non-zero diagonals. This is also optimal in a sense that we cannot hope to get the same result for matrices with only two non-zero diagonals or even tridiagonal matrices, thanks to Allender and Wang (Computational Complexity'16) which showed that the determinant of tridiagonal matrices cannot even compute simple polynomials like $x_1x_2 + x_3x_4 + \cdots + x_{15}x_{16}$.

Our proof involves a structural refinement of the simulation of algebraic formulas by width-3 algebraic branching programs by Ben-Or and Cleve (SIAM Journal of Computing'92). The tetradiagonal matrices we obtain in our proof are also structurally very similar to the tridiagonal matrices of Bringmann, Ikenmeyer and Zuiddam (JACM'18) which showed that, if we allow approximations in the sense of geometric complexity theory, algebraic formulas can be efficiently simulated by the determinant of tridiagonal matrices of a very special form, namely the continuant polynomial. The continuant polynomial family is closely related to the Fibonacci sequence, which was used to model the breeding of rabbits. The determinants of our tetradiagonal matrices, in comparison, is closely related to Narayana's cows sequences, which was originally used to model the breeding of cows. Our result shows that the need for approximation can be eliminated by using Narayana's cows polynomials instead of continuant polynomials, or equivalently, shifting one of the outer diagonals of a tridiagonal matrix one place away from the center.

Conversely, we observe that the determinant (or, permanent) of band matrices can be computed by polynomial-sized algebraic formulas when the bandwidth is bounded by a constant, showing that the determinant (or, permanent) of bandwidth $k$ matrices for all constants $k \geq 2$ yield $\mathsf{VF}$-complete polynomial families. In particular, this implies that the determinant of tetradiagonal matrices in general and Narayana's cows polynomials in particular yield complete polynomial families for the class $\mathsf{VF}$.

ABSTRACT. In this paper, we consider infinitely sorted tree algebras recognising regular language of finite trees. We pursue their analysis under the angle of their asymptotic complexity, i.e. the asymptotic size of the sorts as a function of the number of variables involved.

Our main result establishes an equivalence between the languages recognised by algebras of polynomial complexity and the languages that can be described by nominal word automata that parse linearisation of the trees. On the way, we show that for such algebras, having polynomial complexity corresponds to having uniformly boundedly many orbits under permutation of the variables, or having a notion of bounded support (in a sense similar to the one in nominal sets).

We also show that being recognisable by an algebra of polynomial complexity is a decidable property for a regular language of trees.

ABSTRACT. We study the Escape Problem for discrete-time linear dynamical systems over compact semialgebraic sets. We establish a uniform upper bound on the number of iterations it takes for every orbit of a rational matrix to escape a compact semialgebraic set defined over rational data. Our bound is doubly exponential in the ambient dimension, singly exponential in the degrees of the polynomials used to define the semialgebraic set, and singly exponential in the bitsize of the coefficients of these polynomials and the bitsize of the matrix entries. We show that our bound is tight by providing a matching lower bound.

ABSTRACT. We obtain complete characterizations of the Unique Bipartite Perfect Matching function, and of its Boolean dual, using multilinear polynomials over the reals. Building on previous results, we show that, surprisingly, the dual description is \textit{sparse} and has \textit{low $\ell_1$-norm} -- only exponential in $\Theta(n \log n)$, and this result extends even to other families of matching-related functions. Our approach relies on the M\"obius numbers in the matching-covered lattice, and a key ingredient in our proof is M\"obius' inversion formula.

These polynomial representations yield complexity-theoretic results. For instance, we show that unique bipartite matching is \textit{evasive} for classical decision trees, and \textit{nearly evasive} even for generalized query models. We also obtain a tight $\Theta(n \log n)$ bound on the log-rank of the associated two-party communication task.

ABSTRACT. We consider the problem of listing all avoidable vertices in a given $n$ vertex graph. A vertex is avoidable if every pair of its neighbors is connected by a path whose internal vertices are not neighbors of the vertex or the vertex itself. Recently, Papadopolous and Zisis showed that one can list all avoidable vertices in $O(n^{\omega+1})$ time, where $\omega<2.373$ is the square matrix multiplication exponent, and conjectured that a faster algorithm is not possible.

In this paper we show that under the $3$-OV Hypothesis, and thus the Strong Exponential Time Hypothesis, $n^{3-o(1)}$ time is needed to list all avoidable vertices, and thus the current best algorithm is conditionally optimal if $\omega=2$. We then show that if $\omega>2$, one can obtain an improved algorithm that for the current value of $\omega$ runs in $O(n^{3.32})$ time. We also show that our conditional lower bound is actually higher and supercubic, under a natural High Dimensional $3$-OV hypothesis, implying that for our current knowledge of rectangular matrix multiplication, the avoidable vertex listing problem likely requires $\Omega(n^{3.25})$ time. We obtain further algorithmic improvements for sparse graphs and bounded degree graphs.

ABSTRACT. We say that a Hamilton cycle C=(x_1,...,x_n) in a graph G is k-symmetric, if the mapping x_i ↦ x_{i+n/k} for all i=1,...,n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices x_1,...,x_n equidistantly on a circle and draw the edges of G as straight lines, then the drawing of G has k fold rotational symmetry, i.e., all information about the graph is compressed into a 360°/k wedge of the drawing. We refer to the maximum k for which there exists a k-symmetric Hamilton cycle in G as the Hamilton compression of G. We investigate the Hamilton compression of four different families of vertex-transitive graphs, namely hypercubes, Johnson graphs, permutahedra and Cayley graphs of abelian groups. In several cases we determine their Hamilton compression exactly, and in other cases we provide close lower and upper bounds. The cycles we construct have a much higher compression than several classical Gray codes known from the literature. Our constructions also yield Gray codes for bitstrings, combinations and permutations that have few tracks and/or that are balanced.

ABSTRACT. A graph has arboricity α if its edges can be partitioned into α forests. The dynamic arboricity decomposition problem is to update a partitioning of the graph's edges into forests, as a graph undergoes insertions and deletions of edges. We present an algorithm for maintaining partitioning into α+1 forests, provided the arboricity of the dynamic graph never exceeds α. Our algorithm has an update time of Õ(n^(3/4)) when α is at most polylogarithmic in n.

Similarly, the dynamic bounded out-orientation problem is to orient the edges of the graph such that the out-degree of each vertex is at all times bounded. For this problem, we give an algorithm that orients the edges such that the out-degree is at all times bounded by α+1, with an update time of Õ(n^(5/7)), when α is at most polylogarithmic in n. Here, the choice of α+1 should be viewed in the light of the well-known lower bound by Brodal and Fagerberg which establishes that, for general graphs, maintaining only α out-edges would require linear update time.

However, the lower bound by Brodal and Fagerberg is non-planar. In this paper, we give a lower bound showing that even for planar graphs, linear update time is needed in order to maintain an explicit three-out-orientation. For planar graphs, we show that the dynamic four forest decomposition and four-out-orientations, can be updated in Õ(n^(1/2)) time.

ABSTRACT. Vanishing sums of roots of unity can be seen as a natural generalization of knapsack from Boolean variables to variables taking values over the roots of unity. We show that these sums are hard to prove for polynomial calculus and for sum-of-squares, both in terms of degree and size.

ABSTRACT. We introduce a family of ZX-calculi which axiomatise the stabiliser fragment of quantum theory in odd prime dimensions. These calculi recover many of the nice features of the qubit ZX-calculus which were lost in previous proposals for higher-dimensional systems. We then prove that these calculi are complete, i.e. provide a set of rewrite rules which can be used to prove any equality of stabiliser quantum operations. Finally, we relate them to the graphical language for affine Lagrangian relations, which also axiomatises the stabiliser fragment. Adding a discard construction, we obtain a calculus complete for mixed state stabiliser quantum mechanics in odd prime dimensions, and this furthermore gives a complete axiomatisation for the related diagrammatic language for affine co-isotropic relations.

ABSTRACT. We introduce the countdown mu-calculus, an extension of the modal mu-calculus with ordinal approximations of fixpoint operators. In addition to properties definable in the classical calculus, it can express (un)boundedness properties such as the existence of arbitrarily long sequences of specific actions. The standard correspondence with parity games and automata extends to suitably defined countdown games and automata. However, unlike in the classical setting, the scalar fragment is provably weaker than the full vectorial calculus and corresponds to automata satisfying a simple syntactic condition. We establish some facts, in particular decidability of the model checking problem and strictness of the hierarchy induced by the maximal allowed nesting of our new operators.

ABSTRACT. We show that the Identity Problem is decidable in polynomial time for finitely generated sub-semigroups of the group UT(4, Z) of 4 × 4 unitriangular integer matrices. As a byproduct of our proof, we have also shown the polynomial-time decidability of several subset reachability problems in UT(4, Z).

ABSTRACT. A $0,1$ matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers $k$, there exists a square regular $0,1$ matrix with binary rank $k$, such that the Boolean rank of its complement is $k^{\widetilde{\Omega}(\log k)}$. Equivalently, the ones in the matrix can be partitioned into $k$ combinatorial rectangles, whereas the number of rectangles needed for any cover of its zeros is $k^{\widetilde{\Omega}(\log k)}$. This settles, in a strong form, a question of Pullman (Linear Algebra Appl.~,1988) and a conjecture of Hefner, Henson, Lundgren, and Maybee (Congr. Numer.~,1990). The result can be viewed as a regular analogue of a recent result of Balodis, Ben-David, G{\"{o}}{\"{o}}s, Jain, and Kothari (FOCS,~2021), motivated by the clique vs. independent set problem in communication complexity and by the (disproved) Alon-Saks-Seymour conjecture in graph theory. As an application of the produced regular matrices, we obtain regular counterexamples to the Alon-Saks-Seymour conjecture and prove that for infinitely many integers $k$, there exists a regular graph with biclique partition number $k$ and chromatic number $k^{\widetilde{\Omega}(\log k)}$.

ABSTRACT. A function f uniformizes a relation R(X,Y) if R(X,f(X)) holds for every X in the domain of R. The uniformization problem for a logic L asks whether for every L-definable relation there is an L-definable function that uniformizes it. Gurevich and Shelah proved that no Monadic Second-Order ($\MSO$) definable function uniformizes relation ``Y is a one element subset of X'' in the full binary tree. In other words, there is no MSO definable choice function in the full binary tree.

The cross-section of a relation R(X,Y) at D is the set of all E such that R(D,E) holds. Hence, a function that uniformizes R chooses one element from every non-empty cross-section. The relation ``Y is a one element subset of X'' has finite and countable cross-sections.

We prove that in the full binary tree the following theorems hold:

Theorem (Finite-cross Section) If every cross-section of an MSO definable relation is finite, then it has an MSO definable uniformizer.

Theorem (Uncountable-cross Section) There is an MSO definable relation R such that every MSO definable relation included in R and with the same domain as R has an uncountable cross-section.

ABSTRACT. We study the problem of online tree exploration by a deterministic mobile agent. Our main objective is to establish what features of the model of the mobile agent and the environment allow linear exploration time. We study agents that, upon entering to a node, do not receive as input the edge via which they entered. In such a model, deterministic memoryless exploration is infeasible, hence the agent needs to be allowed to use some memory. The memory can be located at the agent or at each node. The existing lower bounds show that if the memory is either only at the agent or only at the nodes, then the exploration needs superlinear time. We show that tree exploration in dual-memory model, with constant memory at the agent and logarithmic at each node is possible in linear time when one of two additional features is present: fixed initial state of the memory at each node (so called clean memory) or a single movable token. We present two algorithms working in linear time for arbitrary trees in these two models. On the other hand, in our lower bound we show that if the agent has a single bit of memory and one bit is present at each node, then exploration may require quadratic time on paths, if the initial memory at nodes could be set arbitrarily (so called dirty memory). This shows that having clean node memory or a token allows linear exploration of trees in the model with two types of memory, but having neither of those features may lead to quadratic exploration time even on a simple path.

ABSTRACT. We continue the study of $\delta$-dispersion, a continuous facility location problem on a graph where all edges have unit length and where the facilities may also be positioned in the interior of the edges. The goal is to position as many facilities as possible subject to the condition that every two facilities have distance at least $\delta$ from each other.

Our main technical contribution is an efficient procedure to `round-up' distance $\delta$. It transforms a $\delta$-dispersed set $S$ into a set $S'$ of same size such that $S'$ is $\delta'$-dispersed with a slightly larger rational distance $\delta'$ where the numerator is upper bounded by the longest (not-induced) path in the input graph.

Based on this rounding procedure and connections to the distance-d independent set problem we can derive a number of algorithmic results. When parameterized by treewidth, the problem is in XP. When parameterized by treedepth the problem is FPT and has a matching lower bound on its time complexity under ETH. Moreover, we can also settle the parameterized complexity with the solution size as parameter using our rounding technique: $\delta$-\dispersion is FPT for every $\delta \leq 2$ and W[1]-hard for every $\delta > 2$.

Further, we show that $\delta$-dispersion is NP-complete for every fixed irrational distance $\delta$, which was left open in previous work.

ABSTRACT. The Distance Realization problem is defined as follows. Given an $n \times n$ matrix $D$ of nonnegative integers, interpreted as inter-vertex distances, find an $n$-vertex weighted or unweighted graph $G$ realizing $D$, i.e., whose inter-vertex distances satisfy $\dist_G(i,j)=D_{i,j}$ for every $1\le i<j\le n$, or decide that no such realizing graph exists. The problem was studied for general weighted and unweighted graphs, as well as for cases where the realizing graph is restricted to a specific family of graphs (e.g., trees or bipartite graphs). An extension of Distance Realization that was studied in the past is where each entry in the matrix $D$ may contain a \emph{range} of consecutive permissible values. We refer to this extension as Range Distance Realization (or Range-DR). Restricting each range to at most $k$ values yields the problem $k$-Range Distance Realization (or $k$-Range-DR). The current paper introduces a new extension of Distance Realization, in which each entry $D_{i,j}$ of the matrix may contain an arbitrary set of acceptable values for the distance between $i$ and $j$. We refer to this extension as Set Distance Realization (Set-DR), and to the restricted problem where each entry may contain at most $k$ values as $k$-Set Distance Realization (or $k$-Set-DR).

We first show that 2-Rnage-DR is NP-hard for unweighted graphs (implying the same for 2-Set-DR). Next we prove that 2-Set-DR is NP-hard for unweighted and weighted trees. We then explore Set-DR where the realization is restricted to the families of stars, paths, or cycles. For the weighted case, our positive results are that for each of these families there exists a polynomial time algorithm for 2-Set-DR. On the hardness side, we prove that 6-Set-DR is NP-hard for stars and 5-Set-DR is NP-hard for paths and cycles. For the unweighted case, our results are the same, except for the case of unweighted stars, for which $k$-Set-DR is polynomially solvable for any $k$.

ABSTRACT. A graph is temporally connected if there exists a strict temporal path, i.e. a path whose edges have strictly increasing labels, from every vertex $u$ to every other vertex $v$. In this paper we study temporal design problems for undirected temporally connected graphs. The basic setting of these optimization problems is as follows: given a connected undirected graph $G$, what is the smallest number $|\lambda|$ of time-labels that we need to add to the edges of $G$ such that the resulting temporal graph $(G,\lambda)$ is temporally connected? As it turns out, this basic problem, called MINIMUM LABELING (ML), can be optimally solved in polynomial time. However, exploiting the temporal dimension, the problem becomes more interesting and meaningful in its following variations, which we investigate in this paper. First we consider the problem MINIMUM AGED LABELING (MAL) of temporally connecting the graph when we are given an upper-bound on the allowed age (i.e. maximum label) of the obtained temporal graph $(G,\lambda)$. Second we consider the problem MINIMUM STEINER LABELING (MSL), where the aim is now to have a temporal path between any pair of ``important'' vertices which lie in a subset $R\subseteq V$, which we call the terminals. This relaxed problem resembles the problem STEINER TREE in static (i.e. non-temporal) graphs. However, due to the requirement of strictly increasing labels in a temporal path, STEINER TREE is not a special case of MSL. Finally we consider the age-restricted version of MSL, namely MINIMUM AGED STEINER LABELING (MASL). Our main results are threefold: we prove that (i) MAL becomes NP-complete on undirected graphs, while (ii) MASL becomes W[1]-hard with respect to the number $|R|$ of terminals. On the other hand we prove that (iii) although the age-unrestricted problem MSL remains NP-hard, it is in FPT with respect to the number $|R|$ of terminals. That is, adding the age restriction, makes the above problems strictly harder (unless P=NP or W[1]=FPT).

ABSTRACT. Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. For instance, the complexity of implementing the permutation of some given unitary transformations can be strictly decreased by allowing coherent control, rather than using the standard quantum circuit model. In this paper, we address the problem of optimising the resources of coherently controlled quantum computations. We refine the PBS-calculus, a graphical language for coherent control which is inspired by quantum optics. In order to obtain a more resource-sensitive language, it manipulates abstract gates -- that can be interpreted as queries to an oracle -- and more importantly, it avoids the representation of useless wires by allowing unsaturated polarising beam splitters. Technically the language forms a coloured PROP. The language is equipped with an equational theory that we show to be sound, complete, and minimal.

Regarding resource optimisation, we introduce an efficient procedure to minimise the number of oracle queries of a given diagram. We also consider the problem of minimising both the number of oracle queries and the number of polarising beam splitters. We show that this optimisation problem is NP-hard in general, but introduce an efficient heuristic that produces optimal diagrams when at most one query to each oracle is required.

ABSTRACT. Space-bounded computation has been a central topic in classical and quantum complexity theory, since it reflects common practical situations where available memory space is much less than input size. In the quantum case, every elementary gate must be unitary. This restriction makes it unclear whether the power of space-bounded computation changes by allowing intermediate measurement. In the bounded error case, Fefferman and Remscrim [STOC 2021, pp.1343--1356] and Girish et al. [ICALP 2021, pp.73:1--73:20] recently provided the break-through result that it does not change. In this paper, we show that a similar result holds for space-bounded quantum computation with postselection. Namely, we prove that it is possible to eliminate intermediate postselections and measurements in the space-bounded quantum computation in the bounded-error setting. Our result strengthens the recent result by Le Gall et al. [TQC 2021, pp.10:1--10:17] that logarithmic-space bounded-error quantum computation with \emph{intermediate} postselections and measurements is equivalent in computational power to logarithmic-space unbounded-error probabilistic computation. As an application, the space-bounded version of one-clean qubit computation (DQC1) is considered and its computational supremacy is discussed from a complexity theoretic point of view.

ABSTRACT. We introduce the LOv-calculus, a graphical language for reasoning about linear optical quantum circuits with so-called vacuum state auxiliary inputs. We present the axiomatics of the language and prove its soundness and completeness: two LOv-circuits represent the same quantum process if and only if one can be transformed into the other with the rules of the LOv-calculus. We give a confluent and terminating rewrite system to rewrite any polarisation-preserving LOv-circuit into a unique triangular normal form, inspired by the universal decomposition of Reck et al. (1994) for linear optical quantum circuits.