Theory and Algorithms Commons^™

Provably Weak Instances Of Plwe Revisited, Again, Katherine Mendel

CSBSJU Distinguished Thesis

Learning with Errors has emerged as a promising possibility for postquantum cryptography. Variants known as RLWE and PLWE have been shown to be more efficient, but the increased structure can leave them vulnerable to attacks for certain instantiations. This work aims to identify specific cases where proposed cryptographic schemes based on PLWE work particularly poorly under a specific attack.

The Nature Of Numbers: Real Computing, Bradley J. Lucier

Journal of Humanistic Mathematics

While studying the computable real numbers as a professional mathematician, I came to see the computable reals, and not the real numbers as usually presented in undergraduate real analysis classes, as the natural culmination of my evolving understanding of numbers as a schoolchild. This paper attempts to trace and explain that evolution. The first part recounts the nature of numbers as they were presented to us grade-school children. In particular, the introduction of square roots induced a step change in my understanding of numbers. Another incident gave me insight into the brilliance of Alan Turing in his paper introducing both …

Robust Error Estimation Based On Factor-Graph Models For Non-Line-Of-Sight Localization, O. Arda Vanli, Clark N. Taylor

Faculty Publications

This paper presents a method to estimate the covariances of the inputs in a factor-graph formulation for localization under non-line-of-sight conditions. A general solution based on covariance estimation and M-estimators in linear regression problems, is presented that is shown to give unbiased estimators of multiple variances and are robust against outliers. An iteratively re-weighted least squares algorithm is proposed to jointly compute the proposed variance estimators and the state estimates for the nonlinear factor graph optimization. The efficacy of the method is illustrated in a simulation study using a robot localization problem under various process and measurement models and measurement …

The Performance Optimization Of Asp Solving Based On Encoding Rewriting And Encoding Selection, Liu Liu

Theses and Dissertations--Computer Science

Answer set programming (ASP) has long been used for modeling and solving hard search problems. These problems are modeled in ASP as encodings, a collection of rules that declaratively describe the logic of the problem without explicitly listing how to solve it. It is common that the same problem has several different but equivalent encodings in ASP. Experience shows that the performance of these ASP encodings may vary greatly from instance to instance when processed by current state-of-the-art ASP grounder/solver systems. In particular, it is rarely the case that one encoding outperforms all others. Moreover, running an ASP system on …

Finding Optimal Cayley Map Embeddings Using Genetic Algorithms, Jacob Buckelew

Honors Program Theses

Genetic algorithms are a commonly used metaheuristic search method aimed at solving complex optimization problems in a variety of fields. These types of algorithms lend themselves to problems that can incorporate stochastic elements, which allows for a wider search across a search space. However, the nature of the genetic algorithm can often cause challenges regarding time-consumption. Although the genetic algorithm may be widely applicable to various domains, it is not guaranteed that the algorithm will outperform other traditional search methods in solving problems specific to particular domains. In this paper, we test the feasibility of genetic algorithms in solving a …

Reinforcement Learning Applied To The Shoals Marine Laboratory Smart Grid, Daniel C. Mattson

Honors Theses and Capstones

Reinforcement learning (RL) techniques have been applied to smart grids with a variety of applications. The most common objective is to optimize profit for one actor in the system. The goal of this work is to apply different RL models to the smart grid at the Shoals Marine Laboratory (SML) located on Appledore Island, Maine in an effort to reduce costs and minimize the amount of nonrenewable energy consumed on the island. The RL models implemented resulted in more sustainable practices in simulations, with a linear spline model outperforming the naive policy the SML currently uses. Future work includes extending …

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 …

Spaghetti Tracer: A Framework For Tracing Semiregular Filamentous Densities In 3d Tomograms, Salim Sazzed, Peter Scheible, Jing He, Willy Wriggers

Computer Science Faculty Publications

Within cells, cytoskeletal filaments are often arranged into loosely aligned bundles. These fibrous bundles are dense enough to exhibit a certain regularity and mean direction, however, their packing is not sufficient to impose a symmetry between—or specific shape on—individual filaments. This intermediate regularity is computationally difficult to handle because individual filaments have a certain directional freedom, however, the filament densities are not well segmented from each other (especially in the presence of noise, such as in cryo-electron tomography). In this paper, we develop a dynamic programming-based framework, Spaghetti Tracer, to characterizing the structural arrangement of filaments in the challenging 3D …

