Research

Interests

See Home, for my areas of interest. Below are more specific topics I've found interesting.

  • Combinatorial Optimization - combinatorial algorithms and approximation algorithms (maybe more LP based methods in the future)

  • Graph Algorithms and Graph Theory - cuts, flows, graph decompositions, partitioning, metric embeddings, Steiner problems, routing, spectral techniques, and s-t series parallel graphs

  • Algorithms under Uncertainty - stochastic probing problems, adaptivity gaps, online MTS, and ML predictions in online algorithms

  • Algorithmic Game Theory - information design, congestion games, persuasion, and price of anarchy

Many fun problems lie in most of the main categories such as stochastic probing problems in metric spaces and metrical task system problems. Some of my favorites of these kinds are the Adaptive Traveling Salesman Problem, the Bayesian Canadian Traveler's Problem, and the Multilevel Aggregation Problem. I've also been getting into using ML predictions in online algorithms to achieve improved performance.

I also like problems that have applications to or motivations from other fields such as bioinformatics, AGT, and ML. It's really fun finding connections between completely different areas. I'm particularly intrigued by connections between psychology and computer science especially in the context of machine learning and AGT. One particular work of this type I find fascinating is the study of consciousness using TMs.

Publications

Online Algorithms

A D-competitive algorithm for the Multilevel Aggregation Problem with Deadlines [arXiv]

in submission.

Stochastic Optimization

Approximating Pandora's Box with Correlations

with Shuchi Chawla, Evangelia Gergatsouli, and Christos Tzamos, in submission.

Algorithmic Mechanism Design

Noble Deceit: Optimizing Social Welfare for Myopic Multi-Armed Bandits [Games, EC Poster]

with Ashwin Maran and Nathaniel Sauerberg, Games 2020.

Spectral Graph Theory

  • Survey on Spectral Algorithms and Unique Games [Scholar]

  • Manuscript on Variations of Spectral Graph Isomorphism [pdf]

  • Senior thesis on Spectral Graph Isomorphism [pdf]

Research Journey

I have a bad habit of being most successful at the topics that I fear the most. My first experience with spectral graph theory was when making a presentation on random walks in graphs for a course project. Seeing the long equations splattered with lambdas was truly terrifying to my freshman eyes. Years later, when I first approached my senior thesis advisor, Alexandra, about working on a project in complexity theory, I hoped that I could somehow avoid the spectral graph theory that I knew she held dear to her heart. To my demise, the problem she proposed for us to work on was the spectral graph isomorphism problem. I was scared of the spectral aspects, but graph isomorphism was one of my favorite problems at the time, so I wanted to try to overcome the barrier of spectral techniques. To my surprise, my mathematical maturity had increased to such an extent that those same equations from before were as tame as my golden retriever. But even more surprising, Alexandra was able to show me how beautiful spectral graph theory was and I grew to appreciate the astounding connections between spectral properties of a matrix and the structure of a graph. This lead to my senior thesis.

After this experience, you'd think I would have learned to appreciate all areas and get out of my comfort zone, but, unfortunately, I was not that wise. Unlike spectral theory, when I first saw online algorithms I thought they were absolutely magical; in fact, so magical that no mere mortal such as myself could possibly devise such mystical algorithms. I became even more convinced of this as my advanced algorithms homework problems involving online algorithms were impossible for me to solve. Flash forward one year, I began working on Stochastic optimization problems, such as adaptive TSP, with Shuchi. I fell in love with these problems and learned quite a bit about them. Little did I know that the stochastic probing problems were secretly just online problems in disguise. When I finally became serious about MTS, my experience with stochastic probing problems enabled me to break through my mental block to successfully devise and analyze an online algorithm! Finally, I had been freed from my avoiding topics just because they seemed difficult.

Although 37% is the right amount of exploration in secretary problems, I've found I explore with new topics much more than that. I attribute this reaction to the overcorrecting nature of mankind, similar to how steepest descent overshoots when optimizing a quadratic function. A new direction was birthed from this experience. In particular, trying to see connections and applications of algorithms in other related fields like machine learning or bioinformatics. I'm especially intrigued in the interplay with machine learning since I'm also passionate about psychology, and how humans and other species learn which of course also plays into my passion for teaching. Similarly, my interest in algorithmic game theory was also spawn. Overall, I think my love for graph algorithms and approximation theory ensures my curiosity doesn't get too far from the tree.

Like Spectral Graph Theory, I was always suggested to explore work in planar graph algorithms. This is another topic I may dabble in seriously soon.