We give a random-bit-efficient construction for the inverse star discrepancy. For every fixed $u\in(0,1)$, $k$-wise independent uniform points $\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N$ with $k=O(d(1+\log(1+N/d)))$ satisfy the Monte Carlo bound $D_N^*(\boldsymbol{X}_1,\ldots,\boldsymbol{X}_N) =O(\sqrt{d/N})$ with probability at least $u$. Consequently, $N=O(d\varepsilon^{-2})$ and $k=O(d(1+\log\varepsilon^{-1}))$ suffice to attain discrepancy at most $\varepsilon$. The proof isolates the finitely many moments required by a chaining argument and gives explicit constants. A random vector-valued polynomial over a finite field realizes the required bounded independence on a grid using $O(d^2(1+\log(1+N/d))\log N)$ random bits, rather than the $\Theta(dN\log(dN))$ bits used by independent grid sampling.
Let $k_{1,\varepsilon}(n)$ be the smallest number of real linear measurements needed by a randomized oblivious sketch that estimates the nuclear norm of every fixed real $n\times n$ matrix within a factor $1\pm\varepsilon$, with probability at least $2/3$. For every fixed $0<\varepsilon<1$, we prove \[ \frac{n^2}{(\log...
We consider the problem of finding lower bounds for integer linear combinations of $\sqrt{a_1},\ldots,\sqrt{a_K}$, where $a_1,\ldots,a_K$ are positive integers such that their square roots are linearly independent over the rationals. We use a probabilistic approach and prove that for any integers $m_1,\ldots,m_K$, not...
Marco Aymone, Samuel Figueredo, Christian Táfula· 0 citations
For positive integers $d$ and $k$, let $n_k(d)$ be the maximum order of a graph of maximum degree at most $d$ and diameter at most $k$. We prove that $$ \lim_{d\to\infty}\frac{n_k(d)}{d^k}=1$$ for every fixed $k$, thereby resolving the asymptotic degree-diameter problem for fixed diameter and proving a conjecture of Bo...
Wouter Cames van Batenburg, Samuel Korsky· 0 citations
A degree-$d$ polynomial source is the output of a polynomial map of degree at most $d$ over $\mathbb{F}_2$ on arbitrarily many uniform random bits. Khodabandeh and Shinkar (FOCS'26) proved that $\mathrm{Ber}(1/3)^{\otimes N}$ has statistical distance $1-o(1)$ from every constant-degree polynomial source and conjectured...
Let $\Omega_n$ denote the set of $n\times n$ doubly stochastic matrices. Kim and Roush conjectured in 1981 that, for $n=2k+1>1$, $ \max_{A\in\Omega_{2k+1}}\operatorname{per}(I-A)=3\cdot 2^{k-2}$. They proposed the block construction $A_\star=\frac12(J_3-I_3)\oplus P_2^{\oplus(k-1)}$, where $P_2=\begin{pmatrix}0&1\\1&0\...
Let $D(N)$ denote the largest cardinality of a subset of $\{1,\ldots,N\}$ containing no nonzero square difference. While a construction certifying $D(N)\geq (1-o(1))N^{1/2}$ is almost trivial, Erd\H{o}s conjectured that this bound is sharp up to polylogarithmic factors. This was disproved by S\'ark\"ozy and later again...
D. Krachun· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
