Theory and Algorithms Commons^™

Multimodal Data Integration For Real-Time Indoor Navigation Using A Smartphone, Yaohua Chang

Dissertations and Theses

We propose an integrated solution of indoor navigation using a smartphone, especially for assisting people with special needs, such as the blind and visually impaired (BVI) individuals. The system consists of three components: hybrid modeling, real-time navigation, and client-server architecture. In the hybrid modeling component, the hybrid model of a building is created region by region and is organized in a graph structure with nodes as destinations and landmarks, and edges as traversal paths between nodes. A Wi-Fi/cellular-data connectivity map, a beacon signal strength map, a 3D visual model (with destinations and landmarks annotated) are collected while a modeler walks …

V-Slam And Sensor Fusion For Ground Robots, Ejup Hoxha

Dissertations and Theses

In underground, underwater and indoor environments, a robot has to rely solely on its on-board sensors to sense and understand its surroundings. This is the main reason why SLAM gained the popularity it has today. In recent years, we have seen excellent improvement on accuracy of localization using cameras and combinations of different sensors, especially camera-IMU (VIO) fusion. Incorporating more sensors leads to improvement of accuracy,but also robustness of SLAM. However, while testing SLAM in our ground robots, we have seen a decrease in performance quality when using the same algorithms on flying vehicles.We have an additional sensor for ground …

An Optimized Encoding Algorithm For Systematic Polar Codes, Xiumin Wang, Zhihong Zhang, Jun Li, Yu Wang, Haiyan Cao, Zhengquan Li, Liang Shan

Publications and Research

Many different encoding algorithms for systematic polar codes (SPC) have been introduced since SPC was proposed in 2011. However, the number of the computing units of exclusive OR (XOR) has not been optimized yet. According to an iterative property of the generator matrix and particular lower triangular structure of the matrix, we propose an optimized encoding algorithm (OEA) of SPC that can reduce the number of XOR computing units compared with existing non-recursive algorithms. We also prove that this property of the generator matrix could extend to different code lengths and rates of the polar codes. Through the matrix segmentation …

Rationality And Efficient Verifiable Computation, Matteo Campanelli

Dissertations, Theses, and Capstone Projects

In this thesis, we study protocols for delegating computation in a model where one of the parties is rational. In our model, a delegator outsources the computation of a function f on input x to a worker, who receives a (possibly monetary) reward. Our goal is to design very efficient delegation schemes where a worker is economically incentivized to provide the correct result f(x). In this work we strive for not relying on cryptographic assumptions, in particular our results do not require the existence of one-way functions.

We provide several results within the framework of rational proofs introduced by Azar …

List, Sample, And Count, Ali Assarpour

Dissertations, Theses, and Capstone Projects

Counting plays a fundamental role in many scientific fields including chemistry, physics, mathematics, and computer science. There are two approaches for counting, the first relies on analytical tools to drive closed form expression, while the second takes advantage of the combinatorial nature of the problem to construct an algorithm whose output is the number of structures. There are many algorithmic techniques for counting, they cover the explicit approach of counting by listing to the approximate approach of counting by sampling.

This thesis looks at counting three sets of objects. First, we consider a subclass of boolean functions that are monotone. …

An Algorithm For Calculating Top-Dimensional Bounding Chains, J. Frederico Carvalho​, Mikael Vejdemo-Johansson, Danica Kragic, Florian T. Pokorny

Publications and Research

We describe the Coefficient-Flow algorithm for calculating the bounding chain of an (n-1)-boundary on an n-manifold-like simplicial complex S. We prove its correctness and show that it has a computational time complexity of O(|S(n−1)|) (where S(n−1) is the set of (n-1)-faces of S). We estimate the big-O coefficient which depends on the dimension of S and the implementation. We present an implementation, experimentally evaluate the complexity of our algorithm, and compare its performance with that of solving the underlying linear system.

Multiple Sclerosis Identification Based On Fractional Fourier Entropy And A Modified Jaya Algorithm, Shui-Hua Wang, Hong Cheng, Preetha Phillips, Yu-Dong Zhang

Publications and Research

