Hi! I am a final 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 and Rachit Nimavat.
  Large Minors in Expanders. [tl;dr]

  A graph H is a minor of G, if H can be obtained from G via a sequence of vertex and edge deletetions and edge-contractions. We show that given any bounded-degree expander G on n vertices and an arbitrary graph H on roughly n/log n vertices, H is a minor of G. We also show a randomized algorithm to find such a model of H in G. Independently, Krivelevich and Nenadov provide an elegant proof of a similar but stronger result.

  ArXiv Preprint. [arxiv]


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

  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. [tl;dr]

  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. [tl;dr]

  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

• Summer Course on Probability and Machine Learning at TTI-Japan (Summer 2018).
  With Pedro Savarese.


• Approximation Algorithms (Winter 2018).
  Instructor: Prof. Julia Chuzhoy.


• Algorithms (Winter 2017).
  Instructor: Prof. Julia Chuzhoy.

Based on minimal by orderedlist.