138 citations · 191 across the 22 of their papers we have counts for
11 papers · 1 filter
Tarski Fixed Points in Quasi-FPT Queries
Xi Chen, Ruiquan Gao, Yuhao Li +2
We study the query complexity of finding a Tarski fixed point over . Previous work has left a large gap between and . We show tha…
The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
Xi Chen, Yuhao Li, Mihalis Yannakakis
We give an -query algorithm for finding a Tarski fixed point over the -dimensional lattice , matching the lower bound of [EPRY20]. Additionally…
Computing a Fixed Point of Contraction Maps in Polynomial Queries
Xi Chen, Yuhao Li, Mihalis Yannakakis
We give an algorithm for finding an -fixed point of a contraction map under the -norm with query complexity .
The Smoothed Complexity of Policy Iteration for Markov Decision Processes
Miranda Christ, Mihalis Yannakakis
We show subexponential lower bounds (i.e., ) on the smoothed complexity of the classical Howard's Policy Iteration algorithm for Markov Decision Processes. The bounds h…
Extremal combinatorics, iterated pigeonhole arguments, and generalizations of PPP
Amol Pasarkar, Mihalis Yannakakis, Christos Papadimitriou
We study the complexity of computational problems arising from existence theorems in extremal combinatorics. For some of these problems, a solution is guaranteed to exist based on…
Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein +1
The use of monotonicity and Tarski's theorem in existence proofs of equilibria is very widespread in economics, while Tarski's theorem is also often used for similar purposes in th…
A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
The following two decision problems capture the complexity of comparing integers or rationals that are succinctly represented in product-of-exponentials notation, or equivalently,…
The Complexity of Non-Monotone Markets
Xi Chen, Dimitris Paparas, Mihalis Yannakakis
We introduce the notion of non-monotone utilities, which covers a wide variety of utility functions in economic theory. We then prove that it is PPAD-hard to compute an approximate…
Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic max(min) polynomial equations, referred to as maxPPSs (and minPP…
Polynomial Time Algorithms for Multi-Type Branching Processes and Stochastic Context-Free Grammars
Kousha Etessami, Alistair Stewart, Mihalis Yannakakis
We show that one can approximate the least fixed point solution for a multivariate system of monotone probabilistic polynomial equations in time polynomial in both the encoding siz…
Equilibria, Fixed Points, and Complexity Classes
Mihalis Yannakakis
Many models from a variety of areas involve the computation of an equilibrium or fixed point of some kind. Examples include Nash equilibria in games; market equilibria; computing o…