Hardness conjecture for certifying lift-monotone properties of random regular graphs
Statement
Let be a -regular multigraph on vertices, and let . Write for an -sheeted lift of . The operators , , , and denote, respectively, random, respectful random, adversarial, and respectful adversarial noise as defined in the source. Let denote a uniformly random -regular graph on vertices, and let denote the corresponding random bipartite -regular graph. Hardness of detecting noisy lifts. If is Ramanujan, then there is no polynomial-time algorithm that achieves strong detection between and . The same holds when is replaced by any of , , or . If is bipartite Ramanujan, then there is no polynomial-time algorithm that achieves strong detection between and . The same holds when is replaced by any of , , or . These conjectures are intended to imply hardness for certifying quantities that are lift-monotone, such as the independence number divided by the number of vertices, because such quantities can increase under graph lifts.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.