8 papers
Limitations on Autoregressive Token Generation via Sequential Sampling
Gal Arnon, Andrej Bogdanov, Paul Lou +3
We study autoregressive token generation through the notion of sequential samplers: A circuit that samples the next symbol only given the previous ones and possibly a small amount…
Statistically Undetectable Backdoors in Deep Neural Networks
Andrej Bogdanov, Alon Rosen, Neekon Vafa
We show how an adversarial model trainer can plant backdoors in a large class of deep, feedforward neural networks. These backdoors are statistically undetectable in the white-box…
Collision Resistance of Single-Layer Neural Nets
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
We initiate the study of the algorithmic complexity of finding collisions in single-layer binary neural networks. Given a random matrix , an…
Are Neural Networks Collision Resistant?
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
When neural networks are trained to classify a dataset, one finds a set of weights from which the network produces a label for each data point. We study the algorithmic complexity…
Overlap Gap and Computational Thresholds in the Square Wave Perceptron
Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta +5
Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional li…
Adaptive Robustness of Hypergrid Johnson-Lindenstrauss
Andrej Bogdanov, Alon Rosen, Neekon Vafa +1
Johnson and Lindenstrauss (Contemporary Mathematics, 1984) showed that for , a scaled random projection from to is an approximate…
Low-degree Security of the Planted Random Subgraph Problem
Andrej Bogdanov, Chris Jones, Alon Rosen +1
The planted random subgraph detection conjecture of Abram et al. (TCC 2023) asserts the pseudorandomness of a pair of graphs , where is an Erdos-Renyi random graph on $…
Towards a Scalable Reference-Free Evaluation of Generative Models
Azim Ospanov, Jingwei Zhang, Mohammad Jalali +3
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 una…