Papers

For positive definite matrices let $A\#_tB=A^{1/2}(A^{-1/2}BA^{-1/2})^tA^{1/2}$. The note disproves the norm inequality $\|\sum_i(A_i^s\#_tB_i^s)^r\|\le\|(A^{(1-t)srp/2}B^{tsrp}A^{(1-t)srp/2})^{1/p}\|$, with $A=\sum_iA_i$ and $B=\sum_iB_i$, conjectured for every unitarily invariant norm, $0\le t\le1$ and $p,r,s>0$ with $sr\ge1$. It fails for two rational positive definite $2\times2$ summands, the operator …

For positive definite $A,B$ and $0\le t\le1$, the conjecture asserts the log-majorization $s(A^t(A\#_tB)B^{1-t})\prec_{\log}s(AB)$ of singular values, where $\#_t$ is the weighted geometric mean. The note disproves even the largest-singular-value inequality: for $A=\operatorname{diag}(256,1/256,1)$, an explicit integer positive definite $3\times3$ matrix $B$ …

For positive definite matrices let $A\#_{r,t}B=A^{r/2}(A^{-1/2}BA^{-1/2})^tA^{r/2}$. The note disproves the conjectured eigenvalue log-majorization $\lambda((A\#_{r,t}B)^p(A\#_{s,1-t}B)^p)\prec_{\log}\lambda(A^{p(r+s-1)}B^p)$ for $0\le t\le1$, $p\ge1$ and either $r,s\ge1$ or $r,s\le0$. It fails for $r=s=1$, $p=2$ and $t=1/8$, with $A=D^2$ and $B=DT^8D$, where $D=\operatorname{diag}(16,1/12,1)$ and $T$ is an …

The question is whether, for every real-valued concave function $f$ on $[0,\infty)$ with $f(0)\ge0$, not assumed monotone, and all positive semidefinite $A,B$, there are unitaries $U,V$ with $f(A+B)\le Uf(A)U^*+Vf(B)V^*$. The note shows that this fails in dimension two. For $f(t)=t-t^2$, …

The determinant comparison $\det(A^k+|AB|^p)\ge\det(A^k+|BA|^p)$, for positive definite $A$, invertible Hermitian $B$ and $k,p\ge0$, fails for real matrices of order three with $k=6$ and $p=8$. One may take $A=\operatorname{diag}(2,1,1/2)$ and $B=\frac15\begin{pmatrix}-1&2&0\\2&1&2\\0&2&1\end{pmatrix}$, which is symmetric with $\det B=-1/125$. Since $|AB|^2=BA^2B$ and $|BA|^2=AB^2A$, …

The paper proves that there are universal constants $C, c > 0$ and a randomized floating-point algorithm which, given $A \in \mathbb{C}^{n \times n}$ with $\|A\|_2 \le 1$ and $0 < \delta < 1/2$, uses at most $Cn^3\log^c(n/\delta)$ arithmetic operations …

For every odd $n$, every nonsingular $n\times n$ sign matrix satisfies $\kappa_2(A)\ge\sqrt{1+(n-1)/n^2}+\sqrt{n-1}/n$. Hence $h(n)-1\ge\sqrt{n-1}/n$ along the odd orders, and the optimal uniform decay exponent satisfies $\alpha_*\le1/2$. The proof bounds the variance $v$ of the eigenvalues of the Gram matrix $A^TA$, …

Let $C_k$ be the permutation matrix of a directed $k$-cycle, and let $A=\operatorname{diag}(\tfrac12,C_2,C_4)$. This is an entrywise nonnegative real $7\times7$ matrix with characteristic polynomial $p(z)=(z-\tfrac12)(z^2-1)(z^4-1)$. The normalized derivative $q=p'/7$ is not the characteristic polynomial of any entrywise nonnegative real $6\times6$ …

The Laurent polynomial $b(z)=-64z^{-2}+8z^{-1}-128-8z-63z^2-16z^3-z^4$ is real on a star-shaped Jordan curve in $\mathbb C\setminus\{0\}$ enclosing zero, yet its $2\times2$ Toeplitz section has the nonreal eigenvalues $-128\pm8i$. The curve is $\{\rho(t)e^{it}\}$, where $\rho(t)\in(1/2,2)$ is the root of $r^2-1+\tfrac{r^3}{4}\cos t=0$, unique by …

For a diagonalizable complex $n \times n$ matrix $A$ accessed only through exact products $v \mapsto Av$, with a supplied bound $K \ge 1$ on the condition number of an eigenvector matrix and positive spectral radius $\rho$, a randomized algorithm …

Let $A=\operatorname{diag}(S,\tfrac12 J)$, where $S$ is the $2\times2$ swap matrix and $J$ the $2\times2$ all-ones matrix. It is a real symmetric, entrywise nonnegative, stochastic $4\times4$ matrix with spectrum $\{1,1,0,-1\}$ and trace one, and it is spectrally unique up to permutation. …

Let $A\in\mathbb R^{n\times n}$ be symmetric and $V\in\mathbb R^{n\times p}$ of full column rank, and suppose the block Krylov space $\mathcal K_s$ has full dimension $sp$. For all $1\le k<j\le s$ and $1\le i\le(k-1)p$, with Ritz values listed with multiplicity, …

For real data $U$, consider the real stationary pairs $(X,c)$ with $|\det X|=1$ and $X^{T}(U-X)=cI$, and the rule that selects a pair with smallest $|c|$ as the nearest such matrix in Frobenius norm. The rule fails for every diagonal $U=\operatorname{diag}(s_1,s_2,s_3)$ …

For real symmetric positive definite $n\times n$ matrices $A$ and $B$, the operator $\mathcal L(X)=AXB+BXA$, whose matrix under column vectorization is $A\otimes B+B\otimes A$, has a nonzero real positive-semidefinite eigenmatrix for its smallest eigenvalue. The inverse of $\mathcal L$ is …

Our main result is a $3\sqrt{2π}$ bound for the Komlós signing problem: every finite family of real vectors of Euclidean norm at most one admits a signed sum of $\ell_\infty$-norm less than this constant, independently of the dimension and the …

In this paper, we consider $2\times2$ hyperbolic systems of conservation laws in one spatial dimension. We use the computational ansatz introduced in the hyperbolic theory by the author and Székelyhidi to study the constitutive set corresponding to the PDE. The …

Forsythe's conjecture, published in 1968, asserts that for each restart length $s$, every exact-arithmetic restarted conjugate-gradient iteration on a real symmetric positive definite problem either terminates or has normalised residuals that converge separately along the even and odd restart subsequences. …

We construct an endpoint map with no regular values, disproving the sub-Riemannian Sard conjecture. Remarkably, in our construction the minimizing Sard property remains valid.

We develop a novel approach to matrix discrepancy based on matrix small-ball estimates. Specifically, we use a determinantal weight (obtained from the log-barrier) to scale the small-ball probability into a partition function of a tilt of the Gaussian measure. We …

We establish a sharp phase transition for fitting random vectors by an ellipsoid. The random vectors have independent subgaussian coordinates with mean zero, variance one, and a common fourth moment, and the number of vectors is proportional to the square …

The entanglement of purification $E_P$, introduced by Terhal, Horodecki, Leung, and DiVincenzo in 2002, measures the total correlations of a bipartite state by the entanglement needed to purify it; whether it is additive on tensor powers has been open since …

We study the nonconvex optimization landscapes of synchronization problems on spheres. First, we present new results for the statistical problem of synchronization over the two-element group $\mathbf{Z}_2$. We consider the nonconvex least-squares problem with $\mathbf{Z}_2 = \{\pm 1\}$ relaxed to …

We study synchronization in the Kuramoto model on finite graphs. We prove that there is an absolute constant $η>0$ such that every finite simple graph $G$ on $n$ vertices with minimum degree at least $(3/4-η)n$ has no local minima of …

We resolve the ellipsoid fitting conjecture of Saunderson, Chandrasekaran, Parrilo, and Willsky up to a vanishing factor. Concretely, for $m$ independent Gaussian points in dimension $d$, we show that with high probability, for $m \leq (1-o_d(1)) \cdot d^2/4$, there exists …

Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid …

We confirm the Kannan--Lovász--Simonovits conjecture for quadratic forms: if $X \sim μ$ is an isotropic log-concave random vector in $\mathbb{R}^n$, then for any symmetric matrix $M$ one has $$ \operatorname{Var}_{X \sim μ}(\langle MX,X\rangle) \leq 2\,\mathbb{E}_{X \sim μ}|\nabla\langle MX,X\rangle|^2. $$ As …

We prove that, for every fixed degree $d$ and a uniformly random simple $d$-regular graph $G_{n,d}$ on an even number $n>d$ of vertices, $$\mathbb{E}\operatorname{MaxCut}(G_{n,d})-\mathbb{E}\operatorname{MaxBis}(G_{n,d})=o(n).$$ In other words, requiring the two sides of a cut to have exactly the same size …

Let $\mathbb F\in\{\mathbb R,\mathbb C\}$ and $d_{\mathbb F}=\dim_{\mathbb R}\mathbb F$. If $A_m\in\mathbb F^{N_m\times m}$ has independent standard Gaussian entries and $N_m/m\toγ>1$, then \[ \min_{\substack{T\subset[N_m]\\ |T|=m}} σ_{\min}(A_{m,T}) = \left(\frac{γ^γ}{(γ-1)^{γ-1}}\right)^{-m/d_{\mathbb F}+o_P(m)} . \] If $N_m=γm+O(1)$, the convergence of $m^{-1}\log M_m^{\mathbb F}$ has …

We prove the group version of the Matrix Spencer conjecture. For every finite group $G$, there exist signs $\varepsilon\in\{\pm1\}^G$ such that $$\left\| \sum_{g\in G} \varepsilon_gρ(g) \right\|\leq C\, \sqrt{|G|},$$ where $ρ$ is the left regular representation of $G$ and $C$ is …

In this short note, we prove that if $A \in \mathbb C^{N \times M}$ with $N=4M-5$ has i.i.d.\ standard complex Gaussian entries, then the probability that the phase retrieval map generated by $A$ is not injective is positive. This proves …

We prove a degree-four Sum-of-Squares lower bound for the standard vector-coordinate formulations of mutually unbiased bases. For every dimension $d$ and every proposed number $m$ of bases, we construct a degree-four pseudoexpectation satisfying the orthonormality constraints and the cross-unbiasedness constraints …

We study the regularity and branching of strictly abnormal minimizing geodesics in sub-Riemannian geometry. We construct examples of real-analytic sub-Riemannian manifolds admitting minimizing geodesics that lose regularity at an interior point of their domain and exhibit branching, thereby resolving longstanding …

50 years after Thompson's famous triangle inequality for the operator right modulus, we establish a triangle inequality for the quadratic symmetric modulus. We also discuss the corresponding equality cases as well as the infinite-dimensional setting. In addition, we obtain Clarkson--McCarthy …

We prove that for supercritical percolation on every infinite transitive graph, the probability that the origin belongs to a finite cluster of size at least $n$ decays exponentially in $Φ(n)$, where $Φ$ is the isoperimetric function of the graph.

We study the computational phase transition in a multi-frequency group synchronization problem, where pairwise relative measurements of group elements are observed across multiple frequency channels and corrupted by Gaussian noise. Using the framework of \emph{low-degree polynomial algorithms}, we analyze the …

In 1987 Hiroshi Maehara conjectured that a graph can be represented by vectors considered adjacent when not orthogonal (a faithful orthogonal representation) in codimension the minimum degree of the graph. Without settling the conjecture, Làslò Lovàsz, Michael Saks, and Alexander …

In this work, we revisit algorithms for Tensor PCA: given an order-$r$ tensor of the form $T = G+λ\cdot v^{\otimes r}$ where $G$ is a random symmetric Gaussian tensor with unit variance entries and $v$ is an unknown boolean vector …

In this work, we analyze the asymptotic convergence factor of minimal residual iteration (MRI) (or GMRES(1)) for solving linear systems $Ax=b$ based on vector-dependent nonlinear eigenvalue problems. The worst-case root-convergence factor is derived for linear systems with $A$ being symmetric …

By finding orthogonal representation for a family of simple connected called $δ$-graphs it is possible to show that $δ$-graphs satisfy delta conjecture. An extension of the argument to graphs of the form $\overline{P_{Δ(G)+2}\sqcup G}$ where $P_{Δ(G)+2}$ is a path and …

The largest Hamming distance between a Boolean function in $n$ variables and the set of all affine Boolean functions in $n$ variables is known as the covering radius $ρ_n$ of the $[2^n,n+1]$ Reed-Muller code. This number determines how well Boolean …

We show that Laplacian and symmetric diagonally dominant (SDD) matrices can be well approximated by linear-sized sparse Cholesky factorizations. We show that these matrices have constant-factor approximations of the form $L L^{T}$, where $L$ is a lower-triangular matrix with a …

In 2006, 9-variable Boolean functions having nonlinearity 241, which is strictly greater than the bent concatenation bound of 240, have been discovered in the class of Rotation Symmetric Boolean Functions (RSBFs) by Kavut, Maitra and Yucel. To improve this nonlinearity …

We give coordinate-minimal geometric realizations in general position of all 865 vertex-minimal triangulations of the orientable surface of genus 2 in the 4x4x4-cube.