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 $(H,G)$, where $G$ is an Erdos-Renyi random graph on $…