Lab Lunch: 27 October 2020 - Kousha Etessami Title: Computing a fixed point of a monotone function, and some applications Abstract: The task of computing a fixed point of a monotone function arises in a variety of applications. In this talk I will describe recent work in which we have studied the computational complexity of computing a (any) fixed point of a given monotone function that maps a finite d-dimensional grid lattice with sides of length N = 2^n to itself, where the monotone function is presented succinctly via a Boolean circuit with d · n input gates and d · n output gates. The existence of such a fixed point is guaranteed by Tarski's theorem. In turns out that computing such a Tarski fixed point subsumes a number of important computational problems, including solving stochastic games, as well as computing a pure Nash equilibrium for supermodular games. We show that the Tarski fixed point problem is contained in both the total search complexity classes PLS and PPAD. Many questions remain open. I will discuss some of them. (This talk describes joint work with C. Papadimitriou, A. Rubinstein, and M. Yannakakis, in a paper titled: "Tarski's theorem, supermodular games, and the complexity of equilibria", that appeared in ITCS’2020.). Oct 27 2020 13.00 - 14.00 Lab Lunch: 27 October 2020 - Kousha Etessami Speaker: Kousha Etessami Online with Zoom or Skype Invitation Only
Lab Lunch: 27 October 2020 - Kousha Etessami Title: Computing a fixed point of a monotone function, and some applications Abstract: The task of computing a fixed point of a monotone function arises in a variety of applications. In this talk I will describe recent work in which we have studied the computational complexity of computing a (any) fixed point of a given monotone function that maps a finite d-dimensional grid lattice with sides of length N = 2^n to itself, where the monotone function is presented succinctly via a Boolean circuit with d · n input gates and d · n output gates. The existence of such a fixed point is guaranteed by Tarski's theorem. In turns out that computing such a Tarski fixed point subsumes a number of important computational problems, including solving stochastic games, as well as computing a pure Nash equilibrium for supermodular games. We show that the Tarski fixed point problem is contained in both the total search complexity classes PLS and PPAD. Many questions remain open. I will discuss some of them. (This talk describes joint work with C. Papadimitriou, A. Rubinstein, and M. Yannakakis, in a paper titled: "Tarski's theorem, supermodular games, and the complexity of equilibria", that appeared in ITCS’2020.). Oct 27 2020 13.00 - 14.00 Lab Lunch: 27 October 2020 - Kousha Etessami Speaker: Kousha Etessami Online with Zoom or Skype Invitation Only
