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"”.

  1. 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 …

    toronto-retro Repository record for Uniformity and Nonuniformity in Proof Complexity (opens in a new tab)

  2. 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, …

    gatech Repository record for Witness Functions in Program Analysis and Complexity Theory (opens in a new tab)

  3. 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 …

    uiuc Repository record for The complexity of continuous local search (opens in a new tab)

  4. 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 …

    waterloo Repository record for Path Reduction and Coverage Complexity for Fuzzing (opens in a new tab)

  5. 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 …

    maryland Repository record for Nonlinear Complexity of Boolean Permutations (opens in a new tab)

  6. 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 …

    uvic Repository record for An integrated complexity analysis of problems from computational biology (opens in a new tab)

  7. 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 …

    oxford Repository record for Exploiting parallelism in decomposition methods for constraint satisfaction (opens in a new tab)

  8. 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 …

    nus Repository record for Turing Machines and Automatic Functions as Models of Computation (opens in a new tab) Download file for Turing Machines and Automatic Functions as Models of Computation (opens in a new tab)

  9. 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 …

    rice Repository record for FPRAS Approximation of the Matrix Permanent in Practice (opens in a new tab)

  10. 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. …

    manitoba Repository record for Extending and simulating the quantum binomial options pricing model (opens in a new tab)

  11. 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 …

    waterloo Repository record for On the relationship between satisfiability and partially observable Markov decision processes (opens in a new tab)

  12. 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 …

    iastate Repository record for Randomness and dimension in computational learning and analog computation (opens in a new tab)

  13. 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 …

    cornell Repository record for Primitives for Match-Action in Theory and Practice (opens in a new tab)

  14. 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 …

    iastate Repository record for Relations between Space-Bounded and Adaptive Massively Parallel Computations (opens in a new tab)

  15. 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 …

    usf Repository record for Active Cleaning of Label Noise Using Support Vector Machines (opens in a new tab)

  16. 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, …

    colo-mines Repository record for Optimization methods for spin glass problems via accelerated macroscopic quantum tunneling (opens in a new tab)

  17. 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 …

    nus Repository record for Studies in Models of Quantum Proof Systems (opens in a new tab) Download file for Studies in Models of Quantum Proof Systems (opens in a new tab)

  18. 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 …

    oxford Repository record for Certifying hyperbolicity of fibred 3-manifolds (opens in a new tab)

  19. 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 …

    waterloo Repository record for Quantum Annealing: Research and Applications (opens in a new tab)

  20. 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 …

    rit Repository record for Formally Verified Space-Safety for Program Transformations (opens in a new tab)

Page 1 of 3