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
[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]- Rainbow coloring, the topic of several works by Yuster
References
[edit]- 1 2 EATCS-IPEC Nerode Prize 2019, European Association for Theoretical Computer Science, retrieved 2025-04-11
- ↑ 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
- ↑ Yuster, Raphael, Education, University of Haifa, retrieved 2025-04-11
- ↑ Raphael Yuster at the Mathematics Genealogy Project
- ↑ "Raphael Yuster", ORCiD, retrieved 2025-04-11
- ↑ "ESA Test-of-Time Award 2023", European Symposium on Algorithms, retrieved 2025-04-11
External links
[edit]- Home page
- Raphael Yuster publications indexed by Google Scholar
