Abstract Random projections enable efficient dimensionality reduction while preserving geometric structure, with applications spanning accelerating linear algebra computations, differential privacy, and fine-tuning large language models. Variants of the Johnson-Lindenstrauss lemma quantify confidence bounds via Chernoff-type inequalities, yet despite sustained effort, theoretical guarantees remain exponentially weaker than what both known limits and empirical behaviour suggest-gaps often exceeding few orders of magnitude. Closing this gap is both challenging and essential for applicability in non-asymptotic regimes, where precise bounds directly determine computational requirements and guarantees. This paper establishes optimal non-asymptotic concentration bounds for sparse Rademacher projections, achieving the sharp threshold of Burr et al. and improving upon previous results through exponentially better confidence, or equivalently reducing required dimensions by a large factor-observed to be even larger in applications, with extensions to non-oblivious bounds for structured inputs. These results follow from a unified analytical framework of independent interest to probability theory and its applications: a) negative association of moments; b) refined Hanson-Wright-type concentration bounds for randomly masked quadratic chaos achieving optimal constants via rational approximants; and c) precise methods for aggregating conditional Bernstein-type bounds.

This paper develops sharp bounds on moments of sums of k-wise independent bounded random variables, under constrained average variance. The result closes the problem addressed in part in the previous works of Schmidt et al. and Bellare, Rompel. The work also discusses other applications of independent interests, such as asymptotically sharp bounds on binomial moments.

This work shows how the performance of sparse random embeddings depends on the Renyi entropy-like property of data, improving upon recent works from NIPS'18 and NIPS'19. While the prior works relied on involved combinatorics, the novel approach is simpler and modular. As the building blocks, it develops the following probabilistic facts of general interest: b) a comparison inequality between the linear and quadratic chaos c) a comparison inequality between heterogenic and homogenic linear chaos d) a simpler proof of Latala’s strong result on estimating distributions of IID sums e) sharp bounds for binomial moments in all parameter regimes.

We show that the most common flavors of noisy leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to a small statistical simulation error and a slight loss in the leakage parameter. The latter holds true in particular for one of the most used noisy-leakage models, where the noisiness is measured using the conditional average min-entropy (Naor and Segev, CRYPTO’09 and SICOMP’12). Our reductions between noisy and bounded leakage are achieved in two steps. First, we put forward a new leakage model (dubbed the dense leakage model) and prove that dense leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to small statistical distance. Second, we show that the most common noisy-leakage models fall within the class of dense leakage, with good parameters. Third, we prove lower bounds on the amount of bounded leakage required for simulation with sub-constant error, showing that our reductions are nearly optimal. In particular, our results imply that useful general simulation of noisy leakage based on statistical distance and mutual information is impossible. We also provide a complete picture of the relationships between different noisy-leakage models. Our result finds applications to leakage-resilient cryptography, where we are often able to lift security in the presence of bounded leakage to security in the presence of noisy leakage, both in the information-theoretic and in the computational setting. Remarkably, this lifting procedure makes only black-box use of the underlying schemes. Additionally, we show how to use lower bounds in communication complexity to prove that bounded-collusion protocols (Kumar, Meka, and Sahai, FOCS’19) for certain functions do not only require long transcripts, but also necessarily need to reveal enough information about the inputs.

The proper {\em initialization of weights} is crucial for the effective training and fast convergence of {\em deep neural networks} (DNNs). Prior work in this area has mostly focused on the principle of {\em balancing the variance among weights per layer} to maintain stability of (i) the input data propagated forwards through the network, and (ii) the loss gradients propagated backwards, respectively. This prevalent heuristic is however agnostic of dependencies among gradients across the various layers and captures only first-order effects per layer. In this paper, we investigate a {\em unifying approach}, based on approximating and controlling the {\em norm of the layers’ Hessians}, which both generalizes and explains existing initialization schemes such as {\em smooth activation functions}, {\em Dropouts}, and {\em ReLU}.

The seminal result of Johnson and Lindenstrauss on random embeddings has been intensively studied in applied and theoretical computer science. Despite that vast body of literature, we still lack of complete understanding of statistical properties of random projections; a particularly intriguing question is: why are the theoretical bounds that far behind the empirically observed performance? Motivated by this question, this work develops Johnson-Lindenstrauss distributions with optimal, data-oblivious, statistical confidence bounds. These bounds are numerically best possible, for any given data dimension, embedding dimension, and distortion tolerance. They improve upon prior works in terms of statistical accuracy, as well as exactly determine the no-go regimes for data-oblivious approaches. Furthermore, the projection matrices are efficiently samplable. The construction relies on orthogonal matrices, and the proof uses certain elegant properties of the unit sphere. In particular, the following techniques introduced in this work are of independent interest: a) a compact expression for the projection distortion in terms of singular eigenvalues of the projection matrix, b) a parametrization linking the unit sphere and the Dirichlet distribution and c) anti-concentration bounds for the Dirichlet distribution. Besides the technical contribution, the paper presents applications and numerical evaluation along with working implementation in Python (shared as a GitHub repository).

