Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with fine-grained complexity:
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 >>>

TR17-130 | 30th August 2017
Oded Goldreich, Guy Rothblum

Worst-case to Average-case reductions for subclasses of P

Revisions: 2

For every polynomial $q$, we present worst-case to average-case (almost-linear-time) reductions for a class of problems in $\cal P$ that are widely conjectured not to be solvable in time $q$.
These classes contain, for example, the problems of counting the number of $k$-cliques in a graph, for any fixed $k\geq3$.
more >>>

TR18-092 | 4th May 2018
Marco Carmosino, Russell Impagliazzo, Manuel Sabin

Fine-Grained Derandomization: From Problem-Centric to Resource-Centric Complexity

We show that popular hardness conjectures about problems from the field of fine-grained complexity theory imply structural results for resource-based complexity classes. Namely, we show that if either k-Orthogonal Vectors or k-CLIQUE requires $n^{\epsilon k}$ time, for some constant $\epsilon > 1/2$, to count (note that these conjectures are significantly ... more >>>

ISSN 1433-8092 | Imprint