ALT A path or cycle in a 2-edge-coloured graph is alternating if consecutive edges have different colours. These objects are natural analogues of paths and cycles in graphs, and even more so in digraphs. A well-studied class is that of acyclic 2-edge-coloured graphs, that is, those forbidding alternating cycles. In particular, (acyclic) 2-edge-coloured graphs generalize directed (acyclic) graphs (DAGs), but the complexity of problems on DAGs is much better understood than that of the corresponding problems on acyclic 2-edge-coloured graphs. We investigate the complexity of two such problems, whose directed counterparts are well-known. Our first result is an nᴼ⁽ᵏ⁾-time algorithm for the alternating k-linkage problem on acyclic 2-edge-coloured graphs. This problem asks for k vertex-disjoint alternating paths joining k prescribed pairs of vertices. This generalizes the directed k-linkage algorithm for DAGs. For every fixed k, this also yields a polynomial-time algorithm for finding k internal

ALT We study the fundamental problem of PAC learning positive linear combinations of k arbitrary ReLU activations on ℝᵈ with respect to the Gaussian distribution, in L₂ loss. We give the first fully-polynomial time algorithm for this learning task. Specifically, our algorithm draws poly(d, k, 1/∊) samples, runs in poly(d, k, 1/∊) time, and outputs a hypothesis that is ∊-close to the target concept with high probability. All prior algorithms for this problem require super-polynomial time in k or 1/∊, or leverage strong well-conditioned assumptions on the weight matrix. On a technical level, our approach develops a novel boosting procedure of a “weak” learner that recovers the hidden weight vectors to constant error, in a list-decodable manner. To develop this “weak” learning procedure, we leverage implicit tensor computation techniques to construct a low-degree filtering procedure based on Hermite tensors of the target function. This procedure amplifies separation among (clusters of) weight

ALT Boolean matrix multiplication is a fundamental operation in many graph-based applications, including web and social network analysis, information retrieval, and graph query evaluation. However, conventional sparse representations such as CSR}/CSC still incur significant space and time costs on large graphs. In this work, we introduce a method for multiplying Boolean matrices based on a biclique-based compressed representation that decomposes them into dense bipartite subgraphs, thereby capturing large sets of implicit edges. We first improve the iterative biclique extraction algorithm of Hern\'andez and Navarro by introducing percentile-based parameter adaptation that dynamically adjusts its parameters according to the degree distribution, enhancing both extraction efficiency and compression ratio. We then extend the Schoor multiplication algorithm to operate directly on biclique-encoded matrices, thereby enabling a compositional form of multiplication where the output can also be repr

ALT We study the structure and exact certification of nonnegative tensor decompositions supplied through rational factor matrices. Every failure of minimality or essential uniqueness contains an irreducible positive exchange between p supplied terms and q competing terms. A dimension count based on the Lovitz–Petrov splitting theorem bounds the effective order of such an exchange, the sum over the modes of the joint factor-span dimension minus one, by p+q-2, and this bound is attained at every supplied length R≥2. After eliminating ambient-row variables by the Farkas lemma, the resulting semialgebraic systems have fewer than 2R² real variables. For input bit length L, this gives a deterministic G(R)Lᴼ⁽ᴿ²)-time algorithm that computes the nonnegative rank and an exact minimum-length decomposition, decides minimality and essential uniqueness, and returns exact witnesses when either property fails. The exponent is independent of the tensor order and the mode dimensions. For Lebesgue moment te

ALT The selection problem asks to find the k-th smallest element in a given set X. Its complexity is well-known to be Θ(|X|) for every fixed k. We consider the poset selection problem where a partial order P on X is given, and the underlying order of X is guaranteed to be a linear extension of P. This generalizes several variants of the selection problem studied before. Our main result is an algorithm that performs O( k + OPT(P,k) ) comparisons, where OPT(P,k) is the minimum number of comparisons required for the input (P,k). If P is a rooted tree, we obtain an O( OPT log (k / OPT) ) algorithm, which can be further improved to O( OPT log log (k/OPT) ) or O( OPT log OPT) under mild assumptions about P. Our algorithms are based on the work of Kaplan, Kozma, Zamir, and Zwick [SOSA 2019], who used Chazelle's soft heaps [J. ACM 2000] to simplify several older results. We introduce a new soft heap variant, the weighted soft heap, which allows greater control over which elements get corrupted.

