CXChangji Xu

Changji Xu

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Changji Xu has a total of 9 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Spectral gap estimates for mixed p-spin models at high temperature

    by Arka Adhikari, Christian Brennecke, Changji Xu, Horng-Tzer Yau


  • Open Access

    Bulk universality and quantum unique ergodicity for random band matrices in high dimensions

    by Changji Xu, Fan Yang, Horng-Tzer Yau, Jun Yin

    We consider Hermitian random band matrices $H=(h_{xy})$ on the $d$-dimensional lattice $(\mathbb Z/L \mathbb Z)^d$, where the entries $h_{xy}=\overline h_{yx}$ are independent centered complex Gaussian random variables with variances $s_{xy}=\mathbb E|h_{xy}|^2$. The variance matrix $S=(s_{xy})$ has a banded profile so that $s_{xy}$ is negligible if $|x-y|$ exceeds the band width $W$. For dimensions $d\ge 7$, we prove the bulk eigenvalue universality of $H$ under the condition $W \gg L^{95/(d+95)}$. Assuming that $W\geq L^\epsilon $ for a small constant $\epsilon >0$, we also prove the quantum unique ergodicity for the bulk eigenvectors of $H$ and a sharp local law for the Green's function $G(z)=(H-z)^{-1}$ up to ${\mathrm{Im}} \, z \gg W^{-5}L^{5-d}$. The local law implies that the bulk eigenvector entries of $H$ are of order ${\mathrm{O}}(W^{-5/2}L^{-d/2+5/2})$ with high probability.

  • Open Access

    Geometric Barriers for Stable and Online Algorithms for Discrepancy Minimization

    by David Gamarnik, Eren C. Kızıldağ, Will Perkins, Changji Xu

    For many computational problems involving randomness, intricate geometric features of the solution space have been used to rigorously rule out powerful classes of algorithms. This is often accomplished through the lens of the multi Overlap Gap Property ($m$-OGP), a rigorous barrier against algorithms exhibiting input stability. In this paper, we focus on the algorithmic tractability of two models: (i) discrepancy minimization, and (ii) the symmetric binary perceptron (\texttt{SBP}), a random constraint satisfaction problem as well as a toy model of a single-layer neural network. Our first focus is on the limits of online algorithms. By establishing and leveraging a novel geometrical barrier, we obtain sharp hardness guarantees against online algorithms for both the \texttt{SBP} and discrepancy minimization. Our results match the best known algorithmic guarantees, up to constant factors. Our second focus is on efficiently finding a constant discrepancy solution, given a random matrix $\mathcal{M}\in\mathbb{R}^{M\times n}$. In a smooth setting, where the entries of $\mathcal{M}$ are i.i.d. standard normal, we establish the presence of $m$-OGP for $n=Θ(M\log M)$. Consequently, we rule out the class of stable algorithms at this value. These results give the first rigorous evidence towards a conjecture of Altschuler and Niles-Weed~\cite[Conjecture~1]{altschuler2021discrepancy}. Our methods use the intricate geometry of the solution space to prove tight hardness results for online algorithms. The barrier we establish is a novel variant of the $m$-OGP. Furthermore, it regards $m$-tuples of solutions with respect to correlated instances, with growing values of $m$, $m=ω(1)$. Importantly, our results rule out online algorithms succeeding even with an exponentially small probability.