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.