Raphael Yuster

  1. Home
  2. Wiki

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

[edit]

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

[edit]

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

[edit]
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

[edit]

References

[edit]
  1. ^ a b EATCS-IPEC Nerode Prize 2019, European Association for Theoretical Computer Science, retrieved 2025-04-11
  2. ^ Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre (2001), "Proof of the Alon–Yuster conjecture", Discrete Mathematics, 235 (1–3): 255–269, doi:10.1016/S0012-365X(00)00279-X, MR 1829855
  3. ^ Yuster, Raphael, Education, University of Haifa, retrieved 2025-04-11
  4. ^ Raphael Yuster at the Mathematics Genealogy Project
  5. ^ "Raphael Yuster", ORCiD, retrieved 2025-04-11
  6. ^ "ESA Test-of-Time Award 2023", European Symposium on Algorithms, retrieved 2025-04-11
[edit]