In this talk we will describe some of our recent work giving new upper and lower bounds on the approximability of constraint satisfaction problems (CSPs) in the streaming and sketching settings.

A game with *perfect information* is a game in which no information is hidden from the players. All players know the rules and the state of the game at all times.

We show EOPL=PLS PPAD. Here the class EOPL consists of all total search problems that reduce to the End-of-Potential-Line problem, which was introduced in the works by Hubacek and Yogev (SICOMP 2020) and Fearnley et al. (JCSS 2020).

Reconfiguring a system (generally represented by a graph) means gradually transforming one configuration of the system to another configuration by modifying it in a slow and steady step-by-step manner.