  We introduce a new conjecture on the computational hardness of detecting
random lifts of graphs: we claim that there is no polynomial-time algorithm
that can distinguish between a large random $d$-regular graph and a large
random lift of a Ramanujan $d$-regular base graph (provided that the lift is
corrupted by a small amount of extra noise), and likewise for bipartite random
graphs and lifts of bipartite Ramanujan graphs. We give evidence for this
conjecture by proving lower bounds against the local statistics hierarchy of
hypothesis testing semidefinite programs. We then explore the consequences of
this conjecture for the hardness of certifying bounds on numerous functions of
random regular graphs, expanding on a direction initiated by Bandeira, Banks,
Kunisky, Moore, and Wein (2021). Conditional on this conjecture, we show that
no polynomial-time algorithm can certify tight bounds on the maximum cut of
random 3- or 4-regular graphs, the maximum independent set of random 3- or
4-regular graphs, or the chromatic number of random 7-regular graphs. We show
similar gaps asymptotically for large degree for the maximum independent set
and for any degree for the minimum dominating set, finding that naive spectral
and combinatorial bounds are optimal among all polynomial-time certificates.
Likewise, for small-set vertex and edge expansion in the limit of very small
sets, we show that the spectral bounds of Kahale (1995) are optimal among all
polynomial-time certificates.