The brilliant method due to Good and Turing allows for estimating objects not occurring in a sample. The problem, known under names “sample coverage” or “missing mass” goes back to their cryptographic work during WWII, but over years has found has many applications, including language modeling, inference in ecology and estimation of distribution properties. This work characterizes the maximal mean-squared error of the Good-Turina estimator, for any sample and alphabet size.

Determining entropy rates of stochastic processes is a fundamental but difficult problem, with closed-form solutions known only for specific cases. This paper pushes the state-of-the-art by solving the problem for Hidden Markov Models (HMMs) and Renyi entropies. While computation of Renyi entropy for Markov chains reduces to studying the growth of a simple matrix product, computations for HMMs involve products of random matrices. As a result, this case is much harder and no explicit formulas have been known so far. In the finite-sample regime we circumvent this issue for Renyi entropy of integer orders, reducing the problem again to single matrix products where the matrix is built from transition and emission probabilities by means of tensor products. To obtain results in the asymptotic setting, we use a novel technique for determining the growth of non-negative matrix powers. The classical approach - Frobenius-Perron theory - requires positivity assumptions; we instead work directly with the spectral formula. As a consequence, our results do not suffer from limitations such as irreducibility and aperiodicity. This improves our understanding of the entropy rate even for standard (unhidden) chains. A recently published side-channel attack against RSA was proven effective using our result.

Estimating entropy of random processes is one of the fundamental problems of machine learning and property testing. It has numerous applications to anything from DNA testing and predictability of human behaviour to modeling neural activity and cryptography. We investigate the problem of Renyi entropy estimation for sources that form Markov chains. Kamath and Verd (ISIT'16) showed that good mixing properties are essential for that task. We prove that even with very good mixing time, estimation of entropy of order α > 1 requires Ω(K2-1/α) samples, where K is the size of the alphabet; particularly min-entropy requires Ω(K2) sample size and collision entropy requires Ω(K3/2) samples. Our results hold both in asymptotic and non-asymptotic regimes (under mild restrictions). The analysis is completed by the upper complexity bound of O(K2) for the standard plug-in estimator. This leads to an interesting open question how to improve upon a plugin estimator, which looks much more challenging than for IID sources (which tensorize nicely). We achieve the results by applying Le Cam's method to two Markov chains which differ by an appropriately chosen sparse perturbation; the discrepancy between these chains is estimated with help of perturbation theory. Our techniques might be of independent interest.

This paper discusses Bayes factors, an alternative to classical frequentionist hypothesis testing, within the standard A/B proportion testing setup - observing outcomes of independent trails (which finds applications in industrial conversion testing). It is shown that the Bayes factor is controlled by the Jensen-Shannon divergence of success ratios in two tested groups, and the latter one is bounded (under mild conditions) by Welch’s t-statistic. The result implies an optimal bound on the necessary sample size for Bayesian testing, and demonstrates the relation to its frequentionist counterpart (effectively bridging Bayes factors and p-values).

It is well established that the notion of min-entropy fails to satisfy the chain rule of the form H(X, Y ) = H(X/Y ) + H(Y ), known for Shannon Entropy. The lack of a chain rule causes a lot of technical difficulties, particularly in cryptography where the chain rule would be a natural way to analyze how min-entropy is split among smaller blocks. Such problems arise for example when constructing extractors and dispersers. We show that any sequence of variables exhibits a very strong strong block-source structure (conditional distributions of blocks are nearly Hat) when we spoil few correlated bits. This implies, conditioned on the spoiled bits, that splitting-recombination properties hold. In particular, we have many nice properties that minentropy doesn't obey in general, for example strong chain rules, “information can't hurt” inequalities, equivalences of average and worst-case conditional entropy definitions and others. Quantitatively, for any sequence X1,. .. , Xt of random variables over an alphabet X we prove that, when conditioned on m = t O(log log |X| + log log(1/ε) + logt) bits of auxiliary information, all conditional distributions of the form X% X<;% are ε-close to be nearly Hat (only a constant factor away). The argument is combinatorial (based on simplex coverings). This result may be used as a generic tool for exhibiting blocksource structures. We demonstrate this by reproving the fundamental converter due to Nisan and Zuckermann (J. Computer and System Sciences, 1996), which shows that sampling blocks from a min-entropy source roughly preserves the entropy rate. Our bound implies, only by straightforward chain rules, an additive loss of o(1) (for sufficiently many samples), which qualitatively meets the first tighter analysis of this problem due to Vadhan (CRYPTO'03), obtained by large deviation techniques.

Universal hashing found a lot of applications in computer science. In cryptography the most important fact about universal families is the so called Leftover Hash Lemma, proved by Impagliazzo, Levin and Luby. In the language of modern cryptography it states that almost universal families are good extractors. In this work we provide a somewhat surprising characterization in the opposite direction. Namely, every extractor with sufficiently good parameters yields a universal family on a noticeable fraction of its inputs. Our proof technique is based on tools from extremal graph theory applied to the “collision graph” induced by the extractor, and may be of independent interest. We discuss possible applications to the theory of randomness extractors and non-malleable codes.

We revisit the problem of estimating entropy of discrete distributions from independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA 2015), improving their upper and lower bounds on the necessary sample size n. For estimating Renyi entropy of order alpha, up to constant accuracy and error probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha} for integer alpha>1, as the worst case over distributions with Renyi entropy equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha>1, with the constant being an inverse polynomial of the accuracy, as the worst case over all distributions on K elements. Our upper bounds essentially replace the alphabet size by a factor exponential in the entropy, which offers improvements especially in low or medium entropy regimes (interesting for example in anomaly detection). As for the lower bounds, our proof explicitly shows how the complexity depends on both alphabet and accuracy, partially solving the open problem posted in previous works. The argument for upper bounds derives a clean identity for the variance of falling-power sum of a multinomial distribution. Our approach for lower bounds utilizes convex optimization to find a distribution with possibly worse estimation performance, and may be of independent interest as a tool to work with Le Cam’s two point method.

