2026-10-14 | | Total: 30
Non-clashing teaching minimizes teaching complexity among models satisfying the Goldman--Mathias collusion-avoidance criterion. While the Vapnik--Chervonenkis dimension (VCdim) measures the complexity of learning from samples, non-clashing teaching dimension (NCTD) measures the number of examples required when a teacher can select them. Whether NCTD is always bounded above by VCdim remains a fundamental open question in learning theory. In this paper, we investigate this question for the concept classes of closed neighborhoods in planar graphs. We prove a tight upper bound of two on their NCTD, thereby establishing the conjectured inequality for this family. For the positive variant NCTD+, in which teaching sets contain only positive examples, we obtain a tight upper bound of four. Finally, we show that deciding whether either NCTD+ or NCTD is at most one is NP-complete, even for concept classes of closed neighborhoods in planar graphs. In particular, despite the upper bound of two on NCTD for such classes, distinguishing between NCTD values of one and two remains NP-hard.
We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise $p$-norms), and local aggregation (operator $p$-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.
In this short note, we prove that any closed interval in a well-ordered and discrete space is finite. The coincidence between finiteness and boundedness can then be established for transition systems where the state space is well-ordered and discrete. Finally, this result is also proven when the state space is a Cartesian product of $d$ discrete and well-ordered sets.
The central object in this work is the Boolean network, a function $f:\{0,1\}^V \to \{0,1\}^V$. Often identified with $f$ is its dynamics $D_f$, the digraph with exactly $\{x \to y : f(x)=y\}$ as its arcs. The interaction graph of $f$ is the digraph $G$ on $V$ which can be thought of as representing the dependencies of the components of $f$ on one another. On the other hand, model-checking is a major field of study in graph algorithms and complexity. We consider problems at the intersection of these paradigms: for a given property $φ$, we say that a digraph $G$ is $φ$-dynamic if $G$ is the interaction graph of some Boolean network $f$ such that $D_f \models φ$. The corresponding decision problem $φ$-DYNAMIC asks whether $G$ is $φ$-dynamic. Problems of this form are well-studied in the Boolean networks community. For example, it is a well-known result that, letting $φ$ be 'No fixed points' (i.e. $\nexists x:x\to x$), $φ$-DYNAMIC is equivalent to the structural digraph problem NON-ACYCLIC, which is solvable in linear time. We establish, for the first time, properties $φ$ for which $φ$-DYNAMIC is computationally hard. These include the 'Unique fixed point' property $\exists!x:x\to x$, and a range of properties concerning the periodic points of $f$ (i.e. vertices of $D_f$ which lie on a cycle). More widely, we exhibit an infinite family of natural properties $φ$ such that $φ$-DYNAMIC is $\mathrm{NEXPTIME}$-complete, which we call PERIOD PIECE. As a special case, these include all properties of the form 'Unique cycle of length $k$' and 'Exactly $k$ fixed points' for any $k \ge 1$. On the other hand, we show that if the input digraph has bounded in-degree, then for those same problems $φ$-DYNAMIC collapses down to $\mathrm{NP}^{\mathrm{NP}}$, the second level of the polynomial hierarchy, though it remains $\mathrm{NP}^{\mathrm{NP}}$-complete.
We exhibit a fixed $4\times 4$ binary matrix with no polynomial induced ordered removal bound. At depth $h\geq 1$, let $m=2^h$. Our explicit host has order $(14h+2)m$, exactly $2m^6+\frac{1}{2}(m-2)m^5$ induced copies, and exact editing distance $m^2$ cells. Its normalized editing distance is $Θ(h^{-2})$, while its induced-copy density is $Θ(4^{-h}h^{-8})$. The lower bound holds against arbitrary cell edits through an injective family of $m^2$ protected selections. An exhaustive arithmetic classification identifies every induced copy and proves that a matching canonical repair creates none. The original-copy transversal number is exactly $m$, yielding an unbounded gap between hitting existing copies and eliminating all copies. The identities and the obstruction at every depth are formalized in Lean, with verification sources included as ancillary files.
The polynomial threshold degree (or threshold degree) of a Boolean function is the least degree of a real polynomial whose sign represents it. We prove that almost every Boolean function has polynomial threshold degree among the central one or two integers. More precisely, a uniformly chosen Boolean function on $n$ variables has threshold degree $\lfloor n/2\rfloor$ or $\lceil n/2\rceil$ except with probability at most $\exp(-c2^{n/2}/n)$, for an absolute constant $c>0$ and all sufficiently large $n$. A parity example gives a lower bound on the exceptional probability whose exponent differs from ours by a factor of order $n$. The proof relates polynomial sign representation to recovery of Reed--Muller codes from random erasures, and combines sharp-threshold estimates with bounds on generalized Hamming weights and minimum distance.
In this paper we study pairwise compatibility graphs whose witness tree is required to be an unweighted caterpillar. This is a natural restriction of PCGs, in the same line of research as the study of star witnesses, which led to the class of double-threshold graphs. In the caterpillar case, we show that this restriction is equivalent to a one-dimensional difference-labelling problem: a graph admits such a representation if and only if its vertices can be assigned integer labels so that adjacency is determined exactly by whether the absolute difference of two labels belongs to a given interval. Using this characterization, we derive structural properties of the class, including bounded twin-width, and study its relation with familiar graph families. We show that the class contains cycles and two-dimensional grids, while it excludes natural obstructions such as the subdivided star $S_{2,2,2,2,2}$, the cube graph $Q_3$, the wheel $W_6$, and the complement of the $3$-sunlet. We also consider restricted representations, including centipede witnesses and representations with a given interval and we give a polynomial-time recognition algorithm when the interval is fixed.
We construct an approximate sampler for finite doubly free-boundary Macdonald rail-yard processes with Macdonald, boundary, and edge parameters in $(0,1)$. The construction allows arbitrary finite sequences of additions and removals of horizontal or vertical strips and all four boundary types. It reverses a finite commutation--reflection history from a partition sequence whose entries are equal, with the common partition weighted by both boundaries. We derive local reconstruction kernels from the skew Cauchy, Littlewood, and branching identities. Bulk and boundary updates combine integer increments with conditional shape sampling at a prescribed size; same-sign swaps use finite conditional resampling. For $K$ reflection periods and an initial partition-size cutoff $M$, the algorithm terminates almost surely and samples the resulting approximating law exactly. We prove total variation convergence to the target process as $K,M\to\infty$ and give explicit bounds for both truncation errors, decaying geometrically in the cutoffs for fixed input parameters. Under fixed parameter bounds, we also bound the expected operation count of direct enumeration in a unit-cost model. We further construct an exact rejection sampler for the initial partition law without a size cutoff or evaluation of its normalizing constant. Using this sampler removes the size-truncation error, leaving only the error from the finite reflection history.
In the Hunters and Rabbit game, hunters shoot at a set of vertices at each round, while an invisible rabbit must move along an edge. We prove that deciding whether a given number of hunters can guarantee capture is PSPACE-complete, even on simple bipartite graphs. The reduction uses intersection nonemptiness for inverse finite automata: one common word must put all automata in accepting states simultaneously. A clique acting as a safe haven and two families of guards force every winning strategy to simulate common transitions. Existing transformations remove the restriction on the rabbit's initial positions and yield PSPACE-completeness for the directed game with one hunter, even on oriented graphs with positive minimum outdegree. Adjusting the guard sizes also proves PSPACE-completeness of the firefighting game, in which the rabbit may remain at its current vertex.
In a recent breakthrough, Chen, Kyng, Liu, Peng, Probst Gutenberg, and Sachdeva (arXiv:2203.00671) designed the first almost-linear-time algorithm for minimum-cost flow. Their approach uses an Interior Point Method (IPM) to achieve complexity $m^{1+o(1)}\log U \log C$. However, the $m^{1+o(1)}$ factor hides intricate recursive data structures, large constants and multiple log factors. In this paper, we give an implementation following the core ideas of their IPM with practical data structures and empirically obtained decision rules. We compare our solver with the cost scaling and network simplex solvers of LEMON on the instance families of the DIMACS Flow Challenge 2.0 core benchmark. Our implementation scales competitively on five of twelve families and better on two. On grid_wide we observe close to linear scaling: $m^{1.04}$ against $m^{1.48}$ for LEMON. We read these results as first evidence that the almost-linear-time framework can be relevant in practice, discuss our insights gained during the implementation process, and motivate where future work should focus to bridge the theory-practice gap.
I study a dynamic pricing problem in which a seller with limited inventory must sequentially price a perishable product for arriving customers with heterogeneous valuations. The key difficulty lies in balancing immediate sales against future opportunities under capacity constraints and stochastic customer valuations. I propose a simple, interpretable, and asymptotically optimal dynamic pricing algorithm, called Dynamic Run-Out Pricing (DROP), that adjusts prices in real time based on current inventory and anticipated future demand. Under the assumption that customers' valuations follow bounded or exponential distributions, our theoretical results show that DROP's expected revenue converges to the optimal revenue as market size grows. Unlike traditional notions of near-optimality, where the ratio of the algorithm's revenue to the optimal revenue converges to 1, I show that the absolute difference between the two revenues converges to 0 as the market size increases, underscoring the algorithm's effectiveness. Furthermore, I extend our analysis to heavy-tailed valuation distributions, specifically the Pareto distribution, where standard run-out heuristics severely underprice inventory by ignoring the value of waiting for extreme valuations. To correct this, I introduce the Tail-Aware DROP (TA-DROP) heuristic, which intentionally inflates prices to protect inventory, and I prove that it restores asymptotic optimality with a strict polynomial convergence rate.
We study block sensitivity and certificate complexity of rotation symmetric Boolean functions, with particular emphasis on monomial rotation symmetric Boolean functions. We first show that every odd-degree monomial rotation symmetric Boolean function on $n$ variables satisfies $s=bs=C=n$. We then determine sensitivity, block sensitivity, and certificate complexity for every quadratic monomial rotation symmetric Boolean function. For the quadratic function $Q_{n,k}$ generated by $x_0x_k$, we prove, outside the short-orbit case, that \[ C(Q_{n,k})= \begin{cases} n,&4\mid n/\gcd(n,k),\\ n-\gcd(n,k),&4\nmid n/\gcd(n,k). \end{cases} \] Moreover, \(bs(Q_{n,k})=C(Q_{n,k})\) for every quadratic MRS function, and outside the short-orbit case, strict separation \(s<bs=C\) occurs exactly when \[ \frac{n}{\gcd(n,k)}\equiv2\pmod4. \] Finally, for the consecutive quartic family \[ R_n(x)=\bigoplus_{i\in\mathbb Z_n}x_ix_{i+1}x_{i+2}x_{i+3}, \] we determine all three measures in every residue class modulo $6$, using the sensitivity formulas and, in one residue class, finite-state results established in our companion preprint~\cite{LiZhangRSBFSensitivity}. In particular, for $r=2,3$ and $6q+r\ge5$ we obtain strict separation, \[ \boxed{s(R_{6q+r})=6q<bs(R_{6q+r})=C(R_{6q+r})=6q+1,\qquad r=2,3.} \] Thus this family gives an infinite collection of rotation symmetric Boolean functions for which sensitivity is strictly smaller than block sensitivity, while block sensitivity and certificate complexity coincide.
Rotation symmetric Boolean functions are Boolean functions invariant under cyclic permutation of their variables and can be represented by binary necklaces. We express local sensitivity as a weighted bichromatic degree in the necklace quotient and derive an exact formula for the multiplicities between neighboring necklaces. For an odd prime number of variables, we obtain explicit sensitivity formulas and show that multiplicity corrections occur only on an asymptotically negligible family of necklaces. For monomial rotation symmetric Boolean functions, we prove that every odd-degree function has maximum sensitivity, determine the sensitivity of every quadratic function, and determine the sensitivity of the consecutive quartic family. We also determine exactly the sensitivity of cyclic run-threshold functions for arbitrary length and threshold.
We study the number of improving steps that local search may require for $(2,2,r)$-MCA (Maximum Constraint Assignment), a bounded-occurrence version of MAX-CSP with valued constraints in which every constraint involves at most two variables, every variable occurs in at most two constraints, and every variable takes one of $r$ values. We consider the flip neighborhood, where two assignments are neighbors if they differ in the value of exactly one variable; moving to such a neighbor is called a flip. Local search repeatedly performs improving flips, that is, flips that strictly increase the objective value, until a local optimum is reached. Our main result is that $(2,2,5)$-MCA has the all-exp property: there is an infinite family of instances with initial assignments for which every sequence of improving flips ending in a local optimum has length exponential in the number of variables. Thus, on these instances, local search requires exponentially many steps regardless of which improving flip is chosen at each step. This is the first all-exp result for $(2,2,r)$-MCA for any value of $r$, and our result extends to every $r\ge 5$. In contrast, for $(2,2,2)$-MCA every sequence of improving flips has length at most quadratic in the number of variables~\cite{Kaz2020,KCJ2020}. We give a short, direct proof of this result.
Conway's $99$-graph is a strongly regular graph with parameters $(v,k,λ,μ) = (99,14,1,2)$ and whose existence has long been an open problem. We use both a sum-of-squares program and the fact that a strongly regular graph with $λ= 1, μ= 2$ has no diamond or $K_{2,3}$ subgraph to derive a loose upper bound for the number of triangles that such a graph could contain. This bound is less than the number of triangles that the graph's spectrum asserts, implying that it does not exist.
A graph is \emph{elementary} if its edges can be coloured with two colours so that the two edges of every induced path on three vertices receive different colours. Elementary graphs are one of the two basic classes in the Chvátal--Sbihi decomposition of claw-free perfect graphs; they include all line graphs of bipartite multigraphs and all complements of bipartite graphs. We prove that every elementary graph $G$ satisfies $\ch(G)=χ(G)=ω(G)$, confirming for this class the conjecture of Gravier and Maffray that claw-free graphs are chromatic-choosable. The proof combines the Maffray--Reed description of elementary graphs as augmentations of line graphs of bipartite multigraphs, Galvin's theorem, an extremal (edge-maximal) choice of counterexample, and a Hall-type lemma describing how list colourings of a complete graph minus a matching can fail.
A hereditary graph class has strongly edge-sublinear separators if, for some constant $0 \leqslant b < 1$, every graph in the class with $m$ edges admits a balanced separator of size $\mathcal O(m^b)$. We show that Max Weight Independent Set (MWIS) admits a deterministic quasipolynomial-time approximation scheme (QPTAS) on every such class. In particular, this applies to graphs excluding any fixed graph as an induced minor, by a separator theorem of Korhonen and Lokshtanov [SODA 2024]. Our theorem generalizes the QPTASes for axis-parallel rectangles [Adamaszek and Wiese, FOCS 2013] and polygons [Adamaszek, Har-Peled, and Wiese, JACM 2019], or equivalently for packing connected subgraphs of a planar graph [Pilipczuk, van Leeuwen, and Wiese, Algorithmica 2020]. It also generalizes the QPTAS for MWIS on hereditary classes with strongly sublinear separators measured in vertices [Dvořák, EJC 2018; Dvořák and Lahiri, ESA 2021], as well as the QPTASes for graphs excluding particular induced minors [Chudnovsky et al., arXiv 2025; Bonnet et al., SWAT 2026; Czyżewska et al., arXiv 2026].
The extension complexity $\operatorname{xc}(P)$ of a polytope $P$ is the minimum number of facets of a polytope that projects onto it. Motivated by the complexity of neural networks, Hertrich and Loho introduced the virtual extension complexity $\operatorname{vxc}(P)$ of a polytope $P$, which is the minimum of $\operatorname{xc}(Q) + \operatorname{xc}(R)$ among all polytopes $Q$ and $R$ such that $P+Q=R$. We show the following results pertaining to virtual extension complexity. First, we resolve the core open problem on the topic by showing the virtual extension complexity can be exponentially smaller than extension complexity. Second, we show there are matroid base polytopes with exponential virtual extension complexity by adapting a semi-algebraic counting argument by Hrubeš that extends the counting arguments of Rothvoss. Finally, we show that the maximum virtual extension complexity of a polygon with $n$ vertices is $Θ(\sqrt{n})$. This resolves an analogue of a question on extension complexity of Fiorini, Rothvoss, and Tiwary in 2011 in the case of virtual extension complexity.
Distributed Constraint Satisfaction Problems (DCSPs) model distributed decision-making in multi-agent systems, where agents assign values to local variables while satisfying shared constraints. However, many DCSP solvers still rely on broad, repeated peer-to-peer communication and are largely reactive, with limited support for strategic coordination or learning. This increases communication overhead, can lead to stagnation, and reduces the success of hard instances. Hence, we propose Dynamic Conflict Clustering-Incomplete (DCC-Incomplete), a repair-based solver that combines conflict-centred decomposition, structured coordination, strategic repair, and lightweight learning for stagnation recovery. DCC-Incomplete groups the unsolved part of the problem into conflict clusters and restricts communication via a coordination layer to agents within the same conflict region. It also introduces memory-guided restart, enabling agents and clusters to pause, revise, and adapt repairs based on neighbouring conflict states. A thorough evaluation of DCC-Incomplete on distributed graph-colouring benchmarks with planted satisfying assignments shows that its memory-guided restart improves the success rate from 37.50% to 61.11%, reduces median runtime from 0.565s to 0.367s, and cuts median communication from 12.493 to 6.503 messages per constraint. These results suggest that dynamic conflict clustering, combined with lightweight strategic and learning-guided repair, improves both communication efficiency and robustness in incomplete DCSP solving.
Codes in the Levenshtein metric that can correct multiple edits (including deletions, insertions, and substitutions) have attracted a lot of attention recently owing to their application in DNA-based storage and racetrack memories. In this work, we present new techniques for designing explicit binary codes of length $n$ that correct $t$ edits with at most $(2t+1)\log n+O_t(\log\log n)$ bits of redundancy. We first propose to use a polynomial hash to construct a systematic code that corrects $t$ edits with $(4t+2)\log n+O_t(\log\log n)$ bits of redundancy. Then we observe that there are many polynomial hashes like this, some are good, some are bad. So, we propose the second technique, called entropy recycling, to use the indices of good hashes to carry information. As a consequence, we obtain a partial-systematic code of length $n$ that corrects $t$ edits with at most $(2t+1)\log n+O_t(\log\log n)$ bits of redundancy. Finally, we provide deterministic polynomial-time encoding and decoding algorithms for our code.
Can quantum communication determine the size of an anonymous network when no size bound is known? Classical impossibility proofs rely on the covering lemma: an execution can be reproduced on a larger network with the same local structure. Quantum interference invalidates this argument - a measurement record possible on a network can become impossible on a cover. We show that the impossibility of exact counting nevertheless survives. Our main result is a quantum analogue of the covering lemma that preserves local possibilities rather than complete executions. Within a cyclic covering family, every local measurement outcome possible at a node remains possible at a corresponding node in every sufficiently large network. This holds even after information has travelled around the smaller network, beyond the reach of a simple locality argument. We extend the principle to the universal covering tree and finite covers with sufficiently long cycles. The proof combines tensor-network methods with graph coverings: a common representation across network sizes turns normalization into a constraint on which local outcomes can occur. For uniform synchronous protocols with independently prepared nodes, this support-lifting principle rules out zero-error counting and even the production of a guaranteed finite size bound on anonymous rings and the other cyclic covering families considered here. It also rules out exact leader election with termination in finite time with probability one on these families. Measurements, classical control, and local memory growing with time are allowed; no predetermined running-time bound is assumed. Quantum interference thus defeats execution lifting without enabling infallible certification of network size.
FirstFit colors each arriving vertex with the smallest positive integer absent from its previously colored neighborhood. We prove that this rule can require $n^{Ω(1)}$ many colors on certain bipartite graph of $n$ vertices even when the vertices arrive in a uniformly random order. This refutes the conjecture of Bosek, Gutowski, Lasoń, and Przybyło [BGLP24] that FirstFit uses a polylogarithmic expected number of colors on every bipartite graph in the random order model. We obtain the lower bound by analyzing the FirstFit coloring process on random bipartite graphs, where vertices arrive to either side with equal probability, and with an independent edge density $n^{-x}$ for some $0 < x < 1$. Our result can also be viewed as a qualitative strengthening of Kučera [Kuč91], who showed that, for every $ε> 0$, there are graphs with chromatic number at most $n^ε$ on which FirstFit uses $Ω(n/\log n)$ colors in expectation under a uniformly random order. Our result shows that such poor behavior of FirstFit already occurs for $χ(G) = 2$.
We study a natural greedy algorithm for the Airplane Refueling Problem (ARP), based on a well-known priority rule. We show that this algorithm achieves an approximation guarantee of $9/20$, noticeably improving the previously known $1/12$ guarantee for a fast algorithm. We also show that the same priority rule can be implemented in $O(n\log n)$ time and $O(n)$ space using a dynamic convex-hull data structure. These results provide a worst-case approximation guarantee for an existing greedy priority rule and establish an efficient implementation. In the real-RAM model, the running-time bound is independent of the magnitude of the processing times. The resulting method is also suitable as a fast primal routine inside more complex exact and approximation algorithms for large instances. These results narrow the gap between theoretically strong but complex approximation schemes and lightweight algorithms that can be used directly in computational pipelines. The algorithm combines a simple selection rule with a provable performance bound, making it a useful baseline for further algorithmic studies of ARP.
The Game of Cycles, invented by Francis Su, is a two-player game in which the players take turns drawing arrows on the edges of a plane graph, never creating a sink or a source. On a tree only the sink-source rule matters, and the player who makes the last move wins. Several authors conjectured that on a tree the second player wins exactly when the number of markable edges is even. We show that this parity conjecture is false, and we explain why. The explanation is a hidden game of Nim: a path segment that is blocked by an arrow at one end and free at the other behaves exactly like a nim heap whose size is its length. Combined with a calculus for cutting and gluing trees at vertices next to leaves, this shows that the conjecture fails as soon as a single tree has Grundy value at least 2. The smallest counterexamples have 15 vertices. Trees with Grundy values 2 and 4 first appear at 17 vertices, and every value up to 63 occurs, which answers a question of Fokkink and Zandee. We also refute a related conjecture of Zandee. We then look closely at spiders. The spiders S(2,3,z) violate the conjecture for every z >= 14. The Grundy values of S(1,2j,z) are given by an exact formula governed by binary carries. For 99 pairs (x,y), the value of S(x,y,z) is eventually the parity of z. On the positive side, the conjecture holds for all trees in which every thread has at most two edges, and this bound is sharp. Along the way we prove a twin-branch reduction, give an algorithm that is polynomial for spiders with a fixed number of legs, and collect the questions that we could not answer. The boldest asks whether every non-negative integer is the Grundy value of some tree.
Let $D$ be a finite simple minimally strongly $k$-connected digraph, where $k\ge 2$, and let $n=|V(D)|$. Mader proved in 1985 that $|A(D)|\le 2k(n-k)$ for all sufficiently large $n$, with equality if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$ (JCTB 1985). We prove that this bound holds whenever $n\ge 3k-1$ and that the order threshold $3k-1$ is best possible. Moreover, if $n\ge 3k$, then equality holds if and only if $D\cong \overleftrightarrow{K}_{k,n-k}$. The threshold $3k$ is also best possible. These results resolve the conjecture of Mader in (JCTB 1985).