A pseudorandom generator (PRG) stretches a short random seed into a long sequence that "looks Gaussian" to some family of tests. It is the standard tool for replacing random sampling with deterministic enumeration. The hardest common tests are polynomial threshold functions: is a degree-$\ell$ polynomial of the input above or below zero? The yes/no jump at the boundary is what makes them hard. Generators that only need to fool smooth (Lipschitz) functions of a polynomial get by with seeds that grow like $\ell^2$. Generators for the strict yes/no test pay $\ell^{O(\log \ell)}$ or worse, with constants nobody has computed.
This note asks whether star-convexity can close that gap for a large, natural subclass. A set is star-convex, or star-shaped, if every point can see a fixed center along a straight segment that stays inside the set. For such a set, each ray from the center crosses the boundary exactly once. So the Gaussian probability of the set can be computed by integrating out the radius exactly, in one dimension, which leaves only the direction to be fooled. The jump disappears, and what remains is a Lipschitz function of a couple of polynomials. We propose to build the resulting generator, compute its constants explicitly, and test whether the explicit seed length is small enough to be meaningful at realistic dimension and accuracy.
Core Claim
Let $Q$ be a nonnegative homogeneous polynomial of degree $\ell$ on $\mathbb{R}^n$, with $m|x|^\ell \le Q(x) \le M|x|^\ell$ for constants $0<m\le M$. Let $S=\{x: Q(x)\le 1\}$. This set is star-convex about the origin, and every star-shaped sublevel set of this kind is a degree-$\ell$ threshold function. For a standard Gaussian vector $g$, its direction is independent of its length, and the ray in direction $u$ leaves $S$ at radius $Q(u)^{-1/\ell}$. Hence
$$\gamma_n(S)=\mathbb{E}_g\left[F_n\!\left(|g|\,Q(g)^{-1/\ell}\right)\right],$$
where $\gamma_n$ is Gaussian measure and $F_n$ is the cumulative distribution function of the length of an $n$-dimensional standard Gaussian (the chi distribution).
The integrand is a fixed smooth function $H(|g|^2, Q(g))$ of two polynomials, of degrees 2 and $\ell$. After each polynomial is normalized to unit variance, $H$ has a Lipschitz constant bounded by an explicit function of the roundness ratio $M/m$, the degree $\ell$, and the peak density of the chi distribution. The bound $Q \ge m|x|^\ell$ holds at every point, not just in distribution, so pseudorandom inputs cannot drive the function into a steep region.
We therefore conjecture the following. A two-polynomial extension of the Kane–Meka hashing generator fools all such star-shaped thresholds with seed length $(\log n)\,\tilde O(L^2\ell^2/\varepsilon^2)$, where $L$ is that Lipschitz constant. This would replace the $\ell^{O(\log \ell)}$ degree dependence of general threshold-function generators by $\ell^2$, and it needs no smoothing approximation and no anticoncentration argument.
Two existing papers play different roles here.
- A PRG for Lipschitz Functions of Polynomials with Applications to Sparsest Cut builds a generator for one Lipschitz function of one polynomial using hashing, local linearity and bounded independence. It supplies our method. We differ by needing two polynomials, and by producing the Lipschitz structure exactly from geometry rather than assuming it.
- Fooling Gaussian PTFs via local hyperconcentration already fools every degree-$\ell$ threshold, including ours, at seed $d^{O(\log d)}\log n$. It is the result we must beat on this subclass, and it constrains our claim to be a subclass result.
Research Program
Step 1: the theorem. We would extend the Kane–Meka analysis from one polynomial to a fixed number of polynomials. Their local-linearity step approximates a degree-$\ell$ polynomial on each hash bucket by a near-linear function. This should go through coordinate-wise for a vector of polynomials, at the cost of a factor in the number of polynomials. We would then bound $L$ for $H$ explicitly. The chi density peaks at height about $1/\sqrt{\pi}$ independent of $n$. The fluctuations of $|g|^2$ and $Q(g)$ around their means are $O(\sqrt{n})$ and $O(\mathrm{sd}\,Q)$, so in normalized units $L$ should depend on $n$ only through $M/m$. Whether that holds is the first thing the analysis must settle. If $L$ in fact grows with $n$, the seed bound degrades, and we would report that rather than hide it.
The same radial identity extends to a center $x_0\neq 0$. The one-dimensional radial integral then depends on the linear form $\langle x_0,u\rangle$, which adds a third polynomial, of degree 1.
Step 2: what star-convexity buys, and its limit. With $k$ crossings per ray, the conditional probability becomes an alternating sum of $k$ chi-distribution terms evaluated at roots of a one-dimensional polynomial. When two crossings merge, the integrand's slope becomes unbounded. This is the "ray multiplicity" failure that segmentation work runs into on C- and U-shapes, as in TextRay, where radial contours break on tight concavities. It is also a precise version of poor anticoncentration along lines, the obstacle analyzed in A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses. We would prove a lower bound showing that $L$ cannot be bounded once crossing separation goes to zero. That would identify star-convexity, or bounded root separation, as the exact condition under which the cheap generator applies.
Step 3: constants. For the full construction we would track every constant: bucket count, independence level, Taylor remainder, and the $L$ bound. The output is a closed-form seed length in bits at given $(n,\ell,\varepsilon,M/m)$. We would then measure empirically the smallest parameters at which the generator still fools the test. The gap between proven and empirically sufficient parameters is the constant-factor finding. This responds to the file's observation that generator constants are typically never computed.
Baselines
Truly random Monte Carlo (the naive reference). We use plain Monte Carlo estimation of $\gamma_n(S)$ with the same number of samples. Its error scales as $\sqrt{\gamma(1-\gamma)/N}$. Any deterministic method must approach this at equal sample counts to be worth using.
Radially conditioned Monte Carlo. We average $F_n(r(u))$ over truly random directions. This isolates how much of the gain comes from the radial identity alone, before any derandomization. It is the strongest practical competitor.
Scrambled quasi-Monte Carlo. We apply nested uniform scrambling to the radially conditioned integrand, paired with the Lee–Valiant and Minsker–Ndaoud robust mean estimators, following Accelerated convergence of error quantiles using robust randomized quasi Monte Carlo methods. That paper reports quasi-optimal bounds only for one-dimensional integrands, and no numerical error table was found on Lacuna, so we run it ourselves on identical bodies and budgets.
The general threshold-function generator of O'Donnell, Servedio and Tan. This is the strongest existing generator. Its reported seed length is $d^{O(\log d)}\cdot\log n$, also summarized as $\mathrm{poly}(d/\varepsilon)\cdot\log n$, in Fooling Gaussian PTFs via local hyperconcentration. No explicit constants are reported. We will instantiate it with the smallest constants its proof permits and compare explicit bit counts.
Ablation: mollifier route. We apply the same Kane–Meka generator to a smoothed (mollified) version of the indicator $1\{Q\le 1\}$, instead of to the exact radial integrand. This isolates the key ingredient.
Beating the baselines means the following. First, a provably smaller explicit seed than the instantiated O'Donnell–Servedio–Tan bound for $\ell\ge 4$. Second, an empirical fooling error at least as small as the ablation's at equal seed. Third, an error within a small factor of conditioned Monte Carlo at equal sample counts.
Why not just…?
Why not just use radially conditioned Monte Carlo or quasi-Monte Carlo? For someone who only wants a good estimate, this is a real threat and probably the right answer. The radial identity does most of the practical variance reduction, and random directions are simple to draw. Our claim is different: worst-case determinism with a bounded seed. That is what deterministic counting and derandomization arguments need, as in Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions, and there random sampling cannot substitute. The experiments report both, and we will say plainly where the generator is not worth its complexity in practice.
Why not just apply the general threshold-function generator, since star-shaped sets are thresholds anyway? It works, but its degree dependence is $d^{O(\log d)}$ and its constants are uncomputed. The proposal succeeds only if the explicit $\ell^2$ seed beats it at moderate $\ell$. Step 3 is designed to decide this numerically, not rhetorically.
Why not just smooth the indicator and apply the Lipschitz generator? Smoothing introduces an approximation error that must be controlled by anticoncentration of $Q$ near the boundary. That costs extra powers of $1/\varepsilon$ in the Lipschitz constant. The radial identity is exact and has no smoothing error. The mollifier ablation measures this difference directly.
Why not just tune generator parameters empirically? We do exactly that, but as a measurement next to the proven constants, not as a replacement for them. Empirical sufficiency on a test suite says nothing about adversarial bodies. The reported gap shows how loose the proof is.
Proposed Experiments
Test bodies. The bodies are synthetic star-shaped sets in $n\in\{10,100,1000\}$ with known ground truth:
- $\ell_p$ balls for $p\in\{4,6,8\}$, where the Gaussian measure reduces to the distribution of a sum of i.i.d. $|g_i|^p$ and is computable by one-dimensional numerical convolution;
- random positive quartic forms built as sums of squares of random quadratics, with roundness $M/m$ controlled and ground truth from $10^9$ conditioned Monte Carlo samples;
- off-center variants that exercise the linear-form extension.
Ray-multiplicity stress set. A family of non-star-shaped bodies with tunable crossing separation tests Step 2's predicted blow-up.
Metrics. We report absolute fooling error versus seed bits, and error versus sample count. We also report the ratio of proven to empirically sufficient parameters.
Decisive checks. The proposal stands or falls on three outcomes:
- the explicit seed bound is smaller than the instantiated hyperconcentration bound at $\ell\ge 4$;
- the empirically measured $L$ stays flat in $n$ at fixed $M/m$;
- fooling error degrades sharply exactly as crossing separation shrinks on the stress set.
The vision benchmarks in the file (WORM, PARHYALE, BBBC038v1) involve three-dimensional shapes, where generators are irrelevant. We use them only as a sanity check: radial integration over a spherical Fibonacci direction set should reproduce STARDIST-3D polyhedron volumes from Star-convex Polyhedra for 3D Object Detection and Segmentation in Microscopy.
References
- A PRG for lipschitz functions of polynomials with applications to sparsest cut
- Fooling Gaussian PTFs via Local Hyperconcentration
- TextRay: Contour-based Geometric Modeling for Arbitrary-shaped Scene Text Detection
- A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions
- Accelerated convergence of error quantiles using robust randomized quasi Monte Carlo methods
- Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions
- Star-convex Polyhedra for 3D Object Detection and Segmentation in Microscopy