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 20 of 59 for “"Complexity class"”.
-
Uniformity and Nonuniformity in Proof Complexity
… relations between uniform and nonuniform proof complexity and computational complexity. Nonuniform proof complexity studies the lengths of proofs in various propositional proof systems such as Frege . Uniform proof complexity studies the provability strength of bounded arithmetic theories which …
-
Witness Functions in Program Analysis and Complexity Theory
… of program analysis theory and computability/complexity theory. For example, we can prove a program analysis problem is undecidable, meaning that there does not exist an algorithm to precisely solve the problem. As another example, we can prove a problem does not belong to a complexity class, …
-
The complexity of continuous local search
The complexity class CLS was introduced by Daskalakis and Papadimitriou in [9] with the goal of capturing the complexity of some well-known problems in PPAD ∩ PLS that have resisted, in some cases for decades, attempts to put them in polynomial time. No complete problem was known for CLS, and in …
-
Path Reduction and Coverage Complexity for Fuzzing
… phenomenon, we establish the concept of coverage complexity—a quantitative measure of the granularity of coverage metrics. Analogous to complexity and the Big-Onotation in algorithm analysis, coverage complexity classifies metrics into asymptotic complexity classes such as linear, polynomial, and …
-
Nonlinear Complexity of Boolean Permutations
We introduce the concept of nonlinear complexity, where the complexity of a function is determined by the number of nonlinear building blocks required for construction. We group functions by linear equivalence, and induce a complexity hierarchy for the affine equivalent double cosets. We prove …
-
An integrated complexity analysis of problems from computational biology
We perform an Integrated complexity analysis on a number of combinatorial problems arising from the field of computational biology. The classic framework of NP-completeness, algorithmic design techniques for bounded width graphs, and parameterized computational complexity together provide a clear …
-
Exploiting parallelism in decomposition methods for constraint satisfaction
… in general, however, there are many tractable subclasses that rely on the restriction of the structure of their underlying hypergraphs. It is a well-known fact, for instance, that CSPs whose underlying hypergraph is acyclic are tractable. Trying to define “nearly acyclic” hypergraphs led to the …
-
Turing Machines and Automatic Functions as Models of Computation
… This result is extended to the study of the complexity class AF[log n] which is roughly the class of functions which can be computed by a machine with automatic functions as primitive operations in logarithmic time. It is shown that AF[log n] is a proper subclass of DTIME[n log n] but still …
-
FPRAS Approximation of the Matrix Permanent in Practice
The matrix permanent belongs to the complexity class #P-Complete. It is gener- ally believed to be computationally infeasible for large problem sizes, and significant research has been done on approximation algorithms for the matrix permanent. We present an implementation and detailed runtime …
-
Extending and simulating the quantum binomial options pricing model
… be able to price options more efficiently than classical computers. This research extends the quantum binomial option pricing model proposed by Zeqian Chen to European put options and to Barrier options and develops a quantum algorithm to price them. This research produced three key results. …
-
On the relationship between satisfiability and partially observable Markov decision processes
… Since they are all complete for the same complexity class, I show how to convert them into one another in polynomial time and space. I discuss various properties of each encoding and how they get translated into equivalent constructs in the other encodings. An important lesson of these …
-
Randomness and dimension in computational learning and analog computation
… due to Huang et al. (2019) that obtains for this class of analog computers. We use these tools to discuss randomness properties of sequences of real numbers that represent the sojourn times between chemical system state transitions. Finally, we discuss an analog version of the classical randomized …
-
Primitives for Match-Action in Theory and Practice
… etc., are open to formalization. We take both complexity-theoretic and language-theoretic approaches. On the one hand, we give a circuit complexity model for match-action, and we relate the complexity class AC0 to match tables of various sizes. Further, we give a multimatch extension to …
-
Relations between Space-Bounded and Adaptive Massively Parallel Computations
This thesis studies the class of languages solvable by Adaptive Massively Parallel Computations in constant rounds from a computational complexity theory perspective. A language $L$ is in the class $\AMPC^0$ if for every $\varepsilon \in(0,1)$, there is a deterministic AMPC algorithm running in …
-
Active Cleaning of Label Noise Using Support Vector Machines
… in the given labels or label noise affect the classifier performance, classifier complexity, class proportions, etc. It may be that a relatively small, but important class needs to have all its examples identified. Typical solutions to the label noise problem involve creating classifiers that …
-
Optimization methods for spin glass problems via accelerated macroscopic quantum tunneling
… improvements to certain problems over their classical counterparts. A commonly studied problem is the Constraint Satisfaction Problem (CSP) which often finds itself in the NP-Hard complexity class. Current algorithms often struggle to get out of local minima leading to sub-optimal results, …
-
Studies in Models of Quantum Proof Systems
… simplest quantum proof system is captured by the complexity class QMA. Interestingly, it is not known whether QMA retains its expressive power if we force it to have perfect completeness. Currently, the strongest result towards settling this question is by Kobayashi, Le Gall, and Nishimura. They …
-
Certifying hyperbolicity of fibred 3-manifolds
… questions, but also with their computational complexity: a 3-manifold is described by a triangulation, and the efficiency of an algorithm is measured against the number of tetrahedra in the triangulation.<br><br>We prove that the problem of deciding whether a triangulated orientable 3-manifold …
-
Quantum Annealing: Research and Applications
… these optimization problems are in the NP-Hard complexity class, they are of great interest in several fields. One of the leading open questions concerning quantum annealers asks whether they will outperform other classical methods for solving these problems; Some aspects of this question are …
-
Formally Verified Space-Safety for Program Transformations
… behavior, but push that program into a different complexity class entirely. We've seen such blowups like this occurring in practice, and many transformations have pitfalls which can cause issues. Even when a program is not dramatically worsened, it can cause the program to use more resources than …
Page 1 of 3