Martin Costa

Vizing's Theorem in Deterministic Almost-Linear Time

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

Symposium on Discrete Algorithms (SODA) 2026Link opens in a new window (Vancouver, Canada)

Almost Optimal Fully Dynamic k-Center Clustering with RecourseLink opens in a new window [arXivLink opens in a new window] [posterLink opens in a new window]

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

International Conference on Machine Learning (ICML) 2025Link opens in a new window (Vancouver, Canada)

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)

Fully Dynamic k-Clustering in Õ(k) Update TimeLink opens in a new window [arXivLink opens in a new window] [videoLink opens in a new window] [posterLink opens in a new window]

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

Neural Information Processing Systems (NeurIPS) 2023Link opens in a new window (New Orleans, USA)