[Theory] TODAY: 6/1 Thesis Defense: Rachit Nimavat, TTIC
Mary Marre
mmarre at ttic.edu
Thu Jun 1 09:00:00 CDT 2023
*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>*
On Wed, May 31, 2023 at 3:30 PM Mary Marre <mmarre at ttic.edu> wrote:
> *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>*
>
>
> On Tue, May 30, 2023 at 2:50 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *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>*
>>
>>
>> On Wed, May 17, 2023 at 2:06 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *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/20230601/62f65799/attachment-0001.html>
More information about the Theory
mailing list