Martin Costa
I am a PhD student working with the Theory and Foundations group under the supervision of Sayan Bhattacharya, doing research in algorithms. My research is supported by a Google PhD Fellowship in Algorithms and Theory.
Selected Publications
Here are some of my selected publications. For the full list, please see my website: www.martincosta.com
Vizing's Theorem in Near-Linear TimeLink opens in a new window [arXivLink opens in a new window] [TCS+ TalkLink opens in a new window]
Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
Symposium on Theory of Computing (STOC) 2025Link opens in a new window (Prague, Czech Republic)
Best Paper Award at STOC 2025
Fully Dynamic k-Median with Near-Optimal Update Time and RecourseLink opens in a new window [arXivLink opens in a new window]
Sayan Bhattacharya, Martín Costa, Ermiya Farokhnejad
Symposium on Theory of Computing (STOC) 2025Link opens in a new window (Prague, Czech Republic)
Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing ChainsLink opens in a new window [arXivLink opens in a new window]
Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
Symposium on Discrete Algorithms (SODA) 2025Link opens in a new window (New Orleans, USA)
Fully Dynamic k-Clustering with Fast Update Time and Small RecourseLink opens in a new window [arXivLink opens in a new window] [videoLink opens in a new window]
Sayan Bhattacharya, Martín Costa, Naveen Garg, Silvio Lattanzi, Nikos Parotsidis
Symposium on Foundations of Computer Science (FOCS) 2024Link opens in a new window (Chicago, USA)
Faster (Δ + 1)-Edge Coloring: Breaking the m√n Time BarrierLink opens in a new window [arXivLink opens in a new window] [videoLink opens in a new window]
Sayan Bhattacharya, Din Carmon, Martín Costa, Shay Solomon, Tianyi Zhang
Symposium on Foundations of Computer Science (FOCS) 2024Link opens in a new window (Chicago, USA)
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal TimeLink opens in a new window [arXivLink opens in a new window] [videoLink opens in a new window]
Sayan Bhattacharya, Martín Costa, Nadav Panski, Shay Solomon
Symposium on Discrete Algorithms (SODA) 2024Link opens in a new window (Alexandria, USA)
Email: martin [dot] costa [at] warwick [dot] ac [dot] uk
Website: www.martincosta.com
[Google ScholarLink opens in a new window] [DBLPLink opens in a new window]