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 15 of 15 for “"Approximate counting"”.
-
TPA: A New Method for Approximate Counting
<p>Many high dimensional integrals can be reduced to the problem of finding the relative measure of two sets. Often one set will be exponentially larger than the other. A standard method of dealing with this problem is to interpolate between the sets with a series of nested sets where neighboring …
-
On Geometric Range Searching, Approximate Counting and Depth Problems
… and focus on relative approximation of range counting problems. One important problem where it is possible to achieve significant speedup through approximation is halfspace range counting in 3D. Here we continue the previous research done and obtain the first optimal data structure for …
-
Approximate counting via complex zero-free regions and spectral independence
… thesis investigates fundamental problems in approximate counting that arise in the field of statistical mechanics. Building upon recent advancements in the area, our research aims to enhance our understanding of the computational complexity of sampling from the Ising and Potts models, as well …
-
Randomised algorithms for low temperature spin systems
… systems provide a framework for sampling and counting problems in computer science, graph homomorphism problems in combinatorics, and phase transition phenomena in statistical physics. Two natural computational problems associated to a spin system are counting (computing the aggregate weight …
-
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 …
-
High-Dimensional Markov Chains and Applications
… optimization, integration, linear programming, approximate counting, and more. They also play a crucial role in understanding the geometry of subsets in high-dimensional Euclidean space. In this study, we use high-dimensional Markov chains to develop efficient algorithms for two problems: …
-
ANSWER SET COUNTING AND ITS APPLICATIONS
… more advanced tasks such as answer set (model) counting, which is central to probabilistic reasoning and probabilistic logic programming. This thesis develops efficient techniques for answer set counting, addressing the scalability limitations of existing systems. We propose two exact counting …
-
Sampling and Counting Crossing-Free Matchings
… distribution, is equivalent to the problem of counting all such structures. For self-reducible combinatorial structures, once we can produce an almost uniform sample from them, then we can approximately count them. Using a Markov chain Monte Carlo method, this thesis presents polynomial-time …
-
Approximation algorithms and inapproximability of partition functions of spin systems
<p>Over the past 30 years, the study of counting problems has become an interesting and important work. The framework of counting problems can capture applications in diverse fields, such as graph colouring and homomorphism in graph theory, and the Ising and Potts model from statistical physics. In …
-
Sampling and Counting Graph Structures with Triangle Motifs
… latter, specifically the problem of sampling and counting graph structures that incorporate triangle motifs. While efficient algorithms exist for sampling classical structures such as matchings, extending these methods to higher-order motifs remains an important challenge. We introduce the …
-
Vertex enumeration and counting for certain classes of polyhedra
… of polyhedron. We also address the problem of (approximately) counting the vertices without listing them. Pivoting algorithms rely on the correspondence between vertices and feasible bases and are consequently inefficient in the presence of a high degree of degeneracy such as frequently occurs …
-
Annealing and Tempering for Sampling and Counting
… notable exceptions, most known algorithms for approximately uniform sampling and approximate counting rely on the MCMC method. This thesis focuses on algorithms that use MCMC combined with an algorithm from optimization called simulated annealing, for sampling and counting problems. Annealing …
-
Algorithmic Tools for Network Analysis
… analyze the structure and dynamics of networks, counting motifs is one of the most popular methods, as they are considered the basic construction block of the network. In this thesis, we introduce several tools developed for counting motifs on bipartite networks. Despite its importance, counting …
-
Algorithms and Data Structures for Geometric Intersection Query Problems
… studied in the literature are reporting or counting the objects of A intersecting q. In many applications, the same set A is queried several times, in which case one would like to answer a query faster by preprocessing A into a data structure. The goal is to organize the data into a data …
-
Ιδιότητες συναρτήσεων μέτρησης πλήθους λύσεων σε προβλήματα με εύκολη απόφαση ύπαρξης λύσης: πληρότητα, προσεγγισιμότητα, μαρκοβιανές αλυσίδες, αλλαγές φάσης
… problems are hard to count, but there exist hard counting problems with decision version in P. TotP is a subclass of #P that contains all self-reducible problems with easy decision version. It contains many interesting problems from many scientific areas.Cook reductions blur structural differences …