More Like this

1. 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
2. Hamiltonian reconstruction as metric for variational studies

   https://doi.org/10.21468/SciPostPhys.13.3.063  

   Zhang, Kevin; Lederer, Samuel; Choo, Kenny; Neupert, Titus; Carleo, Giuseppe; Kim, Eun-Ah (January 2022, SciPost Physics)

   Variational approaches are among the most powerful techniques toapproximately solve quantum many-body problems. These encompass bothvariational states based on tensor or neural networks, and parameterizedquantum circuits in variational quantum eigensolvers. However,self-consistent evaluation of the quality of variational wavefunctionsis a notoriously hard task. Using a recently developed Hamiltonianreconstruction method, we propose a multi-faceted approach to evaluatingthe quality of neural-network based wavefunctions. Specifically, weconsider convolutional neural network (CNN) and restricted Boltzmannmachine (RBM) states trained on a square latticespin-1/2 $1/2$ J_1\!-\!J_2 $J_1-J_2$ Heisenberg model. We find that the reconstructed Hamiltonians aretypically less frustrated, and have easy-axis anisotropy near the highfrustration point. In addition, the reconstructed Hamiltonians suppressquantum fluctuations in the largeJ_2 $J_2$ limit. Our results highlight the critical importance of thewavefunction’s symmetry. Moreover, the multi-faceted insight from theHamiltonian reconstruction reveals that a variational wave function canfail to capture the true ground state through suppression of quantumfluctuations. 

   more » « less
3. The Generalized Matrix Separation Problem: Algorithms

   https://doi.org/10.1007/s10543-026-01145-5  

   Chen, Xuemei; Deen, Owen (September 2026, BIT Numerical Mathematics)

   Abstract When given a generalized matrix separation problem, which aims to recover a low rank matrix$$L_0$$ $L_0$ and a sparse matrix$$S_0$$ $S_0$ from$$M_0=L_0+HS_0$$ $M_0=L_0+H{S}_0$ , the work [1] proposes a novel convex optimization problem whose objective function is the sum of the$$\ell _1$$ ${\ell }_1$ -norm and nuclear norm. In this paper we detail the iterative algorithms and its associated computations for solving this convex optimization problem. We present various efficient implementation strategies, with attention to practical cases whereHis circulant, separable, or block structured. Notably, we propose a preprocessing technique that drastically improved the performance of our algorithms in terms of efficiency, accuracy, and robustness. While this paper serves as an illustrative algorithm implementation manual, we also provide theoretical guarantee for our preprocessing strategy. Numerical results demonstrate the effectiveness of the proposed approach. 

   more » « less
4. Computing Proximity Operators of Scale and Signed Permutation Invariant Functions

   https://doi.org/10.1007/s10957-025-02871-6  

   Jia, Jianqing; Prater-Bennette, Ashley; Shen, Lixin (January 2026, Journal of Optimization Theory and Applications)

   Abstract This paper investigates the computation of proximity operators for scale and signed permutation invariant functions. A scale invariant function remains unchanged under uniform scaling, while a signed permutation invariant function retains its structure despite permutations and sign changes applied to its input variables. Noteworthy examples include the$$\ell _0$$ ${\ell }_0$ function, the ratio of$$\ell _1/\ell _2$$ ${\ell }_1/{\ell }_2$ , and its square, with their proximity operators being particularly crucial in sparse signal recovery. We delve into the properties of scale and signed permutation invariant functions, delineating the computation of their proximity operators into three sequential steps: the$${\varvec{w}}$$ $w$ -step,r-step, andd-step. These steps collectively form a procedure termed as WRD, with the$${\varvec{w}}$$ $w$ -step being of utmost importance and requiring careful treatment. Leveraging this procedure, we present a method for explicitly and efficiently computing the proximity operator of$$(\ell _1/\ell _2)^2$$ ${({\ell }_1/{\ell }_2)}^2$ and introduce an algorithm for the proximity operator of$$\ell _1/\ell _2$$ ${\ell }_1/{\ell }_2$ . Numerical experiments on sparse signal recovery corroborate the analysis and show that first-order methods equipped with these proximity operators outperform$$\ell _1$$ ${\ell }_1$ -based baselines in reconstruction accuracy. 

   more » « less
5. Torsion phenomena for zero-cycles on a product of curves over a number field

   https://doi.org/10.1007/s40993-024-00519-4  

   Gazaki, Evangelia; Love, Jonathan (June 2024, Research in Number Theory)

   Abstract For a smooth projective varietyXover an algebraic number fieldka conjecture of Bloch and Beilinson predicts that the kernel of the Albanese map ofXis a torsion group. In this article we consider a product$$X=C_1\times \cdots \times C_d$$ $X=C_1\times \cdots \times C_d$ of smooth projective curves and show that if the conjecture is true for any subproduct of two curves, then it is true forX. For a product$$X=C_1\times C_2$$ $X=C_1\times C_2$ of two curves over$$\mathbb {Q} $$ $Q$ with positive genus we construct many nontrivial examples that satisfy the weaker property that the image of the natural map$$J_1(\mathbb {Q})\otimes J_2(\mathbb {Q})\xrightarrow {\varepsilon }{{\,\textrm{CH}\,}}_0(C_1\times C_2)$$ $J_1\left(Q\right)\otimes J_2\left(Q\right)\stackrel{\epsilon }{\to }{\text{CH}}_0(C_1\times C_2)$ is finite, where$$J_i$$ $J_i$ is the Jacobian variety of$$C_i$$ $C_i$ . Our constructions include many new examples of non-isogenous pairs of elliptic curves$$E_1, E_2$$ $E_1,E_2$ with positive rank, including the first known examples of rank greater than 1. Combining these constructions with our previous result, we obtain infinitely many nontrivial products$$X=C_1\times \cdots \times C_d$$ $X=C_1\times \cdots \times C_d$ for which the analogous map$$\varepsilon $$ $\epsilon$ has finite image. 

   more » « less