I'm an associate professor at the school of information science at JAIST.
Before joining JAIST, I was a postdoctoral researcher at NII, Tokyo hosted by Prof. Ken-ichi Kawarabayashi. Before coming to Japan, I completed my PhD at the Technion under the supervision of Prof. Keren Censor-Hillel.
My main research field is graph algorithms, but I also have a broad interest in theoretical computer science.
I am currently supported by JSPS KAKENHI grant 25K00370.
dblp・Google Scholar・greg@jaist.ac.jp
For potential students
To get a rough understanding of my research, please take a look at the following videos:
Mini-batch k-means terminates in O(d/ϵ) iterations
On the Complexity of Load Balancing in Dynamic Networks
Models of Smoothing in Dynamic Networks
Improved Distributed Approximations for Maximum Independent Set
PC member: ACDA 2025, PODC 2025, ICDCN 2025, SSS 2024, OPODIS 2023, ISAAC 2023, PODC 2023, DISC 2021, PDAA 2019
Co-organizer: Shonan Meeting on Algorithmic tools and their applications in emerging models of computation 2025 - Big thanks to all the people that attended! No complaints about the food this time 😎
Co-organizer: Shonan Meeting on Locality in Computation, 2023 - Big thanks to all the people that attended! Sorry about the food ;)
Co-organizer: Shonan Meeting on Distributed Graph Algorithms, 2019 - Big thanks to all the people that attended!
(sub)reviewer: ICML, KDD, ICLR, Distributed Computing, Theory of Computing, Algorithmica, STOC, FOCS, SODA, DISC, ESA, STACS, SOSA, PODC, SPAA, SIROCCO
Co-organizer: CS Technion Theory Lunch, 2017
Publications:
Ran Ben Basat, Keren Censor-Hillel, Yi-Jun Chang, Wenchen Han, Dean Leitersdorf, Gregory Schwartzman:
Bounded Memory in Distributed Networks. SPAA 2025 (to appear)
Ben Jourdan, Gregory Schwartzman, Peter Macgregor, He Sun:
(*) Coreset Spectral Clustering. ICLR 2025 (poster)
Uri Meir, Gregory Schwartzman, Yuichi Yoshida:
Stochastic Distance in Property Testing. RANDOM 2024
Gregory Schwartzman:
Local Max-Cut on Sparse Graphs. ESA 2024
Gregory Schwartzman:
Mini-batch k-means terminates within O(d/ε) iterations. ICLR 2023 (poster)
Taisuke Izumi, Naoki Kitamura, Takamasa Naruse, Gregory Schwartzman:
Fully Polynomial-Time Distributed Computation in Low-Treewidth Graphs. SPAA 2022
Gregory Schwartzman, Yuichi Sudo:
Smoothed Analysis of Population Protocols. DISC 2021
Keren Censor-Hillel, Victor I. Kolobov, Gregory Schwartzman:
Finding Subgraphs in Highly Dynamic Networks. SPAA 2021
Seth Gilbert, Uri Meir, Ami Paz, Gregory Schwartzman:
On the Complexity of Load Balancing in Dynamic Networks. SPAA 2021
Uri Meir, Ami Paz, Gregory Schwartzman:
Models of Smoothing in Dynamic Networks. DISC 2020
Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, Gregory Schwartzman:
Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks. OPODIS 2020
Invited as an hour-long presentation to DiADN workshop @ DISC 2019.
Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, Gregory Schwartzman:
Improved Distributed Approximation to Maximum Independent Set. DISC 2020
Also appeared in: PODC 2020 (Brief announcement).
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman:
Optimal Distributed Covering Algorithms. DISC 2019
Invited to Distributed Computing special issue
Also appeared in: WOLA 2019, HALG 2019 (contributed), PODC 2019 (Brief announcement).
Ran Ben-Basat, Ken-ichi Kawarabayashi, Gregory Schwartzman:
Parameterized Distributed Algorithms. DISC 2019
Ken-ichi Kawarabayashi, Gregory Schwartzman:
Adapting Local Sequential Algorithms to the Distributed Setting. DISC 2018
Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman:
A Deterministic Distributed 2-Approximation for Weighted Vertex Cover in O(log n logΔ/ log2 logΔ) Rounds. SIROCCO 2018
Ami Paz, Gregory Schwartzman:
A (2 + ε)-Approximation for Maximum Weight Matching in the Semi-Streaming Model. SODA 2017
Best student paper award and best paper award
Invited to TALG special issue, invited to HALG 2017
Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, Gregory Schwartzman:
Distributed Approximation of Maximum Independent Set and Maximum Matching. PODC 2017
Invited to Distributed Computing special issue
Keren Censor-Hillel, Merav Parter, Gregory Schwartzman:
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. DISC 2017
Invited to Distributed Computing special issue
Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman:
A Distributed (2+ε)-Approximation for Vertex Cover in O(logΔ / ε log logΔ) Rounds. PODC 2016
Best student paper award
Invited to JACM special issue
Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, Yadu Vasudev:
Fast Distributed Algorithms for Testing Graph Properties. DISC 2016
Keren Censor-Hillel, Merav Parter, Gregory Schwartzman:
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. Distributed Computing 33(3-4): 349-366 (2020)
Keren Censor-Hillel, Eldar Fischer, Gregory Schwartzman, Yadu Vasudev:
Fast Distributed Algorithms for Testing Graph Properties. Distributed Computing 32(1): 41-57 (2019)
Ami Paz, Gregory Schwartzman: A (2 + ε)-Approximation for Maximum Weight Matching in the Semi-Streaming Model. ACM Trans. Algorithms 15(2): 18:1-18:15 (2019)
Reuven Bar-Yehuda, Keren Censor-Hillel, Gregory Schwartzman:
A Distributed (2+ε)-Approximation for Vertex Cover in O(logΔ / ε log logΔ) Rounds. J. ACM 64(3): 23:1-23:11 (2017)