All reports by Author Mihalis Yannakakis:

__
TR24-057
| 28th March 2024
__

Xi Chen, Yuhao Li, Mihalis Yannakakis#### Computing a Fixed Point of Contraction Maps in Polynomial Queries

__
TR23-073
| 15th May 2023
__

Xi Chen, Yuhao Li, Mihalis Yannakakis#### Reducing Tarski to Unique Tarski (in the Black-box Model)

__
TR19-040
| 19th February 2019
__

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis#### The Complexity of Finding {$S$}-factors in Regular Graphs

__
TR13-069
| 1st May 2013
__

Kousha Etessami, Alistair Stewart, Mihalis Yannakakis#### A note on the complexity of comparing succinctly represented integers, with an application to maximum probability parsing

Xi Chen, Yuhao Li, Mihalis Yannakakis

We give an algorithm for finding an $\epsilon$-fixed point of a contraction map $f:[0,1]^k\rightarrow [0,1]^k$ under the $\ell_\infty$-norm with query complexity $O (k^2\log (1/\epsilon ) )$.

more >>>Xi Chen, Yuhao Li, Mihalis Yannakakis

We study the problem of finding a Tarski fixed point over the $k$-dimensional grid $[n]^k$. We give a black-box reduction from the Tarski problem to the same problem with an additional promise that the input function has a unique fixed point. It implies that the Tarski problem and the unique ... more >>>

Sanjana Kolisetty, Linh Le, Ilya Volkovich, Mihalis Yannakakis

A graph $G$ has an \emph{$S$-factor} if there exists a spanning subgraph $F$ of $G$ such that for all $v \in V: \deg_F(v) \in S$.

The simplest example of such factor is a $1$-factor, which corresponds to a perfect matching in a graph. In this paper we study the computational ...
more >>>

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, via arithmetic

circuits using only multiplication and division gates, and integer

inputs:

Input instance: four lists of positive integers:

$a_1, \ldots , a_n; \ b_1, \ldots ,b_n; \ ... more >>>