<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div style="color:rgb(80,0,80)"><b>When</b>:    Thursday, June 1st from <b style="background-color:rgb(255,255,0)">10:00 am - 12 pm CT</b></div><div style="color:rgb(80,0,80)"><b><br></b></div><div style="color:rgb(80,0,80)"><b>Where</b>:  Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>              TTIC, 6045 S. Kenwood Avenue<br>              5th Floor, <b><u><font color="#000000">Room 529</font></u></b><b><br></b><br><b>Virtually</b>: attend virtually <b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/j/93043992699?pwd=QmRObkRXZ0NGN1pCdnJDaDhaZVVuUT09" target="_blank">here</a></font></b><br></div><div style="color:rgb(80,0,80)"><br><b>Who</b>:       Rachit Nimavat, TTIC</div><div style="color:rgb(80,0,80)"><br></div><div style="color:rgb(80,0,80)"><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-size:11pt;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div></div><div style="color:rgb(80,0,80)"><div><div><b>Title:</b>      Graph Theory and Its Uses in Graph Algorithms and Beyond</div><div><br></div><div><b>Abstract:</b> 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.<br><br>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.</div><div><br></div><div><b>Thesis Committee: <a href="mailto:cjulia@ttic.edu" target="_blank">Julia Chuzhoy</a> </b>(Thesis Advisor), Sanjeev Khanna, Yury Makarychev</div></div></div></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, May 31, 2023 at 3:30 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div><b>When</b>:    Thursday, June 1st from <b style="background-color:rgb(255,255,0)">10:00 am - 12 pm CT</b></div><div><b><br></b></div><div><b>Where</b>:  Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>              TTIC, 6045 S. Kenwood Avenue<br>              5th Floor, <b><u><font color="#000000">Room 529</font></u></b><b><br></b><br><b>Virtually</b>: attend virtually <b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/j/93043992699?pwd=QmRObkRXZ0NGN1pCdnJDaDhaZVVuUT09" target="_blank">here</a></font></b><br></div><div><br><b>Who</b>:       Rachit Nimavat, TTIC</div><div><br></div><div><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-size:11pt;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div></div><div><div><div><b>Title:</b>      Graph Theory and Its Uses in Graph Algorithms and Beyond</div><div><br></div><div><b>Abstract:</b> 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 <span>thesis</span>, we exploit this symbiotic relationship between graph theory and algorithms for graph optimization problems and beyond. This <span>thesis</span> consists of three parts.<br><br>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 <span>thesis</span>, 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 <span>thesis</span>, 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.</div><div><br></div><div><b><span>Thesis</span> Committee: <a href="mailto:cjulia@ttic.edu" target="_blank">Julia Chuzhoy</a> </b>(<span>Thesis</span> Advisor), Sanjeev Khanna, Yury Makarychev</div></div></div><div><br></div></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, May 30, 2023 at 2:50 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div style="font-size:small"><div><b>When</b>:    Thursday, June 1st from <b style="background-color:rgb(255,255,0)">10:00 am - 12 pm CT</b></div><div><b><br></b></div><div><b>Where</b>:  Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>              TTIC, 6045 S. Kenwood Avenue<br>              5th Floor, <b><u><font color="#000000">Room 529</font></u></b><b><br></b><br><b>Virtually</b>: attend virtually <b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/j/93043992699?pwd=QmRObkRXZ0NGN1pCdnJDaDhaZVVuUT09" target="_blank">here</a></font></b><br></div><div><br><b>Who</b>:       <span>Rachit</span> Nimavat, TTIC</div><div><br></div><div><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-size:11pt;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div></div><div><div><div><b>Title:</b>      Graph Theory and Its Uses in Graph Algorithms and Beyond</div><div><br></div><div><b>Abstract:</b> 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.<br><br>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.</div><div><br></div><div><b>Thesis Committee: <a href="mailto:cjulia@ttic.edu" target="_blank">Julia Chuzhoy</a> </b>(Thesis Advisor), Sanjeev Khanna, Yury Makarychev</div></div></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, May 17, 2023 at 2:06 PM Mary Marre <<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div style="font-size:small"><div><b>When</b>:    Thursday, June 1st from <b style="background-color:rgb(255,255,0)">10:00 am - 12 pm CT</b></div><div><b><br></b></div><div><b>Where</b>:  Talk will be given <b><font color="#0000ff">live, in-person</font></b> at<br>              TTIC, 6045 S. Kenwood Avenue<br>              5th Floor, <b><u><font color="#000000">Room 529</font></u></b><b><br></b><br><b>Virtually</b>: attend virtually <b><font color="#0000ff"><a href="https://uchicagogroup.zoom.us/j/93043992699?pwd=QmRObkRXZ0NGN1pCdnJDaDhaZVVuUT09" target="_blank">here</a></font></b><br></div><div><br><b>Who</b>:       Rachit Nimavat, TTIC</div><div><br></div><div><div class="MsoNormal" align="center" style="margin:0in 0in 8pt;text-align:center;line-height:15.6933px;font-size:11pt;font-family:Calibri,sans-serif"><hr size="2" width="100%" align="center"></div></div><div><div><div><b>Title:</b>      Graph Theory and Its Uses in Graph Algorithms and Beyond</div><div><br></div><div><b>Abstract:</b> 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.<br><br>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.</div><div><br></div><div><b>Thesis Committee: <a href="mailto:cjulia@ttic.edu" target="_blank">Julia Chuzhoy</a> </b>(Thesis Advisor), Sanjeev Khanna, Yury Makarychev</div></div></div><div><br></div><div><br></div><div><br></div></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</blockquote></div></div>
</blockquote></div></div>
</blockquote></div></div>