Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms Commons

Open Access. Powered by Scholars. Published by Universities.®

1,151 Full-Text Articles 1,454 Authors 259,866 Downloads 103 Institutions

All Articles in Theory and Algorithms

Faceted Search

1,151 full-text articles. Page 1 of 39.

Rationality And Efficient Verifiable Computation, Matteo Campanelli 2018 The Graduate Center, City University of New York

Rationality And Efficient Verifiable Computation, Matteo Campanelli

All 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 ...


Second-Order Know-How Strategies, Pavel Naumov, Jia Tao 2018 Lafayette College

Second-Order Know-How Strategies, Pavel Naumov, Jia Tao

Faculty Research and Reports

The fact that a coalition has a strategy does not mean that the coalition knows what the strategy is. If the coalition knows the strategy, then such a strategy is called a know-how strategy of the coalition. The paper proposes the notion of a second-order know-how strategy for the case when one coalition knows what the strategy of another coalition is. The main technical result is a sound and complete logical system describing the interplay between the distributed knowledge modality and the second-order coalition know-how modality.


Smt-Based Answer Set Solver Cmodels-Diff (System Description), Da Shen, Yuliya Lierler 2018 University of Nebraska at Omaha

Smt-Based Answer Set Solver Cmodels-Diff (System Description), Da Shen, Yuliya Lierler

Yuliya Lierler

Many answer set solvers utilize Satisfiability solvers for search. SMT solvers extend Satisfiability solvers. This paper presents the CMODELS-DIFF system that uses SMT solvers to find answer sets of a logic program. Its theoretical foundation is based on Niemala's characterization of answer sets of a logic program via so called level rankings. The comparative experimental analysis demonstrates that CMODELS-DIFF is a viable answer set solver.


Temporal And Spatiotemporal Investigation Of Tourist Attraction Visit Sentiment On Twitter, Jose J. Padilla, Hamdi Kavak, Christopher J. Lynch, Ross J. Gore, Saikou Y. Diallo 2018 Old Dominion University

Temporal And Spatiotemporal Investigation Of Tourist Attraction Visit Sentiment On Twitter, Jose J. Padilla, Hamdi Kavak, Christopher J. Lynch, Ross J. Gore, Saikou Y. Diallo

VMASC Publications

In this paper, we propose a sentiment-based approach to investigate the temporal and spatiotemporal effects on tourists' emotions when visiting a city's tourist destinations. Our approach consists of four steps: data collection and preprocessing from social media; visitor origin identification; visit sentiment identification; and temporal and spatiotemporal analysis. The temporal and spatiotemporal dimensions include day of the year, season of the year, day of the week, location sentiment progression, enjoyment measure, and multi-location sentiment progression. We apply this approach to the city of Chicago using over eight million tweets. Results show that seasonal weather, as well as special days ...


Finding Spanning Trees In Strongly Connected Graphs With Per-Vertex Degree Constraints, Samuel Benjamin Chase 2018 California Polytechnic State University

Finding Spanning Trees In Strongly Connected Graphs With Per-Vertex Degree Constraints, Samuel Benjamin Chase

Computer Science

No abstract provided.


Word Blending And Other Formal Models Of Bio-Operations, Zihao Wang 2018 The University of Western Ontario

Word Blending And Other Formal Models Of Bio-Operations, Zihao Wang

Electronic Thesis and Dissertation Repository

As part of ongoing efforts to view biological processes as computations, several formal models of DNA-based processes have been proposed and studied in the formal language literature. In this thesis, we survey some classical formal language word and language operations, as well as several bio-operations, and we propose a new operation inspired by a DNA recombination lab protocol known as Cross-pairing Polymerase Chain Reaction, or XPCR. More precisely, we define and study a word operation called word blending which models a special case of XPCR, where two words x w p and q w y sharing a non-empty overlap part ...


Applications Of Artificial Intelligence In Power Systems, Samin Rastgoufard 2018 srastgou

Applications Of Artificial Intelligence In Power Systems, Samin Rastgoufard

University of New Orleans Theses and Dissertations

Artificial intelligence tools, which are fast, robust and adaptive can overcome the drawbacks of traditional solutions for several power systems problems. In this work, applications of AI techniques have been studied for solving two important problems in power systems.

The first problem is static security evaluation (SSE). The objective of SSE is to identify the contingencies in planning and operations of power systems. Numerical conventional solutions are time-consuming, computationally expensive, and are not suitable for online applications. SSE may be considered as a binary-classification, multi-classification or regression problem. In this work, multi-support vector machine is combined with several evolutionary computation ...


Computational Complexity Of Determining The Rigidity Of Ftam Assemblies, Ian Perkins 2018 University of Arkansas, Fayetteville

Computational Complexity Of Determining The Rigidity Of Ftam Assemblies, Ian Perkins

Computer Science and Computer Engineering Undergraduate Honors Theses

