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.
Before starting my PhD, 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
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, Nikos Parotsidis
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
Symposium on Discrete Algorithms (SODA) 2025 (New Orleans, USA)
Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis
Symposium on Foundations of Computer Science (FOCS) 2024 (Chicago, USA)
Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang
Symposium on Foundations of Computer Science (FOCS) 2024 (Chicago, USA)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
European Symposium on Algorithms (ESA) 2024 (London, UK)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Scandinavian Symposium on Algorithm Theory (SWAT) 2024 (Helsinki, Finland)
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Symposium on Discrete Algorithms (SODA) 2024 (Alexandria, USA)
Sayan Bhattacharya, Martín Costa, Silvio Lattanzi, Nikos Parotsidis
Neural Information Processing Systems (NeurIPS) 2023 (New Orleans, USA)
Unless stated otherwise, author names are listed in alphabetical order.
Invited Talks
TCS+ Talk (Online Seminar, Dec. 2024) (Upcoming)
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
Algorithms and Complexity Theory Seminar (University of 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) (Upcoming)
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, Sept. 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 (Charles University, 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)
Teaching
I have been a Senior Graduate Teaching Assistant at the University of Warwick since 2021 and have been involved in teaching the following courses.
CS418 Advanced Topics in Algorithms and Complexity (2022 - 2023)
Awards and Prizes
EPSRC Doctoral Training Partnership Award (2022)
Best overall graduating MEng student in Discrete Mathematics prize (2022) (Awarded by the University of Warwick)
Best Discrete Mathematics third-year project prize (2021) (Awarded by the University of Warwick) (Dissertation available here)
Highest achieving second-year student in Computer Science (2020) (Awarded by the University of Warwick)
Service
Co-organized the FoCS Theory Workshop 2023 (University of Warwick, Coventry, UK, Jun. 2023)
External reviewer for STOC 2025, ESA 2024, SODA 2025, 2024, ICALP 2024, 2023, SEA 2023, and SOSA 2023.
Workshops
Dagstuhl Seminar on Graph Algorithms: Distributed Meets Dynamic (Dagstuhl, Germany, Nov. 2024)
ADFOCS Algorithmic Foundations of Data Analysis (Max Planck Institute, Saarbrücken, Germany, Aug. 2023)
DIMACS Modern Techniques in Graph Algorithms (Rutgers University, New Jersey, USA, Jun. 2023)
Weizmann-Warwick Workshop 2023 (Weizmann Institute, Tel Aviv, Israel, Feb. 2023)
Conferences
Foundations of Computer Science (FOCS) 2024 (Chicago, USA, Oct. 2024)
European Symposium on Algorithms (ESA) 2024 (London, UK, Sept. 2024)
Scandinavian Symposium on Algorithm Theory (SWAT) 2024 (Helsinki, Finland, Jun. 2024)
Highlights of Algorithms (HALG) 2024 (Warsaw, Poland, Jun. 2024)
Neural Information Processing Systems (NeurIPS) 2023 (New Orleans, USA, Dec. 2023)
Computational Complexity Conference (CCC) 2023 (University of Warwick, Coventry, UK, Jul. 2023)
Highlights of Algorithms (HALG) 2023 (Charles University, Prague, Czech Republic, Jun. 2023)
Symposium on Theory of Computing (STOC) 2022 (Rome, Italy, Jun. 2022)