Aim: Currently, identifying multiple sclerosis (MS) by human experts may come across the problem of “normal-appearing white matter”, which causes a low sensitivity. Methods: In this study, we presented a computer vision based approached to identify MS in an automatic way. This proposed method first extracted the fractional Fourier entropy map from a specified brain image. Afterwards, it sent the features to a multilayer perceptron trained by a proposed improved parameter-free Jaya algorithm. We used cost-sensitivity learning to handle the imbalanced data problem. Results: The 10 × 10-fold cross validation showed our method yielded a sensitivity of 97.40 ± 0.60%, …

Relating Justification Logic Modality And Type Theory In Curry–Howard Fashion, Konstantinos Pouliasis

Dissertations, Theses, and Capstone Projects

This dissertation is a work in the intersection of Justification Logic and Curry--Howard Isomorphism. Justification logic is an umbrella of modal logics of knowledge with explicit evidence. Justification logics have been used to tackle traditional problems in proof theory (in relation to Godel's provability) and philosophy (Gettier examples, Russel's barn paradox). The Curry--Howard Isomorphism or proofs-as-programs is an understanding of logic that places logical studies in conjunction with type theory and -- in current developments -- category theory. The point being that understanding a system as a logic, a typed calculus and, a language of a class of categories constitutes …

Cryptosystems Using Subgroup Distortion, Indira Chatterji, Delaram Kahrobaei, Ni Yen Lu

Publications and Research

In this paper we propose cryptosystems based on subgroup distortion in hyperbolic groups. We also include concrete examples of hyperbolic groups as possible platforms.

Gradient Estimation For Attractor Networks, Thomas Flynn

Dissertations, Theses, and Capstone Projects

It has been hypothesized that neural network models with cyclic connectivity may be more powerful than their feed-forward counterparts. This thesis investigates this hypothesis in several ways. We study the gradient estimation and optimization procedures for several variants of these networks. We show how the convergence of the gradient estimation procedures are related to the properties of the networks. Then we consider how to tune the relative rates of gradient estimation and parameter adaptation to ensure successful optimization in these models. We also derive new gradient estimators for stochastic models. First, we port the forward sensitivity analysis method to the …

Ethics And Bias In Machine Learning: A Technical Study Of What Makes Us “Good”, Ashley Nicole Shadowen

Student Theses

The topic of machine ethics is growing in recognition and energy, but bias in machine learning algorithms outpaces it to date. Bias is a complicated term with good and bad connotations in the field of algorithmic prediction making. Especially in circumstances with legal and ethical consequences, we must study the results of these machines to ensure fairness. This paper attempts to address ethics at the algorithmic level of autonomous machines. There is no one solution to solving machine bias, it depends on the context of the given system and the most reasonable way to avoid biased decisions while maintaining the …

Approximation Algorithms For Effective Team Formation, George Rabanca

Dissertations, Theses, and Capstone Projects

This dissertation investigates the problem of creating multiple disjoint teams of maximum efficacy from a fixed set of workers. We identify three parameters which directly correlate to the team effectiveness — team expertise, team cohesion and team size — and propose efficient algorithms for optimizing each in various settings. We show that under standard assumptions the problems we explore are not optimally solvable in polynomial time, and thus we focus on developing efficient algorithms with guaranteed worst case approximation bounds. First, we investigate maximizing team expertise in a setting where each worker has different expertise for each job and each …

A Combinatorial Framework For Multiple Rna Interaction Prediction, Syed Ali Ahmed

Dissertations, Theses, and Capstone Projects

The interaction of two RNA molecules involves a complex interplay between folding and binding that warranted recent developments in RNA-RNA interaction algorithms. However, biological mechanisms in which more than two RNAs take part in an interaction also exist.

A typical algorithmic approach to such problems is to find the minimum energy structure. Often the computationally optimal solution does not represent the biologically correct structure of the interaction. In addition, different biological structures may be observed, depending on several factors. Furthermore, scoring techniques often miss critical details about dependencies within different parts of the structure, which typically leads to lower scores …

Morphogenesis And Growth Driven By Selection Of Dynamical Properties, Yuri Cantor

Dissertations, Theses, and Capstone Projects

Organisms are understood to be complex adaptive systems that evolved to thrive in hostile environments. Though widely studied, the phenomena of organism development and growth, and their relationship to organism dynamics is not well understood. Indeed, the large number of components, their interconnectivity, and complex system interactions all obscure our ability to see, describe, and understand the functioning of biological organisms.