De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over $n$-bit strings which has constant statistical distance to uniform (e.g., the output of a pseudorandom generator mapping $n-1$ to $n$ bit strings), can be distinguished from the uniform distribution with advantage $ε$ by a circuit of size $O( 2^nε^2)$. We generalize this result, showing that a distribution which has less than $k$ bits of min-entropy, can be distinguished from any distribution with $k$ bits of $δ$-smooth min-entropy with advantage $ε$ by a circuit of size $O(2^kε^2/δ^2)$. As a special case, this implies that any distribution with support at most $2^k$ (e.g., the output of a pseudoentropy generator mapping $k$ to $n$ bit strings) can be distinguished from any given distribution with min-entropy $k+1$ with advantage $ε$ by a circuit of size $O(2^kε^2)$. Our result thus shows that pseudoentropy distributions face basically the same non-uniform attacks as pseudorandom distributions.

This paper studies the complexity of estimating Rényi divergences of discrete distributions: p observed from samples and the baseline distribution q known a priori. Extending the results of Acharya et al. (SODA'15) on estimating Rényi entropy, we present improved estimation techniques together with upper and lower bounds on the sample complexity. We show that, contrarily to estimating Rényi entropy where a sublinear (in the alphabet size) number of samples suffices, the sample complexity is heavily dependent on events occurring unlikely in q, and is unbounded in general (no matter what an estimation technique is used). For any divergence of integer order bigger than 1, we provide upper and lower bounds on the number of samples dependent on probabilities of p and q (the lower bounds hold for non-integer orders as well). We conclude that the worst-case sample complexity is polynomial in the alphabet size if and only if the probabilities of q are non-negligible. This gives theoretical insights into heuristics used in the applied literature to handle numerical instability, which occurs for small probabilities of q. Our result shows that they should be handled with care not only because of numerical issues, but also because of a blow up in the sample complexity.

Security of cryptographic applications is typically defined by security games. The adversary, within certain resources, cannot win with probability much better than 0 (for unpredictability applications, like one-way functions) or much better than 1/2 (indistinguishability applications for instance encryption schemes). In so called squared-friendly applications the winning probability of the adversary, for different values of the application secret randomness, is not only close to 0 or 1/2 on average, but also concentrated in the sense that its second central moment is small. The class of squared-friendly applications, which contains all unpredictability applications and many indistinguishability applications, is particularly important for key derivation. Barak et al. observed that for square-friendly applications one can beat the "RT-bound", extracting secure keys with significantly smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications one can directly use a "weak" key, which has only high entropy, as a secure key. In this paper we give sharp lower bounds on square security assuming security for "weak" keys. We show that any application which is either (a) secure with weak keys or (b) allows for entropy savings for keys derived by universal hashing, must be square-friendly. Quantitatively, our lower bounds match the positive results of Dodis and Yu and Barak et al. (TCC'13, CRYPTO'11) Hence, they can be understood as a general characterization of squared-friendly applications. While the positive results on squared-friendly applications where derived by one clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we need more machinery. In our approach we use convex optimization techniques and some theory of circular matrices.