Theory and Algorithms Commons^™

Advances In The Automatic Detection Of Optimization Opportunities In Computer Programs, Delaram Talaashrafi

Electronic Thesis and Dissertation Repository

Massively parallel and heterogeneous systems together with their APIs have been used for various applications. To achieve high-performance software, the programmer should develop optimized algorithms to maximize the system’s resource utilization. However, designing such algorithms is challenging and time-consuming. Therefore, optimizing compilers are developed to take part in the programmer’s optimization burden. Developing effective optimizing compilers is an active area of research. Specifically, because loop nests are usually the hot spots in a program, their optimization has been the main subject of many optimization algorithms. This thesis aims to improve the scope and applicability of performance optimization algorithms used in …

The History Of The Enigma Machine, Jenna Siobhan Parkinson

History Publications

The history of the Enigma machine begins with the invention of the rotor-based cipher machine in 1915. Various models for rotor-based cipher machines were developed somewhat simultaneously in different parts of the world. However, the first documented rotor machine was developed by Dutch naval officers in 1915. Nonetheless, the Enigma machine was officially invented following the end of World War I by Arthur Scherbius in 1918 (Faint, 2016).

Three Contributions To The Theory And Practice Of Optimizing Compilers, Linxiao Wang

Electronic Thesis and Dissertation Repository

The theory and practice of optimizing compilers gather techniques that, from input computer programs, aim at generating code making the best use of modern computer hardware. On the theory side, this thesis contributes new results and algorithms in polyhedral geometry. On the practical side, this thesis contributes techniques for the tuning of parameters of programs targeting GPUs. We detailed these two fronts of our work below.

Consider a convex polyhedral set P given by a system of linear inequalities A*x <= b, where A is an integer matrix and b is an integer vector. We are interested in the integer hull P_I of P which is the smallest convex polyhedral set that contains all the integer points in P. In Chapter …

Understanding Deep Learning With Noisy Labels, Li Yi

Electronic Thesis and Dissertation Repository

Over the past decades, deep neural networks have achieved unprecedented success in image classification, which largely relies on the availability of correctly annotated large-scale datasets. However, collecting high-quality labels for large-scale datasets is expensive and time-consuming or even infeasible in practice. Approaches to addressing this issue include: acquiring labels from non-expert labelers, crowdsourcing-like platforms or other unreliable resources, where the label noise is inevitably involved. It becomes crucial to develop methods that are robust to label noise.

In this thesis, we study deep learning with noisy labels from two aspects. Specifically, the first part of this thesis, including two chapters, …

Simulating Salience: Developing A Model Of Choice In The Visual Coordination Game, Adib Sedig

Undergraduate Student Research Internships Conference

This project is primarily inspired by three papers: Colin Camerer and Xiaomin Li’s (2019 working paper)—Using Visual Salience in Empirical Game Theory, Ryan Oprea’s (2020)—What Makes a Rule Complex?, and Caplin et. al.’s (2011)—Search and Satisficing. Over the summer, I worked towards constructing a model of choice for the visual coordination game that can model player behavior more accurately than traditional game theoretic predictions. It attempts to do so by incorporating a degree of bias towards salience into a cellular automaton search algorithm and utilizing it alongside a sequential search mechanism of satisficing. This …

The Design And Implementation Of A High-Performance Polynomial System Solver, Alexander Brandt

Electronic Thesis and Dissertation Repository

This thesis examines the algorithmic and practical challenges of solving systems of polynomial equations. We discuss the design and implementation of triangular decomposition to solve polynomials systems exactly by means of symbolic computation.

Incremental triangular decomposition solves one equation from the input list of polynomials at a time. Each step may produce several different components (points, curves, surfaces, etc.) of the solution set. Independent components imply that the solving process may proceed on each component concurrently. This so-called component-level parallelism is a theoretical and practical challenge characterized by irregular parallelism. Parallelism is not an algorithmic property but rather a geometrical …