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 5 of 5 for “"Counting complexity"”.
-
Counting complexity: compressed Ηamming distance, vertex covers and recent highlights
Σε αυτήν την εργασία αντιμετωπίζουμε το πρόβλημα της συμπιεσμένης απόστασης Hamming. Η απόσταση Hamming είναι ένα εύκολο πρόβλημα, ωστόσο όταν τα δεδομένα εισόδου είναι τεράστιου μεγέθους, χρειαζόαμστε μια συμπίεσή τους για να μπορέσουμε να δημιουργήσουμε αποδωτικούς αλγορίθμους. Σ' αυτήν την …
-
Probabilistic techniques for analyzing sampling algorithms and the dynamics of lattice models
… throughout machine learning, optimization, and counting complexity. In this dissertation, we present several new techniques based on random walks for analyzing sampling algorithms and the dynamics of various lattice models from statistical physics. We start by investigating the mixing time of …
-
On parameterized counting
… analyze the intrinsic hardness of parameterized counting problems. We have analyzed the parameterized complexity of #W(P)-complete problems. We proved that, (under some complexity theoretic hypothesis): <br>1. Any #W(P)-complete is harder than any problem in the A hierarchy. <br>2. Any …
-
On Tractability and Consistency of Probabilistic Inference in Relational Domains
… the intractability of Weighted First Order Model Counting (WFOMC), as both learning and inference in SRL models can be reduced to instances of WFOMC. Hence, fragments of first-order logic that admit tractable WFOMC, widely known as domain-liftable, can significantly advance the practicality and …
-
Ιδιότητες συναρτήσεων μέτρησης πλήθους λύσεων σε προβλήματα με εύκολη απόφαση ύπαρξης λύσης: πληρότητα, προσεγγισιμότητα, μαρκοβιανές αλυσίδες, αλλαγές φάσης
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 …