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.

Research:
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.
Contact:
  • E-mail: [lastname] @ ttic.edu
    •
    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:
  • Mohammad Roghani, (2024)
  • Sherry Sarkar, (2024)
  • Ce Jin, (2023)
  • Sandeep Silwal, (2023)
  • Shyam Narayanan, (2022)
  • Thuy (June) Duong Vuong, (2022)
    • Academic Service:
  • Program Committee: FOCS 2025 , 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
    Pre-prints:
    • Streaming Algorithms for Network Design,
      Chandra Chekuri, Rhea Jain, Sepideh Mahabadi, Ali Vakilian,
      arXiv. (pdf)
    • Graph-Based Algorithms for Diverse Similarity Search,
      Piyush Anand, Piotr Indyk, Ravishankar Krishnaswamy, Sepideh Mahabadi, Vikas C. Raykar, Kirankumar Shiragur, Haike Xu,
      arXiv. (pdf)
    • Composable Coresets for Constrained Determinant Maximization and Beyond,
      Sepideh Mahabadi, Thuy-Duong Vuong,
      arXiv. (pdf)
    Publications:
    Undergraduate
    Publications:
    • Construction of Random Perfect Phylogeny Matrix,
      M. Sadeghi, H. Pezeshk, C. Eslahchi, S. Ahmadian, S. Mahabadi,
      Advances and Applications in Bioinformatics and Chemistry 2010.
    • An Algorithm for Construction of all Perfect Phylogeny Matrices,
      H. Mirzaei, S. Ahmadian, S. Mahabadi, M. Sadeghi M., C. Eslahchi, H. Pezeshk,
      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)

    Talks
    • 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
    Teaching
    • 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.

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