Moshe Babaioff

Faculty @CseHuji. Algorithmic Game Theory. Fairness.

[Inbal Talgam-Cohen @InbalTalgam]

הכנס של מדעי המחשב יהיה לזכר מיכאל רבין, עם הרצאות מרכזיות של @ShafiGoldwasser, @IritDinur, Ronitt Rubinfeld

הרשמה כאן:
https://t.co/q8lL5lBCTr

[Daniel Bachmat @DanielBachmat]

��א שמעתם על זה בחדשות, אבל השבוע נפטר אחד מגדולי ישראל - חלוץ מדעי המחשב מיכאל רבין.

היום נתקלתי בפוסט המצורף מטה ⬇️ של התלתל שנותן הזדמנות מעולה להסביר את אחד מההישגים הרבים של רבין.

התלתל מצא מספר ראשוני עם 6,624 ספרות שנראה כמו דיוקן של דמות מוכרת. על פניו זה ממש קסם. איך מוצאים מספר כזה?

מתחילים הפוך - לוקחים תמונה של האדם, מחלקים אותה ל-6,624 פיקסלים, מתאימים לכל גוון של פיקסל ספרה והמוח כבר משלים לבד את התמונה.

אבל יש בעיה, למה שייצא דווקא מספר ראשוני? אין סיבה. רק אחת מכל עשרת אלפים תמונות כאלו בערך תהיה מספר ראשוני. כדי לפתור את זה התלתל השתמש בטריק - הוא שינה את 5 הספרות האחרונות של המספר שוב ושוב עד שמצא קומבינציה שנותנת מספר ראשוני.

אבל עדיין יש בעיה גדולה - בכל פעם שמשנים את הספרות איך אפשר לבדוק שיצא מספר ראשוני? אם אנחנו תמימים ננסה פשוט לחלק את המספר שיצא במספרים שקטנים ממנו ורק אם הוא לא מתחלק באף אחד נדע שהוא ראשוני. הבעיה היא שזה מספר כל כך גדול, שגם אם נקח את כל החומר ביקום ונכין ממנו מחשב-על שינסה לבחון את כל החלוקות האפשריות עדיין ייקח הרבה הרבה יותר זמן מגיל היקום כדי לוודא שהמספר ראשוני.

אז איך התלתל הצליח למצוא מספר כזה בכמה דקות במחשב ביתי?
בזכות מיכאל רבין.

רבין התבסס על רעיון של גרי מילר שבעצמו התבסס על רעיון בן 300 שנה של פרמה. הוא בנה מן מבחן חישובי, שאם הוא מבוצע למספר ראשוני התשובה היא תמיד ״כן״ ואם המספר לא ראשוני אז יש סיכוי של 75% לפחות ל״לא״. את המבחן הזה מריצים שוב ושוב 10-20 פעמים ואם כל הזמן התשובה היא ״כן״ אפשר לק��וע מעבר לכל ספק סביר שמדובר בראשוני.

המבחן הזה, שנקרא מבחן מילר-רבין הוא לא סתם שעשוע מתמטי, הוא בשימוש יומיומי בכל העולם לצרכים פרקטיים. זאת מכיוון שחלק גדול מהתקשורת המוצפנת בין מחשבים מתבססת על מציאת מספרים ראשוניים גדולים. התגלית הזו, פשוטו כמשמעו, שווה מיליארדים.

זו רק דוגמה אחת להישג של רבין. כיליד 1931 שהחל את הקריירה בשנות החמישים, הוא פרח בתקופה שבה מחשבים פיזיים היו נדירים ומסורבלים. תקופה שבה חלוצי מדעי המחשב ניסו להבין מה זה הכלי החדש הזה ואיזה פוטנציאל גלום בו. הוא היה ממניחי היסודות לתחום שהפך לקריטי בכל אספקט בחיינו.

כל האוניברסיטאות הגדולות בארה״ב ובאירופה חיזרו אחרי רבין, אבל ב-1970 בחר להקים את החוג למדעי המחשב באוניברסיטה העברית (יחד עם אלי שמיר שגם נפטר השנה). ב-1976 היה הישראלי הראשון לזכות בפרס טיורינג, הנובל של מדעי המחשב.

נזכור לברכה את החלוץ שסלל את הדרך בתחום שהפך לסמל להצלחה ישראלית.

[ACM SIGecom @AcmSIGecom]

Reminder: register your #ACMEC26 abstracts by *tomorrow*, 11:59pm anywhere on earth. Paper submission then due 7 days later, Feb 9, 11:59pm AoE.

[Michal Feldman @MichalFeldman9]

📢Excited to announce: EC'26

📅 When: July 6–10, 2026
🍝 Where: Rome, Italy

General Chair: Stefano Leonardi
PC Chairs: Alex Teytelboym & Matt Weinberg

Hope to see as many of you there!

@AcmSIGecom @econD47
#ACMEC26

[Aaron Roth @Aaroth]

Check out the terrific set of EC 2025 accepted papers! https://t.co/U0rQXig9ay

[Aaron Roth @Aaroth]

EC 2025 will be held at Stanford from July 7-12. Itai Ashlagi and I are the chairs. The abstract deadline is February 3, and the paper deadline is February 10. The scope is inclusive of many topics across CS, economics, and operations research. Submit your best work!

[Moshe Babaioff @moshebab]

@hasolidit אסטרטגיה ידועה בשם “Buy, Borrow, Die”

[Haris Aziz @harisazizk]

ACM EC'25 will be at Stanford, CA, from July 7-11 2025

https://t.co/H6DV9ojOA4

[Moshe Babaioff @moshebab]

New paper with Noam Nisan

