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 13 of 13 for “"Average-case complexity"”.

  1. Complexity cores in average-case complexity theory

    <p>Complexity cores in average-case complexity theory</p> <p>In average-case complexity theory, one of the interesting questions is</p> <p>whether the existence of worst-case hard problems in NP implies the</p> <p>existence of problems in NP that are hard on average. In other words, `If P</p> …

    iastate Repository record for Complexity cores in average-case complexity theory (opens in a new tab)

  2. Dynamics of the spherical Sherrington-Kirkpatrick model and average case complexity for top eigenvectors

    … of this thesis is that we analyze the complexity of the zerotemperature Langevin dynamics (a.k.a. the gradient descent algorithm) on the SSK model. We establish lower and upper bound for the hitting time, defined as the first time required for the output of the algorithm to achieve a …

    waterloo Repository record for Dynamics of the spherical Sherrington-Kirkpatrick model and average case complexity for top eigenvectors (opens in a new tab)

  3. Probabilistic phenomena in random combinatorial problems

    … of three combinatorial problems. I examined the average-case complexity of random 3-SAT and of 3-Colorability of random graphs, and the satisfiability of random 1-3-HornSAT. All these problems, not only are interesting for their own sake, but also are of great practical importance since many …

    rice Repository record for Probabilistic phenomena in random combinatorial problems (opens in a new tab)

  4. Two Aspects of Statistical Learning in High Dimensions: Iterative Algorithms and Average-Case Reductions

    … design and analysis are often guided by worst-case upper bounds that may not reflect practical performance. On the statistical side, classical information-theoretic limits on sample complexity or signal-to-noise ratio may be unattainable by any polynomial-time procedure, making these limits an …

    gatech Repository record for Two Aspects of Statistical Learning in High Dimensions: Iterative Algorithms and Average-Case Reductions (opens in a new tab)

  5. Efficient and practical algorithms for sequence analysis: algorithm and data analysis research

    … we present an "expected" linear-time algorithm (average case complexity) linked to the same problem, and we also generalise the algorithm to k-mappability that permits up to k mismatches. Additionally, we study a new type of uncertain string, called "degenerate strings"; here our goal is to …

    kings Repository record for Efficient and practical algorithms for sequence analysis: algorithm and data analysis research (opens in a new tab) Download PDF for Efficient and practical algorithms for sequence analysis: algorithm and data analysis research (opens in a new tab)

  6. On learning from lower bounds

    … of converting Nisan's method of communication-complexity-based circuit lower bounds to algorithms for learning circuits with threshold gates. From this we obtain: A generic transformation of any circuit lower bound proved by Nisan's method into an efficient distributional PAC-learning …

    bu Repository record for On learning from lower bounds (opens in a new tab)

  7. Strong lower bounds on generic convex relaxations

    … (CSPs). Planted Clique is a central question in average case complexity where the goal is to find a clique of size [omega] planted in the Erdős-Rényi random graph G(n,0.5). While information theoretically, such a clique can be found whenever [omega] >> 2log(n), state-of-the-art polynomial time …

    texas Repository record for Strong lower bounds on generic convex relaxations (opens in a new tab)

  8. Application of extreme order statistics to the average-case analysis of parallel algorithms

    … for a linear array are analyzed for worst-case time complexity. An average-case analysis of one of these is then done using a lattice path model of list arrangement. A new parallel sorting algorithm is presented and analyzed. The algorithm consists of a local sorting phase followed by …

    ucf Repository record for Application of extreme order statistics to the average-case analysis of parallel algorithms (opens in a new tab)

  9. Algorithmic Problems in Strings with Applications to the Analysis of Biological Sequences

    … and<br/>computing covers.<br/>We investigate the average-case complexity of wildcard matching. Wildcards<br/>can be used to model single nucleotide polymorphisms and so, efficient<br/>algorithms to search for strings with wildcards are necessary. In this document<br/>we investigate how efficient …

    kings Repository record for Algorithmic Problems in Strings with Applications to the Analysis of Biological Sequences (opens in a new tab) Download PDF for Algorithmic Problems in Strings with Applications to the Analysis of Biological Sequences (opens in a new tab)

  10. Randomness and complexity in random complex quantum systems

    The interaction of computational complexity and quantum physics touches a wide range of topics from emerging technologies such as quantum computers to the physics of black holes. While tools from quantum information theory can help to answer questions in theoretical computer science, conversely, …

    fu-berlin Repository record for Randomness and complexity in random complex quantum systems (opens in a new tab)

  11. Closing the Defect Reduction Gap between Software Inspection and Test-Driven Development: Applying Mutation Analysis to Iterative, Test-First Programming

    … is not available or is not known. An estimated average case complexity analysis indicates that the algorithm's time and space complexity is linear in the size of the program under analysis, and a simulation experiment indicates that the algorithm can capitalize on the iterative nature of TDD to …

    arizona-thes Repository record for Closing the Defect Reduction Gap between Software Inspection and Test-Driven Development: Applying Mutation Analysis to Iterative, Test-First Programming (opens in a new tab)

  12. Lower Bounds on Average-Case and Non-Local Quantum Computation

    … In Part I, we present lower bounds on the average-case complexity of certain tasks in classical and quantum settings. We develop a general framework for constructing efficient worst-case to average-case reductions. Applying this framework, we obtain such reductions for fundamental problems …

    waterloo Repository record for Lower Bounds on Average-Case and Non-Local Quantum Computation (opens in a new tab)

  13. Practical lattice-based cryptography over structured lattices

    … amount of time. In 1995, Ajtai showed that the average case complexity of these problems is at least as hard as solving the problems in the worst case. Furthermore, lattice-based schemes are the only remaining contender in the NIST process to provide the important primitives of encryption, key …

    qu-belfast Repository record for Practical lattice-based cryptography over structured lattices (opens in a new tab) Download PDF for Practical lattice-based cryptography over structured lattices (opens in a new tab)