All reports by Author Mihalis Yannakakis:

__
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

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 >>>