We present a spectral signing algorithm solving the Koml\'os problem with a constant discrepancy in polynomial time. Given a matrix $A\in\mathbb{R}^{m\times n}$ whose columns have Euclidean norm at most $1$, the algorithm finds a vector $\varepsilon\in\{-1,1\}^n$ satisfying $\|A\varepsilon\|_\infty\le C$, where $C$ is...
Let $G$ be the Boolean hypercube which carries uniform measure $\lambda$, and let $T_\mu$ denote convolution by a finite positive measure $\mu$ on $G$. For $\psi_\mu(u)=\sup\{u\lambda(\{T_\mu f\geq u\}):f\geq 0,\|f\|_1=1\},$ we prove Talagrand's convolution conjecture (Talagrand, 1989): if $\mu_a=((1+a)\delta_1/2+(1-a)...
Our main result is a $3\sqrt{2\pi}$ bound for the Koml\'os 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 family size. For any $\kappa\ge0$, if a bounded open convex set supports...
Kalai's cube--simplex conjecture asserts that for all positive integers $\ell,k$, there is an integer $f(\ell,k)$ such that every polytope of dimension at least $f(\ell,k)$ has either a simplex $\ell$-face or a cube $k$-face; let $f_s(\ell,k)$ denote the threshold restricted to simple polytopes. Finiteness of $f(\ell,k...
J. De Loera, Ethan X. Fang, Sheng Guo et al.· 0 citations
We prove that $S^2\times S^3$ admits a Riemannian metric with positive sectional curvature. We view it as a principal circle bundle over $S^2\times S^2$. A diagonal Cheeger deformation of the base and a connection whose curvature form vanishes on the remaining flat tori yield a nonnegatively curved connection metric wh...
Sheng Guo, Ethan X. Fang, Junwei Lu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
