Statistical and Computational Phase Transitions in Group Testing.

Amin Coja-Oghlan Oliver Gebhard Max Hahn-Klimroth Alexander S. Wein Ilias Zadik

Published in: COLT (2022)

Keyphrases

phase transition
group testing
random constraint satisfaction problems
constraint satisfaction
satisfiability problem

disjoint sets
combinatorial problems
hard problems
cellular automata
np complete

randomly generated
graph coloring
sat problem
deep structure

random instances
mathematical programming
constraint satisfaction problems
random graphs