Uri Zwick - COLLOQUIUM LECTURE- CANCELLED
Advisor: Dept. of Computer Science - Tel-Aviv University
Two-player turn-based zero-sum stochastic games is an interesting family
of infinite duration games played on a finite set of states. These games
may be seen as an extension of Markov Decisions Processes (MDPs) to a
two-player setting. Such games have applications in various areas
ranging from Artificial Intelligence, Operations Research and Automatic
Verification. From the theoretical point of view they are interesting
because they are known to be in NP intersection co-NP, yet no polynomial
time algorithm is known for their solution. They also belong to the
complexity classes PLS, PPAD and CLS, but are not known to be complete
in then. The talk will survey known algorithmic approaches for solving
such games, as well as restricted families of games such as Mean Payoff
Games (MPGs) and Parity Games (PGs).
Uri Zwick has worked on graph algorithms, in particular on distances in graphs and on the
color-coding technique for subgraph isomorphism. With Howard Karloff, he is the namesake
of the Karloff-Zwick algorithm for approximating the MAX-3SAT problem of Boolean
satisfiability. He and his coauthors have won the David P. Robbins Prize in 2011 for their
work on the block-stacking problem.
Zwick earned a bachelor's degree from the Technion, and completed his doctorate at Tel
Aviv University in 1989 under the supervision of Noga Alon. He is currently a professor
of computer science at Tel Aviv University.
Rereshments will be served from 14:15
Lecture starts at 14:30