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 11 of 11 for “"Sampling and Counting"”.
-
Sampling and Counting Crossing-Free Matchings
Sampling of combinatorial structures is an important statistical tool used in applications in a number of areas ranging from statistical physics, data mining, to biological sciences. Of comparable importance is the computation of the cor- responding partition function, which, in the case of the …
-
Annealing and Tempering for Sampling and Counting
… the 1950's in areas such as biology, statistics, and physics. However, it is only in the last few decades that powerful techniques for obtaining rigorous performance guarantees with respect to the running time have been developed. Today, with only a few notable exceptions, most known algorithms …
-
Sampling and Counting Graph Structures with Triangle Motifs
Understanding the structure of real-world networks often relies on identifying significant (i.e., occurring significantly more frequently than random) subgraph patterns, or motifs, such as triangles. To assess their significance, null models generate random samples from a constrained distribution …
-
Efficient Sampling and Counting of Graph Structures related to Chordal Graphs
Counting problems aim to count the number of solutions for a given input, for example, counting the number of variable assignments that satisfy a Boolean formula. Sampling problems aim to produce a random object from a desired distribution, for example, producing a variable assignment drawn …
-
Random CNF-XOR Formulas
… as artificial intelligence, formal verification, and biology. Recent universal-hashing based approaches to the problems of sampling and counting crucially depend on the runtime performance of specialized SAT solvers on formulas expressed as the conjunction of both k-CNF constraints and …
-
Randomised algorithms for low temperature spin systems
… Spin 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 …
-
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 …
-
Constrained Counting and Sampling: Bridging the Gap Between Theory and Practice
Constrained counting and sampling are two fundamental problems in Computer Science with numerous applications, including network reliability, privacy, probabilistic reasoning, and constrained-random verification. In constrained counting, the task is to compute the total weight, subject to a given …
-
Quantitative Reasoning on Hybrid Formulas with Dynamic Programming
… that involves the existential quantifier, the random quantifier, and Boolean formulas. SSAT generalizes the Weighted Satisfiability (WSAT), Weighted Model Counting (WMC), Weighted Projected Model Counting (WPMC), and Existential-Random Satisfiability (ERSAT) problems. SSAT has been used to model …
-
FUNCTIONAL SYNTHESIS VIA FORMAL METHODS AND MACHINE LEARNING
… strides, practical challenges persist, and there are still real-world situations where current methods encounter limitations. In this thesis, we explore functional synthesis using machine learning and formal methods. Our novel approach, Manthan, treats it as a classification problem. …
-
Reinventing wildlife census with unmanned aerial systems: new survey designs for ungulate counts in the vast African semi-open ecosystems
… have shown a sharp decline in abundance and range. The vast (semi-)open ecosystems of Sub- Saharan Africa have among the most incredible mammal richness in the world, including many large ungulates species. Unfortunately, many are threatened by increasing human pressures. Natural …