[Theory] 6/1 Thesis Defense: Rachit Nimavat, TTIC

[Mary Marre]

*When*:    Thursday, June 1st from *10:00 am - 12 pm CT*

*Where*:  Talk will be given *live, in-person* at
              TTIC, 6045 S. Kenwood Avenue
              5th Floor, *Room 529*

*Virtually*: attend virtually *here
<https://uchicagogroup.zoom.us/j/93043992699?pwd=QmRObkRXZ0NGN1pCdnJDaDhaZVVuUT09>*

*Who*:       Rachit Nimavat, TTIC

------------------------------
*Title:*      Graph Theory and Its Uses in Graph Algorithms and Beyond

*Abstract:* Graphs are fundamental objects that find widespread
applications across computer science and beyond. Graph Theory has yielded
deep insights about structural properties of various families of graphs,
which are leveraged in the design and analysis of algorithms for graph
optimization problems and other computational optimization problems. These
insights have also proved helpful in understanding the limits of efficient
computation by providing constructions of hard problem instances. At the
same time, algorithmic tools and techniques provide a fresh perspective on
graph theoretic problems, often leading to novel discoveries. In this
thesis, we exploit this symbiotic relationship between graph theory and
algorithms for graph optimization problems and beyond. This thesis consists
of three parts.

In the first part, we study a classical graph routing problem called the
Node-Disjoint Paths (NDP) problem. Given an undirected graph and a set of
source-destination pairs of its vertices, the goal in this problem is to
route the maximum number of pairs via node-disjoint paths. We come close to
resolving the approximability of NDP by showing that it is
$n^{\Omega(1/\poly \log \log n)}$-hard to approximate, even on grid graphs,
where n is the number of grid vertices. In the second part of this thesis,
we use graph decomposition techniques developed for efficient algorithms
and tools from the analysis of random processes to derive a graph theoretic
result. Specifically, we show that for every n-vertex expander graph G, if
H is any graph with at most $O(n/\log n)$ vertices and edges, then H is a
minor of G. In the last part of this thesis, we show that the graph
theoretic tools and graph algorithmic techniques can shed light on problems
seemingly unrelated to graphs. Specifically, we demonstrate that the
randomized space complexity of the Longest Increasing Subsequence (LIS)
problem in the streaming model is intrinsically tied to the
query-complexity of the Non-Crossing Matching problem on graphs in a new
model of computation that we define.

*Thesis Committee: Julia Chuzhoy <cjulia at ttic.edu> *(Thesis
Advisor), Sanjeev Khanna, Yury Makarychev



Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue, Rm 517*
*Chicago, IL  60637*
*773-834-1757*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20230517/0ebd9deb/attachment.html>