Thank you to arXiv for use of its open access interoperability.
Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.
We present a top-down depth-four circuit lower bound for Majority function by extending recent work of Göös, Riazanov, Sofronova, and Sokolov (FOCS 2023), who gave a top-down proof of a depth-four circuit lower bound for Parity which relies on the robust sunflower to construct a mirror set and the block unpredictability to find the local limits. The main challenge for the case of Majority is to construct a corresponding mirror set, the difference is that to flip the value of Majority function, one may have to flip many bits of the input Boolean string, while for Parity, flipping one bit suffices. We avoid this flipping by considering slices of the Boolean cube, that is, Boolean strings of fixed Hamming weight approximately $n/2$.
We present a top-down depth-four circuit lower bound for Majority function by extending recent work of Göös, Riazanov, Sofronova, and Sokolov (FOCS 2023), who gave a top-down proof of a depth-four circuit lower bound for Parity which relies on the robust sunflower to construct a mirror set and the block unpredictability to find the local limits. The main challenge for the case of Majority is to construct a corresponding mirror set, the difference is that to flip the value of Majority function, one may have to flip many bits of the input Boolean string, while for Parity, flipping one bit suffices. We avoid this flipping by considering slices of the Boolean cube, that is, Boolean strings of fixed Hamming weight approximately $n/2$.
We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.
We prove a sharp lower bound for smooth nonconvex stochastic optimization with uniformly bounded gradient noise. In the \(K=1\) fresh-sample model, every randomized adaptive algorithm requires $$Ω\left( \frac{ΔL}{ε^2} + \frac{ΔLσ^2}{ε^4} \right)$$ queries to find a point with expected gradient norm at most \(ε\). This matches the standard upper bound and, to the best of our knowledge, resolves the question raised by [Arjevani et al. 2023] of whether almost-surely bounded oracle error permits a better rate than bounded variance. The proof was independently generated with GPT-5.6 Sol in Codex's Ultra mode during a two-hour session. The human author supplied the prompt and was responsible only forchecking the proof and revising and polishing the manuscript.
A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information.
To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions.
We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.
A Proof of Space, PoS, as introduced by Dziembowski et al. [CRYPTO'15], is a two-phase protocol that enables a Prover to convince an efficient Verifier that it has allocated a large amount of persistent memory to storing some information.
To our knowledge, all existing PoS protocols are only known to be secure in the random oracle model (or under ad hoc assumptions about cryptographic assumptions). We provide an elementary framework for constructing PoS from a combination of derandomization assumptions and cryptographic assumptions.
We provide a few simple instantiations of the framework. We show that non-trivial PoS follow from (a) $\mathsf{E}=\mathsf{DTIME[2^{O(n)}]}$ is hard for exponential-size nondeterministic circuits (an assumption introduced to show $\mathsf{AM}=\mathsf{NP}$), and (b) collision-resistant hash functions. We also show that PoS with nearly optimal parameters and interaction pattern follows from assumption (a) above and (c) SNARGs for $\mathsf{P}$.
Authors: Michal Garl\'\ik, Svyatoslav Gryaznov, Hanlin Ren, Iddo Tzameret
Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, the *weak rank principle* (WRank) states the equation $XY = A$ is unsatisfiable when $m>n$ and rank of $A$ exceeds $n$. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP). As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, while still supporting analogous applications.
*Generators for PCR$_{F_2}$*: We prove exponential size lower bounds for algebraic, perfect matching, and bamboo-tree encodings of WRank in PCR$_{F_2}$. The latter encoding is the most relevant for applications to circuit lower-bound formulas, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Using a standard iteration technique we amplify the stretch to exponential. This resolves the open problem concerning the construction of proof complexity generators with good stretch for PCR$_{F_2}$.
*Generators for Sherali--Adams:* We develop a new size lower-bound technique showing that WRank, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a pseudoexpectation tailored specifically to the rank principle (and incompatible with WPHP).
*Circuit lower bound formulas:* We show that PCR$_{F_2}$ does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits. This settles the open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCR$_{F_2}$.
*Strength of the weak rank principle:* Finally, we show that WRank is *necessary* for proving NC$^2$ circuit lower bounds and, for odd primes $p$, *sufficient* within the theory corresponding to AC$^{0}[p]$ for deriving AC$^{0}[p]$ lower bounds.
Given two symbolic matrices $X$ and $Y$ of dimensions $m\times n$ and $n\times m$, the *weak rank principle* (WRank) states the equation $XY = A$ is unsatisfiable when $m>n$ and rank of $A$ exceeds $n$. We study this principle as an algebraic generalisation of the weak pigeonhole principle (WPHP). As a strengthening of WPHP, it admits proof complexity lower bounds in settings where none are known for WPHP, while still supporting analogous applications.
*Generators for PCR$_{F_2}$*: We prove exponential size lower bounds for algebraic, perfect matching, and bamboo-tree encodings of WRank in PCR$_{F_2}$. The latter encoding is the most relevant for applications to circuit lower-bound formulas, as considered by Alekhnovich, Ben-Sasson, Razborov, and Wigderson (SIAM J. Comput., 2004) and Razborov (Ann. Math., 2015). Using a standard iteration technique we amplify the stretch to exponential. This resolves the open problem concerning the construction of proof complexity generators with good stretch for PCR$_{F_2}$.
*Generators for Sherali--Adams:* We develop a new size lower-bound technique showing that WRank, encoded as a bamboo-tree CNF, serves as a proof complexity generator for SA. Our method introduces a pseudoexpectation tailored specifically to the rank principle (and incompatible with WPHP).
*Circuit lower bound formulas:* We show that PCR$_{F_2}$ does not admit short proofs of lower-bound statements against Boolean circuits, nor against weak models of algebraic circuits. This settles the open problem raised by Razborov (Ann. Math., 2015) concerning the provability of such lower bounds in PCR$_{F_2}$.
*Strength of the weak rank principle:* Finally, we show that WRank is *necessary* for proving NC$^2$ circuit lower bounds and, for odd primes $p$, *sufficient* within the theory corresponding to AC$^{0}[p]$ for deriving AC$^{0}[p]$ lower bounds.
We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform AC$^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and every sufficiently large fixed $k$, we obtain unconditional bounds $n^{Ω(k)}$ for $k$-OV and $(n/k)^{Ω(k)}$ for $k$-XOR and $k$-SUM, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, the unconditional floor $n^{Ω_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{Ω(k)}$ at depth two for both top-gate orientations, i.e., top conjunction and top disjunction. Assuming a pattern-uniform strengthening of the Li--Razborov--Rossman source lower bound, the same projections complete the subpolynomial frontier with $n^{Ω_d(k)}$ at depth three for both orientations and for every fixed depth $d \geq 4$. All direct $k$-XOR bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-SUM projection works for both parities. At the bit width $m = Θ(k\log(en/k))$ used by our projection, a block-carry $Σ_3$ upper bound of size $(n/k)^{O(k)}$ matches the fixed-$k$ specialization of the top-disjunction depth-three lower bound $(n/k)^{Ω(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.
We prove lower bounds for $k$-OV, $k$-XOR, and $k$-SUM in nonuniform AC$^0$, tracking how the circuit-size exponent scales with $k$ and using no running-time hypothesis. Our framework gives depth-zero projections from colored subgraph isomorphism to the three targets at dimension, row count, or bit width $O(k\log n)$, without increasing depth or size, and preserving gate orientation. For every fixed depth and every sufficiently large fixed $k$, we obtain unconditional bounds $n^{Ω(k)}$ for $k$-OV and $(n/k)^{Ω(k)}$ for $k$-XOR and $k$-SUM, with an absolute exponent-rate constant independent of both $k$ and the depth, while the onset threshold may depend on $(d,k)$. For growing $k = n^{o(1)}$, we obtain, for every fixed depth $d$, the unconditional floor $n^{Ω_d(\min\{\sqrt{k},\log n\})}$. This strengthens to $n^{Ω(k)}$ at depth two for both top-gate orientations, i.e., top conjunction and top disjunction. Assuming a pattern-uniform strengthening of the Li--Razborov--Rossman source lower bound, the same projections complete the subpolynomial frontier with $n^{Ω_d(k)}$ at depth three for both orientations and for every fixed depth $d \geq 4$. All direct $k$-XOR bounds stated above concern odd $k$; a black-box odd-to-even lift transfers any such lower bound through a supplied admissible parameter decomposition. The $k$-SUM projection works for both parities. At the bit width $m = Θ(k\log(en/k))$ used by our projection, a block-carry $Σ_3$ upper bound of size $(n/k)^{O(k)}$ matches the fixed-$k$ specialization of the top-disjunction depth-three lower bound $(n/k)^{Ω(k)}$ up to constants in the exponent. The remaining upper-versus-lower-bound gaps concern depth two, top-conjunction depth three, and other width regimes.
We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013).
In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[
\mathsf{NEXP}
= \mathsf{QMA}^{+}(2,c,s)
=
\mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[
\mathsf{QMA}^{\mathbb R}(2)
=
\mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \]
Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.
We study gap amplification of the class $\mathsf{QMA}^{+}(2)$ characterized by unentangled quantum proofs whose amplitudes are nonnegative in the computational basis. This class was recently introduced by Jeronimo and Wu (STOC 2023), and its behavior depends sharply on the completeness-soundness gap: although it captures the power of $\mathsf{NEXP}$ for some small constant gap, it is equal to $\mathsf{QMA}(2)$ for larger constant gap. This is in stark contrast to $\mathsf{QMA}(2)$ where strong gap amplification is known due to the product test by Harrow and Montanaro (FOCS 2010, JACM 2013).
In this paper, we prove for every completeness $c$ and soundness $s$ with $c-s=1/\mathrm{poly}(n)$, \[
\mathsf{NEXP}
= \mathsf{QMA}^{+}(2,c,s)
=
\mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14+\frac1{\mathrm{poly}(n)}\right). \] Our result gives a clean complexity phase transition for $\mathsf{QMA}^{+}(2)$ since we have \[
\mathsf{QMA}^{\mathbb R}(2)
=
\mathsf{QMA}^{+}\left(2,1-\frac1{\mathrm{poly}(n)},\frac14-\frac1{\mathrm{poly}(n)}\right), \] where $\mathsf{QMA}^{\mathbb R}(2)$ denotes $\mathsf{QMA}(2)$ with witnesses restricted to real amplitudes. Our amplification is thus optimal in the sense that a slight improvement of our soundness would have the collapse \[ \mathsf{QMA}^{\mathbb R}(2)=\mathsf{NEXP}. \]
Our proof combines symmetric-subspace projections with the relation $\mathsf{QMA}^{+}(1)=\mathsf{NEXP}$ of Bassirian, Fefferman, and Marwaha (ITCS 2024). The main technical ingredient is a dimension-independent de Finetti theorem in Hilbert-Schmidt norm that applies when the number of registers under consideration grows logarithmically.
Authors: Arkopal Dutt, Dale Jacobs, John Jeang, Saeed Mehraban, Vladimir Podolskii
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning $n$-qubit quantum unitaries $U$ and Hamiltonians $H$, given query access to $U$ or the unitary evolution of $H$, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form $U = \sum_i α_i C_i$ over Cliffords $C_i$ with bounded Clifford extent $\sum_i |α_i|$. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary $U$ with optimal Clifford fidelity $\textsf{opt}$, outputs a Clifford unitary witnessing fidelity $\geq \textsf{opt} - \varepsilon$ for some error $\varepsilon > 0$, in time $\textsf{poly}(n,(1/\varepsilon)^{\log(1/\varepsilon)})$. We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity $Ω(2^n)$) in the Pauli basis but are Clifford structured.
Vehicle platooning offers significant benefits, including reduced energy consumption, lower emissions, improved road utilization, enhanced safety, and reduced driver fatigue. As intelligent driving technologies continue to advance, platoon sizes are expected to increase substantially, making the efficient sequencing and resequencing of vehicles increasingly important. We study the vehicle platoon sequencing and resequencing problem on road networks with varying segment lengths under two fundamental objectives: minimizing total energy consumption and minimizing the maximum energy consumption of any vehicle. For the typically encountered combinations of vehicle and road characteristics, we provide a complete computational complexity classification, either developing polynomial-time algorithms or proving computational intractability. For several intractable cases, we design fully polynomial-time approximation schemes and polynomial-time heuristics with provable performance guarantees. A computational study demonstrates that the proposed heuristics achieve average solutions within 1\% of optimal. We also consider settings in which only limited information about position-dependent energy savings is available and develop a heuristic with bounded worst-case performance. In addition, we present an efficient algorithm for on-road vehicle resequencing when only limited position changes are permitted. Together, these results provide a comprehensive algorithmic framework for energy-efficient vehicle platoon sequencing and resequencing.
Vehicle platooning offers significant benefits, including reduced energy consumption, lower emissions, improved road utilization, enhanced safety, and reduced driver fatigue. As intelligent driving technologies continue to advance, platoon sizes are expected to increase substantially, making the efficient sequencing and resequencing of vehicles increasingly important. We study the vehicle platoon sequencing and resequencing problem on road networks with varying segment lengths under two fundamental objectives: minimizing total energy consumption and minimizing the maximum energy consumption of any vehicle. For the typically encountered combinations of vehicle and road characteristics, we provide a complete computational complexity classification, either developing polynomial-time algorithms or proving computational intractability. For several intractable cases, we design fully polynomial-time approximation schemes and polynomial-time heuristics with provable performance guarantees. A computational study demonstrates that the proposed heuristics achieve average solutions within 1\% of optimal. We also consider settings in which only limited information about position-dependent energy savings is available and develop a heuristic with bounded worst-case performance. In addition, we present an efficient algorithm for on-road vehicle resequencing when only limited position changes are permitted. Together, these results provide a comprehensive algorithmic framework for energy-efficient vehicle platoon sequencing and resequencing.
Given a polygonal domain $\cal P$ consisting $h$ pairwise disjoint convex polygonal obstacles together defined with $n$ vertices and a positive real number $ε$ in $(0, 0.6)$, this paper presents an algorithm to preprocess $\cal P$ in $O(n+\frac{h}ε(h+\frac{1}{\sqrtε})\lg(\frac{h}{\sqrtε}))$ time to compute data structures of size $O(n+\frac{h}{\sqrtε} (h+\frac{1}ε))$ so that given any two points $s$ and $t$ in the free space defined by $\cal P$, a path between $s$ and $t$ with a $(1+ε)$ multiplicative stretch and $13\ell$ additive stretch is output in $O(\frac{1}{\sqrtε}(\lg{\frac{h}{\sqrtε}})+\frac{h}{ε^{2.5}}(\lg{\lg(\frac{h}{\sqrtε})}))$ time. Here, $\ell$ is upper bounded by $(\sqrt{2ε}) (\max_{P_i \in \cal P} \max_{p, q \in P_i} |pq|)$.
Given a polygonal domain $\cal P$ consisting $h$ pairwise disjoint convex polygonal obstacles together defined with $n$ vertices and a positive real number $ε$ in $(0, 0.6)$, this paper presents an algorithm to preprocess $\cal P$ in $O(n+\frac{h}ε(h+\frac{1}{\sqrtε})\lg(\frac{h}{\sqrtε}))$ time to compute data structures of size $O(n+\frac{h}{\sqrtε} (h+\frac{1}ε))$ so that given any two points $s$ and $t$ in the free space defined by $\cal P$, a path between $s$ and $t$ with a $(1+ε)$ multiplicative stretch and $13\ell$ additive stretch is output in $O(\frac{1}{\sqrtε}(\lg{\frac{h}{\sqrtε}})+\frac{h}{ε^{2.5}}(\lg{\lg(\frac{h}{\sqrtε})}))$ time. Here, $\ell$ is upper bounded by $(\sqrt{2ε}) (\max_{P_i \in \cal P} \max_{p, q \in P_i} |pq|)$.
A metric graph is a metric space obtained from a finite collection of intervals whose endpoints are identified in groups. It can also be seen as a finite, edge-weighted graph where the continuum of points along the interior of each edge is taken into consideration, and each edge is locally isometric to an interval whose length is the edge-weight. The diameter of a metric graph $G$ is the maximum distance between all pairs of points of $G$. We show that the total length of a metric graph $G$ with $\ell(G)$ leaves, cyclomatic number $cyc(G)$, and diameter $diam(G)$ is at most $(cyc(G) + max\{1, \ell(G)/2\}) \cdot diam(G)$. Furthermore, we show that his bound is tight, and we characterize the metric graphs where equality holds. As an application, we provide tight bounds in certain cases for the diameter of metric graphs obtained from a cycle or a star by the identification of a fixed number of points (pairwise or in groups).
A metric graph is a metric space obtained from a finite collection of intervals whose endpoints are identified in groups. It can also be seen as a finite, edge-weighted graph where the continuum of points along the interior of each edge is taken into consideration, and each edge is locally isometric to an interval whose length is the edge-weight. The diameter of a metric graph $G$ is the maximum distance between all pairs of points of $G$. We show that the total length of a metric graph $G$ with $\ell(G)$ leaves, cyclomatic number $cyc(G)$, and diameter $diam(G)$ is at most $(cyc(G) + max\{1, \ell(G)/2\}) \cdot diam(G)$. Furthermore, we show that his bound is tight, and we characterize the metric graphs where equality holds. As an application, we provide tight bounds in certain cases for the diameter of metric graphs obtained from a cycle or a star by the identification of a fixed number of points (pairwise or in groups).
Volumetric parameterization, the process of mapping a 3-manifold onto a simplified volumetric domain, is important for many tasks in computer graphics and imaging science. However, most prior volumetric parameterization approaches have only utilized standardized domains such as a solid ball regardless of the overall shape of the given 3-manifolds, which introduces significant geometric distortion and affects the subsequent shape processing and analysis tasks. To overcome this issue, in this work we propose a novel volumetric parameterization framework for simply connected 3-manifolds. Specifically, the proposed framework jointly controls local shape and mass distortions, while adapting the target domain during the optimization process. It enables three progressively more flexible target-domain settings for the parameterization: a prescribed solid ellipsoid, a volume-normalized adaptive ellipsoid with variable radii, and a sea-embedded free-boundary domain. For each setting, the parameterization algorithm consists of a 3D quasi-conformality shape update, a diffusion-based density-equalizing update, and a geometric correction procedure for removing element foldings, thereby allowing for volumetric parameterizations with different desired effects. Experimental results are presented to demonstrate the effectiveness of our proposed framework. Moreover, our framework can be easily applied to multiresolution and localized adaptive volumetric remeshing, volumetric registration, and volumetric morphing. Altogether, our work provides a new way for the representation, processing, and analysis of 3-manifolds.
Volumetric parameterization, the process of mapping a 3-manifold onto a simplified volumetric domain, is important for many tasks in computer graphics and imaging science. However, most prior volumetric parameterization approaches have only utilized standardized domains such as a solid ball regardless of the overall shape of the given 3-manifolds, which introduces significant geometric distortion and affects the subsequent shape processing and analysis tasks. To overcome this issue, in this work we propose a novel volumetric parameterization framework for simply connected 3-manifolds. Specifically, the proposed framework jointly controls local shape and mass distortions, while adapting the target domain during the optimization process. It enables three progressively more flexible target-domain settings for the parameterization: a prescribed solid ellipsoid, a volume-normalized adaptive ellipsoid with variable radii, and a sea-embedded free-boundary domain. For each setting, the parameterization algorithm consists of a 3D quasi-conformality shape update, a diffusion-based density-equalizing update, and a geometric correction procedure for removing element foldings, thereby allowing for volumetric parameterizations with different desired effects. Experimental results are presented to demonstrate the effectiveness of our proposed framework. Moreover, our framework can be easily applied to multiresolution and localized adaptive volumetric remeshing, volumetric registration, and volumetric morphing. Altogether, our work provides a new way for the representation, processing, and analysis of 3-manifolds.
Given a polygonal domain $\cal P$ comprising $h$ pairwise disjoint convex polygonal obstacles in the plane, together defined with $n$ vertices, this paper presents an algorithm to preprocess $\cal P$ to compute routing tables at the vertices of $\cal P$ so that a data packet from any vertex of $\cal P$ is routed to any other vertex belonging to $\cal P$. At every vertex $v$ of $\cal P$ along the routing path, until the packet reaches its destination, the next hop is determined using the routing tables at $v$ and the information stored in the packet header. In $O(n^2(\lg{n}))$ time, our preprocessing algorithm assigns a unique label of size $O(\sqrt{h} (\lg{h}) \lg{n})$ to each vertex of $\cal P$ and computes routing tables of size $O(h\lg{n} + \sqrt{h}(\lg{h})(\min((\frac{1}ε)^{O( \lg α)},n))$ $\lg {n})$ at each vertex of $\cal P$. The routing path output has a $(7 + ε)(\lg{h})$ multiplicative stretch. Here, $ε> 0$ is an input parameter and $α> 1$ is a geometric parameter.
Given a polygonal domain $\cal P$ comprising $h$ pairwise disjoint convex polygonal obstacles in the plane, together defined with $n$ vertices, this paper presents an algorithm to preprocess $\cal P$ to compute routing tables at the vertices of $\cal P$ so that a data packet from any vertex of $\cal P$ is routed to any other vertex belonging to $\cal P$. At every vertex $v$ of $\cal P$ along the routing path, until the packet reaches its destination, the next hop is determined using the routing tables at $v$ and the information stored in the packet header. In $O(n^2(\lg{n}))$ time, our preprocessing algorithm assigns a unique label of size $O(\sqrt{h} (\lg{h}) \lg{n})$ to each vertex of $\cal P$ and computes routing tables of size $O(h\lg{n} + \sqrt{h}(\lg{h})(\min((\frac{1}ε)^{O( \lg α)},n))$ $\lg {n})$ at each vertex of $\cal P$. The routing path output has a $(7 + ε)(\lg{h})$ multiplicative stretch. Here, $ε> 0$ is an input parameter and $α> 1$ is a geometric parameter.
A convex polygon is called small if its diameter is at most one. Reinhardt proved the universal perimeter bound $\mathrm{perim}(P) \leq U_n := 2n\sin(π/(2n))$, and the bound is attained whenever $n$ has a nontrivial odd divisor. The remaining power-of-two cases have resisted exact solution beyond $n=8$. This paper presents computer-assisted proof candidates for the first three open cases, $n=16,32,64$. In each case, the candidate theorem asserts uniqueness of the maximizing congruence class. The proof architecture is common to all three cases: pass to the difference body $P-P$; encode its reconstruction by a sign code; prove that every global maximizer is saturated, so all difference-body vertices lie on the unit circle; localize every competitive configuration near the regular angle vector; exhaustively screen the sign codes using exact arithmetic; eliminate all nonwinning dihedral orbits; and prove uniqueness inside the winning code by strong convexity and a quantitative KKT argument. The exact certificates cover $2^{15}$ normalized codes for $n=16$, $2^{31}$ normalized codes for $n=32$, and all $2^{64}$ half-codes for $n=64$, leaving respectively $16$, $96$, and $896$ survivors before orbit elimination. The accompanying source package contains the verifiers, recorded outputs, and separate computational cross-checks. These results have not yet received independent human expert review and are therefore deliberately presented as proof candidates rather than literature-established theorems.
A convex polygon is called small if its diameter is at most one. Reinhardt proved the universal perimeter bound $\mathrm{perim}(P) \leq U_n := 2n\sin(π/(2n))$, and the bound is attained whenever $n$ has a nontrivial odd divisor. The remaining power-of-two cases have resisted exact solution beyond $n=8$. This paper presents computer-assisted proof candidates for the first three open cases, $n=16,32,64$. In each case, the candidate theorem asserts uniqueness of the maximizing congruence class. The proof architecture is common to all three cases: pass to the difference body $P-P$; encode its reconstruction by a sign code; prove that every global maximizer is saturated, so all difference-body vertices lie on the unit circle; localize every competitive configuration near the regular angle vector; exhaustively screen the sign codes using exact arithmetic; eliminate all nonwinning dihedral orbits; and prove uniqueness inside the winning code by strong convexity and a quantitative KKT argument. The exact certificates cover $2^{15}$ normalized codes for $n=16$, $2^{31}$ normalized codes for $n=32$, and all $2^{64}$ half-codes for $n=64$, leaving respectively $16$, $96$, and $896$ survivors before orbit elimination. The accompanying source package contains the verifiers, recorded outputs, and separate computational cross-checks. These results have not yet received independent human expert review and are therefore deliberately presented as proof candidates rather than literature-established theorems.
Authors: Felipe Bartelt, Ali Umut Kaypak, Anthony Tzes, Farshad Khorrami, Luciano C. A. Pimenta, Vinicius M. Gonçalves
Computing distances between sets is essential in robotic motion planning and control, where differentiable gradients enable real-time optimization. The Euclidean Signed Distance Function (SDF), however, is not differentiable everywhere, and existing alternatives often sacrifice differentiability, sign information, or computational efficiency. In this letter, we introduce a novel differentiable signed distance between convex polyhedra. To this end, we first propose differentiable versions of the minimum and maximum operators, termed the Hölder minimum and Hölder maximum. We then replace the original min-max operators in the classical SDF formulation, yielding the Hölder signed distance. Unlike prior differentiable distance formulations that rely on iterative algorithms, our approach is computed in closed form, eliminating convergence issues while remaining naturally amenable to GPU parallelization. We validate the practical advantages and computational performance of the proposed distance through runtime comparisons with existing approaches. We also present a robotic manipulator experiment, demonstrating its suitability for applications in control.
Computing distances between sets is essential in robotic motion planning and control, where differentiable gradients enable real-time optimization. The Euclidean Signed Distance Function (SDF), however, is not differentiable everywhere, and existing alternatives often sacrifice differentiability, sign information, or computational efficiency. In this letter, we introduce a novel differentiable signed distance between convex polyhedra. To this end, we first propose differentiable versions of the minimum and maximum operators, termed the Hölder minimum and Hölder maximum. We then replace the original min-max operators in the classical SDF formulation, yielding the Hölder signed distance. Unlike prior differentiable distance formulations that rely on iterative algorithms, our approach is computed in closed form, eliminating convergence issues while remaining naturally amenable to GPU parallelization. We validate the practical advantages and computational performance of the proposed distance through runtime comparisons with existing approaches. We also present a robotic manipulator experiment, demonstrating its suitability for applications in control.
Authors: Prosenjit Bose, Jean Lou de Carufel, Anil Maheshwari, Bobby Miraftab, Michiel Smid, Leonidas Theocharous
The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an earlier one. Its spanning ratio is known to be bounded by a universal constant, but the standard bound obtained from the diamond and good-polygon properties is about $11739.1$. We prove a substantially smaller bound for points in convex position. In particular, for every finite point set $P\subset\mathbb{R}^2$ in convex position and every pair $u,v\in P$, the greedy triangulation contains a $u$--$v$ path of length at most $κ|uv|$, where $κ<17.814$. Thus, the greedy triangulation of a convex point set is an $18$-spanner.
The greedy triangulation of a finite planar point set is obtained by considering all segments in nondecreasing order of length and inserting each segment that does not cross an earlier one. Its spanning ratio is known to be bounded by a universal constant, but the standard bound obtained from the diamond and good-polygon properties is about $11739.1$. We prove a substantially smaller bound for points in convex position. In particular, for every finite point set $P\subset\mathbb{R}^2$ in convex position and every pair $u,v\in P$, the greedy triangulation contains a $u$--$v$ path of length at most $κ|uv|$, where $κ<17.814$. Thus, the greedy triangulation of a convex point set is an $18$-spanner.
We study per-colour independent (k)-rainbow domination and its connection with independent domination in generalized prisms. Building on the known prism identity and the trivial regime above the maximum degree, we focus on the boundary case where the number of colours equals the maximum degree.
For every fixed (k\ge 3), we prove that the decision problem remains NP-complete even on a highly restricted class of graphs: (C_4)-free, bipartite, ((k,2))-biregular subdivision graphs arising from simple (k)-regular graphs. The reduction gives an exact correspondence between optimal rainbow-independent dominating functions on the subdivision graph and proper (k)-edge-colourings of the original graph.
We also introduce an excess parameter measuring how far the domination number lies above its natural lower bound. For cubic graphs, this excess coincides with the classical edge-colouring degree and therefore with standard resistance parameters for subcubic graphs.
These results reveal a sharp one-unit threshold: above the maximum degree the problem becomes trivial for every graph, while at the boundary NP-hard instances already occur within a very narrow structural family.
We study per-colour independent (k)-rainbow domination and its connection with independent domination in generalized prisms. Building on the known prism identity and the trivial regime above the maximum degree, we focus on the boundary case where the number of colours equals the maximum degree.
For every fixed (k\ge 3), we prove that the decision problem remains NP-complete even on a highly restricted class of graphs: (C_4)-free, bipartite, ((k,2))-biregular subdivision graphs arising from simple (k)-regular graphs. The reduction gives an exact correspondence between optimal rainbow-independent dominating functions on the subdivision graph and proper (k)-edge-colourings of the original graph.
We also introduce an excess parameter measuring how far the domination number lies above its natural lower bound. For cubic graphs, this excess coincides with the classical edge-colouring degree and therefore with standard resistance parameters for subcubic graphs.
These results reveal a sharp one-unit threshold: above the maximum degree the problem becomes trivial for every graph, while at the boundary NP-hard instances already occur within a very narrow structural family.
We study the stretch--size tradeoff for geometric spanners in high-dimensional $\ell_p$ spaces. Our main contribution is a simple proof of a lower bound shown by Har-Peled, Indyk, and Sidiropoulos [SODA 2013]: Every $2$-hop $t$-spanner of the pointset $\{0,1\}^d$ under $\ell_2$ norm has at least $(2^d)^{1+Ω(1/t^2)}$ edges. Our proof further extends this result to spanners with Steiner vertices. In addition, we establish a connection between bounded-hop spanners and general spanners, as follows. If every subset $Y$ of an $n$-point metric has a $t$-spanner with at most $μ|Y|$ edges, then the metric has an $O(t)$-hop $O(t)$-spanner of size $O(n(μ+\log n))$. Consequently, hop-restricted spanner lower bounds for a metric imply lower bounds without hop restriction for one of its subsets.
We study the stretch--size tradeoff for geometric spanners in high-dimensional $\ell_p$ spaces. Our main contribution is a simple proof of a lower bound shown by Har-Peled, Indyk, and Sidiropoulos [SODA 2013]: Every $2$-hop $t$-spanner of the pointset $\{0,1\}^d$ under $\ell_2$ norm has at least $(2^d)^{1+Ω(1/t^2)}$ edges. Our proof further extends this result to spanners with Steiner vertices. In addition, we establish a connection between bounded-hop spanners and general spanners, as follows. If every subset $Y$ of an $n$-point metric has a $t$-spanner with at most $μ|Y|$ edges, then the metric has an $O(t)$-hop $O(t)$-spanner of size $O(n(μ+\log n))$. Consequently, hop-restricted spanner lower bounds for a metric imply lower bounds without hop restriction for one of its subsets.
Authors: Ferenc Bencs, Leslie Ann Goldberg, Matthew Jenssen, Mark Jerrum, Gabor Pete, Guus Regts, Yitong Yin
We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $Δ\geq 3$ we show that the expected self-intersection time is $O(\sqrt{n} \log n)$ on $n$-vertex graphs with minimum degree at least $3$ and maximum degree at most $Δ$. For regular graphs with a uniform spectral gap, we improve this to $O(\sqrt{n})$. We also show an $Ω(\sqrt{n})$ lower bound on a class of regular expanders. Our upper bound on the expected self-intersection time implies an improved mixing time bound on Glauber dynamics for the Ising model on $Δ$-regular graphs at the tree uniqueness threshold.
We study the self-intersection time of the non-backtracking random walk on connected undirected graphs. For every fixed $Δ\geq 3$ we show that the expected self-intersection time is $O(\sqrt{n} \log n)$ on $n$-vertex graphs with minimum degree at least $3$ and maximum degree at most $Δ$. For regular graphs with a uniform spectral gap, we improve this to $O(\sqrt{n})$. We also show an $Ω(\sqrt{n})$ lower bound on a class of regular expanders. Our upper bound on the expected self-intersection time implies an improved mixing time bound on Glauber dynamics for the Ising model on $Δ$-regular graphs at the tree uniqueness threshold.
Authors: Fedor V. Fomin, Petr A. Golovach, Yash Hiren More
In the Ultrametric Violation Distance problem, we are given a set of distances between $n$ points, and the goal is to modify the minimum number of distances so that the resulting set forms a valid ultrametric. In other words, the task is to fit an ultrametric to the given data, where the quality of the fit is measured by the $\ell_0$-norm of the error.
While variants of this problem under the $\ell_\infty$ and $\ell_1$-norms have been well studied, the complexity of Ultrametric Violation Distance under the $\ell_0$-norm remained largely unexplored until recently. This changed with the work of Cohen-Addad, Fan, Lee, and Mesmay [FOCS 2022], who introduced a constant-factor approximation algorithm. Significant further progress on approximation algorithms was made in subsequent work by Charikar and Gao [SODA 2024], and by An, Kao, Lee, and Lee [FOCS 2025].
In this paper, we initiate a systematic study of Ultrametric Violation Distance from the perspectives of kernelization and fixed-parameter tractability (FPT). By the work of Fan, Gilbert, Raichel, Sonthalia, and Van Buskirk [SWAT 2020], the problem is known to be FPT when parameterized by the number of violated distances $k$. We show that the problem admits a kernel with $\mathcal{O}(k^2)$ points. Additionally, we present a single-exponential-time algorithm with running time $9^k \cdot n^{\mathcal{O}(1)}$, which is asymptotically tight.
In the Ultrametric Violation Distance problem, we are given a set of distances between $n$ points, and the goal is to modify the minimum number of distances so that the resulting set forms a valid ultrametric. In other words, the task is to fit an ultrametric to the given data, where the quality of the fit is measured by the $\ell_0$-norm of the error.
While variants of this problem under the $\ell_\infty$ and $\ell_1$-norms have been well studied, the complexity of Ultrametric Violation Distance under the $\ell_0$-norm remained largely unexplored until recently. This changed with the work of Cohen-Addad, Fan, Lee, and Mesmay [FOCS 2022], who introduced a constant-factor approximation algorithm. Significant further progress on approximation algorithms was made in subsequent work by Charikar and Gao [SODA 2024], and by An, Kao, Lee, and Lee [FOCS 2025].
In this paper, we initiate a systematic study of Ultrametric Violation Distance from the perspectives of kernelization and fixed-parameter tractability (FPT). By the work of Fan, Gilbert, Raichel, Sonthalia, and Van Buskirk [SWAT 2020], the problem is known to be FPT when parameterized by the number of violated distances $k$. We show that the problem admits a kernel with $\mathcal{O}(k^2)$ points. Additionally, we present a single-exponential-time algorithm with running time $9^k \cdot n^{\mathcal{O}(1)}$, which is asymptotically tight.
Authors: Brandon Augustino, Yue Sun, Atithi Acharya, Shouvanik Chakrabarti, Junhyung Lyle Kim, Shree Hari Sureshbabu, Charlie Che
We study algorithms for approximating the multimarginal optimal transport (MOT) distance, a generalization of the classic optimal transport distance, between $m$ discrete probability distributions each supported on at most $n$ points. We give a classical algorithm that computes a coupling between these marginals whose expected transportation cost is within an additive $\varepsilon > 0$ of the MOT distance in time $O(m^2 n^m \varepsilon^{-1}\mathrm{polylog}(m,n,\varepsilon^{-1}))$. This is, to our knowledge, the first bound for general MOT problems with simultaneous linear dependence on the dimension $n^m$ and on the accuracy parameter $\varepsilon^{-1}$, improving the prior state of the art.
On the quantum side, we give two algorithms that achieve speedups in dimension, though with worse accuracy dependence than classical approaches. First, we construct a quantum projected subgradient method for estimating the MOT distance within an additive $\varepsilon >0$ with runtime $O( m^3 n^{\frac{m}{2}+1} \varepsilon^{-2} \mathrm{polylog}(m,n,\varepsilon^{-1}))$. This algorithm works with the linear programming dual of the MOT problem, and does not return a coupling. We also give a quantum multimarginal Sinkhorn algorithm for entropy-regularized MOT. This algorithm returns an implicit description of an approximately optimal coupling with runtime $O(m^8n^{\frac{m+1}{2}} \varepsilon^{-5} \mathrm{polylog}(m,n,\varepsilon^{-1})))$ after the usual reduction from entropic MOT to unregularized MOT. We also record query lower bounds: for any precision $\varepsilon<1/2$, randomized classical algorithms require $Ω(n^m/(1+\varepsilon n))$ queries and quantum algorithms require $Ω(\sqrt{n^m/(1+\varepsilon n)})$ queries.
We study algorithms for approximating the multimarginal optimal transport (MOT) distance, a generalization of the classic optimal transport distance, between $m$ discrete probability distributions each supported on at most $n$ points. We give a classical algorithm that computes a coupling between these marginals whose expected transportation cost is within an additive $\varepsilon > 0$ of the MOT distance in time $O(m^2 n^m \varepsilon^{-1}\mathrm{polylog}(m,n,\varepsilon^{-1}))$. This is, to our knowledge, the first bound for general MOT problems with simultaneous linear dependence on the dimension $n^m$ and on the accuracy parameter $\varepsilon^{-1}$, improving the prior state of the art.
On the quantum side, we give two algorithms that achieve speedups in dimension, though with worse accuracy dependence than classical approaches. First, we construct a quantum projected subgradient method for estimating the MOT distance within an additive $\varepsilon >0$ with runtime $O( m^3 n^{\frac{m}{2}+1} \varepsilon^{-2} \mathrm{polylog}(m,n,\varepsilon^{-1}))$. This algorithm works with the linear programming dual of the MOT problem, and does not return a coupling. We also give a quantum multimarginal Sinkhorn algorithm for entropy-regularized MOT. This algorithm returns an implicit description of an approximately optimal coupling with runtime $O(m^8n^{\frac{m+1}{2}} \varepsilon^{-5} \mathrm{polylog}(m,n,\varepsilon^{-1})))$ after the usual reduction from entropic MOT to unregularized MOT. We also record query lower bounds: for any precision $\varepsilon<1/2$, randomized classical algorithms require $Ω(n^m/(1+\varepsilon n))$ queries and quantum algorithms require $Ω(\sqrt{n^m/(1+\varepsilon n)})$ queries.
Authors: Yaseen Abd-Elhaleem, Michal Dory, Oren Weimann
Persistent efforts in recent years have been devoted to devising distributed algorithms for fundamental optimization problems in planar graphs. In particular, for Single-Source Shortest-Paths, there is an $\tilde O(D^2)$-rounds exact algorithm [Li, Parter STOC'19] for directed planar graphs, and an $\tilde {O}(D)$-rounds $(1+o(1))$-approximation algorithm [Rozhon, Grunau, Haeupler, Zuzic, Li STOC'22] for undirected planar graphs (where $D$ is the graph's hop-diameter). Recently [Abd-Elhaleem, Dory, Parter, Weimann PODC'25], a matching bound for the exact case was obtained for the Maximum $st$-Flow problem. Namely, an $\tilde O(D^2)$-rounds exact algorithm for directed planar graphs. However, for the approximate case, they give a $D\cdot n^{o(1)}$-rounds $(1-o(1))$-approximation algorithm for undirected planar graphs that works only for the special case where both $s$ and $t$ lie on the same face.
In this paper, we remove the restriction that both $s$ and $t$ must lie on the same face (we also eliminate the $n^{o(1)}$ factor). Namely, we present the first distributed near-optimal $\tilde{O}(D)$-rounds $(1-o(1))$-approximation algorithm for Maximum $st$-Flow in general undirected planar graphs. Our main technical contribution is a distributed implementation of the classical Reif's [SICOMP'83] centralized algorithm. This is achieved by a careful recursive incision procedure on the planar dual $G^*$ of the graph $G$. It is challenging, because we need to simulate dynamic changes (incisions) over the dual graph $G^*$, while we can only communicate over the input graph $G$.
Persistent efforts in recent years have been devoted to devising distributed algorithms for fundamental optimization problems in planar graphs. In particular, for Single-Source Shortest-Paths, there is an $\tilde O(D^2)$-rounds exact algorithm [Li, Parter STOC'19] for directed planar graphs, and an $\tilde {O}(D)$-rounds $(1+o(1))$-approximation algorithm [Rozhon, Grunau, Haeupler, Zuzic, Li STOC'22] for undirected planar graphs (where $D$ is the graph's hop-diameter). Recently [Abd-Elhaleem, Dory, Parter, Weimann PODC'25], a matching bound for the exact case was obtained for the Maximum $st$-Flow problem. Namely, an $\tilde O(D^2)$-rounds exact algorithm for directed planar graphs. However, for the approximate case, they give a $D\cdot n^{o(1)}$-rounds $(1-o(1))$-approximation algorithm for undirected planar graphs that works only for the special case where both $s$ and $t$ lie on the same face.
In this paper, we remove the restriction that both $s$ and $t$ must lie on the same face (we also eliminate the $n^{o(1)}$ factor). Namely, we present the first distributed near-optimal $\tilde{O}(D)$-rounds $(1-o(1))$-approximation algorithm for Maximum $st$-Flow in general undirected planar graphs. Our main technical contribution is a distributed implementation of the classical Reif's [SICOMP'83] centralized algorithm. This is achieved by a careful recursive incision procedure on the planar dual $G^*$ of the graph $G$. It is challenging, because we need to simulate dynamic changes (incisions) over the dual graph $G^*$, while we can only communicate over the input graph $G$.
We introduce the \emph{Safe Bicycle Network with Bounded Detours} (\emph{SBNBD}) problem, motivated by upgrading rural road networks for bicycle traffic. Given an undirected graph with safe and unsafe edges, edge lengths, upgrade costs, terminal pairs, a budget, and a detour factor $α$, the task is to upgrade unsafe edges so that each terminal pair is connected by a safe path of length at most $α$ times its shortest-path distance in the original network.
We study SBNBD from a parameterized perspective. We prove strong NP-hardness on restricted graph classes, including planar graphs of treewidth two, graphs with feedback vertex set number one, and graphs of maximum degree three, and complement these lower bounds with polynomial-time algorithms for trees and graphs of maximum degree two. We show fixed-parameter tractability for the number of unsafe edges and prove matching SETH-based lower bounds, a polynomial-kernel lower bound, and W-hardness for natural parameters. Our main structural result maps any instance to an equivalent instance with $O(\mathrm{fes}+p)$ vertices and edges, where $\mathrm{fes}$ is the feedback edge number and $p$ the number of terminal pairs; this yields fixed-parameter tractability for $\mathrm{fes}+p$.
Finally, we evaluate ILP-based algorithms on OpenStreetMap road networks for small German municipalities and their surroundings. The instances have small treewidth upper bounds and moderate feedback edge structure. Preprocessing based on the $\mathrm{fes}+p$ reduction and tree-decomposition-based cut generation both improve exact solving, especially on harder instances. Experiments with different detour factors show that increasing $α$ can reduce the upgraded-edge length, revealing trade-offs between upgrade cost and allowed relative detours. Overall, structural graph parameters provide a useful algorithmic lens for safe bicycle-network design.
We introduce the \emph{Safe Bicycle Network with Bounded Detours} (\emph{SBNBD}) problem, motivated by upgrading rural road networks for bicycle traffic. Given an undirected graph with safe and unsafe edges, edge lengths, upgrade costs, terminal pairs, a budget, and a detour factor $α$, the task is to upgrade unsafe edges so that each terminal pair is connected by a safe path of length at most $α$ times its shortest-path distance in the original network.
We study SBNBD from a parameterized perspective. We prove strong NP-hardness on restricted graph classes, including planar graphs of treewidth two, graphs with feedback vertex set number one, and graphs of maximum degree three, and complement these lower bounds with polynomial-time algorithms for trees and graphs of maximum degree two. We show fixed-parameter tractability for the number of unsafe edges and prove matching SETH-based lower bounds, a polynomial-kernel lower bound, and W-hardness for natural parameters. Our main structural result maps any instance to an equivalent instance with $O(\mathrm{fes}+p)$ vertices and edges, where $\mathrm{fes}$ is the feedback edge number and $p$ the number of terminal pairs; this yields fixed-parameter tractability for $\mathrm{fes}+p$.
Finally, we evaluate ILP-based algorithms on OpenStreetMap road networks for small German municipalities and their surroundings. The instances have small treewidth upper bounds and moderate feedback edge structure. Preprocessing based on the $\mathrm{fes}+p$ reduction and tree-decomposition-based cut generation both improve exact solving, especially on harder instances. Experiments with different detour factors show that increasing $α$ can reduce the upgraded-edge length, revealing trade-offs between upgrade cost and allowed relative detours. Overall, structural graph parameters provide a useful algorithmic lens for safe bicycle-network design.
We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\sqrt{e}/2\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. Our proof extends the complete-bipartite alternating construction of Wang and Wong to an arbitrary number of alternations. The resulting adversary is described by a monotone integral recurrence. If the recurrence never violates the competitive budget, its iterates converge to an integrable fixed point; classifying all such fixed points forces the excess ratio to be at least $\sqrt{e}/2$. A truncated discrete recurrence and a Riemann-sum argument convert every strict continuous violation into a finite, algorithm-dependent but realization-oblivious input. We also exhibit a critical fixed point showing that $1+\sqrt{e}/2$ is the exact limit of this homogeneous complete-bipartite recurrence, rather than a numerical artifact.
We prove that no randomized integral or fractional algorithm for online vertex cover under general vertex arrivals achieves a competitive ratio strictly below $1+\sqrt{e}/2\approx1.824360635$, even on bipartite graphs and against an oblivious adversary. This improves the previous lower bound of approximately $1.753$. Our proof extends the complete-bipartite alternating construction of Wang and Wong to an arbitrary number of alternations. The resulting adversary is described by a monotone integral recurrence. If the recurrence never violates the competitive budget, its iterates converge to an integrable fixed point; classifying all such fixed points forces the excess ratio to be at least $\sqrt{e}/2$. A truncated discrete recurrence and a Riemann-sum argument convert every strict continuous violation into a finite, algorithm-dependent but realization-oblivious input. We also exhibit a critical fixed point showing that $1+\sqrt{e}/2$ is the exact limit of this homogeneous complete-bipartite recurrence, rather than a numerical artifact.
Authors: Patrick Loiseau, Mathieu Molina, Vianney Perchet, Sebastian Perez-Salazar, Victor Verdugo
The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irrevocably select at most one. Classical single-threshold guarantees are tight in the worst case, but the hard instances that prove tightness are highly irregular: the prophet's advantage is driven by rare, very large realizations of the maximum. We refine this worst-case picture by imposing a bound on the relative variance of the prophet's value, $\mathrm{Var}(\max_{i\in[n]}X_i)/\mathbb E[\max_{i\in[n]}X_i]^2$. This yields a nonparametric complexity measure that interpolates between deterministic instances, where the full prophet value can be recovered, and the unrestricted worst-case regime.
Our main technical contribution is a general kernel method for single-threshold prophet inequalities. The method represents an instance by the quantile function of the maximum and rewrites the payoff of a threshold as a linear kernel functional of this quantile. This turns the worst-case analysis into an infinite-dimensional convex program, restores strong minimax duality in quantile space, and reduces the bounded-variance adversary's problem to a one-parameter variational family. Applying this framework, we obtain an exact characterization of the IID bounded-variance curve and asymptotically optimal finite-horizon thresholds, a closed-form expression for the fixed-order non-identical model, and a prophet-secretary lower-bound program together with a strict separation from the IID benchmark at every positive finite variance constraint. As a further application of the same kernel viewpoint, we derive an exact formula for IID random horizons under a convexity condition on the horizon pgf, which includes monotone-hazard-rate horizons, highlighting the broad applicability of this new technique for single threshold settings.
The single-selection prophet inequality is a canonical Bayesian online selection problem in which independent nonnegative values arrive sequentially and the decision-maker must irrevocably select at most one. Classical single-threshold guarantees are tight in the worst case, but the hard instances that prove tightness are highly irregular: the prophet's advantage is driven by rare, very large realizations of the maximum. We refine this worst-case picture by imposing a bound on the relative variance of the prophet's value, $\mathrm{Var}(\max_{i\in[n]}X_i)/\mathbb E[\max_{i\in[n]}X_i]^2$. This yields a nonparametric complexity measure that interpolates between deterministic instances, where the full prophet value can be recovered, and the unrestricted worst-case regime.
Our main technical contribution is a general kernel method for single-threshold prophet inequalities. The method represents an instance by the quantile function of the maximum and rewrites the payoff of a threshold as a linear kernel functional of this quantile. This turns the worst-case analysis into an infinite-dimensional convex program, restores strong minimax duality in quantile space, and reduces the bounded-variance adversary's problem to a one-parameter variational family. Applying this framework, we obtain an exact characterization of the IID bounded-variance curve and asymptotically optimal finite-horizon thresholds, a closed-form expression for the fixed-order non-identical model, and a prophet-secretary lower-bound program together with a strict separation from the IID benchmark at every positive finite variance constraint. As a further application of the same kernel viewpoint, we derive an exact formula for IID random horizons under a convexity condition on the horizon pgf, which includes monotone-hazard-rate horizons, highlighting the broad applicability of this new technique for single threshold settings.
We study online metric matching with per-request action predictions. On the real line, every deterministic $(1+\varepsilon)$-consistent algorithm has robustness at least $1+\sum_{j=1}^{k-1}2^{j+1}/\varepsilon^j$, and we give a deterministic algorithm for arbitrary metrics with the same leading term. Thus, for every fixed $k$, $\lim_{\varepsilon\downarrow 0}\varepsilon^{k-1}R_k^{\mathbb{R}}(1+\varepsilon)=\lim_{\varepsilon\downarrow 0}\varepsilon^{k-1}R_k(1+\varepsilon)=2^k$. The comparison is uniform up to an absolute constant for $0<\varepsilon\le 1/(k-1)$. We determine the two-server trade-off in both settings and the real-line three-server value $1+4/\varepsilon+8/\varepsilon^2$ for $0<\varepsilon\le\sqrt{13}-3$. When the predicted labels are distinct, the algorithm pays at most $(1+\varepsilon)$ times the cost of the predicted matching. For randomised algorithms, the fixed-$k$ dependence remains $Θ_k(1/\varepsilon^{k-1})$. Uniformly in $k$, robustness is at most $M_0(\varepsilon)ρ_k^0$, where $ρ_k^0$ is the optimal strict prediction-free randomised ratio on the real line and $M_0(\varepsilon)=(2e+o(1))e^{2/\varepsilon}$. For every $η>0$, a lower bound $\exp((2-η)/\varepsilon)$ holds once $k\ge C_η/\varepsilon$. The randomised upper bound follows from a comparison theorem for two online algorithms whose states can be coupled at a cost bounded by their cumulative costs. For every fixed $c>1$, the least comparison factor $M^*(c,\varepsilon)$ under these assumptions satisfies $\lim_{\varepsilon\downarrow 0}\varepsilon\log M^*(c,\varepsilon)=2$. The guarantee is strictly multiplicative and has no diameter-dependent additive term. Irrevocable metric matching and metrical task systems satisfy the assumptions, and the exponent $2$ is optimal under them.
We study online metric matching with per-request action predictions. On the real line, every deterministic $(1+\varepsilon)$-consistent algorithm has robustness at least $1+\sum_{j=1}^{k-1}2^{j+1}/\varepsilon^j$, and we give a deterministic algorithm for arbitrary metrics with the same leading term. Thus, for every fixed $k$, $\lim_{\varepsilon\downarrow 0}\varepsilon^{k-1}R_k^{\mathbb{R}}(1+\varepsilon)=\lim_{\varepsilon\downarrow 0}\varepsilon^{k-1}R_k(1+\varepsilon)=2^k$. The comparison is uniform up to an absolute constant for $0<\varepsilon\le 1/(k-1)$. We determine the two-server trade-off in both settings and the real-line three-server value $1+4/\varepsilon+8/\varepsilon^2$ for $0<\varepsilon\le\sqrt{13}-3$. When the predicted labels are distinct, the algorithm pays at most $(1+\varepsilon)$ times the cost of the predicted matching. For randomised algorithms, the fixed-$k$ dependence remains $Θ_k(1/\varepsilon^{k-1})$. Uniformly in $k$, robustness is at most $M_0(\varepsilon)ρ_k^0$, where $ρ_k^0$ is the optimal strict prediction-free randomised ratio on the real line and $M_0(\varepsilon)=(2e+o(1))e^{2/\varepsilon}$. For every $η>0$, a lower bound $\exp((2-η)/\varepsilon)$ holds once $k\ge C_η/\varepsilon$. The randomised upper bound follows from a comparison theorem for two online algorithms whose states can be coupled at a cost bounded by their cumulative costs. For every fixed $c>1$, the least comparison factor $M^*(c,\varepsilon)$ under these assumptions satisfies $\lim_{\varepsilon\downarrow 0}\varepsilon\log M^*(c,\varepsilon)=2$. The guarantee is strictly multiplicative and has no diameter-dependent additive term. Irrevocable metric matching and metrical task systems satisfy the assumptions, and the exponent $2$ is optimal under them.
We establish a counting analogue of the Lovász Local Lemma: we give polynomial-time algorithms for approximately counting satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime $$ 4 \mathrm{e}\cdot p\cdot (D+1)^2\leq 1, $$ where $p$ is the maximum constraint violation probability and $D$ is the maximum dependency degree.
This condition is tight up to constant factors, matching known lower bounds $pD^2\gtrsim 1$ for approximate counting in natural subclasses of CSPs. The core of our approach is a novel $2$-tree expansion for constraint marginal probabilities, which captures the decay of correlations in the local lemma regime.
We establish a counting analogue of the Lovász Local Lemma: we give polynomial-time algorithms for approximately counting satisfying assignments of general constraint satisfaction problems (CSPs) in the local lemma regime $$ 4 \mathrm{e}\cdot p\cdot (D+1)^2\leq 1, $$ where $p$ is the maximum constraint violation probability and $D$ is the maximum dependency degree.
This condition is tight up to constant factors, matching known lower bounds $pD^2\gtrsim 1$ for approximate counting in natural subclasses of CSPs. The core of our approach is a novel $2$-tree expansion for constraint marginal probabilities, which captures the decay of correlations in the local lemma regime.
The Learned Count-Min Sketch (LCMS) is a learned data structure that estimates element frequencies in a multiset and has been experimentally shown to outperform classical data structures in the capacity-accuracy trade-off. However, its performance depends heavily on parameter selection. Because systematic optimization has not been adequately discussed, previous approaches relied on inefficient brute-force methods. In this study, we propose a method to rapidly optimize the parameters of the original LCMS. We experimentally confirmed that when the machine learning model performs well enough, using a single hash function is sufficient to optimize the weighted error metric. Based on this, we introduce a ternary search approach to efficiently find the optimal proportion of Unique Buckets. Our method achieves the same performance as brute-force approaches while speeding up parameter optimization by $216$-$729$ times when the machine learning model's performance is sufficient. Furthermore, even when the model's performance is suboptimal, our approach still determines appropriate parameters $221$-$740$ times faster than the brute-force approach.
The Learned Count-Min Sketch (LCMS) is a learned data structure that estimates element frequencies in a multiset and has been experimentally shown to outperform classical data structures in the capacity-accuracy trade-off. However, its performance depends heavily on parameter selection. Because systematic optimization has not been adequately discussed, previous approaches relied on inefficient brute-force methods. In this study, we propose a method to rapidly optimize the parameters of the original LCMS. We experimentally confirmed that when the machine learning model performs well enough, using a single hash function is sufficient to optimize the weighted error metric. Based on this, we introduce a ternary search approach to efficiently find the optimal proportion of Unique Buckets. Our method achieves the same performance as brute-force approaches while speeding up parameter optimization by $216$-$729$ times when the machine learning model's performance is sufficient. Furthermore, even when the model's performance is suboptimal, our approach still determines appropriate parameters $221$-$740$ times faster than the brute-force approach.
Let $a$ and $b$ be distinct real weights. An $\{a,b\}$-edge-weighting of a tree assigns one of these weights to each edge and is proper if adjacent vertices have different sums of incident edge weights. For every such pair, we give an explicit structural characterization of the trees that do not admit a proper $\{a,b\}$-edge-weighting. If $ab(a+b)\neq0$, then $K_2$ is the only tree without such a weighting. If $a+b=0$, then a tree has no proper $\{a,b\}$-edge-weighting exactly when every vertex has degree $1$ or $3$ and the subgraph induced by the degree-$3$ vertices has a perfect matching. For the remaining case $ab=0$, form the spanning forest consisting of the edges whose deletion leaves two odd-order components. A tree $T$ has no proper $\{a,b\}$-edge-weighting exactly when both bipartition classes have odd order and every component of this forest satisfies two conditions. First, every component satisfies the preceding degree-and-matching condition. Second, within each component, the degree of a vertex $v$ in the forest plus twice the number of incident edges $e$ outside the forest for which the component of $T-e$ not containing $v$ has an odd number of vertices from each bipartition class is independent of $v$. For every fixed pair of distinct real weights, the proofs yield a linear-time algorithm that decides whether a proper $\{a,b\}$-edge-weighting exists and constructs one when it does.
Let $a$ and $b$ be distinct real weights. An $\{a,b\}$-edge-weighting of a tree assigns one of these weights to each edge and is proper if adjacent vertices have different sums of incident edge weights. For every such pair, we give an explicit structural characterization of the trees that do not admit a proper $\{a,b\}$-edge-weighting. If $ab(a+b)\neq0$, then $K_2$ is the only tree without such a weighting. If $a+b=0$, then a tree has no proper $\{a,b\}$-edge-weighting exactly when every vertex has degree $1$ or $3$ and the subgraph induced by the degree-$3$ vertices has a perfect matching. For the remaining case $ab=0$, form the spanning forest consisting of the edges whose deletion leaves two odd-order components. A tree $T$ has no proper $\{a,b\}$-edge-weighting exactly when both bipartition classes have odd order and every component of this forest satisfies two conditions. First, every component satisfies the preceding degree-and-matching condition. Second, within each component, the degree of a vertex $v$ in the forest plus twice the number of incident edges $e$ outside the forest for which the component of $T-e$ not containing $v$ has an odd number of vertices from each bipartition class is independent of $v$. For every fixed pair of distinct real weights, the proofs yield a linear-time algorithm that decides whether a proper $\{a,b\}$-edge-weighting exists and constructs one when it does.
We study the online busy time scheduling model on one machine of unbounded capacity, with non-preemptive jobs. In our setting, flexible jobs arrive online with a processing time and deadline that becomes known to the algorithm at the job's arrival time. The goal is to schedule jobs on the machine to finish all the jobs by their deadline, so that the total time when the machine is turned on (busy time, also called span in this setting) is minimized.
We present a randomized online algorithm with performance ratio of 1 + e < 3.72, where e is Euler's number, against an oblivious adversary, and show that no randomized algorithm can have competitive ratio better than e against an oblivious adversary. This holds even for algorithm that are allowed to restart jobs. Previous work either dealt with special cases, or with deterministic algorithms, where the known upper bound on the competitive ratio is 5 and the known lower bound is 4. Our findings offer fresh insights on randomization in online energy-aware scheduling.
In the setting where jobs have uniform lengths, and a job that is started by the algorithm must be finished, we show that no deterministic algorithm can do better than 2, even when the jobs are agreeable.
We study the online busy time scheduling model on one machine of unbounded capacity, with non-preemptive jobs. In our setting, flexible jobs arrive online with a processing time and deadline that becomes known to the algorithm at the job's arrival time. The goal is to schedule jobs on the machine to finish all the jobs by their deadline, so that the total time when the machine is turned on (busy time, also called span in this setting) is minimized.
We present a randomized online algorithm with performance ratio of 1 + e < 3.72, where e is Euler's number, against an oblivious adversary, and show that no randomized algorithm can have competitive ratio better than e against an oblivious adversary. This holds even for algorithm that are allowed to restart jobs. Previous work either dealt with special cases, or with deterministic algorithms, where the known upper bound on the competitive ratio is 5 and the known lower bound is 4. Our findings offer fresh insights on randomization in online energy-aware scheduling.
In the setting where jobs have uniform lengths, and a job that is started by the algorithm must be finished, we show that no deterministic algorithm can do better than 2, even when the jobs are agreeable.
We consider standard top-down recursive Mergesort, where we do a single comparison before calling merge to check if the two recursively sorted subproblems happens to already be correctly ordered. (If so, we can skip the merging step). We show for any input $A[0..n)$ of elements consisting of $r$ runs (maximal increasing contiguous subranges in $A$) of respective lengths $L_1,\ldots, L_r$, the mergecost $M$ (the sum of output sizes of all merges) satisfies $M \le (\mathcal H+3)n$ for $\mathcal H = \sum_{i=1}^r (L_i / n) \log_2(n/L_i)$ the runlength entropy.
We consider standard top-down recursive Mergesort, where we do a single comparison before calling merge to check if the two recursively sorted subproblems happens to already be correctly ordered. (If so, we can skip the merging step). We show for any input $A[0..n)$ of elements consisting of $r$ runs (maximal increasing contiguous subranges in $A$) of respective lengths $L_1,\ldots, L_r$, the mergecost $M$ (the sum of output sizes of all merges) satisfies $M \le (\mathcal H+3)n$ for $\mathcal H = \sum_{i=1}^r (L_i / n) \log_2(n/L_i)$ the runlength entropy.
We show that set cover on a universe of size $n$ and with sets of size at most $k$ can be solved in time $2^{(1-1/k+O(1/k^{3/2}))n}$. This improves on a $2^{(1-0.929/k)n}$-time algorithm of Björklund (STACS 2010) for all sufficiently large $k$.
We show that set cover on a universe of size $n$ and with sets of size at most $k$ can be solved in time $2^{(1-1/k+O(1/k^{3/2}))n}$. This improves on a $2^{(1-0.929/k)n}$-time algorithm of Björklund (STACS 2010) for all sufficiently large $k$.
We give deterministic parallel algorithms that compute a $(Δ+1)$-coloring and a maximal independent set for a simple graph with $n$ vertices and $m$ edges in $O(n+m)$ work and $O(\mathrm{poly}\log n)$ depth.
We give deterministic parallel algorithms that compute a $(Δ+1)$-coloring and a maximal independent set for a simple graph with $n$ vertices and $m$ edges in $O(n+m)$ work and $O(\mathrm{poly}\log n)$ depth.
By using a simple textbook reduction from vertex cover, we show that the following three problems are all UG-hard to approximate with constant-factor smaller than two; minimum weakness strong triadic closure, cluster deletion and constrained correlation clustering. Additionally, we analyze the well-known low-diameter decomposition by Calinescu, Karloff and Raban applied to the standard LP relaxation semi-metric for constrained correlation clustering. As opposed to traditional pivot-based approaches, a CKR partition elegantly handles must-link and cannot-link constraints. It guarantees a 3-approximation in expectation, which matches the state-of-the-art approximation ratio by van Zuylen and Williamson. We conjecture that it in fact achieves a strictly better than 3-approximation, yet this remains an open problem.
By using a simple textbook reduction from vertex cover, we show that the following three problems are all UG-hard to approximate with constant-factor smaller than two; minimum weakness strong triadic closure, cluster deletion and constrained correlation clustering. Additionally, we analyze the well-known low-diameter decomposition by Calinescu, Karloff and Raban applied to the standard LP relaxation semi-metric for constrained correlation clustering. As opposed to traditional pivot-based approaches, a CKR partition elegantly handles must-link and cannot-link constraints. It guarantees a 3-approximation in expectation, which matches the state-of-the-art approximation ratio by van Zuylen and Williamson. We conjecture that it in fact achieves a strictly better than 3-approximation, yet this remains an open problem.
We give a randomised algorithm for Equal Subset Sum that runs in time $O\big((5/3)^n\mathrm{poly}(n)+n^2m\big)$ on $n$ integers of at most $m\le2^n$ bits, never outputs a non-solution, and outputs a solution with probability $1-2^{-Ω(n)}$ whenever one exists.
We give a randomised algorithm for Equal Subset Sum that runs in time $O\big((5/3)^n\mathrm{poly}(n)+n^2m\big)$ on $n$ integers of at most $m\le2^n$ bits, never outputs a non-solution, and outputs a solution with probability $1-2^{-Ω(n)}$ whenever one exists.
In open addressed hashing, quadratic probing is attractive for striking a nice balance between having a high locality of reference and a low number of probes per search. However, these are empirical observations, not theoretical guarantees. Indeed, until recently, it was not known whether quadratic probing had constant expected insertion cost under any positive load factor $α> 0$, even with uniformly random hash functions.
In a recent breakthrough---albeit a numerically understated breakthrough---Kuszmaul and Xi (2024) proved that any fixed offset sequence (including quadratic probing) does, in fact, have constant expected insertion cost for load factors $α\leq 8.9\%$. This is well below what we would like to prove, that quadratic probing has constant insertion cost for any load factor $α< 1-ε$ bounded away from 1.
In this paper, we prove that open addressed hashing with any fixed offset sequence has constant expected insertion cost for load factors up to $35.74\%$, and that for quadratic probing in particular, we can increase the load factor to $37.61\%$. Our main innovation is a new type of witness forest for recording collisions among the probe sequences.
In open addressed hashing, quadratic probing is attractive for striking a nice balance between having a high locality of reference and a low number of probes per search. However, these are empirical observations, not theoretical guarantees. Indeed, until recently, it was not known whether quadratic probing had constant expected insertion cost under any positive load factor $α> 0$, even with uniformly random hash functions.
In a recent breakthrough---albeit a numerically understated breakthrough---Kuszmaul and Xi (2024) proved that any fixed offset sequence (including quadratic probing) does, in fact, have constant expected insertion cost for load factors $α\leq 8.9\%$. This is well below what we would like to prove, that quadratic probing has constant insertion cost for any load factor $α< 1-ε$ bounded away from 1.
In this paper, we prove that open addressed hashing with any fixed offset sequence has constant expected insertion cost for load factors up to $35.74\%$, and that for quadratic probing in particular, we can increase the load factor to $37.61\%$. Our main innovation is a new type of witness forest for recording collisions among the probe sequences.
Web and social graphs are analyzed repeatedly for community structure, yet many of their edges are redundant for this purpose, which motivates sparsification. Existing sparsifiers preserve spectral quantities, cuts, local similarity, or a single clustering, but none preserves the thresholded connectivity structure of an edge-relevance filtration, the multiscale pattern by which groups form at high relevance and merge through weaker bridges. We study persistent-connectivity-preserving sparsification: given a graph, an edge-relevance filtration, and a proxy partition computed once during preprocessing, select a budgeted subgraph that preserves the labeled component partition at every threshold, and hence the zero-dimensional persistence diagram, while retaining community evidence for later analyses. Our method, TopoBudget, first extracts a tie-aware persistence backbone that enforces this constraint, then allocates the residual edge budget by greedily maximizing a backbone-conditioned submodular objective that rewards balanced recovery of proxy-internal degree. We prove exact preservation of the component partition at every threshold, and that the conditioned objective is monotone and submodular, so greedy attains a (1-1/e) guarantee for the fixed-backbone residual problem. On held-out synthetic benchmarks and six real Web and social graphs at equal budget, TopoBudget gives the strongest community preservation among topology-preserving methods under Louvain, remains competitive under Infomap, incurs zero topology mismatch, and runs substantially faster than an effective-resistance baseline. A no-backbone ablation shows that, on the real graphs, the mandatory backbone improves average quality while providing the exact guarantee. TopoBudget thus couples exact multiscale connectivity with budgeted, reusable community preservation.
Web and social graphs are analyzed repeatedly for community structure, yet many of their edges are redundant for this purpose, which motivates sparsification. Existing sparsifiers preserve spectral quantities, cuts, local similarity, or a single clustering, but none preserves the thresholded connectivity structure of an edge-relevance filtration, the multiscale pattern by which groups form at high relevance and merge through weaker bridges. We study persistent-connectivity-preserving sparsification: given a graph, an edge-relevance filtration, and a proxy partition computed once during preprocessing, select a budgeted subgraph that preserves the labeled component partition at every threshold, and hence the zero-dimensional persistence diagram, while retaining community evidence for later analyses. Our method, TopoBudget, first extracts a tie-aware persistence backbone that enforces this constraint, then allocates the residual edge budget by greedily maximizing a backbone-conditioned submodular objective that rewards balanced recovery of proxy-internal degree. We prove exact preservation of the component partition at every threshold, and that the conditioned objective is monotone and submodular, so greedy attains a (1-1/e) guarantee for the fixed-backbone residual problem. On held-out synthetic benchmarks and six real Web and social graphs at equal budget, TopoBudget gives the strongest community preservation among topology-preserving methods under Louvain, remains competitive under Infomap, incurs zero topology mismatch, and runs substantially faster than an effective-resistance baseline. A no-backbone ablation shows that, on the real graphs, the mandatory backbone improves average quality while providing the exact guarantee. TopoBudget thus couples exact multiscale connectivity with budgeted, reusable community preservation.
In this note, we show that the approximation algorithm for Boolean Max $k$-CSP presented in [Makarychev and Makarychev 2014] yields a $(1-o_k(1))k/2^k$ approximation, as conjectured in [Makarychev and Makarychev 2017]. This improves the previous guarantee of $(0.626612-o_k(1))k/2^k$ from [Makarychev and Makarychev 2014] and asymptotically matches the known hardness results. The result is a short corollary of the Gaussian stochastic domination theorem of Mulgund.
In this note, we show that the approximation algorithm for Boolean Max $k$-CSP presented in [Makarychev and Makarychev 2014] yields a $(1-o_k(1))k/2^k$ approximation, as conjectured in [Makarychev and Makarychev 2017]. This improves the previous guarantee of $(0.626612-o_k(1))k/2^k$ from [Makarychev and Makarychev 2014] and asymptotically matches the known hardness results. The result is a short corollary of the Gaussian stochastic domination theorem of Mulgund.
Authors: Ioanna Evtushevskaya-Konovalova, Alexander Tiskin
The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. Bruhat decomposition is an important method in numerical linear algebra, generalising ordinary LU decomposition while providing a symmetric structured way of expessing pivoting. Block-recursive algorithms have been developed in the past for various numerical linear algebra problems, including Bruhat decomposition; however, expressing recursive algorithms in the BSP model still remains a challenge. In this paper, we consider the communication and synchronisation complexity of Bruhat decomposition in the BSP model. We develop a new block-recursive, communication-efficient BSP algorithm for Bruhat decomposition.
The model of bulk-synchronous parallel (BSP) computation is an emerging paradigm of general-purpose parallel computing. Bruhat decomposition is an important method in numerical linear algebra, generalising ordinary LU decomposition while providing a symmetric structured way of expessing pivoting. Block-recursive algorithms have been developed in the past for various numerical linear algebra problems, including Bruhat decomposition; however, expressing recursive algorithms in the BSP model still remains a challenge. In this paper, we consider the communication and synchronisation complexity of Bruhat decomposition in the BSP model. We develop a new block-recursive, communication-efficient BSP algorithm for Bruhat decomposition.
Real distance data rarely cooperate: measurements are noisy, observations are missing, and the numbers that result seldom satisfy the triangle inequality. A family of methods exists to correct them, and every one of those methods rests on the same hope --- that analysis run on the corrected data is a more faithful surrogate for the truth than analysis run on the raw data. We are not aware of anyone having tested that hope. We test it through the problem of Metric Repair, which asks for the fewest edges whose reweighting restores the triangle inequality. We implement a suite of algorithms, covering the literature and new methods, both with theoretical guarantees and heuristics, and evaluate their performance on real and synthetic data, both inherently non metric and corrupted. We demonstrate that the algorithms' performance is determined predominantly by the type and fraction of corruption, rather than the corruption's magnitude or graph size.
We further test the effect of repair on downstream tasks, namely MDS and $k$NN, and ask if the repair got the result closer to the truth compared to a corrupted instance. In most cases it did not, and we identify the culprit. A small set of edges is not enough. Finding the correct set of edges, be it an injected corruption or a natural non-metricity, is critical. Moreover, deciding on a weight rule impacts performance: on data instances with available metric ground truth, a metric repair algorithm can pull the graph further from the truth, while an oracle access to the true weights helps. Surprisingly, the opposite can be true as well. Setting the weights is not an implementation detail; it is half the problem.
Real distance data rarely cooperate: measurements are noisy, observations are missing, and the numbers that result seldom satisfy the triangle inequality. A family of methods exists to correct them, and every one of those methods rests on the same hope --- that analysis run on the corrected data is a more faithful surrogate for the truth than analysis run on the raw data. We are not aware of anyone having tested that hope. We test it through the problem of Metric Repair, which asks for the fewest edges whose reweighting restores the triangle inequality. We implement a suite of algorithms, covering the literature and new methods, both with theoretical guarantees and heuristics, and evaluate their performance on real and synthetic data, both inherently non metric and corrupted. We demonstrate that the algorithms' performance is determined predominantly by the type and fraction of corruption, rather than the corruption's magnitude or graph size.
We further test the effect of repair on downstream tasks, namely MDS and $k$NN, and ask if the repair got the result closer to the truth compared to a corrupted instance. In most cases it did not, and we identify the culprit. A small set of edges is not enough. Finding the correct set of edges, be it an injected corruption or a natural non-metricity, is critical. Moreover, deciding on a weight rule impacts performance: on data instances with available metric ground truth, a metric repair algorithm can pull the graph further from the truth, while an oracle access to the true weights helps. Surprisingly, the opposite can be true as well. Setting the weights is not an implementation detail; it is half the problem.
In this paper, we study the {\em perfect fair-triangle packing} problem (abbreviated as PFTP), which incorporates the fairness criterion from {\em fair clustering} into the {\em maximum-weight triangle packing} problem. Specifically, the input is an edge-weighted complete graph $G = (V, E)$ with $|V| = 3n$, where each vertex is colored red or blue. A {\em fair triangle} is a triangle containing vertices of both colors. PFTP asks for a partition of $V$ into $n$ fair triangles such that the total edge weight is maximized. To the best of our knowledge, this is the first paper to study PFTP.
PFTP is NP-hard. Our main contributions are a deterministic $\frac 13$-approximation algorithm running in $O(n^3)$ time and an improved randomized $(\frac {16}{47}-ε)$-approximation algorithm running in $O(n^4)$ time, where $ε> 0$ is a fixed small constant. The deterministic algorithm is matching-based whereas the randomized algorithm employs several additional techniques, including maximum-weight $[1, 2]$-factor, a random cycle-breaking procedure, and maximum-weight matchings.
Keywords: Triangle packing; fairness; approximation algorithms; randomized algorithms
In this paper, we study the {\em perfect fair-triangle packing} problem (abbreviated as PFTP), which incorporates the fairness criterion from {\em fair clustering} into the {\em maximum-weight triangle packing} problem. Specifically, the input is an edge-weighted complete graph $G = (V, E)$ with $|V| = 3n$, where each vertex is colored red or blue. A {\em fair triangle} is a triangle containing vertices of both colors. PFTP asks for a partition of $V$ into $n$ fair triangles such that the total edge weight is maximized. To the best of our knowledge, this is the first paper to study PFTP.
PFTP is NP-hard. Our main contributions are a deterministic $\frac 13$-approximation algorithm running in $O(n^3)$ time and an improved randomized $(\frac {16}{47}-ε)$-approximation algorithm running in $O(n^4)$ time, where $ε> 0$ is a fixed small constant. The deterministic algorithm is matching-based whereas the randomized algorithm employs several additional techniques, including maximum-weight $[1, 2]$-factor, a random cycle-breaking procedure, and maximum-weight matchings.
Keywords: Triangle packing; fairness; approximation algorithms; randomized algorithms
Authors: Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann, Roohani Sharma
For a constant $η\geq 0$, Pathwidth-$η$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$, there is a set $S \subseteq V(G)$ of size at most $k$ such that the pathwidth of $G - S$ is at most $η$. The problems Treewidth-$η$ Deletion and Treedepth-$η$ Deletion are defined similarly for the parameters treewidth and treedepth, respectively. A landmark result of Fomin et al. [FOCS, 2012] shows that, for any constant $η$, all three problems admit a kernel on $O(k^{c(η)})$ vertices, where $c(η)$ is a constant depending on $η$.
Giannopoulou et al. [ACM TALG, 2017] show that, in some sense, this result is optimal for Treewidth-$η$ Deletion: for $η\geq 2$ and even when parameterizing by the size of a vertex cover $M$ of the input graph, there is no kernel of size $O(|M|^{\frac{η+1}{2}-\varepsilon})$, for any $\varepsilon > 0$. Contrasting this result, they prove that Treedepth-$η$ Deletion admits a uniform polynomial kernel, that is, a kernel of size $O(k^c)$ for a constant $c$ that is independent of $η$.
In comparison, the question whether Pathwidth-$η$ Deletion admits a uniform polynomial kernel has been neglected in the literature. As treewidth and pathwidth tend to behave similarly, it is natural to expect that no uniform kernel exists when parameterizing by the size of a vertex cover. Surprisingly, we show this not to be the case. More concretely, we prove the existence of a uniform polynomial kernel for Pathwidth-$η$ Deletion when parameterizing by (1) the solution size $k$ plus the size of a set $M$ such that $G - M$ has bounded treedepth; (2) the (vertex-deletion) distance to pathwidth-$1$ graphs; (3) the distance to the class of graphs with treedepth at most $η+ 1$.
This leads us to conjecture that Pathwidth-$η$ Deletion admits a uniform kernel when parameterizing by the solution size $k$.
For a constant $η\geq 0$, Pathwidth-$η$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$, there is a set $S \subseteq V(G)$ of size at most $k$ such that the pathwidth of $G - S$ is at most $η$. The problems Treewidth-$η$ Deletion and Treedepth-$η$ Deletion are defined similarly for the parameters treewidth and treedepth, respectively. A landmark result of Fomin et al. [FOCS, 2012] shows that, for any constant $η$, all three problems admit a kernel on $O(k^{c(η)})$ vertices, where $c(η)$ is a constant depending on $η$.
Giannopoulou et al. [ACM TALG, 2017] show that, in some sense, this result is optimal for Treewidth-$η$ Deletion: for $η\geq 2$ and even when parameterizing by the size of a vertex cover $M$ of the input graph, there is no kernel of size $O(|M|^{\frac{η+1}{2}-\varepsilon})$, for any $\varepsilon > 0$. Contrasting this result, they prove that Treedepth-$η$ Deletion admits a uniform polynomial kernel, that is, a kernel of size $O(k^c)$ for a constant $c$ that is independent of $η$.
In comparison, the question whether Pathwidth-$η$ Deletion admits a uniform polynomial kernel has been neglected in the literature. As treewidth and pathwidth tend to behave similarly, it is natural to expect that no uniform kernel exists when parameterizing by the size of a vertex cover. Surprisingly, we show this not to be the case. More concretely, we prove the existence of a uniform polynomial kernel for Pathwidth-$η$ Deletion when parameterizing by (1) the solution size $k$ plus the size of a set $M$ such that $G - M$ has bounded treedepth; (2) the (vertex-deletion) distance to pathwidth-$1$ graphs; (3) the distance to the class of graphs with treedepth at most $η+ 1$.
This leads us to conjecture that Pathwidth-$η$ Deletion admits a uniform kernel when parameterizing by the solution size $k$.
A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m\ge 2$ is a
pair of ordered lists $U=(u_1,\ldots,u_K)$ and $V=(v_1,\ldots,v_K)$ with
$u_i,v_j\in \Z_m^n$ such that $\langle u_i,v_i\rangle=0 \pmod m$ for every
$i\in[K]$, while $\langle u_i,v_j\rangle\ne 0 \pmod m$ for every $i\ne j$. It
is called $r$-restricted if the set of all inner products
$\langle u_i,v_j\rangle$ has size at most $r$, including the diagonal value
$0$. Restricted matching vector families are central to the matching-vector
construction of constant-query subexponential locally decodable codes: an
$r$-restricted family of size $K$ in $\Z_m^n$ gives an $r$-query matching-vector
code with message length $K$ and codeword length $N=m^n$.
The best previous bound tailored to the $3$-restricted case was
$MV(m,n,3)\le \exp\bigl(O_m(n/\log n)\bigr)$ for fixed $m$, due to Bhowmick, Dvir and Lovett~\cite{bdl13}, who showed this bound under the polynomial Freiman Ruzsa conjecture, which was proved by Gowers, Green, Manners, and Tao~\cite{PFR24}. In this
work we prove the subexponential upper bound
\[
MV(m,n,3) \le \exp\bigl(O_m(\sqrt{n\log n})\bigr)
\]
for every fixed modulus $m$. Consequently, every $3$-query matching-vector
code over a fixed modulus has codeword length
\[
N \ge \exp\left(\Omega_m\left(\frac{(\log K)^2}{\log\log K}\right)\right).
\]
Our proof answers an explicit technical question left by the work of Aggarwal, Dutta, Li, Obremski, and Saraogi~\cite{ADLOS}: the
entropy-growth method for sums of matching vectors can be pushed far beyond the
initial constant-sum regime. We show that, for $3$-restricted families, entropy
continues to grow for sums of length $L$ as large as
$\Theta_m(\sqrt{n/\log n})$. The new ingredient is an exact-count rank
bootstrap: a long-sum collision changes the exact number of one residue class
seen from a suitable pivot, and exact-weight polynomials convert a disjoint
collision family into a low-rank identity matrix.
A Matching Vector ($\mathbf{MV}$) family modulo a positive integer $m\ge 2$ is a
pair of ordered lists $U=(u_1,\ldots,u_K)$ and $V=(v_1,\ldots,v_K)$ with
$u_i,v_j\in \Z_m^n$ such that $\langle u_i,v_i\rangle=0 \pmod m$ for every
$i\in[K]$, while $\langle u_i,v_j\rangle\ne 0 \pmod m$ for every $i\ne j$. It
is called $r$-restricted if the set of all inner products
$\langle u_i,v_j\rangle$ has size at most $r$, including the diagonal value
$0$. Restricted matching vector families are central to the matching-vector
construction of constant-query subexponential locally decodable codes: an
$r$-restricted family of size $K$ in $\Z_m^n$ gives an $r$-query matching-vector
code with message length $K$ and codeword length $N=m^n$.
The best previous bound tailored to the $3$-restricted case was
$MV(m,n,3)\le \exp\bigl(O_m(n/\log n)\bigr)$ for fixed $m$, due to Bhowmick, Dvir and Lovett~\cite{bdl13}, who showed this bound under the polynomial Freiman Ruzsa conjecture, which was proved by Gowers, Green, Manners, and Tao~\cite{PFR24}. In this
work we prove the subexponential upper bound
\[
MV(m,n,3) \le \exp\bigl(O_m(\sqrt{n\log n})\bigr)
\]
for every fixed modulus $m$. Consequently, every $3$-query matching-vector
code over a fixed modulus has codeword length
\[
N \ge \exp\left(\Omega_m\left(\frac{(\log K)^2}{\log\log K}\right)\right).
\]
Our proof answers an explicit technical question left by the work of Aggarwal, Dutta, Li, Obremski, and Saraogi~\cite{ADLOS}: the
entropy-growth method for sums of matching vectors can be pushed far beyond the
initial constant-sum regime. We show that, for $3$-restricted families, entropy
continues to grow for sums of length $L$ as large as
$\Theta_m(\sqrt{n/\log n})$. The new ingredient is an exact-count rank
bootstrap: a long-sum collision changes the exact number of one residue class
seen from a suitable pivot, and exact-weight polynomials convert a disjoint
collision family into a low-rank identity matrix.
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below $\delta$, then every length-$n$ binary code, linear or nonlinear, of relative distance $\delta$ has rate at most the channel's capacity, up to an $O(n^{-1/2})$ correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly.
This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every $0 < \delta < \frac{1}{2}$, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below $\delta$, then every length-$n$ binary code, linear or nonlinear, of relative distance $\delta$ has rate at most the channel's capacity, up to an $O(n^{-1/2})$ correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly.
This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every $0 < \delta < \frac{1}{2}$, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.
Authors: Nikolai Chukhin, Alexander S. Kulikov, Maksim Levitskii, Ivan Mihajlin
The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem is a parameterized version of Subset Sum asking whether there are $k$ integers that sum to the target. The best classical upper bound for it is $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{Φ_k})$ is known, where
$$ Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$
(Schrottenloher, 2021).
We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{Ψ_k})$, where
$$ Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$
The algorithm is not only faster for all $k$ congruent to $3$ or $6$ modulo $7$, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for $7$-SUM with the standard block reduction technique yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.
The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem is a parameterized version of Subset Sum asking whether there are $k$ integers that sum to the target. The best classical upper bound for it is $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{Φ_k})$ is known, where
$$ Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$
(Schrottenloher, 2021).
We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{Ψ_k})$, where
$$ Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$
The algorithm is not only faster for all $k$ congruent to $3$ or $6$ modulo $7$, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for $7$-SUM with the standard block reduction technique yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.
For sufficiently large $N$ which is a power of 2, we prove that changing at most one percent of the entries of the $N\times N$ Walsh-Hadamard Transform cannot reduce its rank over $\mathbb{F}_3$ to $\lfloor \log^2 N/80\rfloor$ or below. To the best of our knowledge, this is the first constant-fraction rigidity lower bound for an explicit matrix family at a superlogarithmic target rank over any choice of field, inching toward the parameters in Razborov's program for communication complexity lower bounds.
For sufficiently large $N$ which is a power of 2, we prove that changing at most one percent of the entries of the $N\times N$ Walsh-Hadamard Transform cannot reduce its rank over $\mathbb{F}_3$ to $\lfloor \log^2 N/80\rfloor$ or below. To the best of our knowledge, this is the first constant-fraction rigidity lower bound for an explicit matrix family at a superlogarithmic target rank over any choice of field, inching toward the parameters in Razborov's program for communication complexity lower bounds.
For a homogeneous polynomial f of degree d, the degree-k restricted strength C_k(f) is the least number of products needed to write f with factor degrees k and d-k. We introduce a two-cut coherence parameter C_{k,l}(f): the least r such that f = sum_{i,j=1}^{r} p_i m_{ij} q_j with deg p_i = k, deg m_{ij} = l-k, and deg q_j = d-l. This requires two degree interfaces to be realized by a single common factorization. We show it equals the minimum common endpoint width of a three-block compressed transfer network, and equivalently the minimum, over all tensor lifts of f through commutative multiplication, of the larger of the two tensor-train endpoint ranks. In particular it lower-bounds homogeneous ABP width.
Our main result is an extraction-completeness theorem for quintics at cuts (1,3). Let D(f) be the largest polynomial slice rank C_1 of a second directional derivative of f, and let t = C_3(f). Over an algebraically closed field of characteristic zero, ceil(D(f)/3) <= Cbar_{1,3}(f) <= C_{1,3}(f) <= t*D(f) + 2t^2, where Cbar denotes border complexity. Hence when C_3 is bounded, ordinary and border two-cut coherence are equivalent up to constants to a one-cut obstruction exposed by a second derivative.
We also prove a border-stable lifting separation. For coprime nonzero cubics A and B, the quintic L = abA + cdB has ordinary and border local values C_1 = C_3 = 2, while ceil(max{C_1(A), C_1(B)}/3) <= Cbar_{1,3}(L) <= C_1(A) + C_1(B). Taking A to be a Fermat cubic in n variables, for which we show C_1 = ceil(n/2), gives an unbounded gap between separately optimal local interfaces and a common interface, even in border complexity. This refutes any universal bound of the form C_{k,l} <= C_k + C_l.
For a homogeneous polynomial f of degree d, the degree-k restricted strength C_k(f) is the least number of products needed to write f with factor degrees k and d-k. We introduce a two-cut coherence parameter C_{k,l}(f): the least r such that f = sum_{i,j=1}^{r} p_i m_{ij} q_j with deg p_i = k, deg m_{ij} = l-k, and deg q_j = d-l. This requires two degree interfaces to be realized by a single common factorization. We show it equals the minimum common endpoint width of a three-block compressed transfer network, and equivalently the minimum, over all tensor lifts of f through commutative multiplication, of the larger of the two tensor-train endpoint ranks. In particular it lower-bounds homogeneous ABP width.
Our main result is an extraction-completeness theorem for quintics at cuts (1,3). Let D(f) be the largest polynomial slice rank C_1 of a second directional derivative of f, and let t = C_3(f). Over an algebraically closed field of characteristic zero, ceil(D(f)/3) <= Cbar_{1,3}(f) <= C_{1,3}(f) <= t*D(f) + 2t^2, where Cbar denotes border complexity. Hence when C_3 is bounded, ordinary and border two-cut coherence are equivalent up to constants to a one-cut obstruction exposed by a second derivative.
We also prove a border-stable lifting separation. For coprime nonzero cubics A and B, the quintic L = abA + cdB has ordinary and border local values C_1 = C_3 = 2, while ceil(max{C_1(A), C_1(B)}/3) <= Cbar_{1,3}(L) <= C_1(A) + C_1(B). Taking A to be a Fermat cubic in n variables, for which we show C_1 = ceil(n/2), gives an unbounded gap between separately optimal local interfaces and a common interface, even in border complexity. This refutes any universal bound of the form C_{k,l} <= C_k + C_l.
Authors: Petar Hristov, Ingrid Hotz, Talha Bin Masood
Trait-induced merge trees (TIMTs) provide a robust topology-based method for selecting and browsing feature level sets in multivariate data by analyzing the distance field induced by a user-specified trait in attribute space. Existing TIMT computations typically sample this distance field at mesh vertices and assume piecewise-linear interpolation, although the Euclidean distance-to-trait function is generally not piecewise linear on the original mesh. As a result, the resulting merge tree may miss zero-valued features and may perturb the locations and values of minima and merge events. We study the exact computation of TIMTs for piecewise-linear bivariate fields, focusing first on point traits. We show that the restricted sublevel sets inside each tetrahedron are convex and therefore have trivial local merge-tree structure, implying that global topological changes arise only through gluing across simplex boundaries. Based on this observation, we construct a weighted graph whose merge tree is isomorphic to the exact merge tree of the induced distance field. We further relate TIMTs to Jacobi sets, showing how nonzero edge events of the TIMT are localized by the singular structure of the underlying bivariate map. We establish a theoretical upper bound on the error of the vertex-sampled linear interpolation, expressed in terms of the maximum length of projected mesh edges in the range. We discuss extensions to line, line-segment, and finite point-set traits, and implement the method robustly using CGAL and VTK, demonstrating results on both synthetic and real-world datasets.
Trait-induced merge trees (TIMTs) provide a robust topology-based method for selecting and browsing feature level sets in multivariate data by analyzing the distance field induced by a user-specified trait in attribute space. Existing TIMT computations typically sample this distance field at mesh vertices and assume piecewise-linear interpolation, although the Euclidean distance-to-trait function is generally not piecewise linear on the original mesh. As a result, the resulting merge tree may miss zero-valued features and may perturb the locations and values of minima and merge events. We study the exact computation of TIMTs for piecewise-linear bivariate fields, focusing first on point traits. We show that the restricted sublevel sets inside each tetrahedron are convex and therefore have trivial local merge-tree structure, implying that global topological changes arise only through gluing across simplex boundaries. Based on this observation, we construct a weighted graph whose merge tree is isomorphic to the exact merge tree of the induced distance field. We further relate TIMTs to Jacobi sets, showing how nonzero edge events of the TIMT are localized by the singular structure of the underlying bivariate map. We establish a theoretical upper bound on the error of the vertex-sampled linear interpolation, expressed in terms of the maximum length of projected mesh edges in the range. We discuss extensions to line, line-segment, and finite point-set traits, and implement the method robustly using CGAL and VTK, demonstrating results on both synthetic and real-world datasets.
Authors: Tamal K. Dey, Andrew Haas, Michał Lipiński
Recent advances in combinatorial dynamical systems that generalize the classic discrete Morse theory have prompted algorithmic studies of combinatorial vector fields. In this regard, authors in [7] recently proposed the concept of Conley-Morse persistence barcode that summarizes the continuation of invariant sets in an evolving vector field through homological persistence. They proposed an algorithm to compute this barcode using a filtration of the so called \emph{index pairs} on a poset called \emph{transition diagram}. The algorithm becomes costly due to multiple runs of zigzag persistence it executes on filtrations of `unwieldy' structures of index pairs. We overcome this difficulty by replacing the index pairs with \emph{blocks}, which are structurally much simpler. These replacements need reversal of certain relations in the transition diagram resulting in a much simpler algorithm. The algorithm works by updating matrix decompositions akin to computing `vineyard' in standard persistence.
Recent advances in combinatorial dynamical systems that generalize the classic discrete Morse theory have prompted algorithmic studies of combinatorial vector fields. In this regard, authors in [7] recently proposed the concept of Conley-Morse persistence barcode that summarizes the continuation of invariant sets in an evolving vector field through homological persistence. They proposed an algorithm to compute this barcode using a filtration of the so called \emph{index pairs} on a poset called \emph{transition diagram}. The algorithm becomes costly due to multiple runs of zigzag persistence it executes on filtrations of `unwieldy' structures of index pairs. We overcome this difficulty by replacing the index pairs with \emph{blocks}, which are structurally much simpler. These replacements need reversal of certain relations in the transition diagram resulting in a much simpler algorithm. The algorithm works by updating matrix decompositions akin to computing `vineyard' in standard persistence.
Let \(G\) be a connected simple undirected graph. A vertex \(w\) is said to \emph{strongly resolve} a pair of distinct vertices \(u, v \in V(G)\) if either there exists an isometric path (i.e.~a shortest path) from \(w\) to \(u\) that contains \(v\), or there exists an isometric path from \(w\) to \(v\) that contains \(u\). A subset \(S \subseteq V(G)\) is said to \emph{strongly resolve} \(G\) if every pair of distinct vertices of \(G\) is strongly resolved by at least one vertex in \(S\). In the \textsc{Strong Metric Dimension} problem, the input consists of a graph \(G\) and a positive integer \(k\), and the objective is to determine whether there exists a subset \(S \subseteq V(G)\) of size at most \(k\) that strongly resolves \(G\). In this article, we show that \textsc{Strong Metric Dimension} is \NP-complete even on \((i)\) graphs of diameter two, and \((ii)\) graphs of constant pathwidth and constant feedback vertex set number.
Let \(G\) be a connected simple undirected graph. A vertex \(w\) is said to \emph{strongly resolve} a pair of distinct vertices \(u, v \in V(G)\) if either there exists an isometric path (i.e.~a shortest path) from \(w\) to \(u\) that contains \(v\), or there exists an isometric path from \(w\) to \(v\) that contains \(u\). A subset \(S \subseteq V(G)\) is said to \emph{strongly resolve} \(G\) if every pair of distinct vertices of \(G\) is strongly resolved by at least one vertex in \(S\). In the \textsc{Strong Metric Dimension} problem, the input consists of a graph \(G\) and a positive integer \(k\), and the objective is to determine whether there exists a subset \(S \subseteq V(G)\) of size at most \(k\) that strongly resolves \(G\). In this article, we show that \textsc{Strong Metric Dimension} is \NP-complete even on \((i)\) graphs of diameter two, and \((ii)\) graphs of constant pathwidth and constant feedback vertex set number.
Authors: Sami Davies, Benjamin Moseley, Heather Newman
The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than $Ω(n)$. Prior works bypass this lower bound by relaxing the online model through recourse, random arrival order, or seeding the algorithm with an offline sample of the underlying input. We instead ask whether additional structure in the input itself can overcome this lower bound. We study weighted correlation clustering under probability constraints, where $w^+_{uv}+w^-_{uv}=1$ for every $uv$ edge, and triangle inequality constraints, where the negative weights $w^-$ satisfy triangle inequality. While this version of correlation clustering is well-studied in the offline setting, we initiate its online study and give a deterministic online algorithm that maintains a clustering whose total weighted disagreement cost is within an $O(1)$ factor of the offline optimum, against adversarial arrival order. This is the first constant-competitive online algorithm for a natural minimization variant of correlation clustering in the fully online model, and shows that metric consistency on the edge weights separates tractable from intractable online instances.
The standard online version of correlation clustering is prohibitively hard, as even randomized algorithms cannot achieve competitive ratio better than $Ω(n)$. Prior works bypass this lower bound by relaxing the online model through recourse, random arrival order, or seeding the algorithm with an offline sample of the underlying input. We instead ask whether additional structure in the input itself can overcome this lower bound. We study weighted correlation clustering under probability constraints, where $w^+_{uv}+w^-_{uv}=1$ for every $uv$ edge, and triangle inequality constraints, where the negative weights $w^-$ satisfy triangle inequality. While this version of correlation clustering is well-studied in the offline setting, we initiate its online study and give a deterministic online algorithm that maintains a clustering whose total weighted disagreement cost is within an $O(1)$ factor of the offline optimum, against adversarial arrival order. This is the first constant-competitive online algorithm for a natural minimization variant of correlation clustering in the fully online model, and shows that metric consistency on the edge weights separates tractable from intractable online instances.