Here we take a synthetic and computational approach to the problem, abstracting the organism as a cellular automaton. Such systems are discrete digital models of real-world environments, making them more accessible and easier to study then their physical world …

Solving Algorithmic Problems In Finitely Presented Groups Via Machine Learning, Jonathan Gryak

Dissertations, Theses, and Capstone Projects

Machine learning and pattern recognition techniques have been successfully applied to algorithmic problems in free groups. In this dissertation, we seek to extend these techniques to finitely presented non-free groups, in particular to polycyclic and metabelian groups that are of interest to non-commutative cryptography.

As a prototypical example, we utilize supervised learning methods to construct classifiers that can solve the conjugacy decision problem, i.e., determine whether or not a pair of elements from a specified group are conjugate. The accuracies of classifiers created using decision trees, random forests, and N-tuple neural network models are evaluated for several non-free groups. …

The History Of Algorithmic Complexity, Audrey A. Nasar

Publications and Research

This paper provides a historical account of the development of algorithmic complexity in a form that is suitable to instructors of mathematics at the high school or undergraduate level. The study of algorithmic complexity, despite being deeply rooted in mathematics, is usually restricted to the computer science curriculum. By providing a historical account of algorithmic complexity through a mathematical lens, this paper aims to equip mathematics educators with the necessary background and framework for incorporating the analysis of algorithmic complexity into mathematics courses as early on as algebra or pre-calculus.

Inferring Interaction Type In Gene Regulatory Networks Using Co-Expression Data, Pegah Khosravi, Vahid H. Gazestani, Leila Pirhaji, Brian Law, Mehdi Sadeghi, Bahram Goliaei, Gary D. Bader

Publications and Research

Background

Knowledge of interaction types in biological networks is important for understanding the functional organization of the cell. Currently information-based approaches are widely used for inferring gene regulatory interactions from genomics data, such as gene expression profiles; however, these approaches do not provide evidence about the regulation type (positive or negative sign) of the interaction.

Results

This paper describes a novel algorithm, “Signing of Regulatory Networks” (SIREN), which can infer the regulatory type of interactions in a known gene regulatory network (GRN) given corresponding genome-wide gene expression data. To assess our new approach, we applied it to three different benchmark …

Nearest Neighbor Search With Strong Location Privacy, Stavros Papadopoulos, Spiridon Bakiras, Dimitris Papadias

Publications and Research

The tremendous growth of the Internet has significantly reduced the cost of obtaining and sharing information about individuals, raising many concerns about user privacy. Spatial queries pose an additional threat to privacy because the location of a query may be sufficient to reveal sensitive information about the querier. In this paper we focus on k nearest neighbor (kNN) queries and define the notion of strong location privacy, which renders a query indistinguishable from any location in the data space. We argue that previous work fails to support this property for arbitrary kNN search. Towards this end, we introduce methods that …

A Symbolic Sonification Of L-Systems, Adam James Wilson

Publications and Research

This paper describes a simple technique for the sonification of branching structures in plants. The example is intended to illustrate a qualitative definition of best practices for sonification aimed at the production of musical material. Visually manifest results of tree growth are modelled and subsequently mapped to pitch, time, and amplitude. Sample results are provided in symbolic music notation.

Flocking In The Time-Dissonance Plane, Adam James Wilson

Publications and Research

This paper describes a technique for the sonification of an idealized model of the flocking behavior of birds, fish, and insects. Flocking agents are represented by pitches that move through time to produce chords of variable dissonance. The objective of each agent is to move toward more consonant chord formations with other agents. The output of the sonification is intended to provide material for use in musical composition.

Classical And Quantum Algorithms For Finding Cycles, Jill Cirasella

Publications and Research

Quantum computing—so weird, so wonderful—inspires much speculation about the line between the possible and the impossible. (Of course, there is still unclarity about how “impossible” intractable problems are and about how “possible” quantum computers are.) This thesis takes a slightly different tack: instead of focusing on how to make the impossible possible, it focuses on how to make the possible easier.

More specifically, this paper discusses quantum algorithms for finding cycles in graphs, a problem for which polynomial-time classical algorithms already exist. It explains and compares the classical and quantum algorithms, and it introduces a few new algorithms and observations. …