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.