A Comparison Of Deep Learning Algorithms On Image Data For Detecting Floodwater On Roadways, Sarp Salih, Kuzlu Murat, Zhao Yanxiao, Cetin Mecit

Engineering Technology Faculty Publications

Object detection and segmentation algorithms evolved significantly in the last decade. Simultaneous object detection and segmentation paved the way for real-time applications such as autonomous driving. Detection and segmentation of (partially) flooded roadways are essential inputs for vehicle routing and traffic management systems. This paper proposes an automatic floodwater detection and segmentation method utilizing the Mask Region-Based Convolutional Neural Networks (Mask-R-CNN) and Generative Adversarial Networks (GAN) algorithms. To train the model, manually labeled images with urban, suburban, and natural settings are used. The performances of the algorithms are assessed in accurately detecting the floodwater captured in images. The results show …

Bounded-Degree Plane Geometric Spanners: Connecting The Dots Between Theory And Practice, Matthew Alexander Graham

UNF Graduate Theses and Dissertations

The construction of bounded-degree plane geometric spanners has been a focus of interest since 2002 when Bose, Gudmundsson, and Smid proposed the first algorithm to construct such spanners. To date, eleven algorithms have been designed with various trade-offs in degree and stretch factor. We have implemented these sophisticated algorithms in C++ using the CGAL library and experimented with them using large synthetic and real-world pointsets. Our experiments have revealed their practical behavior and real-world efficacy. We share the implementations via GitHub for broader uses and future research.

We present a simple practical algorithm, named AppxStretchFactor, that can estimate stretch factors …

Spectrum Sensing With Energy Detection In Multiple Alternating Time Slots, Călin Vlădeanu, Alexandru Marţian, Dimitrie C. Popescu

Electrical & Computer Engineering Faculty Publications

Energy detection (ED) represents a low complexity approach used by secondary users (SU) to sense spectrum occupancy by primary users (PU) in cognitive radio (CR) systems. In this paper, we present a new algorithm that senses the spectrum occupancy by performing ED in K consecutive sensing time slots starting from the current slot and continuing by alternating before and after the current slot. We consider a PU traffic model specified in terms of an average duty cycle value, and derive analytical expressions for the false alarm probability (FAP) and correct detection probability (CDP) for any value of K . Our …

Algorithm Vs. Algorithm, Cary Coglianese, Alicia Lai

Faculty Scholarship at Penn Carey Law

Critics raise alarm bells about governmental use of digital algorithms, charging that they are too complex, inscrutable, and prone to bias. A realistic assessment of digital algorithms, though, must acknowledge that government is already driven by algorithms of arguably greater complexity and potential for abuse: the algorithms implicit in human decision-making. The human brain operates algorithmically through complex neural networks. And when humans make collective decisions, they operate via algorithms too—those reflected in legislative, judicial, and administrative processes. Yet these human algorithms undeniably fail and are far from transparent. On an individual level, human decision-making suffers from memory limitations, fatigue, …

From Negative To Positive Algorithm Rights, Cary Coglianese, Kat Hefter

Faculty Scholarship at Penn Carey Law

Artificial intelligence, or “AI,” is raising alarm bells. Advocates and scholars propose policies to constrain or even prohibit certain AI uses by governmental entities. These efforts to establish a negative right to be free from AI stem from an understandable motivation to protect the public from arbitrary, biased, or unjust applications of algorithms. This movement to enshrine protective rights follows a familiar pattern of suspicion that has accompanied the introduction of other technologies into governmental processes. Sometimes this initial suspicion of a new technology later transforms into widespread acceptance and even a demand for its use. In this paper, we …

Lasso: Listing All Subset Sums Obediently For Evaluating Unbounded Subset Sums, Christopher N. Burgoyne, Travis J. Wheeler

Graduate Student Theses, Dissertations, & Professional Papers

In this study we present a novel algorithm, LASSO, for solving the unbounded and bounded subset sum problem. The LASSO algorithm was designed to solve the unbounded SSP quickly and to return all subsets summing to a target sum. As speed was the highest priority, we benchmarked the run time performance of LASSO against implementations of some common approaches to the bounded SSP, as well as the only comparable implementation for solving the unbounded SSP that we could find. In solving the bounded SSP, our algorithm had a significantly faster run time than the competing algorithms when the target sum …

