Seminars & Colloquia

Jeremy Kun

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

 

Abstract:

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.

Short Bio:

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

Media Files:
No media files available at this time

Video Presentation: Host is responsible for requesting video recording by filling out this Web form. For other technical issues, contact us at csc_help@ncsu.edu.
No streaming video available at this time

Back to Seminar Listings
Back to Colloquia Home Page