We prove that every $n$-point set in the plane has a two-coloring with discrepancy $O(n^{1/4})$ for all triangles. This improves the previous bound $O(n^{1/4}\sqrt{\log n})$ and matches the classical lower bound.
We prove that every $n$-point set in the plane has a two-coloring with discrepancy $O(n^{1/4})$ for all triangles. This improves the previous bound $O(n^{1/4}\sqrt{\log n})$ and matches the classical lower bound.
Let $X=(X_1,\dots,X_n)\in\{0,1\}^n$ have a multivariate totally positive ($\mathrm{MTP}_2$) law. We prove that $$ \sum_{i<j}\mathbb{E}\left[\left|\mathrm{Cov}(X_i,X_j \mid X_{[n]\setminus\{i,j\}})\right|\right] \le n/2, $$ and more generally a weighted MaxCut inequality for the fully conditioned covariances. As an appl...
We prove that every strictly positive probability distribution on \(\{-1,1\}^n\) is represented exactly by a sigmoid belief network with finite parameters. This answers a question of Sutskever and Hinton. The proof upgrades their probability-sharing approximation to exact representation using Brouwer's fixed-point theo...
Gleb Smirnov· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.