Andrej Bogdanov

Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta et al.

We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix $\mathbf{A} \in \mathbb{R}^{m\times n}$, an input $\mathbf{x} \in \{-1,1\}^n$ is mapped to a binary output vector $φ(\mathbf{A}\mathbf{x})\in \{-1,1\}^m$, where $φ$ is an activation function with constant behavior on $[κ, \infty)$ for some threshold $κ\geq 0$. We identify the threshold scale $κ=Θ(1/\sqrtα)$, where $α=m/n$, as separating two complementary phenomena. When $κ\ll 1/\sqrtα$, we give a simple online algorithm that efficiently produces extensive collisions. When $κ\gg 1/\sqrtα$, for a natural \emph{randomized} non-periodic activation and suitable oscillation complexity, we prove that the extensive-collision space exhibits an overlap gap property (OGP), yielding an exponential lower bound against online algorithms. Ours is the first work to use the overlap gap property as a rigorous criterion for collision resistance. The key difference between collision finding and average-case search is that collision finding has a new ``worst-case'' aspect: the collision finder has full control over the choice of colliding pairs. Our lower bound is proved in the online model; extending such guarantees to broader classes of algorithms, including spectral, algebraic, lattice-based, or quantum methods, remains an open direction.

Azim Ospanov, Jingwei Zhang, Mohammad Jalali et al.

While standard evaluation scores for generative models are mostly reference-based, a reference-dependent assessment of generative models could be generally difficult due to the unavailability of applicable reference datasets. Recently, the reference-free entropy scores, VENDI and RKE, have been proposed to evaluate the diversity of generated data. However, estimating these scores from data leads to significant computational costs for large-scale generative models. In this work, we leverage the random Fourier features framework to reduce the computational price and propose the Fourier-based Kernel Entropy Approximation (FKEA) method. We utilize FKEA's approximated eigenspectrum of the kernel matrix to efficiently estimate the mentioned entropy scores. Furthermore, we show the application of FKEA's proxy eigenvectors to reveal the method's identified modes in evaluating the diversity of produced samples. We provide a stochastic implementation of the FKEA assessment algorithm with a complexity $O(n)$ linearly growing with sample size $n$. We extensively evaluate FKEA's numerical performance in application to standard image, text, and video datasets. Our empirical results indicate the method's scalability and interpretability applied to large-scale generative models. The codebase is available at https://github.com/aziksh-ospanov/FKEA.

Andrej Bogdanov, Baoxiang Wang

$ $Let $F$ be a multivariate function from a product set $Σ^n$ to an Abelian group $G$. A $k$-partition of $F$ with cost $δ$ is a partition of the set of variables $\mathbf{V}$ into $k$ non-empty subsets $(\mathbf{X}_1, \dots, \mathbf{X}_k)$ such that $F(\mathbf{V})$ is $δ$-close to $F_1(\mathbf{X}_1)+\dots+F_k(\mathbf{X}_k)$ for some $F_1, \dots, F_k$ with respect to a given error metric. We study algorithms for agnostically learning $k$ partitions and testing $k$-partitionability over various groups and error metrics given query access to $F$. In particular we show that $1.$ Given a function that has a $k$-partition of cost $δ$, a partition of cost $\mathcal{O}(k n^2)(δ+ ε)$ can be learned in time $\tilde{\mathcal{O}}(n^2 \mathrm{poly} (1/ε))$ for any $ε> 0$. In contrast, for $k = 2$ and $n = 3$ learning a partition of cost $δ+ ε$ is NP-hard. $2.$ When $F$ is real-valued and the error metric is the 2-norm, a 2-partition of cost $\sqrt{δ^2 + ε}$ can be learned in time $\tilde{\mathcal{O}}(n^5/ε^2)$. $3.$ When $F$ is $\mathbb{Z}_q$-valued and the error metric is Hamming weight, $k$-partitionability is testable with one-sided error and $\mathcal{O}(kn^3/ε)$ non-adaptive queries. We also show that even two-sided testers require $Ω(n)$ queries when $k = 2$. This work was motivated by reinforcement learning control tasks in which the set of control variables can be partitioned. The partitioning reduces the task into multiple lower-dimensional ones that are relatively easier to learn. Our second algorithm empirically increases the scores attained over previous heuristic partitioning methods applied in this context.

Andrej Bogdanov, Siyao Guo

We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, we seek extractors for essentially all the entropy without any assumption on the underlying distribution beyond a min-entropy requirement. We give two simple constructions of sparse extractor families, which are collections of sparse functions such that for any distribution X on inputs of sufficiently high min-entropy, the output of most functions from the collection on a random input chosen from X is statistically close to uniform. For strong extractor families (i.e., functions in the family do not take additional randomness) we give upper and lower bounds on the sparsity that are tight up to a constant factor for a wide range of min-entropies. We then prove that for some min-entropies weak extractor families can achieve better sparsity. We show how this construction can be used towards more efficient parallel transformation of (non-uniform) one-way functions into pseudorandom generators. More generally, sparse extractor families can be used instead of pairwise independence in various randomized or nonuniform settings where preserving locality (i.e., parallelism) is of interest.