Sagar Kale

Pronunciation: Sāgar Kālé     In Marathi: सागर काळे

I am currently a post-doc at University of Vienna, and Prof. Monika Henzinger is my host.

Previously, I spent two years as a post-doc at EPFL in Lausanne, Switzerland, where Prof. Ola Svensson was my host.

I completed my Ph.D. from Dartmouth College in November 2017 and was fortunate to have Prof. Amit Chakrabarti as my advisor. My thesis is titled "Finding Good Matchings in Graph Streams."

Email: on gmail [@AT] SGRKL4

Research area: theoretical computer science, specifically, algorithms for combinatorial optimization problems in computational models such as streaming, massively parallel computing, and dynamic algorithms.

Masters: M. Tech. in Computer Science and Engineering at IIT Bombay, Mumbai, where my advisor was Prof. Sundar Vishwanathan.

Professional Service: PC member of ESA 2019.

Published/Accepted Research Papers

  • Krishnendu Chatterjee, Monika Henzinger, Sagar Sudhir Kale, and Alexander Svozil
    In ICALP 2021: Faster Algorithms for Bounded Liveness in Graphs and Game Graphs
    Link to paper.
  • Monika Henzinger and Sagar Kale
    In ESA 2020: Fully-Dynamic Coresets
    arXiv link YouTube link for my talk.
  • Ashish Chiplunkar, Sagar Kale, and Sivaramakrishnan Natarajan Ramamoorthy
    In ICML 2020: How to Solve Fair k-Center in Massive Data Models
    arXiv link YouTube link for my talk.
  • Paritosh Garg, Sagar Kale, Lars Rohwedder, and Ola Svensson
    In ICALP 2020: Robust Algorithms under Adversarial Injections
    arXiv link.
  • Sagar Kale
    In APPROX 2019: Small Space Stream Summary for Matroid Center
    arXiv link.
  • Buddhima Gamlath, Sagar Kale, Slobodan Mitrović, and Ola Svensson
    In PODC 2019: Weighted Matchings via Unweighted Augmentations
    arXiv link.
  • Buddhima Gamlath, Sagar Kale, and Ola Svensson
    In SODA 2019: Beating Greedy for Stochastic Bipartite Matching
  • Sagar Kale, Sumedh Tirodkar
    In APPROX 2017: Maximum Matching in Two, Three, and a Few More Passes Over Graph Streams
    arXiv link; YouTube link for my talk
  • Amit Chakrabarti, Sagar Kale
    In FOCS 2016: Strong Fooling Sets for Multi-Player Communication with Applications to Deterministic Estimation of Stream Statistics
    ECCC link YouTube link for my talk
  • Amit Chakrabarti, Sagar Kale
    In IPCO 2014: Submodular Maximization Meets Streaming: Matchings, Matroids, and More
    Journal version in Math. Program. 154(1-2) 2015
    arXiv link


I also like hiking and running (both mountain running and road running).

I ran Sierre-Zinal 2019, which is part of the Golden Trail World Series, with 31km distance and 2200m of elevation gain, and finished in 5h22. Diploma.

My best half-marathon time is 1h37 in Geneva Half Marathon in May 2018. Photo.

I have hiked extensively in Switzerland during my postdoc and in New England during my Ph.D. I am officially a member of the White Mountain Four Thousand Footers club (hiking highest 48 mountains in New Hampshire) and the New England Four Thousand Footers club (highest 67 mountains in New England). See this for more information. Photo NH48.