More Like this

1. Better Hardness Results for the Minimum Spanning Tree Congestion Problem

   https://doi.org/10.1007/s00453-024-01278-5  

   Luu, Huong; Chrobak, Marek (January 2025, Algorithmica)

   Abstract In the spanning tree congestion problem, given a connected graphG, the objective is to compute a spanning treeTinGthat minimizes its maximum edge congestion, where the congestion of an edgeeofTis the number of edges inGfor which the unique path inTbetween their endpoints traversese. The problem is known to be$$\mathbb{N}\mathbb{P}$$ $NP$ -hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratioo(n). In the decision version of this problem, denoted$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$ , we need to determine ifGhas a spanning tree with congestion at mostK. It is known that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$ is$$\mathbb{N}\mathbb{P}$$ $NP$ -complete for$$K\ge 8$$ $K\ge 8$ , and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,$${\varvec{3}-\textsf {STC}}$$ $3-\mathrm{STC}$ can be solved in polynomial time, with the complexity status of this problem for$$K\in { \left\{ 4,5,6,7 \right\} }$$ $K\in \left(4,,,5,,,6,,,7\right)$ remaining an open problem. We substantially improve the earlier hardness results by proving that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$ is$$\mathbb{N}\mathbb{P}$$ $NP$ -complete for$$K\ge 5$$ $K\ge 5$ . This leaves only the case$$K=4$$ $K=4$ open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$ restricted to graphs of radius 2, and we prove that this variant is$$\mathbb{N}\mathbb{P}$$ $NP$ -complete for all$$K\ge 6$$ $K\ge 6$ . 

   more » « less
2. Polynomial Bounds for Chromatic Number. IV: A Near-polynomial Bound for Excluding the Five-vertex Path

   https://doi.org/10.1007/s00493-023-00015-w  

   Scott, Alex; Seymour, Paul; Spirkl, Sophie (October 2023, Combinatorica)

   Abstract A graphGisH-freeif it has no induced subgraph isomorphic toH. We prove that a$$P_5$$ $P_5$ -free graph with clique number$$\omega \ge 3$$ $\omega \ge 3$ has chromatic number at most$$\omega ^{\log _2(\omega )}$$ ${\omega }^{{log}_2\left(\omega \right)}$ . The best previous result was an exponential upper bound$$(5/27)3^{\omega }$$ $(5/27)3^{\omega }$ , due to Esperet, Lemoine, Maffray, and Morel. A polynomial bound would imply that the celebrated Erdős-Hajnal conjecture holds for$$P_5$$ $P_5$ , which is the smallest open case. Thus, there is great interest in whether there is a polynomial bound for$$P_5$$ $P_5$ -free graphs, and our result is an attempt to approach that. 

   more » « less
3. Rates of convergence for regression with the graph poly-Laplacian

   https://doi.org/10.1007/s43670-023-00075-5  

   Trillos, Nicolás García; Murray, Ryan; Thorpe, Matthew (December 2023, Sampling Theory, Signal Processing, and Data Analysis)

   Abstract In the (special) smoothing spline problem one considers a variational problem with a quadratic data fidelity penalty and Laplacian regularization. Higher order regularity can be obtained via replacing the Laplacian regulariser with a poly-Laplacian regulariser. The methodology is readily adapted to graphs and here we consider graph poly-Laplacian regularization in a fully supervised, non-parametric, noise corrupted, regression problem. In particular, given a dataset$$\{x_i\}_{i=1}^n$$ ${\left\{x_i\right\}}_{i=1}^n$ and a set of noisy labels$$\{y_i\}_{i=1}^n\subset \mathbb {R}$$ ${\left\{y_i\right\}}_{i=1}^n\subset R$ we let$$u_n{:}\{x_i\}_{i=1}^n\rightarrow \mathbb {R}$$ $u_n:{\left\{x_i\right\}}_{i=1}^n\to R$ be the minimizer of an energy which consists of a data fidelity term and an appropriately scaled graph poly-Laplacian term. When$$y_i = g(x_i)+\xi _i$$ $y_i=g\left(x_i\right)+{\xi }_i$ , for iid noise$$\xi _i$$ ${\xi }_i$ , and using the geometric random graph, we identify (with high probability) the rate of convergence of$$u_n$$ $u_n$ togin the large data limit$$n\rightarrow \infty $$ $n\to \infty$ . Furthermore, our rate is close to the known rate of convergence in the usual smoothing spline model. 

   more » « less
4. Extended fiducial inference for individual treatment effects via deep neural networks

   https://doi.org/10.1007/s11222-025-10624-8  

   Kim, Sehwan; Liang, Faming (August 2025, Statistics and Computing)

   Abstract Individual treatment effect estimation has gained significant attention in recent data science literature. This work introduces the Double Neural Network (Double-NN) method to address this problem within the framework of extended fiducial inference (EFI). In the proposed method, deep neural networks are used to model the treatment and control effect functions, while an additional neural network is employed to estimate their parameters. The universal approximation capability of deep neural networks ensures the broad applicability of this method. Numerical results highlight the superior performance of the proposed Double-NN method compared to the conformal quantile regression (CQR) method in individual treatment effect estimation. From the perspective of statistical inference, this work advances the theory and methodology for statistical inference of large models. Specifically, it is theoretically proven that the proposed method permits the model size to increase with the sample sizenat a rate of$$O(n^{\zeta })$$ $O\left(n^{\zeta }\right)$ for some$$0 \le \zeta <1$$ $0\le \zeta <1$ , while still maintaining proper quantification of uncertainty in the model parameters. This result marks a significant improvement compared to the range$$0\le \zeta < \frac{1}{2}$$ $0\le \zeta <\frac{1}{2}$ required by the classical central limit theorem. Furthermore, this work provides a rigorous framework for quantifying the uncertainty of deep neural networks under the neural scaling law, representing a substantial contribution to the statistical understanding of large-scale neural network models. 

   more » « less
5. Construction of a Dirichlet form on Metric Measure Spaces of Controlled Geometry

   https://doi.org/10.1007/s11118-024-10144-6  

   Butaev, Almaz; Luo, Liangbing; Shanmugalingam, Nageswari (March 2025, Potential Analysis)

   Abstract Given a compact doubling metric measure spaceXthat supports a 2-Poincaré inequality, we construct a Dirichlet form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$ that is comparable to the upper gradient energy form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$ . Our approach is based on the approximation ofXby a family of graphs that is doubling and supports a 2-Poincaré inequality (see [20]). We construct a bilinear form on$$N^{1,2}(X)$$ $N^{1,2}\left(X\right)$ using the Dirichlet form on the graph. We show that the$$\Gamma $$ $\Gamma$ -limit$$\mathcal {E}$$ $E$ of this family of bilinear forms (by taking a subsequence) exists and that$$\mathcal {E}$$ $E$ is a Dirichlet form onX. Properties of$$\mathcal {E}$$ $E$ are established. Moreover, we prove that$$\mathcal {E}$$ $E$ has the property of matching boundary values on a domain$$\Omega \subseteq X$$ $\Omega \subseteq X$ . This construction makes it possible to approximate harmonic functions (with respect to the Dirichlet form$$\mathcal {E}$$ $E$ ) on a domain inXwith a prescribed Lipschitz boundary data via a numerical scheme dictated by the approximating Dirichlet forms, which are discrete objects. 

   more » « less