2023/03/09 by Samuel S. Epstein, Epstein, Samuel
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2303.05616
Using derandomization, we provide an upper bound on the compression size of solutions to the graph coloring problem. In general, if solutions to a combinatorial problem exist with high probability and the probability is simple, then there exists a simple solution to the problem. Otherwise the problem instance has high mutual information with the halting problem.