RACHIT NIMAVAT
Semiretired Programmer, Consumed by Wanderlust, Skilled in Locating Free Food

CV

nimavat@ttic.edu

Hi! I am a third year PhD student at the Toyota Technological Institute at Chicago, where I am advised by Prof. Julia Chuzhoy. I am interested in Theoretical Computer Science, mainly Approximation Algorithms and Hardness of Approximation.

Before that, I received my BTech in Computer Science and Engineering from Indian Institute of Technology, Kanpur under the supervision of Prof. Surender Baswana.

In my free time I cook, while trying to optimize the ratio of taste over effort. I try to keep the recipes Gujarati at heart, but cook with convenient ingredients (see the recipe of my staple dinner). When the weather is warm enough I like to read on my hammock, somewhere close to the lake-shore. Also, I am learning sailing these days!

### Publications

• Julia Chuzhoy, David Kim and Rachit Nimavat.
Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary.

Node-Disjoint Paths (NDP) is a problem where we are given a graph and some source-destination pairs. The goal is to 'route' as many of these pairs of vertices as possible, along paths that don't intersect anywhere. We give an approximation algorithm for a special case of NDP problem: (i) the graph is an undirected grid; and (ii) the sources lie on its boundary.

ICALP 2018. [arxiv] [slides]

• Julia Chuzhoy, David Kim and Rachit Nimavat.
Almost Polynomial Hardness for Node-Disjoint Paths in Grids.

Node-Disjoint Paths (NDP) is a problem where we are given a graph and some source-destination pairs. The goal is to 'route' as many of these pairs of vertices as possible, along paths that don't intersect anywhere. We show that it is hard to approximate the solution, even when the graph is a grid. The hardness of approximation factor that we achieve is almost polynomial.

STOC 2018. Gave a talk about this result at Workshop on Approximation algorithms and Hardness of Approximation, Banff, CA, Nov, 2017. [arxiv] [slides] [video]

• Julia Chuzhoy, David Kim and Rachit Nimavat.
New Hardness Results for Routing on Disjoint Paths.

Node-Disjoint Paths (NDP) is a problem where we are given a graph and some source-destination pairs. The goal is to 'route' as many of these pairs of vertices as possible, along paths that don't intersect anywhere. We show that it is quite hard to approximate the solution, even when the graph is planar.

STOC 2017. Invited to the SICOMP STOC 2017 special issue. [arxiv] [poster]

### Project Reports

• Improper Learning Equals Refutation.
Theory of Machine Learning (Spring 2018). [pdf]

• Knock, Knock, Neo! Spawning Knock-Knock Jokes.
Natural Language Processing (Winter 2016). [pdf]

### Teaching

Cartoon by Divya.
Based on minimal by orderedlist.