We initiate the study of *unate distributions* over $\{\pm1\}^n$ -- a natural analogue of unate Boolean functions -- by considering two basic testing problems that parallel well-studied questions for monotone distributions: - Uniformity Testing of Unate Distributions: We show that $\widetilde{\Theta}(n^{3/2})$ samples are sufficient and necessary, in contrast to the $\widetilde{\Theta}(n)$ sample complexity of the analogous problem for monotone distributions (Rubinfeld and Servedio, STOC 2005; Adamaszek, Czumaj, and Sohler, SODA 2010). - Unateness Testing of Arbitrary Distributions: We give a tester that uses $\widetilde{O}(n^{3/2})$ conditional samples in the subcube conditional model. On the other hand, every tester that draws conditional samples in a similar fashion, namely from $O(1)$-dimensional subcubes, must have an $\widetilde{\Omega}(n^{2/3})$ complexity. In the same model, the complexity of monotonicity testing was recently shown to be $\widetilde{\Theta}(n)$ (Chakrabarty et al., STOC 2025). Our algorithms for both problems significantly outperform the naive approach of reducing to the monotone case, which would incur $\Omega(n^2)$ sample complexity. Our uniformity tester relies on a subroutine that"weakly"learns the hidden orientations of a unate distribution, together with a new correlation bound for these estimates. Both tools may be of independent interest in studying monotonicity and unateness over $\{\pm1\}^n$.
Given $[0,1]$-valued random variables $X_1,\dots,X_n$ such that $\mathbb{E}[X_i | X_1,\dots,X_{i-1}]= \mu$ for all $i$, we propose a new nonasymptotic confidence interval for $\mu$ that is obtained by inverting terminal e-values generated by a novel betting strategy. When the data are iid, its limiting width matches that of the central limit theorem (``Gaussian-efficient''), finally surpassing the inefficient limits of previous betting intervals. Our main conceptual advance involves designing betting fractions that track the conditional rejection probability of the most powerful terminal test in a limiting Gaussian experiment. When one predictable variance estimator is shared across candidate means, the deterministic inversion is an interval for every data sequence and its two endpoints can be found easily. The width can be improved further with external randomization. In simulations, our method yields the tightest intervals to date; for every distribution tested and all sufficiently large $n$, our deterministic version beats STaR-Bets and is competitive with Gaffke, while the randomized improvement beats both. It thus combines finite-sample validity under martingale dependence, easy endpoint computation, Gaussian-efficient inference for iid data, and excellent empirical performance. We also extend the construction and its efficiency theory to sampling without replacement, where it again achieves state-of-the-art empirical performance.
Diego Martinez-Taboada, Aaditya Ramdas· 0 citations
Let $P$ be a finite nonempty poset with $n$ elements, let $f:P\to\{1,\ldots,n\}$ be a uniformly random order-preserving bijection, and put $h_P(x)=\mathbb E[f(x)]$. Define $\operatorname{gap}(P)$ as the largest difference between consecutive values in the ordered list consisting of $0$, $n+1$, and all the expected ranks $h_P(x)$. Write $w(P)$ for the largest size of a pairwise incomparable subset. We prove three results. The first proves an old conjectural relation between width and expected-rank gaps that has appeared repeatedly, in increasingly general forms, in work of Brightwell and Trotter (2002), Bir\'o and Trotter (2011), and Aires and Kahn (2025): $\operatorname{gap}(P)\le 2w(P)-1$. Second, for every $L>0$ we construct a width-two poset such that every maximal chain has an expected-rank gap of at least $L$, where the two endpoint spacings are included when computing this gap. Finally, for every $r\in\mathbb N$, we construct a poset $P_r$ for which the relative order induced on every nonempty selected set $X$ has base-two entropy below $3|X|$, while $\operatorname{gap}(P_r)\ge(3/2)^r$. Thus the gap can be arbitrarily large while the induced order on every selected set has relatively small entropy. The key ideas behind all three results were found by ChatGPT 5.6 Sol.
A long-standing question posed by Fukuda (1995) and Ziegler (2000) inquires about the asymptotic behavior of $g(n)$, the maximum number of facets that an $n$-dimensional $0/1$-polytope can have. A remarkable result by B\'ar\'any and P\'or (2001) via probabilistic methods established that $g(n)$ is at least superexponential in $n$. In this paper, we propose a drastic change of perspective, which leads us to show that for each $n\geq 10$ there exists a $0/1$-polytope having at least $(n-\lceil 2\log_2 (n)\rceil - 1)!$ facets. This provides a significant improvement over the currently known lower bounds for $g(n)$. Furthermore, when combined with known upper bounds, our construction establishes the asymptotic behavior of $\log g(n)$ up to an error of $O((\log n)^2)$. The methods employed throughout this paper are elementary and fully deterministic. The underlying ideas in our proof stem from the combinatorics of hypersimplices and permutohedra.
Every fixed first-order sentence $\varphi$ determines an enumerative sequence $n\mapsto\mathrm{FOMC}(\varphi,n)$, counting its models on the labeled domain $[n]$. We study the complexity of these sequences when logical specifications may use genuine unary function symbols and hence nested terms $x,f(x),f^2(x),\ldots$. We first prove that, for every fixed sentence $\varphi\in\mathrm{C}^1_{=}[f]$, with one unary function and an arbitrary finite relational vocabulary, $\mathrm{FOMC}(\varphi,n)$ is computable in time polynomial in $n$. By contrast, permitting either a second variable or a second unary function already yields hardness. Without counting quantifiers, there is a fixed sentence in $\mathrm{FO}^2_{=}[f]$ whose model-counting function is $\#\mathrm{P}_1$-complete. With one variable and two unary functions, there is a fixed constant-free universal sentence in $\mathrm{FO}^1_{=}[f,g]$, using only unary predicates besides $f$ and $g$, whose model-counting function is again $\#\mathrm{P}_1$-complete. We also relate labeled and unlabeled enumeration exactly. For every relational sentence $\varphi$, we construct an extension $\varphi_{\mathrm{aut}}$ in which a unary function records an automorphism and $\mathrm{FOMC}(\varphi_{\mathrm{aut}},n)=n!\cdot\mathrm{UFOMC}(\varphi,n)$, where $\mathrm{UFOMC}(\varphi,n)$ denotes the number of $n$-element models of $\varphi$ up to isomorphism. Thus automorphism marking gives a one-query exact reduction from unlabeled to labeled model counting at the same domain size. Over relational vocabularies of maximum arity at most $k$, where $k\geq2$, eliminating the auxiliary function yields single-query reductions from unlabeled $\mathrm{FO}^k_{=}$ and $\mathrm{C}^k$ model counting to labeled $\mathrm{FO}^{k+1}_{=}$ and $\mathrm{C}^{k+1}$ model counting, respectively.
In this note, we introduce the notion of ranked spreadness, a strengthening of the usual spread condition in which the elements of each member can be ordered so that their one-coordinate marginals decay geometrically with their rank. This additional structure removes the dependence on the maximum set size in random-containment estimates. We prove width-free hitting and weighted-concentration theorems for ranked-spread set systems, together with an elementary kernel-extraction theorem showing that ranked spreadness arises naturally in arbitrary distributions on small sets. Our main application is to the simulation of nonadaptive property testers by sample-based testers. If a one-sided tester has average query complexity $d$ and rejects every far input with probability at least $\delta$, then, for every integer $c>d/\delta$, it admits a one-sided sample-based simulation with expected sample complexity $O_{d,\delta,|\Sigma|}\bigl(n^{1-1/c}\bigr)$. More generally, if positive inputs are rejected with probability at most $\gamma$ and far inputs with probability at least $\delta>\gamma$, the same conclusion holds for every $c>d/(\delta-\gamma)$. In particular, for constant-query nonadaptive testers we obtain an exponent $1-\Theta(1/q)$, matching, up to the dependence on the rejection gap, the exponent conjectured by Fischer, Lachish, and Vasudev.
The optimal sample complexity of testing if an $n$-vertex graph has an independent set of size $\rho n$, or is $\varepsilon$-far from having an independent set of size $\rho n$, was established to be $\widetilde{O}(\rho^3/\varepsilon^2)$, in a notable result by Blais and Seth (SICOMP 2025). In contrast, for $q$-uniform hypergraphs, there is a significant gap between the best known upper and lower bounds, and there has been no progress on the problem for the last two decades. In this work, we prove a new upper bound of $\widetilde{O}\!\left(\frac{q\rho^{2q-3}}{\varepsilon^2 (q-2)!^2}\right)$ on the sample complexity of testing the $\rho$-independent set property. The previous best known upper bound was $\widetilde{O}\!\left(\frac{2^q q! \rho^{2q}}{\varepsilon^3}\right)$, due to Langberg (RANDOM 2004). This establishes the optimal dependence on $\varepsilon$ and gives an exponential improvement in the dependence on $q$. We prove our result via a new application of the hypergraph container method.
Elena Grigorescu, Shreya Nasa, Cameron Seth· 1 citation