Seminars & Colloquia
Mathematics, University of Illinois, Chicago
"Resilience and new approaches to approximate graph coloring "
Monday November 02, 2015 11:00 AM
Location: 3211, EBII NCSU Centennial Campus
(Visitor parking instructions)
This talk is part of the Theory Seminar Series
An interesting class of combinatorial objects are those which are 'resilient' to adversarial manipulations of some kind. For example, a Hamiltonian graph can be 'resilient' if it still has a Hamiltonian path even after an adversary is allowed to remove any edge. One can then ask: are there efficient algorithms to actually find Hamiltonian paths in sufficiently resilient graphs? I will discuss the notion of resilience as a general theme in theoretical computer science, and then describe some of my work giving algorithms and lower bounds for resilient versions of boolean satisfiability and graph coloring.
Jeremy Kun is a PhD student at the University of Illinois at Chicago. His research covers a broad variety of topics in theoretical computer science including network science, complexity theory, distributed computing, and the emerging field of algorithmic fairness. He writes a blog called Math ∩ Programming at jeremykun.com.
Host: Blair D. Sullivan, CSC