Peter Kiss
About me
I am final year Phd student at the University of Warwick supervised by Sayan Bhattacharya. I work in the Theory and Fundations group (FOCS) at the Warwick University Computer Science Deparment. My primary area is dynamic algorithm research. I have completed my undergraduate and masters degree at Worcester College, University of Oxford.
peter dot kiss at warwick dot ac dot uk
Research Interests
My research is primarily focused on dynamic graph algorithms and the approximate maximum matching problem in particular. More recently I have been working on sub-linear algorithms and their applications in the dynamic model. I am very interested in graph theoretical applications of convex optimisation techniques in all models.
Conference Papers
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs (STOC2024, arXiv)
With Sayan Bhattacharya, Aaron Sidford, David Wajc
Dynamic (1+\epsilon)-Approximate Matching Size in Truly Sublinear Update Time (FOCS2023, arXiv)
With Sayan Bhattacharya, Thatchaphol Saranurak
Presentation at MPI, PPT
Incremental (1+\epsilon)-approximate dynamic matching in poly(1/\epsilon) update time (ESA2023, arXiv)
With Joakim Blikstad
Best Student Paper Award
Sublinear Algorithms for (3/2+\epsilon)-Approximate Matching (STOC2023, arXiv)
With Sayan Bhattacharya, Thatchaphol Saranurak
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time (SODA2023, arXiv)
Best Paper Award
With Sayan Bhattacharya, Thatchaphol Saranurak, David Wajc
Dynamic Algorithms for Linear Programs under Relaxing or Restricting Updates (SODA2023, arXiv)
With Sayan Bhattacharya, Thatchaphol Saranurak
Presentation at ETH oline seminar
Deterministic Dynamic Matching In Worst-Case Update Time (ITCS2022 arXiv)
Best Student Paper Award
Presentation at ITCS2022
Deterministic Rounding of Dynamic Fractional Matchings (ICALP2021 arXiv)
With Sayan Bhattacharya
Best Paper Award (Track A)
Presentation by Sayan Bhattacharya at the DIMAP seminar, Warwick
Journal Papers
Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time (JACM 2024)
With Sayan Bhattacharya, Thatchaphol Saranurak, David Wajc
Deterministic Dynamic Matching In Worst-Case Update Time (Algorithmica 2023)
Publications outside of TCS
Deep Learning - based atherosclerotic coronary plaque segmentation on coronary CT angiography (European Radiology 2022)
With Natasa Jávorszky, Bálint Homonnay, Gary Gerstenblith, David Bluemke, Mihály Török, David Celentano, Hong Lai, Shenghan Lai, Márton Kolossváry
Teaching Work
Senior Graduate Teaching Assistant for CS136 Warwick, Discrete Mathematics and Its Applications (2020 - 2024)
Senior Graduate Teaching Assistant for CS147 Warwick, Discrete Mathematics and Its Applications 2 (2023-2024)
Senior Graduate Teaching Assistant for CS356, Warwick, Approximation and Randomized Algorithms (2020-2023)
Senior Graduate Teaching Assistant for CS260, Warwick, Algorithms (2020-2024)
Senior Graduate Teaching Assistant for CS430/910 Warwick, Foundations of Data Analytics (2023-2024)
Course Editor for Certificate in Artificial Intelligence, Oxford University Department for Continuing Education (2019-2021)
Research Visits/Internships
- Internship at Google Research, 2023 April-2024 April
- Internship at Max-Planck-Institut für Informatik, 2022 October - 2023 February
Conference/Seminar/Workshop Presentations
STOC2024: Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
FOCS2023, YRM, Google Research theory seminar, Weizman-Warwick workshop, ITTC, MPI theory seminar, HALG2023, DIMACS2023: Dynamic (1+\epsilon)-Approximate Matching Size in Truly Sublinear Update Time
STOC2023: Sublinear Algorithms for (3/2+\epsilon)-Approximate Matching
SODA2023: Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time, Dynamic Algorithms for Linear Programs under Relaxing or Restricting Updates
ETH theory online seminar, Dogsthul dynamic seminar, SODA2023: Dynamic Algorithms for Linear Programs under Relaxing or Restricting UpdatesYR
ITCS2022, HALG2022: Deterministic Dynamic Matching In Worst-Case Update Time
ICALP2021, WPTCS2022: Deterministic Rounding of Dynamic Fractional Matchings