📑 Table of Contents▼

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

📚 Artikel Terkait di Wikipedia

Yuster

Yuster is a surname. Notable people with the surname include: Raphael Yuster, Israeli mathematician Rose Yuster, American anarchist, member of No Conscription

Greedy algorithm

use greedy strategies in proofs as well. A classic example is what Raphael Yuster refers to as the greedy proof that every tournament in graph contains

Blow-up lemma

(for a fixed k {\displaystyle k} ) in 1998. In 1995, Noga Alon and Raphael Yuster considered the generalization of the well-known Hajnal–Szemerédi theorem

Noga Alon

103–112. doi:10.1016/0001-8708(92)90052-M. MR 1185788. Alon, Noga; Yuster, Raphael; Zwick, Uri (1995). "Color-coding". Journal of the ACM. 42 (4): 844–856

Color-coding

color-coding method was proposed and analyzed in 1994 by Noga Alon, Raphael Yuster, and Uri Zwick. The following results can be obtained through the method

Nerode Prize

kernels for odd cycle transversal and related problems. 2019: Noga Alon, Raphael Yuster, and Uri Zwick, for inventing the Color-coding technique, a vastly important

Rainbow coloring

S2CID 7505197. Chakraborty, Sourav; Fischer, Eldar; Matsliah, Arie; Yuster, Raphael (2011), "Hardness and algorithms for rainbow connection", Journal of

Second neighborhood problem

1016/j.dam.2021.12.034, ISSN 0166-218X Chen, Guantao; Shen, Jian; Yuster, Raphael (2003), "Second neighborhood via first neighborhood in digraphs", Annals