2 papers
cs.CR2024
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 $…
cs.CC2022
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…