In this paper, we discuss a tile-based self-assembly model called the Folding Tile Assembly Model (FTAM). We briefly define what makes the FTAM unique in its ability to have folding 2D tiles. We also discuss the difficulty of determining the computational complexity of certain FTAM properties despite it being simpler for less dynamic models. Specifically, we discuss the property of rigidity in FTAM assemblies by devising a simple definition of rigidity, so that it is easier to determine its complexity. We use a reduction between an assembly and a 3SAT instance along with a series of proofs to give a ...


Tamscript - High Level Programming Interface For The Abstract Tile Assembly Model, Perry Mills 2018 University of Arkansas, Fayetteville

Tamscript - High Level Programming Interface For The Abstract Tile Assembly Model, Perry Mills

Computer Science and Computer Engineering Undergraduate Honors Theses

This paper describes a programming interface, TAMScript, for use with the PyTAS simulator. The interface allows for the dynamic generation of tile types as the simulation progresses, with the goal of reducing complexity for researchers. This paper begins with an introduction to the PyTAS software and a description of the 3D model which it simulates. Next, the changes made to support a dynamic generation scheme are detailed, and some of the potential benefits of this scheme are outlined. Then several of the example scripts which have been written using the TAMScript interface are reviewed. Finally, the potential for future research ...


Minimization Techniques For Symbolic Automata, Jonathan Homburg 2018 University of Connecticut

Minimization Techniques For Symbolic Automata, Jonathan Homburg

Honors Scholar Theses

Symbolic finite automata (SFAs) are generalizations of classical finite state automata. Whereas the transitions of classical automata are labeled by characters from some alphabet, the transitions of symbolic automata are labeled by predicates over a Boolean algebra defined on the alphabet. This allows for SFAs to be efficiently constructed over extremely large, and possibly infinite, alphabets. This thesis examines an existing incremental algorithm for the minimization of deterministic finite automata. Several extensions of this algorithm to de- terministic symbolic automata are introduced. Although more efficient algorithms already exist for deterministic SFA minimization, the presented algorithms are uniquely designed to minimize ...


Computer Vision Evidence Supporting Craniometric Alignment Of Rat Brain Atlases To Streamline Expert-Guided, First-Order Migration Of Hypothalamic Spatial Datasets Related To Behavioral Control, Arshad M. Khan, Jose G. Perez, Claire E. Wells, Olac Fuentes 2018 University of Texas at El Paso

Computer Vision Evidence Supporting Craniometric Alignment Of Rat Brain Atlases To Streamline Expert-Guided, First-Order Migration Of Hypothalamic Spatial Datasets Related To Behavioral Control, Arshad M. Khan, Jose G. Perez, Claire E. Wells, Olac Fuentes

Arshad M. Khan, Ph.D.

The rat has arguably the most widely studied brain among all animals, with numerous reference atlases for rat brain having been published since 1946. For example, many neuroscientists have used the atlases of Paxinos and Watson (PW, first published in 1982) or Swanson (S, first published in 1992) as guides to probe or map specific rat brain structures and their connections. Despite nearly three decades of contemporaneous publication, no independent attempt has been made to establish a basic framework that allows data mapped in PWto be placed in register with S, or vice versa. Such data migration would allow ...


Analysis Challenges For High Dimensional Data, Bangxin Zhao 2018 The University of Western Ontario

Analysis Challenges For High Dimensional Data, Bangxin Zhao

Electronic Thesis and Dissertation Repository

In this thesis, we propose new methodologies targeting the areas of high-dimensional variable screening, influence measure and post-selection inference. We propose a new estimator for the correlation between the response and high-dimensional predictor variables, and based on the estimator we develop a new screening technique termed Dynamic Tilted Current Correlation Screening (DTCCS) for high dimensional variables screening. DTCCS is capable of picking up the relevant predictor variables within a finite number of steps. The DTCCS method takes the popular used sure independent screening (SIS) method and the high-dimensional ordinary least squares projection (HOLP) approach as its special cases.

Two methods ...


Use Of The Proof-Of-Stake Algorithm For Distributed Consensus In Blockchain Protocol For Cryptocurrency, Spencer J. Hosack 2018 University of Connecticut

Use Of The Proof-Of-Stake Algorithm For Distributed Consensus In Blockchain Protocol For Cryptocurrency, Spencer J. Hosack

Honors Scholar Theses

Recent attention to Bitcoin and other cryptocurrencies has opened investors and the public to the realm of digital currency. Greater exposure around the world has led to a frenzy of entry into the market and a test into the long-term feasibility of Bitcoin being able to remain a functioning peer-to-peer (P2P), decentralized currency. Its main structure is supported by the Proof-of-Work (PoW) protocol in which users can elect to participate in determining transaction approval and ensuring an honest blockchain. This system relies on elected users to expend computational power and energy to solve puzzles to prove the accuracy of the ...


Blockchain In Payment Card Systems, Darlene Godfrey-Welch, Remy Lagrois, Jared Law, Russell Scott Anderwald 2018 Southern Methodist University

Blockchain In Payment Card Systems, Darlene Godfrey-Welch, Remy Lagrois, Jared Law, Russell Scott Anderwald

