Kun_Jeremy.pdf (958.54 kB)
0/0

Graphs, New Models, and Complexity

Download (958.54 kB)
thesis
posted on 01.07.2016 by Jeremy J. Kun
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.

History

Advisor

Reyzin, Lev

Department

Mathematics, Statistics, and Computer Science

Degree Grantor

University of Illinois at Chicago

Degree Level

Doctoral

Committee Member

Turán, György Mubayi, Dhruv Sloan, Robert Suk, Andrew

Submitted date

2016-05

Language

en

Issue date

01/07/2016

Exports

Categories

Exports