The Taub Faculty of Computer Science Events and Talks

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). Short Bio: ========== 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