7 citations · 7 across the 6 of their papers we have counts for
9 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…
Uncertainty Principles for the Number Theoretic Transform
Giulio Malavolta, Alon Rosen
Motivated by polynomial identity testing with exponentials (Li and Wu, ITCS'26), we study uncertainty principles for the number-theoretic transform (NTT). We show that the NTT sati…
Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
Jarosław Błasiok, Paul Lou, Alon Rosen +1
In the noisy -XOR problem, one is given and must distinguish between uniform and , where is the adjacency matrix of a -left-regula…
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 $…
PPP-Completeness and Extremal Combinatorics
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček +2
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on mono…
Downward Self-Reducibility in TFNP
Prahladh Harsha, Daniel Mitropolsky, Alon Rosen
A problem is \emph{downward self-reducible} if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, down…
The impossibility of obfuscation with auxiliary input or a universal simulator
Nir Bitansky, Ran Canetti, Henry Cohn +4
In this paper we show that the existence of general indistinguishability obfuscators conjectured in a few recent works implies, somewhat counterintuitively, strong impossibility re…
Sequential Rationality in Cryptographic Protocols
Ronen Gradwohl, Noam Livne, Alon Rosen
Much of the literature on rational cryptography focuses on analyzing the strategic properties of cryptographic protocols. However, due to the presence of computationally-bounded pl…