Theoretical foundations for practical problems : network analysis, algorithm selection, and interaction design
Abstract/Contents
- Abstract
- Characterizing algorithm performance is a tricky business. For most problems, any given algorithm is going to have widely varying performance over the possible inputs to the problem, and the performance of any two reasonable algorithms will be uncomparable over the input space. Over the last forty years, worst-case analysis has emerged as the dominant theoretical framework for resolving this issue: score each algorithm by the input on which it does the worst, and then rank algorithms by their score. While inspiring many of the algorithms in use today, worst-case analysis runs into a natural block when the "worst-case" inputs are not representative of the inputs typically seen in practice. In this dissertation, we look at several problem domains facing this issue, and introduce frameworks that go beyond worst-case analysis. The first domain is graph algorithms on social networks. We define a new class of graphs, "triangle-dense" graphs, which encompasses all known models of social networks, but is restricted enough to exclude worst-case inputs. One can then employ the following strategy for ranking social network algorithms: score each algorithm by the input from this class on which it does the worst, and then rank algorithms by their score. We present novel clustering and clique-counting algorithms demonstrating that this framework is both mathematically tractable and a useful restriction of the worst-case framework. The second domain we consider is application-specific algorithm selection, including parameter tuning. In this setting an engineer has a set of candidate algorithms and a list of representative inputs from an application, and needs to pick an algorithm to run on future inputs from the application. Intuitively, the less complex the set of algorithms, the fewer representative inputs the engineer needs to do a good job. We introduce two new models that allow one to formally reason about this tradeoff. Finally, we look at a problem that arises in understanding how users are interacting with an application, given traces of their behavior. We model the problem as that of recovering a mixture of Markov chains, and show surprising conditions under which one can recover the mixture.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2016 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Gupta, Rishi Vijay |
|---|---|
| Associated with | Stanford University, Department of Computer Science. |
| Primary advisor | Roughgarden, Tim |
| Thesis advisor | Roughgarden, Tim |
| Thesis advisor | Valiant, Gregory |
| Thesis advisor | Williams Vassilevska, Virginia, 1980- |
| Advisor | Valiant, Gregory |
| Advisor | Williams Vassilevska, Virginia, 1980- |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Rishi Vijay Gupta. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2016. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2016 by Rishi Vijay Gupta
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...