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 35 for “"computational complexity theory"”.
-
Structural Properties of NP-Hard Sets and Uniform Characterisations of Complexity Classes
This thesis is devoted to the study of computational complexity theory, a branch of theoretical computer science. Computational complexity theory investigates the inherent difficulty in designing efficient algorithms for computational problems. By doing so, it analyses the scalability of …
-
Problems in computational algebra and integer programming
… combinatorics: one in tropical geometry, one in computational algebra, and two in discrete geometry and integer programming. Key tools used in this thesis include the theory of polyhedra, Grobner bases, and computational complexity theory.
-
A model-independent theory of computational complexity: from patience to precision and beyond
<p>The field of computational complexity theory--which chiefly aims to quantify the difficulty encountered when performing calculations--is, in the case of conventional computers, correctly practised and well understood (some important and fundamental open questions notwithstanding); however, such …
-
Inherently quantum lower bounds on computational complexity
Computational complexity theory is usually phrased in terms of decision problems and Boolean functions, whose inputs and outputs are purely classical. However, many quantum computational tasks motivated by physics, machine learning, and cryptography involve operation on quantum information in a …
-
Compute Faster and Learn Better: Model-based Nonconvex Optimization for Machine Learning
… estimation robustness, adaptivity, and computational scalability. Although classical computational complexity theory has shown that solving nonconvex optimization is generally NP-hard in the worst case, practitioners have proposed numerous heuristic optimization algorithms, which achieve …
-
Regular orderings of left orderable groups
… nilpotent groups through the lens of computational complexity theory. We demonstrate that both types of groups admit regular left orderings. In chapters 2 and 3, the preliminaries of orderable groups and formal languages are introduced. In Chapter 4, we establish that the set of …
-
Relations between Space-Bounded and Adaptive Massively Parallel Computations
… 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 constant rounds with a $\textup{poly}(n)$ processors, where the local …
-
Parallelism with limited nondeterminism
Computational complexity theory studies which computational problems can be solved with limited access to resources. The past fifty years have seen a focus on the relationship between intractable problems and efficient algorithms. However, the relationship between inherently sequential problems and …
-
Abstract Complexity Theory and the Degrees of Unsolvability
We focus on the A° sets and show that abstract complexity theory can be applied to the degrees of unsolvability simply by relativizing the notion of a complexity measure to 0'. Since the Gap Theorem holds in our context, we need to develop the concept of a A° honest function just as one needs to …
-
Efficient Evaluation of Rectangular Matrix Permanents
… many domains, including traditional fields like computational complexity theory, graph theory, and many-body quantum theory and emerging disciplines like machine learning and quantum computing. While conceptually simple, evaluating the permanent is extremely challenging: no polynomial-time …
-
Studies in Classical Behavioural Economics
… out from the perspective of Computability Theory and Computational Complexity Theory, which provide a coherent foundation for Herbert Simon's work on problem solving and for CBE in general. The second part of the thesis explores the game of Go from the perspective of problem solving in CBE. …
-
Tractable cognition : complexity theory in cognitive psychology
… research investigates the import and utility of computational complexity theory in cognitive psychology. A common conception in cognitive psychology is that a cognitive system is to be understood in terms of the function that it computes. The recognition that cognitive systems-being physical …
-
Quantum álgorithms for the combinatorial invariants of numerical semigroups
… hide some really hard problems from a computational perspective: the theory of numerical semigroups. As will be seen later, the definition of numerical semigroup does not involve sophisticated knowledge from any somewhat obscure and distant branch of the tree of mathematics. …
-
An Interactive Tutorial for NP-Completeness
A Theory of Algorithms course is essential to any Computer Science curriculum at both the undergraduate and graduate levels. It is also considered to be difficult material to teach or to learn. In particular the topics of Computational Complexity Theory, reductions, and the NP-Complete class of …
-
New Lower Bounds in Algebraic Complexity and Connections to Polynomial Identity Testing
Computational complexity theory asks a deceptively simple question: What makes some problems fundamentally harder than others? By studying the resources needed to solve computational tasks---such as time, memory, and amount of allowed randomness---this field aims to reveal the fundamental limits of …
-
Prospect Theory Preferences in Noncooperative Game Theory
… model of human preference under risk, prospect theory, into the equilibrium theory of noncooperative games. Three primary, candidate definitions are systematically identified on the basis of classical characterizations of Nash Equilibrium; in addition, three equilibrium subtypes are defined for …
-
Complexity and Partitions
Computational complexity theory usually investigates the complexity of sets, i.e., the complexity of partitions into two parts. But often it is more appropriate to represent natural problems by partitions into more than two parts. A particularly interesting class of such problems consists of …
-
Extensions of Presburger arithmetic and model checking one-counter automata
… The first part of this thesis covers the complexity of decision problems for different types of linear arithmetic, namely the existential subset of the first-order linear theory over the <em>p</em>-adic numbers and the existential subset of Presburger arithmetic with divisibility, with all …
-
On the Algebraic Proof Complexity of Constraint Satisfaction
… comprises three papers in the field of proof complexity, in which the objects of study are certificates of unsatisfiability. In algebraic proof complexity, the aim is to prove lower bounds on the complexity of certifying that there is no common root of a given set of polynomials. We will be …
Page 1 of 2