ALT We consider the problem of maintaining the triconnectivity in some biconnected graph G in the incremental dynamic setting. We consider updates in the form of edge insertions and edge subdivisions, and triconnectivity queries, i.e. queries of the form "are there at least three vertex disjoint paths between a and b?". All algorithms presented in this paper are deterministic. All queries and updates are answered in worst-case O(log n) time. By combining this result for biconnected graphs with a result of Holm and Rotenberg [SODA'20] we get an algorithm for general graphs with a worst-case running time of O(log² n) per operation. These algorithms represent an improvement of the state-of-the-art by a factor of O(log n).

ALT We establish an Ω(d) lower bound on the competitive ratio of convex body chasing in ℝᵈ with ℓₚ movement costs for any p ∈ [1, ∞). Previously, the best known lower bound for general p was Ω(max{√d, d¹⁻¹/ᵖ}), established by Bubeck et al. (2019); a linear lower bound was known only for p = ∞, realized by the standard construction of chasing faces of a hypercube. Our lower bound strictly improves on the prior bound for every fixed p ∈ [1, ∞) and shows that the functional Steiner point algorithm of Sellke (2023) - which has competitive ratio O(d) - is asymptotically optimal for every ℓₚ norm. Our lower bound is based on the recursive construction of Bubeck, Coester, and Rabani (2023) for metrical service systems, which gives a lower bound of Ω(r²) for requests of size O(r) in that setting. We show that requests in their construction, each comprising a set of discrete points in a graph metric, can be mapped to the vertices of convex requests in a (2r+1)-dimensional vector space while approxi

ALT We give a combinatorial algorithm that computes an exact minimum-cost flow in n²⁺ᵒ⁽¹⁾ time. This is the first combinatorial improvement since Goldberg-Tarjan [GT87], and is almost optimal in dense graphs. All previous faster algorithms, including the almost-linear-time algorithm of Chen et al. [CKL+22], rely on interior-point methods. Our main conceptual contribution is a black-box reduction from exact minimum-cost flow on general graphs to its approximation on DAGs, with only an nᵒ⁽¹⁾ loss on the running time. This reduction allows future work on combinatorial minimum-cost flow to focus on DAGs, typically much easier to handle than general graphs. Our n²⁺ᵒ⁽¹⁾-time algorithm follows by combining this reduction with a simple augmenting-path-based approximation algorithm on DAGs. The reduction is based on a new structural result, called a flow-cost-preserving DAG projection. Given an arbitrary directed graph, this construction produces a DAG that approximately preserves both the congesti

ALT The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope. In the nonclairvoyant online setting, Proportional Fairness (PF), a practical allocation rule rooted in market theory, is the leading general-purpose algorithm. On a single machine, PF coincides with weighted Round-Robin, which is 2-competitive for weighted completion time with uniform release dates (optimal for nonclairvoyant algorithms) and (2+ε)-speed O(1/ε)-competitive for weighted flow time. Known guarantees beyond a single machine are weaker. This raises a central question: Are these heterogeneous environments intrinsically harder than a single machine under nonclairvoyance? We show that they are not: PF retains both single-machine guarantees on the novel class of support-submodular polytopes, which includes unrelated machines and polymatroids. On unrelated machines, this refutes a belief (JACM'18, SODA'25) that PF is not

ALT We study preemptive single-machine scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is c-consistent if it is c-competitive when the prediction is correct, and R-robust if it is R-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every R>2, we give an R-robust algorithm whose consistency is c(R)=R(1-(1-ᴿ⁺²⁄R^₂)^{fracRR+2}), and we prove that no deterministic R-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency 1+\eps is achievable with robustness \eps^-1/2+¹⁄₆+O(√\eps), whereas all previous algorithms required robustness Θ(1/\eps). Our algorithm is greedy: it follo

ALT The asymptotic competitive ratio of online bin packing has been bracketed since 2018 by the lower bound 1.54278 of Balogh, Bekesi, Dosa, Epstein and Levin and the upper bound 1.57829 of their Advanced Harmonic algorithm. We revisit both sides with exact rational computation and prove what the computations say. On the upper bound, we rebuild the certification of Advanced Harmonic as an exact optimization over its dual parameters; with the published parameters this already certifies a ratio strictly below the published one, and re-tuning the algorithm's proportion parameters gives a certified ratio of 1.5782147437 (an exact rational), independently re-verified on all 402 scenarios. To our knowledge this is the first movement of the upper bound since 2018. On the lower bound, we prove that the 2018 adversary construction is rigid: extending it by any finite number of new batches of ordinary size (outside the window of sizes s with 2s > 1 and rational part at most 0.64819), placed anywhere

ALT The Smallest Grammar Problem (SGP) asks for a smallest straight-line grammar generating a given string, where size is the total length of the right-hand sides. Rules may be nested, so locally optimal choices of repeated fragments need not combine into an optimal grammar. We show that in an optimal grammar one can choose an occurrence of the expansion of each auxiliary nonterminal such that these intervals are pairwise disjoint. Hence the dictionary can be read off from a partition of the input, decoupling the choice of the dictionary from the parsing of rules. Using this property together with a bound on references to rules of length two, we obtain an exact algorithm running in O¹.⁸⁷²³^ⁿ time and O(n) words of space, improving the O³^ⁿ bound of Casel et al. for general grammars. For alphabet size σ and R=logσ n, we give a 2^O((n/R)log(R+1))-time algorithm, which is subexponential for fixed alphabets. Conversely, using an anchor-based projection from encoded grammars back to source gram

ALT Smith's rule orders jobs by their weight-to-processing-time ratios. We study the robustness of its list schedule on identical parallel machines when job j is ordered using a nominal processing time μⱼ and its true processing time satisfies μⱼ≤ pⱼ≤αμⱼ, where α≥1. We determine the exact worst-case approximation ratio against the clairvoyant optimum, taking the supremum over machine counts. The ratio is an explicit continuous piecewise-algebraic function of α. It equals the Kawaguchi–Kyan constant (1+√2)/2 at α=1 and is exactly √(α) for α≥4. On one machine the exact ratio is √(α). For every fixed machine count, no deterministic nonpreemptive algorithm can improve on this guarantee, even with knowledge of α. The proof reduces to a common nominal Smith ratio and endpoint errors. Cutting the list schedule at its minimum final machine load yields a prefix–suffix certificate; two packings of matching lower-bound instances explain the branches below α=4. We also prove a nominal-to-robust transf

ALT Since the early days of fine-grained complexity, many geometric problems have been shown to require quadratic time under the 3SUM Hypothesis. But as the 3SUM Hypothesis was recently refuted, these lower bounds have lost their foundation. In this note we point out that many of them can be recovered under an alternative hardness assumption, the k-AP Hypothesis. The required changes to the proofs are trivial, so the lower bounds remain just as easy to teach.