Tiling of a surface is acted upon by its automorphism group. The tilings with single vertex orbit, the transitive tilings, are well studied since antiquity.

Raghavendra's famous result from 2008 fully characterizes the inapproximability of every maximum constraint satisfaction problem (Max-CSP). However, the result inherently loses perfect completeness.

Paper: Michael Saks and Rahul Santhanam, "Circuit Lower Bounds from NP-Hardness of MCSP Under Turing Reductions"
https://drops.dagstuhl.de/opus/volltexte/2020/12578/

"Paper: Yuchen Zhang, John C Duchi, Michael I Jordan, Martin J Wainwright, Information-theoretic lower bounds for distributed statistical estimation with communication constraints"