Parameterized Fine-Grained Reductions

During recent years the field of fine-grained complexity has bloomed to produce a plethora of results, with both applied and theoretical impact on the computer science community. The cornerstone of the framework is the notion of fine-grained reductions, which correlate the exact complexities of prob...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-02
Main Authors: Anastasiadi, Elli, Antonopoulos, Antonis, Pagourtzis, Aris, Petsalakis, Stavros
Format: Article
Language:English
Subjects:
Algorithms
Parameterization
Parameters
Run time (computers)
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:During recent years the field of fine-grained complexity has bloomed to produce a plethora of results, with both applied and theoretical impact on the computer science community. The cornerstone of the framework is the notion of fine-grained reductions, which correlate the exact complexities of problems such that improvements in their running times or hardness results are carried over. We provide a parameterized viewpoint of these reductions (PFGR) in order to further analyze the structure of improvable problems and set the foundations of a unified methodology for extending algorithmic results. In this context, we define a class of problems (FPI) that admit fixed-parameter improvements on their running time. As an application of this framework we present a truly sub-quadratic fixed-parameter algorithm for the orthogonal vectors problem. Finally, we provide a circuit characterization for FPI to further solidify the notion of improvement.
ISSN:2331-8422