Open Access. Powered by Scholars. Published by Universities.®
- Discipline
- Keyword
-
- (Abstract Harmonic Analysis) Explicit machine computation and programs (not the theory of computation or programming) (1)
- 03D15 Complexity of computation (1)
- 13A50 Invariant Theory (1)
- 20C30 (1)
- 43-04 (1)
-
- 43A30 (1)
- 68Q01 (1)
- 68Q05 Models of computation (1)
- 68Q15 (1)
- 68Q17 (1)
- Bounds (1)
- Circuit satisfiability (1)
- Combinatorial game (1)
- Combinatorics (1)
- Completeness (1)
- Complexity classes (hierarchies (1)
- Computational difficulty of problems (lower bounds (1)
- Conjecture (1)
- Difficulty of approximation (1)
- Etc.) (1)
- Fourier and Fourier-Stieltjes transforms on nonabelian groups and on semigroups (1)
- General topics in the theory of computing (1)
- Graph coloring (1)
- Hirsch (1)
- Lower Bounds (1)
- Machine Learning (1)
- Polynomial (1)
- Polynomial hierarchy (1)
- Preconditioning (1)
- Randomized Numerical Linear Algebra (1)
Articles 1 - 6 of 6
Full-Text Articles in Theory and Algorithms
Games For One, Games For Two: Computationally Complex Fun For Polynomial-Hierarchical Families, Kye Shi
Games For One, Games For Two: Computationally Complex Fun For Polynomial-Hierarchical Families, Kye Shi
HMC Senior Theses
In the first half of this thesis, we explore the polynomial-time hierarchy, emphasizing an intuitive perspective that associates decision problems in the polynomial hierarchy to combinatorial games with fixed numbers of turns. Specifically, problems in π are thought of as 0-turn games, ππ as 1-turn βpuzzleβ games, and in general πΊβπ as π-turn games, in which decision problems answer the binary question, βcan the starting player guarantee a win?β We introduce the formalisms of the polynomial hierarchy through this perspective, alongside definitions of π-turn CIRCUIT SATISFIABILITY games, whose πΊβπ-completeness is assumed from prior work (we briefly justify this assumption β¦
Going Meta On The Minimum Circuit Size Problem: How Hard Is It To Show How Hard Showing Hardness Is?, ZoΓ« Bell
Going Meta On The Minimum Circuit Size Problem: How Hard Is It To Show How Hard Showing Hardness Is?, ZoΓ« Bell
HMC Senior Theses
The Minimum Circuit Size Problem (MCSP) is a problem with a long history in computational complexity theory which has recently experienced a resurgence in attention. MCSP takes as input the description of a Boolean function f as a truth table as well as a size parameter s, and outputs whether there is a circuit that computes f of size β€ s. It is of great interest whether MCSP is NP-complete, but there have been shown to be many technical obstacles to proving that it is. Most of these results come in the following form: If MCSP is NP-complete β¦
The Complexity Of Symmetry, Matthew Lemay
The Complexity Of Symmetry, Matthew Lemay
HMC Senior Theses
One of the main goals of theoretical computer science is to prove limits on how efficiently certain Boolean functions can be computed. The study of the algebraic complexity of polynomials provides an indirect approach to exploring these questions, which may prove fruitful since much is known about polynomials already from the field of algebra. This paper explores current research in establishing lower bounds on invariant rings and polynomial families. It explains the construction of an invariant ring for whom a succinct encoding would imply that NP is in P/poly. It then states a theorem about the circuit complexity partial β¦
Randomized Algorithms For Preconditioner Selection With Applications To Kernel Regression, Conner Dipaolo
Randomized Algorithms For Preconditioner Selection With Applications To Kernel Regression, Conner Dipaolo
HMC Senior Theses
The task of choosing a preconditioner M to use when solving a linear system Ax=b with iterative methods is often tedious and most methods remain ad-hoc. This thesis presents a randomized algorithm to make this chore less painful through use of randomized algorithms for estimating traces. In particular, we show that the preconditioner stability || I - M-1A ||F, known to forecast preconditioner quality, can be computed in the time it takes to run a constant number of iterations of conjugate gradients through use of sketching methods. This is in spite of folklore which β¦
Combinatorial Polynomial Hirsch Conjecture, Sam Miller
Combinatorial Polynomial Hirsch Conjecture, Sam Miller
HMC Senior Theses
The Hirsch Conjecture states that for a d-dimensional polytope with n facets, the diameter of the graph of the polytope is at most n-d. This conjecture was disproven in 2010 by Francisco Santos Leal. However, a polynomial bound in n and d on the diameter of a polytope may still exist. Finding a polynomial bound would provide a worst-case scenario runtime for the Simplex Method of Linear Programming. However working only with polytopes in higher dimensions can prove challenging, so other approaches are welcome. There are many equivalent formulations of the Hirsch Conjecture, one of which is the β¦
Fast Algorithms For Analyzing Partially Ranked Data, Matthew Mcdermott
Fast Algorithms For Analyzing Partially Ranked Data, Matthew Mcdermott
HMC Senior Theses
Imagine your local creamery administers a survey asking their patrons to choose their five favorite ice cream flavors. Any data collected by this survey would be an example of partially ranked data, as the set of all possible flavors is only ranked into subsets of the chosen flavors and the non-chosen flavors. If the creamery asks you to help analyze this data, what approaches could you take? One approach is to use the natural symmetries of the underlying data space to decompose any data set into smaller parts that can be more easily understood. In this work, I describe β¦