Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ivan Mikhailin:

TR19-002 | 31st December 2018
Alexander Kulikov, Ivan Mikhailin, Andrey Mokhov, Vladimir Podolskii

Complexity of Linear Operators

Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$?

As we observe in this paper, this problem contains ... more >>>

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

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

ISSN 1433-8092 | Imprint