All reports by Author Jiawei Gao:

__
TR19-045
| 19th February 2019
__

Jiawei Gao#### On the Fine-grained Complexity of Least Weight Subsequence in Graphs

Revisions: 1

__
TR19-009
| 16th January 2019
__

Jiawei Gao, Russell Impagliazzo#### The Fine-Grained Complexity of Strengthenings of First-Order Logic

Revisions: 1

__
TR16-053
| 6th April 2016
__

Jiawei Gao, Russell Impagliazzo#### Orthogonal Vectors is hard for first-order properties on sparse graphs

Revisions: 3

__
TR15-148
| 9th September 2015
__

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider#### Nondeterministic extensions of the Strong Exponential Time Hypothesis and consequences for non-reducibility

Revisions: 1

Jiawei Gao

Least Weight Subsequence (LWS) is a type of highly sequential optimization problems with form $F(j) = \min_{i < j} [F(i) + c_{i,j}]$. They can be solved in quadratic time using dynamic programming, but it is not known whether these problems can be solved faster than $n^{2-o(1)}$ time. Surprisingly, each such ... more >>>

Jiawei Gao, Russell Impagliazzo

The class of model checking for first-order formulas on sparse graphs has a complete problem with respect to fine-grained reductions, Orthogonal Vectors (OV) [GIKW17]. This paper studies extensions of this class or more lenient parameterizations. We consider classes obtained by allowing function symbols;

first-order on ordered structures; adding various notions ...
more >>>

Jiawei Gao, Russell Impagliazzo

Fine-grained reductions, introduced by Vassilevska-Williams and Williams, preserve any improvement in the known algorithms. These have been used very successfully in relating the exact complexities of a wide range of problems, from NP-complete problems like SAT to important quadratic time solvable problems within P such as Edit Distance. However, until ... more >>>

Marco Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mikhailin, Ramamohan Paturi, Stefan Schneider

We introduce the Nondeterministic Strong Exponential Time Hypothesis

(NSETH) as a natural extension of the Strong Exponential Time

Hypothesis (SETH). We show that both refuting and proving

NSETH would have interesting consequences.

In particular we show that disproving NSETH would ...
more >>>