Random Instances and Randomness in Algorithms
Event details
| Date | 03.07.2019 |
| Hour | 13:00 › 15:00 |
| Speaker | Xinrui Jia |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Michael Kapralov
Thesis advisor: Prof. Ola Svensson
Co-examiner: Prof. Friedrich Eisenbrand
Abstract
There are two main ways that randomness is used in algorithms. The first is randomness in the input, and the other is access to random bits in algorithm design. These aspects are connected and the goal is to design better algorithms with provable guarantees. We study a framework in maximizing submodular functions subject to independence constraints, derandomization of a parallel algorithm, and a lower bound for the complexity of the perfect matching polytope. The objective is to apply similar techniques to investigate random algorithms.
Background papers
Bipartite Perfect Matching is in quasi-NC, by Fenner, S., et al. arxiv.org 2016.
The matching polytope has exponential extensioncomplexity, by Rothvoss, T. arxiv.org 2017.
Submodular Function Maximization via the Multilinear Relaxationand Contention Resolution Schemes,by Chekuri, C., et al. arxiv.org 2014.
Exam president: Prof. Michael Kapralov
Thesis advisor: Prof. Ola Svensson
Co-examiner: Prof. Friedrich Eisenbrand
Abstract
There are two main ways that randomness is used in algorithms. The first is randomness in the input, and the other is access to random bits in algorithm design. These aspects are connected and the goal is to design better algorithms with provable guarantees. We study a framework in maximizing submodular functions subject to independence constraints, derandomization of a parallel algorithm, and a lower bound for the complexity of the perfect matching polytope. The objective is to apply similar techniques to investigate random algorithms.
Background papers
Bipartite Perfect Matching is in quasi-NC, by Fenner, S., et al. arxiv.org 2016.
The matching polytope has exponential extensioncomplexity, by Rothvoss, T. arxiv.org 2017.
Submodular Function Maximization via the Multilinear Relaxationand Contention Resolution Schemes,by Chekuri, C., et al. arxiv.org 2014.
Practical information
- General public
- Free