Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 9 of 9 for “"Fine-grained complexity"”.
-
Fine-Grained Complexity: Exploring Reductions and their Properties
Η σχεδίαση αλγορίθμων αποτελεί ένα απο τα κύρια θέματα ενδιαφέροντος για τον τομέα της Πληροφορικής. Παρά τα πολλά αποτελέσματα σε ορισμένους τομείς, η προσέγγιση αυτή έχει πετύχει κάποια πρακτικά αδιέξοδα που έχουν αποδειχτεί προβληματικά στην πρόοδο του τομέα. Επίσης, οι κλασικές πρακτικές …
-
Algorithms, parallelism and fine-grained complexity for shortest path problems in sparse graphs
… and distributed settings. We also present fine-grained reductions that establish fine-grained hardness for several problems related to shortest paths. In the sequential context, we consider the fine-grained complexity of sparse graph problems whose time complexities have stayed at Õ(mn) …
-
Distributed fault tolerant distance computation in graphs : algorithms and lower bounds
… little was known about the distributed round complexity of these problems. In many cases, we obtain near optimal bounds for our problems. The sequential fine-grained complexity of these fault-tolerant path problems is closely related to other fundamental graph problems, such as the Minimum …
-
Theoretical Bounds and Systems Development for Exact/Approximate Multiplicities in Bag PDBs
… under bag semantics which has PTIME data complexity. However, does this imply that bag probabilistic databases are practical? We strive to answer this question from both a theoretical as well as a systems perspective. The problem of computing the marginal probability of a tuple in the …
-
Scheduling and Packing Problems
… in polynomial time. The goal of parameterized complexity - and this thesis - is to find out exactly what makes these problems difficult to solve and to identify special cases that can be solved efficiently. One part of this is finding algorithms with running times that are efficient when …
-
Database-Inspired Reasoning Problems in Description Logics With Path Expressions
… of the “expressive power versus computational complexity” trade-off for the Z family of DLs, we provide a more fine-grained complexity analysis for the query entailment problem over ontologies. In the thesis we focus on tame fragments of ZOIQ, namely the fragments in which either one the three …
-
Ιδιότητες συναρτήσεων μέτρησης πλήθους λύσεων σε προβλήματα με εύκολη απόφαση ύπαρξης λύσης: πληρότητα, προσεγγισιμότητα, μαρκοβιανές αλυσίδες, αλλαγές φάσης
The complexity class #P is the class of functions that count the number of solutions to problems in NP, e.g. #SAT is the function that on input a formula ϕ returns the number of satisfying assignments of ϕ. NP-complete problems are hard to count, but there exist hard counting problems with decision …
-
Structural parameters, tight bounds, and parameterized approximation
… problems through structural parameterization andfine-grained analysis. For our problems of study we (i) locate the boundary betweenfixed-parameter tractability and W[1]-hardness, by giving improved hardness reductionsand designing new FPT algorithms; (ii) match natural DP algorithms with tight …