Raphael Yuster

Raphael "Raphy" Yuster (Hebrew: רפאל יוסטר) is an Israeli mathematician specializing in combinatorics and graph theory. He is a professor of mathematics at the University of Haifa. He is a recipient of the Nerode Prize for his work on color-coding,^[1][A] and is also known for the Alon–Yuster conjecture relating the chromatic numbers of graphs to the number of disjoint copies of a smaller graph that can be found in a larger one, later proven by János Komlós, Gábor N. Sárközy, and Endre Szemerédi.^[2][B]

Education and career

Yuster was a student at Tel Aviv University, where he received a bachelor's degree in 1989, a master's degree in 1991, and a Ph.D. in 1995.^[3] His doctoral dissertation, Non Constructive Graph Theoretic Proofs and Their Algorithmic Aspects, was supervised by Noga Alon.^[4]

He has been a faculty member at the University of Haifa since 2004.^[5]

Recognition

With Noga Alon and Uri Zwick, Yuster was a recipient of the 2019 Nerode Prize, given for their work on color coding, an application of the probabilistic method to subgraph isomorphism.^[1][A]

His work with Zwick on sparse matrix multiplication received the 2023 European Symposium on Algorithms Test-of-Time Award.^[6][C]

Selected publications

A.	Alon, Noga; Yuster, Raphael; Zwick, Uri (1995), "Color-coding", Journal of the ACM, 42 (4): 844–856, doi:10.1145/210332.210337, MR 1411787

B.	Alon, Noga; Yuster, Raphael (1996), "H-factors in dense graphs", Journal of Combinatorial Theory, Series B, 66 (2): 269–282, doi:10.1006/jctb.1996.0020, MR 1376050

C.	Yuster, Raphael; Zwick, Uri (2005), "Fast sparse matrix multiplication", ACM Transactions on Algorithms, 1 (1): 2–13, doi:10.1145/1077464.1077466, MR 2163127; previously announced at ESA 2004

See also

• Rainbow coloring, the topic of several works by Yuster