[Noam Nisan @noamnisan]

New paper: On the Optimality of EIP-1559 for Patient Bidders https://t.co/SZSLK5Yfjl

[Moshe Babaioff @moshebab]

We will never forget

[Elad Simchayoff @Elad_Si]

Yuval, a Nova music festival survivor:
“I saw my husband dead. I smeared his blood on me and on my friends so if the terrorists look at us they’ll think we are dead.
We saw point blank killings and kidnapping but the hardest thing we witnessed was the rape. I never heard cries for help like from that woman”.

[Yannai A. Gonczarowski @YannaiGonch]

"𝘛𝘩𝘦𝘳𝘦'𝘴 𝘢 𝘨𝘳𝘪𝘦𝘧 𝘵𝘩𝘢𝘵 𝘤𝘢𝘯'𝘵 𝘣𝘦 𝘴𝘱𝘰𝘬𝘦𝘯
𝘛𝘩𝘦𝘳𝘦'𝘴 𝘢 𝘱𝘢𝘪𝘯 𝘨𝘰𝘦𝘴 𝘰𝘯 𝘢𝘯𝘥 𝘰𝘯
𝘌𝘮𝘱𝘵𝘺 𝘤𝘩𝘢𝘪𝘳𝘴 𝘢𝘵 𝘦𝘮𝘱𝘵𝘺 𝘵𝘢𝘣𝘭𝘦𝘴
𝘕𝘰𝘸 𝘮𝘺 𝘧𝘳𝘪𝘦𝘯𝘥𝘴 𝘢𝘳𝘦 𝘥𝘦𝘢𝘥 𝘢𝘯𝘥 𝘨𝘰𝘯𝘦"

Exactly a year ago, the largest massacre of Jewish people since the Holocaust took place.

More than 1100 were murdered in this massacre, in which also employees of the "United Nations Relief and Works Agency for Palestine Refugees" @UNRWA participated. In addition, more than 250 hostages were abducted that day from their homes or from a music festival, during a Saturday morning on a Jewish holiday. Over a hundred of those abducted are still held by Hamas and by others in Gaza and not allowed any Red Cross @ifrc visits. These include then-9-month-old baby Kfir Bibas, who has by now spent most of his life in captivity, as well as five American citizens still in captivity. For more than half of the hostages, we don't even know whether they are alive.

The next day, Hezbollah—a terrorist organization from Lebanon, a country with whom Israel has no internationally recognized territorial dispute—has started raining rockets on the north of Israel, which it continues non-stop to this day, and a year later, still many of those living in the north of Israel cannot safely return home.

Today is a day of mourning. Whoever celebrates "resistance" more today than on other days is celebrating the rape, murder, and mutilation of Jewish people. Whoever marks "a year of genocide in Gaza" today out of all days despite the Israeli defensive counterstrike on Gaza not starting on October 7, both urgently needs a history lesson on what genocide is, and is celebrating the rape and murder of Jewish people.

Mourning today doesn't make anyone anti-Palestinian; in contrast, bashing Jews today is extremely telling.

Let them go. Bring them home.

[Hebrew University @HebrewU]

The Hebrew University bows its head in memory of the 30 members of our university community who were murdered, killed, and fell in the wake of the October 7th massacre and the outbreak of the Iron Swords War. Each and every one of them was a world unto themselves. They will forever remain in our hearts—students, faculty, alumni, and partners. We will remember them all, always. #NeverForget

[Hebrew University @HebrewU]

The Hebrew University of Jerusalem bows its head in mourning for Carmel Gat, a Master’s student at the School of Occupational Therapy, who was murdered while in the captivity of Hamas.

The bodies of Carmel and five others were tragically recovered by the IDF from a Hamas terror tunnel in Rafah, Gaza.

We also mourn the loss of Hersh Goldberg-Polin (23), Almog Sarusi (27), Ori Danino (25), Alexander Lobanov (33), and Eden Yerushalmi (24).

May their memories forever be a blessing. 🕯️

[Moshe Babaioff @moshebab]

That is great, welcome!

[Deborah Marciano @DeborahMarcian0]

Delighted to announce that I'll be joining the Federmann Center for the Study of Rationality at @HebrewU. This is truly a dream come true!

[Moshe Babaioff @moshebab]

We start in five minutes. See you!

[Moshe Babaioff @moshebab]

Excited about the tutorial next week!

[Moshe Babaioff @moshebab]

@ittaia @lauradoval @AcmSIGecom Yes

[Laura Doval @lauradoval]

🚨🚨Starts 11 am ET🚨🚨
You have one more chance to partake of the @AcmSIGecom #EC24 tutorials: @moshebab and Uri Feige will be talking about **Fair allocation of indivisible items**

[Laura Doval @lauradoval]

🚨🚨🚨Coming tomorrow: @AcmSIGecom #EC24 tutorials 🚨🚨🚨 We have an amazing lineup of speakers and topics. Don't forget to register!

[Moshe Babaioff @moshebab]

Excited about the tutorial next week!

[Laura Doval @lauradoval]

📢📢 We are closing the @AcmSIGecom #EC24 tutorials with 🎆🎆
Join us on June 27 at 11 am ET to learn about fairness from @moshebab and Uri Feige about Fair allocation of indivisible items

In the meantime, read more about the tutorial from Moshe's post

[Alon Eden @AlonEden8]

Really excited about this year's #EC24Tutorials! @lauradoval and received an amazingly high quality set of proposals, 8 (!) of them will appear on the program in EC24 Preview week, June 25-27:
https://t.co/WHqvzYDe4n

Registration:
https://t.co/KsPlSTrdBI