Sepideh Mahabadi
I am currently a Senior Researcher at the Algorithms group of Microsoft Research, Redmond.
I received my PhD in Computer Science, at the Theory of Computation (TOC) group at CSAIL, MIT. I was very fortunate to have Piotr Indyk as my advisor.
For a year, I was a Postdoctoral Research Scientist at Simons Collaboration on Algorithms and Geometry based at Columbia University, hosted by Alexandr Andoni.
Then, I spent three years as a Research Assistant Professor at Toyota Technological Institute at Chicago (TTIC), 2018-2021.
I received my B.Sc. in Computer Engineering from Sharif University of Technology, Iran 2007-2011.

My research is mostly focused on Theoretical Foundations of Massive Data including High Dimensional Computational Geometry; Streaming and Sub-linear Time Algorithms; Data Summarization; Graph Algorithms; Metric Embeddings; as well as Societal Aspects of Algorithms including Diversity, Fairness, and Privacy.
  • Our paper Composable Core-sets for Diversity and Coverage Maximization has received the ACM PODS Alberto O. Mendelzon Test-of-Time Award 2024.
  • Our paper Sampling Near Neighbors in Search for Fairness has appeared in Communications of the ACM 2022.
  • E-mail: [lastname] @
  • Internship at MSR:
    The Algorithms group at MSR hires summer interns each year. The deadline is normally end of November [the link will be posted here]. If you are a strong TCS student and are interested to work on theoretical problems with me, please contact me.

    I have co-hosted the following great interns:
  • Ce Jin , (2023)
  • Sandeep Silwal , (2023)
  • Shyam Narayanan , (2022)
  • Thuy (June) Duong Vuong , (2022)
  • Academic Service:
  • Program Committee: SODA 2025 , ICALP 2023 , STOC 2023 , WOLA 2022 , SoCG 2022 , HALG 2022 , STOC 2021 , SODA 2021 , RANDOM 2020 and ITCS 2019 ; and Reviewer: NeurIPS 2023, ICML 2018, and NeurIPS 2017.
  • Workshop Organization:
  • Member of the Diversity, Equity, and Inclusion Committee at TTIC, 2020-2021.

  • Publications
    • Sepideh Mahabadi, Thuy-Duong Vuong,
      Composable Coresets for Constrained Determinant Maximization and Beyond,
      arXiv. (pdf)
    • M. Sadeghi, H. Pezeshk, C. Eslahchi, S. Ahmadian, S. Mahabadi,
      Construction of Random Perfect Phylogeny Matrix,
      Advances and Applications in Bioinformatics and Chemistry 2010.
    • H. Mirzaei, S. Ahmadian, S. Mahabadi, M. Sadeghi M., C. Eslahchi, H. Pezeshk,
      An Algorithm for Construction of all Perfect Phylogeny Matrices,
      Communications in Mathematical and in Computer Chemistry (MATCH) 2009.
    Master's Thesis:
    (MIT, June 2013)
    Approximate Nearest Neighbor And Its Many Variants (pdf)
    PhD Thesis:
    (MIT, Sept. 2017)
    Sub-linear Algorithms for Massive Data Problems (pdf)

    • Recent Advances in Diversity Maximization in the Offline and Composable Coreset Models

      • Dynamic Graphs and Algorithm Design Workshop at Simons Institute, September 2023

    • Sampling a Near Neighbor in High Dimensions Who is the Fairest of Them All?

      • RAISE (Responsible AI and Software Experiences) at UW, November 2022
      • Sublinear Algorithms Workshop, MIT, August 2022

    • Non-Adaptive Adaptive Sampling in Turnstile Streams

      • IDEAL Workshop on High-Dimensional Geometry and Analysis, May 2022
      • Michigan-Purdue Theory Seminar, September 2020
      • TCS+ Talk, April 2020

    • Two-sided Kirszbraun Theorem
      Workshop on Algorithms for Large Data, August 2021

    • Diversity and Fairness in Data Summarization Algorithms

      • ICPCU Alumni Lecture Series, June 2021
      • IPM Combinatorics and Computing Conference (IPMCCC), May 2021
      • EPFL, IC School, April 2021
      • Columbia University, CS Department, April 2021
      • University of Michigan, CSE Division, March 2021
      • Google Research, March 2021
      • CMU, CS Department, March 2021
      • University of Maryland, CS Department, March 2021
      • Purdue University, CS Department, February 2021
      • Georgia Institute of Technology, School of CS, February 2021
      • MSR Redmond, MLO and Algorithms groups, February 2021
      • University of Waterloo, CS Department, Januray 2021

    • Determinant Maximization over Large Data Sets
      Sub-linear Reading Group, MIT, September 2020

    • Composable Core-sets for the Determinant Maximization Problem
      Rising Stars Talk, TCS Women Spotlight Workshop, June 2020

    • Composable Core-sets for Determinant Maximization Problems via Spectral Spanners

      • CMU, November 2019
      • UIUC, February 2019
      • Junior Theorists Workshop, Northwestern Univeristy, November 2018

    • Diversity Maximization over Large Data Sets

      • The Statistics and Data Sciences (SDS) Seminar Series, UT Austin, October 2022
      • UCSB Theory Colloquium, April 2022
      • MSR Redmond, October 2019
      • Optimization Methods in Computer Vision and Image Processing workshop, ICERM, May 2019
      • Midwest Theory Day, Purdue University, April 2019

    • Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extension

      • Metric Embeddings & Dimensionality Reduction workshop, Northwestern Univeristy, May 2019
      • University of Chicago, October 2018
      • Google New York, July 2018

    • Set Cover in Sub-linear Time

      • Workshop on Local Algorithms (WOLA), MIT, June 2018
      • Rutgers Univeristy/DIMCAS, May 2018
      • Midwest Theory Day, TTIC, April 2018
      • New York Area Theory Day, NYU, December 2017

    • Fractional Set Cover in the Streaming Model
      Simons Collaboration on Algorithms & Geometry, February 2018

    • Approximate Nearest Neighbor and Its Many Variants

      • University of Washington, April 2017
      • IBM Watson, December 2016

    • Towards Tight Bounds for the Streaming Set Cover Problem
      University of Toronto, November 2015

    • Approximate Nearest Line Search in High Dimensions
      Brown University, November 2014

    • Instructor: Taught a course on Algorithms for Massive Data in Spring 2021 at TTIC.
    • Guest Lecturer for Approximation Algorithms taught by Julia Chuzhoy, TTIC, Fall 2019.
    • Teaching Assistant
      • Introduction to Algorithms, (Spring 2017, MIT)
      • Advanced Algorithms, (Spring 2013, MIT)
      • Design and Analysis of Algorithms (Spring 2010, Sharif UT)
      • Theory of Languages and Machines (Fall 2010, Sharif UT)
      • Introduction to Programming (Fall 2010, Sharif UT)
    • Olympiad Camps: Teaching special topics in Computer Science at the training camps of Iranian National Olympiad in Informatics (NIOI), 2008-2009.

    Internships & Visits

    Olympiad and Programming Contests
    • Gold Medal in International Olympiad in Informatics (IOI) 2007.
      • Only female contestant to win a gold medal at IOI 2007.
      • First Iranian female to win a gold medal ever at IOI.
    • ACM-ICPC World Finals 2011, Ranked 13th.
      • Representing Sharif UT.
    • ACM-ICPC World Finals 2013, Ranked 14th.
      • Representing MIT.
      • Only female contestant among all participants from US.
    • Member of the Host Scientific Committee in International Olympiad in Informatics (IOI) 2017.

    (سپیده مه آبادی)