Ronen Vaisenberg

Under Construction.

I'm starting a list of amazing (or at least very cool) problems that ignite my passion to the field of Computer Science and will hopefully affect others.

I'll try adding the smallest number of representative problems in each CS area. All problems are aimed to be understood by talented people, without any CS background. Please email me if you think I should add/change or remove something from my list.

Distributed Systems

•The Byzantine Generals problem: Two generals are on hills either side of a valley. They each have an army of 1000 soldiers. In the woods in the valley is an enemy army of 1500 men. If each general attacks alone, his army will lose. If they attack together, they will win. They wish to send messengers through the valley to coordinate when to attack. However, the messengers may get lost or caught in the woods (or brainwashed into delivering different messages). How can they devise a scheme by which they either attack with high probability, or not at all?

Status: Solved under (realistic) assumptions.

Algorithms

•The Stable Matching problem: Given a group of 100 man and 100 woman, each member of the group ranks the members of the opposite sex according to preference.
Can you match every man to exacly one woman, without missing out even one true love.
Example of a true love missed: If Joe prefers Marry over his matched partner and so does Marry.

Status: Solved.

1.        The Subset Sum problem: Given a set of n numbers, determine if there is a way to assign each number to one of two groups such that the sum of elements at both groups is equal.

Status: No better solution than iterating over all options is known.