On the effect of randomness on planted 3-coloring models

DOI10.1145/2897518.2897561zbMath1376.68052arXiv1603.05183OpenAlexW2301205936MaRDI QIDQ5361820

Roee David

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1603.05183

zbMATH Keywords

NP-hardnessexpandersexact recoveryadversary

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

The simultaneous semi-random model for TSP ⋮ Unnamed Item ⋮ Finding Pseudorandom Colorings of Pseudorandom Graphs

This page was built for publication: On the effect of randomness on planted 3-coloring models