Fine-Grained Complexity: Exploring Reductions and their Properties

Postgraduate Thesis uoadl:2815281 105 Read counter

Unit:
Κατεύθυνση Αλγόριθμοι, Λογική και Διακριτά Μαθηματικά (Α.Λ.ΜΑ.)
Πληροφορική
Deposit date:
2018-10-30
Year:
2018
Author:
Petsalakis Stavros
Supervisors info:
Αρης Παγουρτζής, Αναπληρωτής Καθηγητής, Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Εθνικό Μετσόβιο Πολυτεχνείο
Στάθης Ζάχος, Ομότιμος Καθηγητής, Ηλεκτρολόγων Μηχανικών και Μηχανικών Υπολογιστών, Εθνικό Μετσόβιο Πολυτεχνείο
Βασίλης Ζησιμόπουλος, Καθηγητής, Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Fine-Grained Complexity: Exploring Reductions and their Properties
Languages:
English
Translated title:
Fine-Grained Complexity: Exploring Reductions and their Properties
Summary:
Algorithmic design has been one of the main subjects of interest for Computer science. While very effective in some areas, this approach has been met with some practical dead ends that have been very problematic in the progress of the field. Classical Computational Complexity practices have also not been able to bypass these blocks. Understanding the hardness of each problem is not trivial. Fine-Grained Complexity provides new perspectives on classic problems, resulting to solid links between famous conjectures in Complexity, and Algorithmic design. It serves as a tool to prove conditional lower bounds for problems with polynomial time complexity, a field that had seen very little progress until now. Popular conjectures such as SETH, k-OV, 3SUM, and APSP, imply many bounds that have yet to be proven using classic techniques, and provide a new understanding of the structure and entropy of problems in general. The aim of this thesis is to contribute towards solidifying the framework for reductions from each conjecture, and to explore the structural difference between the problems in each case
Main subject category:
Technology - Computer science
Keywords:
Reductions, Complexity, Hardness in P
Index:
Yes
Number of index pages:
4
Contains images:
Yes
Number of references:
92
Number of pages:
80
StavrosPetsalakisMscThesis.pdf (586 KB) Open in new window