Learning a graph via random colorings

Eric Vigoda

College of Computing, Georgia Institute of Technology, Atlanta, GA, USA

College of Computing, Georgia Institute of Technology, Atlanta, GA, USA

2018/6/11 Mon 5PM-6PM

For an unknown graph G on n vertices, given random k-colorings of G, can one learn the edges of G? We present results on identifiability/non-identifiability of the graph G and efficient algorithms for learning G. The results have interesting connections to statistical physics phase transitions.

This is joint work with Antonio Blanca, Zongchen Chen, and Daniel Stefankovic.

This is joint work with Antonio Blanca, Zongchen Chen, and Daniel Stefankovic.