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