Unit:
Department of Informatics and TelecommunicationsΠληροφορική
Author:
VASILAKIS VASILEIOS
Supervisors info:
ΑΡΧΟΝΤΙΑ ΓΙΑΝΝΟΠΟΥΛΟΥ, ΕΠΙΚΟΥΡΗ ΚΑΘΗΓΗΤΡΙΑ, ΤΜΗΜΑ ΠΛΗΡΟΦΟΡΙΚΗΣ ΚΑΙ ΤΗΛΕΠΙΚΟΙΝΩΝΙΩΝ, ΕΚΠΑ
Original Title:
Consequences of Polynomial Hierarchy in Parameterized Complexity: Tight Lower Bounds
Translated title:
Consequences of Polynomial Hierarchy in Parameterized Complexity: Tight Lower Bounds
Summary:
An abstract 2-person communication model is presented and defined, where the 2 participants use a predetermined communication protocol between them, in order to decide a predetermined language. With each protocol, a cost is defined and quantified, and the goal is to minimize the cost across all protocols. In this direction, trivial protocols are presented for the NP-Complete problems of d-Sat and d-Vertex-Cover. These trivial protocols, assuming the polynomial hierarchy does not collapse, are proven to be cost-optimal. This fact has interesting consequences regarding areas of Parameterized Complexity for these problems, and in particular the areas of sparsification, kernelization and lossy compression. These consequences are presented as corollaries of the main results.
Main subject category:
Science
Keywords:
Computation by Abstract Devices, Circuit Complexity, Polynomial Reductions, Polynomial Hierarchy, Communication Protocol
