Graphs, New Models, and Complexity

Over the past few decades the internet and social networks became central to our society. As a consequence, the study of networks and the algorithmic complexity of problems about networks are an increasingly important part of the application of mathematics to practical problems. The content of this dissertation explores a variety of topics on this theme. First, we explore the tractibility of computing certain kinds of equilibria for anticoordination games played on graphs. Next, we study a generic notion of ``resilience'' for combinatorial search problems, specifically studying the complexity of resilient graph coloring. Then we turn to the study of MapReduce, a popular distributed computing framework whose crucial open questions are about its capacity to solve certain graph problems. Finally, we study a model of disaster recovery in networks, and prove results about the inability for algorithms to compute approximate solutions.