Predicting League Of Legends Ranked Games Outcome, Ngoc Linh Chi Nguyen

Senior Projects Spring 2022

League of Legends (LoL) is the one of most popular multiplayer online battle arena (MOBA) games in the world. For LoL, the most competitive way to evaluate a player’s skill level, below the professional Esports level, is competitive ranked games. These ranked games utilize a matchmaking system based on the player’s ranks to form a fair team for each game. However, a rank game's outcome cannot necessarily be predicted using just players’ ranks, there are a significant number of different variables impacting a rank game depending on how well each team plays. In this paper, I propose a method to …

"Mystify": A Proactive Moving-Target Defense For A Resilient Sdn Controller In Software Defined Cps, Mohamed Azab, Mohamed Samir, Effat Samir

Electrical & Computer Engineering Faculty Publications

The recent devastating mission Cyber–Physical System (CPS) attacks, failures, and the desperate need to scale and to dynamically adapt to changes, revolutionized traditional CPS to what we name as Software Defined CPS (SD-CPS). SD-CPS embraces the concept of Software Defined (SD) everything where CPS infrastructure is more elastic, dynamically adaptable and online-programmable. However, in SD-CPS, the threat became more immanent, as the long-been physically-protected assets are now programmatically accessible to cyber attackers. In SD-CPSs, a network failure hinders the entire functionality of the system. In this paper, we present MystifY, a spatiotemporal runtime diversification for Moving-Target Defense (MTD) to secure …

Transformer-Based Joint Learning Approach For Text Normalization In Vietnamese Automatic Speech Recognition Systems, The Viet Bui, Tho Chi Luong, Oanh Thi Tran

Research Collection School Of Computing and Information Systems

In this article, we investigate the task of normalizing transcribed texts in Vietnamese Automatic Speech Recognition (ASR) systems in order to improve user readability and the performance of downstream tasks. This task usually consists of two main sub-tasks: predicting and inserting punctuation (i.e., period, comma); and detecting and standardizing named entities (i.e., numbers, person names) from spoken forms to their appropriate written forms. To achieve these goals, we introduce a complete corpus including of 87,700 sentences and investigate conditional joint learning approaches which globally optimize two sub-tasks simultaneously. The experimental results are quite promising. Overall, the proposed architecture outperformed the …

Matrix Interpretations And Tools For Investigating Even Functionals, Benjamin Stringer

Theses and Dissertations--Computer Science

Even functionals are a set of polynomials evaluated on the terms of hollow symmetric matrices. Their properties lend themselves to applications such as counting subgraph embeddings in generic (weighted or unweighted) host graphs and computing moments of binary quadratic forms, which occur in combinatorial optimization. This research focuses primarily on counting subgraph embeddings, which is traditionally accomplished with brute-force algorithms or algorithms curated for special types of graphs. Even functionals provide a method for counting subgraphs algebraically in time proportional to matrix multiplication and is not restricted to particular graph types. Counting subgraph embeddings can be accomplished by evaluating a …

Decoding Cyclic Codes Via Gröbner Bases, Eduardo Sosa

Honors Theses

In this paper, we analyze the decoding of cyclic codes. First, we introduce linear and cyclic codes, standard decoding processes, and some standard theorems in coding theory. Then, we will introduce Gr¨obner Bases, and describe their connection to the decoding of cyclic codes. Finally, we go in-depth into how we decode cyclic codes using the key equation, and how a breakthrough by A. Brinton Cooper on decoding BCH codes using Gr¨obner Bases gave rise to the search for a polynomial-time algorithm that could someday decode any cyclic code. We discuss the different approaches taken toward developing such an algorithm and …

A Quantum Interpretation Of Separating Conjunction For Local Reasoning Of Quantum Programs Based On Separation Logic, Xuan-Bach Le, Shang-Wei Lin, Jun Sun, David Sanan

Research Collection School Of Computing and Information Systems

It is well-known that quantum programs are not only complicated to design but also challenging to verify because the quantum states can have exponential size and require sophisticated mathematics to encode and manipulate. To tackle the state-space explosion problem for quantum reasoning, we propose a Hoare-style inference framework that supports local reasoning for quantum programs. By providing a quantum interpretation of the separating conjunction, we are able to infuse separation logic into our framework and apply local reasoning using a quantum frame rule that is similar to the classical frame rule. For evaluation, we apply our framework to verify various …