Martín Costa

Email: martin[dot]costa[at]warwick[dot]ac[dot]uk

Office: CS2.18, Department of Computer Science

[LinkedIn] [GitHub] [Google Scholar] [DBLP]

About Me

I am a third-year PhD student at the University of Warwick doing research in theoretical computer science under the supervision of Sayan Bhattacharya. I am also working as a student researcher within the Graph Mining Team at Google Research.

My research is funded by a Google PhD Fellowship and the Engineering and Physical Sciences Research Council.

I received my Master of Engineering in Discrete Mathematics from the University of Warwick.

Research Interests

My research interests primarily lie within the field of algorithms, with a particular focus on dynamic algorithms, graph algorithms, and clustering algorithms. Two problems that I am particularly interested in are k-clustering and edge coloring—and all of their static, dynamic, distributed, and online variants.

Publications

Almost Optimal Fully Dynamic k-Center Clustering with Recourse [arXiv]

Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad, Silvio Lattanzi, Nikos Parotsidis

International Conference on Machine Learning (ICML) 2025 (Vancouver, Canada)

Deterministic k-Median Clustering in Near-Optimal Time [arXiv]

Martín Costa, Ermiya Farokhnejad

International Colloquium on Automata, Languages, and Programming (ICALP) 2025 (Aarhus, Denmark)

Fully Dynamic k-Median with Near-Optimal Update Time and Recourse [arXiv]

Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad

Symposium on Theory of Computing (STOC) 2025 (Prague, Czech Republic)

Vizing's Theorem in Near-Linear Time [arXiv] [TCS+ Talk]

Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang

Symposium on Theory of Computing (STOC) 2025 (Prague, Czech Republic)

Best Paper Award at STOC 2025

Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains [arXiv]

Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang

Symposium on Discrete Algorithms (SODA) 2025 (New Orleans, USA)

Fully Dynamic k-Clustering with Fast Update Time and Small Recourse [arXiv] [video]

Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis

Symposium on Foundations of Computer Science (FOCS) 2024 (Chicago, USA)

Faster (Δ + 1)-Edge Coloring: Breaking the m√n Time Barrier [arXiv] [video]

Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang

Symposium on Foundations of Computer Science (FOCS) 2024 (Chicago, USA)

Density-Sensitive Algorithms for (Δ + 1)-Edge Coloring [arXiv]

Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon

European Symposium on Algorithms (ESA) 2024 (London, UK)

Arboricity-Dependent Algorithms for Edge Coloring [arXiv]

Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon

Scandinavian Symposium on Algorithm Theory (SWAT) 2024 (Helsinki, Finland)

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time [arXiv] [video]

Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon

Symposium on Discrete Algorithms (SODA) 2024 (Alexandria, USA)

Fully Dynamic k-Clustering in Õ(k) Update Time [arXiv] [video] [poster]

Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, Nikos Parotsidis

Neural Information Processing Systems (NeurIPS) 2023 (New Orleans, USA)

Author names are always listed in alphabetical order.

Invited Talks

University of Waterloo Algorithms and Complexity Seminar (Waterloo, Canada, Mar. 2025)

Vizing's Theorem in Near-Linear Time

TCS+ Talk (Online Seminar, Dec. 2024)

Vizing's Theorem in Near-Linear Time

Dagstuhl Seminar on Graph Algorithms: Distributed Meets Dynamic (Dagstuhl, Germany, Nov. 2024)

Fully Dynamic k-Clustering with Fast Update Time and Small Recourse

University of Oxford Algorithms and Complexity Theory Seminar (Oxford, UK, May 2024)

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time

Conference and Workshop Talks

Symposium on Discrete Algorithms (SODA) 2025 (New Orleans, USA, Jan. 2025)

Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains

Foundations of Computer Science (FOCS) 2024 (Chicago, USA, Oct. 2024)

Fully Dynamic k-Clustering with Fast Update Time and Small Recourse

Foundations of Computer Science (FOCS) 2024 (Chicago, USA, Oct. 2024)

Faster (Δ + 1)-Edge Coloring: Breaking the m√n Time Barrier

European Symposium on Algorithms (ESA) 2024 (London, UK, Sep. 2024)

Density-Sensitive Algorithms for (Δ + 1)-Edge Coloring

Scandinavian Symposium on Algorithm Theory (SWAT) 2024 (Helsinki, Finland, Jun. 2024)

Arboricity-Dependent Algorithms for Edge Coloring

Highlights of Algorithms (HALG) 2024 (Warsaw, Poland, Jun. 2024)

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time

Highlights of Algorithms (HALG) 2023 (Prague, Czech Republic, Jun. 2023)

Fully Dynamic k-Clustering in Õ(k) Update Time

Weizmann-Warwick Workshop 2023 (Weizmann Institute, Tel Aviv, Israel, Feb. 2023)

Fully Dynamic k-Clustering in Õ(k) Update Time

Weizmann-Warwick Workshop 2023 (Weizmann Institute, Tel Aviv, Israel, Feb. 2023)

Online Edge Coloring (Updated slides)

Honors and Awards

Best Paper Award at ACM Symposium on Theory of Computing (STOC) (2025)
Google PhD Fellowship in Algorithms and Theory (2024)
EPSRC Doctoral Training Partnership Award (2022)
Best Overall Graduating MEng Student in Discrete Mathematics Prize (2022) (University of Warwick)
Best Discrete Mathematics Third-Year Project Prize (2021) (University of Warwick) (Dissertation available here)
Highest Achieving Second-Year Student in Computer Science (2020) (University of Warwick)