SMU Data Science Review

Payment cards (e.g., credit and debit cards) are the most frequent form of payment in use today. A payment card transaction entails many verification information exchanges between the cardholder, merchant, issuing bank, a merchant bank, and third-party payment card processors. Today, a record of the payment transaction often records to multiple ledgers. Merchant’s incur fees for both accepting and processing payment cards. The payment card industry is in dire need of technology which removes the need for third-party verification and records transaction details to a single tamper-resistant digital ledger. The private blockchain is that technology. Private blockchain provides ...


A Reasonable Bias Approach To Gerrymandering: Using Automated Plan Generation To Evaluate Redistricting Proposals, Bruce E. Cain, Wendy K. Tam Cho, Yan Y. Liu, Emily R. Zhang 2018 College of William & Mary Law School

A Reasonable Bias Approach To Gerrymandering: Using Automated Plan Generation To Evaluate Redistricting Proposals, Bruce E. Cain, Wendy K. Tam Cho, Yan Y. Liu, Emily R. Zhang

William & Mary Law Review

No abstract provided.


Modular Scheduling System For Westside School District, Tyler Bienhoff 2018 University of Nebraska-Lincoln

Modular Scheduling System For Westside School District, Tyler Bienhoff

Honors Theses, University of Nebraska-Lincoln

Westside School district offers a modular scheduling system for their high school that is more similar to a college schedule than the typical high school system. Due to the complexity of their master schedule each semester, there are no commercially available products that can assist in creating a schedule. Hence, this thesis discusses a scheduling algorithm and management system that was built specifically for Westside High School with the potential to be expanded for use by other interested schools. The first part of the paper is focused on gathering input from students and faculty for which courses and how many ...


Quantum Attacks On Modern Cryptography And Post-Quantum Cryptosystems, Zachary Marron 2018 Liberty University

Quantum Attacks On Modern Cryptography And Post-Quantum Cryptosystems, Zachary Marron

Senior Honors Theses

Cryptography is a critical technology in the modern computing industry, but the security of many cryptosystems relies on the difficulty of mathematical problems such as integer factorization and discrete logarithms. Large quantum computers can solve these problems efficiently, enabling the effective cryptanalysis of many common cryptosystems using such algorithms as Shor’s and Grover’s. If data integrity and security are to be preserved in the future, the algorithms that are vulnerable to quantum cryptanalytic techniques must be phased out in favor of quantum-proof cryptosystems. While quantum computer technology is still developing and is not yet capable of breaking commercial ...


Understanding Natural Keyboard Typing Using Convolutional Neural Networks On Mobile Sensor Data, Travis Siems 2018 Southern Methodist University

Understanding Natural Keyboard Typing Using Convolutional Neural Networks On Mobile Sensor Data, Travis Siems

Computer Science and Engineering Theses and Dissertations

Mobile phones and other devices with embedded sensors are becoming increasingly ubiquitous. Audio and motion sensor data may be able to detect information that we did not think possible. Some researchers have created models that can predict computer keyboard typing from a nearby mobile device; however, certain limitations to their experiment setup and methods compelled us to be skeptical of the models’ realistic prediction capability. We investigate the possibility of understanding natural keyboard typing from mobile phones by performing a well-designed data collection experiment that encourages natural typing and interactions. This data collection helps capture realistic vulnerabilities of the security ...


Similarity Based Classification Of Adhd Using Singular Value Decomposition, Taban Eslami, Fahad Saeed 2018 Western Michigan University

Similarity Based Classification Of Adhd Using Singular Value Decomposition, Taban Eslami, Fahad Saeed

Parallel Computing and Data Science Lab Technical Reports

Attention deficit hyperactivity disorder (ADHD) is one of the most common brain disorders among children. This disorder is considered as a big threat for public health and causes attention, focus and organizing difficulties for children and even adults. Since the cause of ADHD is not known yet, data mining algorithms are being used to help discover patterns which discriminate healthy from ADHD subjects. Numerous efforts are underway with the goal of developing classification tools for ADHD diagnosis based on functional and structural magnetic resonance imaging data of the brain. In this paper, we used Eros, which is a technique for ...


Application Of Huffman Data Compression Algorithm In Hashing Computation, Lakshmi Narasimha Devulapalli Venkata, 2018 Western Kentucky University

Application Of Huffman Data Compression Algorithm In Hashing Computation, Lakshmi Narasimha Devulapalli Venkata,

Masters Theses & Specialist Projects

Cryptography is the art of protecting information by encrypting the original message into an unreadable format. A cryptographic hash function is a hash function which takes an arbitrary length of the text message as input and converts that text into a fixed length of encrypted characters which is infeasible to invert. The values returned by the hash function are called as the message digest or simply hash values. Because of its versatility, hash functions are used in many applications such as message authentication, digital signatures, and password hashing [Thomsen and Knudsen, 2005].

The purpose of this study is to apply ...


Digital Commons powered by bepress