Computer Sciences Commons^™

Hardness Of Reconfiguring Robot Swarms With Uniform External Control In Limited Directions, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie

Computer Science Faculty Publications

Motivated by advances is nanoscale applications and simplistic robot agents, we look at problems based on using a global signal to move all agents when given a limited number of directional signals and immovable geometry. We study a model where unit square particles move within a 2D grid based on uniform external forces. Movement is based on a sequence of uniform commands which cause all particles to move 1 step in a specific direction. The 2D grid board additionally contains \blocked" spaces which prevent particles from entry. Within this model, we investigate the complexity of deciding 1) whether a target …

Different Approximation Algorithms For Channel Scheduling In Wireless Networks, Qiufen Ni, Chuanhe Huang, Panos M. Pardalos, Jia Ye, Bin Fu

Computer Science Faculty Publications

We introduce a new two-side approximation method for the channel scheduling problem, which controls the accuracy of approximation in two sides by a pair of parameters . We present a series of simple and practical-for-implementation greedy algorithms which give constant factor approximation in both sides. First, we propose four approximation algorithms for the weighted channel allocation problem: 1. a greedy algorithm for the multichannel with fixed interference radius scheduling problem is proposed and an one side -IS-approximation is obtained; 2. a greedy -approximation algorithm for single channel with fixed interference radius scheduling problem is presented; 3. we improve the existing …

Divide And Slide: Layer-Wise Refinement For Output Range Analysis Of Deep Neural Networks, Chao Huang, Jiameng Fan, Xin Chen, Wenchao Li, Qi Zhu

Computer Science Faculty Publications

In this article, we present a layer-wise refinement method for neural network output range analysis. While approaches such as nonlinear programming (NLP) can directly model the high nonlinearity brought by neural networks in output range analysis, they are known to be difficult to solve in general. We propose to use a convex polygonal relaxation (overapproximation) of the activation functions to cope with the nonlinearity. This allows us to encode the relaxed problem into a mixed-integer linear program (MILP), and control the tightness of the relaxation by adjusting the number of segments in the polygon. Starting with a segment number of …

Deepfrag-K: A Fragment-Based Deep Learning Approach For Protein Fold Recognition, Wessam Elhefnawy, Min Li, Jianxin Wang, Yaohang Li

Computer Science Faculty Publications

Background: One of the most essential problems in structural bioinformatics is protein fold recognition. In this paper, we design a novel deep learning architecture, so-called DeepFrag-k, which identifies fold discriminative features at fragment level to improve the accuracy of protein fold recognition. DeepFrag-k is composed of two stages: the first stage employs a multi-modal Deep Belief Network (DBN) to predict the potential structural fragments given a sequence, represented as a fragment vector, and then the second stage uses a deep convolutional neural network (CNN) to classify the fragment vector into the corresponding fold.

Results: Our results show that DeepFrag-k yields …

A User Study Of A Wearable System To Enhance Bystanders’ Facial Privacy, Alfredo J. Perez, Sherali Zeadally, Scott Griffith, Luis Y. Matos Garcia, Jason A. Mouloud

Computer Science Faculty Publications

The privacy of users and information are becoming increasingly important with the growth and pervasive use of mobile devices such as wearables, mobile phones, drones, and Internet of Things (IoT) devices. Today many of these mobile devices are equipped with cameras which enable users to take pictures and record videos anytime they need to do so. In many such cases, bystanders’ privacy is not a concern, and as a result, audio and video of bystanders are often captured without their consent. We present results from a user study in which 21 participants were asked to use a wearable system called …

Effect Of Implementing Subgoals In Code.Org's Intro To Programming Unit In Computer Science Principles, Lauren E. Margulieux, Briana Baker Morrison, Baker Franke, Hari Ramilison

Computer Science Faculty Publications

The subgoal learning framework has improved performance for novice programmers in higher education, but it has only started to be applied and studied in K-12 (primary/secondary). Programming education in K-12 is growing, and many international initiatives are attempting to increase participation, including curricular initiatives like Computer Science Principles and non-profit organizations like Code.org. Given that subgoal learning is designed to help students with no prior knowledge, we designed and implemented subgoals in the introduction to programming unit in Code.org's Computer Science Principles course. The redesigned unit includes subgoal-oriented instruction and subgoal-themed pre-written comments that students could add to their programming …

Relocating Units In Robot Swarms With Uniform Control Signals Is Pspace-Complete, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie

Computer Science Faculty Publications

This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction on a 2D grid board with geometric obstacles. We show that the problem of deciding if a particular particle can be relocated to a specified location on the board is PSPACE-complete when only allowing 1x1 particles. This shows a separation between this problem, called the relocation problem, and the occupancy problem in which we ask whether a particular location can be occupied by any particle on the …

Secure Authentication And Privacy-Preserving Techniques In Vehicular Ad-Hoc Networks (Vanets), Dakshnamoorthy Manivannan, Shafika Showkat Moni, Sherali Zeadally

Computer Science Faculty Publications

In the last decade, there has been growing interest in Vehicular Ad Hoc NETworks (VANETs). Today car manufacturers have already started to equip vehicles with sophisticated sensors that can provide many assistive features such as front collision avoidance, automatic lane tracking, partial autonomous driving, suggestive lane changing, and so on. Such technological advancements are enabling the adoption of VANETs not only to provide safer and more comfortable driving experience but also provide many other useful services to the driver as well as passengers of a vehicle. However, privacy, authentication and secure message dissemination are some of the main issues that …

The Majority Rule: A General Protection On Recommender System, Lei Xu, Lin Chen, Martin Flores, Hansheng Lei, Liyu Zhang, Mahmoud K. Quweider, Fitratullah Khan, Weidong Shi

Computer Science Faculty Publications

Recommender systems are widely used in a variety of scenarios, including online shopping, social network, and contents distribution. As users rely more on recommender systems for information retrieval, they also become attractive targets for cyber-attacks. The high-level idea of attacking a recommender system is straightforward. An adversary selects a strategy to inject manipulated data into the database of the recommender system to influence the recommendation results, which is also known as a profile injection attack. Most existing works treat attacking and protection in a static manner, i.e., they only consider the adversary’s behavior when analyzing the influence without considering normal …

Timing Of Maximal Weight Reduction Following Bariatric Surgery: A Study In Chinese Patients, Ting Xu, Chen Wang, Hongwei Zhang, Xiaodong Han, Weijie Liu, Junfeng Han, Haoyong Yu, Jin Chen, Pin Zhang, Jianzhong Di

Computer Science Faculty Publications

Introduction: Bariatric surgery is a well-received treatment for obesity with maximal weight loss at 12–36 months postoperatively. We investigated the effect of early bariatric surgery on weight reduction of Chinese patients in accordance with their preoperation characteristics.

Materials and Methods: Altogether, 409 patients with obesity from a prospective cohort in a single bariatric center were enrolled retrospectively and evaluated for up to 4 years. Measurements obtained included surgery type, duration of diabetic condition, besides the usual body mass index data tuple. Weight reduction was expressed as percent total weight loss (%TWL) and percent excess weight loss (%EWL).

Results: RYGB or …

A Bio-Inspired Transportation Network For Scalable Swarm Foraging, Qi Lu, G. Matthew Fricke, Takaya Tsuno, Melanie E. Moses

Computer Science Faculty Publications

Scalability is a significant challenge for robot swarms. Generally, larger groups of cooperating robots produce more inter-robot collisions, and in swarm robot foraging, larger search arenas result in larger travel costs. This paper demonstrates a scale-invariant swarm foraging algorithm that ensures that each robot finds and delivers targets to a central collection zone at the same rate regardless of the size of the swarm or the search area. Dispersed mobile depots aggregate locally collected targets and transport them to a central place via a hierarchical branching transportation network. This approach is inspired by ubiquitous fractal branching networks such as tree …

Real-Time Road Hazard Information System, Carlos Pena-Caballero, Dong-Chul Kim, Adolfo Gonzalez, Osvaldo Castellanos, Angel A. Cantu, Jungseok Ho

Computer Science Faculty Publications

Infrastructure is a significant factor in economic growth for systems of government. In order to increase economic productivity, maintaining infrastructure quality is essential. One of the elements of infrastructure is roads. Roads are means which help local and national economies be more productive. Furthermore, road damage such as potholes, debris, or cracks is the cause of many on-road accidents that have cost the lives of many drivers. In this paper, we propose a system that uses Convolutional Neural Networks to detect road degradations without data pre-processing. We utilize the state-of-the-art object detection algorithm, YOLO detector for the system. First, we …

Analyzing Sensor-Based Individual And Population Behavior Patterns Via Inverse Reinforcement Learning, Beiyu Lin, Diane J. Cook

Computer Science Faculty Publications

Digital markers of behavior can be continuously created, in everyday settings, using time series data collected by ambient sensors. The goal of this work was to perform individual- and population-level behavior analysis from such time series sensor data. In this paper, we introduce a novel algorithm-Resident Relative Entropy-Inverse Reinforcement Learning (RRE-IRL)-to perform an analysis of a single smart home resident or a group of residents, using inverse reinforcement learning. By employing this method, we learnt an individual's behavioral routine preferences. We then analyzed daily routines for an individual and for eight smart home residents grouped by health diagnoses. We observed …

New Bounds On Augmenting Steps Of Block-Structured Integer Programs, Lin Chen, Martin Koutecký, Lei Xu, Weidong Shi

Computer Science Faculty Publications

Iterative augmentation has recently emerged as an overarching method for solving Integer Programs (IP) in variable dimension, in stark contrast with the volume and flatness techniques of IP in fixed dimension. Here we consider 4-block n-fold integer programs, which are the most general class considered so far. A 4-block n-fold IP has a constraint matrix which consists of n copies of small matrices A, B, and D, and one copy of C, in a specific block structure. Iterative augmentation methods rely on the so-called Graver basis of the constraint matrix, which constitutes a set of fundamental augmenting steps. All existing …

Building Patterned Shapes In Robot Swarms With Uniform Control Signals, David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie

Computer Science Faculty Publications

This paper investigates a restricted version of robot motion planning, in which particles on a board uniformly respond to global signals that cause them to move one unit distance in a particular direction. We look at the problem of assembling patterns within this model. We first derive upper and lower bounds on the worst-case number of steps needed to reconfigure a general purpose board into a target pattern. We then show that the construction of k-colored patterns of size-n requires Ω(n log k) steps in general, and Ω(n log k + √ k) steps if the constructed shape must always …

Hardness Of Sparse Sets And Minimal Circuit Size Problem, Bin Fu

Computer Science Faculty Publications

We study the magnification of hardness of sparse sets in nondeterministic time complexity classes on a randomized streaming model. One of our results shows that if there exists a 2no(1) -sparse set in NDTIME(2no(1)) that does not have any randomized streaming algorithm with no(1) updating time, and no(1) space, then NEXP≠BPP , where a f(n)-sparse set is a language that has at most f(n) strings of length n. We also show that if MCSP is ZPP -hard under polynomial time truth-table reductions, then EXP≠ZPP .

Computational Complexity Characterization Of Protecting Elections From Bribery, Lin Chen, Ahmed Sunny, Lei Xu, Shouhuai Xu, Zhimin Gao, Yang Lu, Weidong Shi, Nolan Shah

Computer Science Faculty Publications

The bribery problem in election has received considerable attention in the literature, upon which various algorithmic and complexity results have been obtained. It is thus natural to ask whether we can protect an election from potential bribery. We assume that the protector can protect a voter with some cost (e.g., by isolating the voter from potential bribers). A protected voter cannot be bribed. Under this setting, we consider the following bi-level decision problem: Is it possible for the protector to protect a proper subset of voters such that no briber with a fixed budget on bribery can alter the election …

Polyhedra Circuits And Their Applications, Bin Fu, Pengfei Gu, Yuming Zhao

Computer Science Faculty Publications

To better compute the volume and count the lattice points in geometric objects, we propose polyhedral circuits. Each polyhedral circuit characterizes a geometric region in Rd . They can be applied to represent a rich class of geometric objects, which include all polyhedra and the union of a finite number of polyhedron. They can be also used to approximate a large class of d-dimensional manifolds in Rd . Barvinok [3] developed polynomial time algorithms to compute the volume of a rational polyhedron, and to count the number of lattice points in a rational polyhedron in Rd with a fixed dimensional …

Weak Mitoticity Of Bounded Disjunctive And Conjunctive Truth-Table Autoreducible Sets, Liyu Zhang, Mahmoud K. Quweider, Hangsheng Lei, Fitratullah Khan

Computer Science Faculty Publications

Glaßer et al. (SIAMJCOMP 2008 and TCS 2009)2 proved existence of two sparse sets A and B in EXP, where A is 3-tt (truth-table) polynomial-time autoreducible but not weakly polynomial-time Turing mitotic and B is polynomial-time 2-tt autoreducible but not weakly polynomial-time 2-tt mitotic. We unify and strengthen both of those results by showing that there is a sparse set in EXP that is polynomial-time 2-tt autoreducible but not even weakly polynomial-time Turing mitotic. All these results indicate that polynomial-time autoreducibilities in general do not imply polynomial-time mitoticity at all with the only exceptions of the many-one and 1-tt reductions. …

Infusing Raspberry Pi In The Computer Science Curriculum For Enhanced Learning, Fitratullah Khan, Mahmoud K. Quweider, Ala Qubbaj, Emmett Tomai, Lei Xu, Liyu Zhang, Hansheng Lei

Computer Science Faculty Publications

With the advent of cloud computing, the Internet of Things (IoT), and mobile computing, CS faculty are continuously revamping the curriculum material to address such burgeoning set of technologies in practical and relatable ways. Raspberry Pi (RPi) devices represent an ideal hardware/software framework that embodies all these technologies through its simple architecture, small form factor (that minimizes the volume and footprint of a desktop computer), and ability to integrate various sensors that network together and connect to the Cloud. Therefore, one of the strategies of Computer Science Department, to enhance depth of learning concepts, has been to infuse Raspberry Pi …

Interactive Free-Viewpoint Video Generation, Yanru Wang, Zhihao Huang, Hao Zhu, Wei Li, Xun Cao, Ruigang Yang

Computer Science Faculty Publications

Background

Free-viewpoint video (FVV) is processed video content in which viewers can freely select the viewing position and angle. FVV delivers an improved visual experience and can also help synthesize special effects and virtual reality content. In this paper, a complete FVV system is proposed to interactively control the viewpoints of video relay programs through multimedia terminals such as computers and tablets.

Methods

The hardware of the FVV generation system is a set of synchronously controlled cameras, and the software generates videos in novel viewpoints from the captured video using view interpolation. The interactive interface is designed to visualize the …

Cybersecurity, Digital Forensics, And Mobile Computing: Building The Pipeline Of Next-Generation University Graduates Through Focused High School Summer Camps, Mahmoud K. Quweider, Fitratullah Khan, Liyu Zhang, Lei Xu, Yessica Rodriguez, Yessenia Rodriguez

Computer Science Faculty Publications

To prepare the next generation of skilled university graduates that would help in filling the national need for cybersecurity, digital forensics, and mobile computing professionals, a team of minority/under-represented graduate students, the University Upward Bound Program (a federally funded program and part of the U.S. Department of Education; one of 967 programs nationwide) staff, and faculty from the Computer Science (CS) department got together and proposed a focused 10-week long funded summer camp for two local high schools with the following objectives:

1. Provide graduate students to instruct in the areas of` mobile application development, forensics and cyber Security.

2. …

Visual Attention Consistency Under Image Transforms For Multi-Label Image Classification, Hao Guo, Kang Zheng, Xiaochuan Fan, Hongkai Yu, Song Wang

Computer Science Faculty Publications

Human visual perception shows good consistency for many multi-label image classification tasks under certain spatial transforms, such as scaling, rotation, flipping and translation. This has motivated the data augmentation strategy widely used in CNN classifier training -- transformed images are included for training by assuming the same class labels as their original images. In this paper, we further propose the assumption of perceptual consistency of visual attention regions for classification under such transforms, i.e., the attention region for a classification follows the same transform if the input image is spatially transformed. While the attention regions of CNN classifiers can be …

Reducing Withdrawal And Failure Rates In Introductory Programming With Subgoal Labeled Worked Examples, Lauren E. Margulieux, Briana B. Morrison, Adrienne Decker

Computer Science Faculty Publications

Background

Programming a computer is an increasingly valuable skill, but dropout and failure rates in introductory programming courses are regularly as high as 50%. Like many fields, programming requires students to learn complex problem-solving procedures from instructors who tend to have tacit knowledge about low-level procedures that they have automatized. The subgoal learning framework has been used in programming and other fields to breakdown procedural problem solving into smaller pieces that novices can grasp more easily, but it has only been used in short-term interventions. In this study, the subgoal learning framework was implemented throughout a semester-long introductory programming course …

Using Continuous Sensor Data To Formalize A Model Of In-Home Activity Patterns, Beiyu Lin, Diane J. Cook, Maureen Schmitter-Edgecombe

Computer Science Faculty Publications

Formal modeling and analysis of human behavior can properly advance disciplines ranging from psychology to economics. The ability to perform such modeling has been limited by a lack of ecologically-valid data collected regarding human daily activity. We propose a formal model of indoor routine behavior based on data from automatically-sensed and recognized activities. A mechanistic description of behavior patterns for identical activity is offered to both investigate behavioral norms with 99 smart homes and compare these norms between subgroups. We identify and model the patterns of human behaviors based on inter-arrival times, the time interval between two successive activities, for …

A Semi-Automated Technique For Transcribing Accurate Crowd Motions, Alexander Fuchsberger, Brian Ricks, Zhicheng Chen

Computer Science Faculty Publications

We present a novel technique for transcribing crowds in video scenes that allows extracting the positions of moving objects in video frames. The technique can be used as a more precise alternative to image processing methods, such as background-removal or automated pedestrian detection based on feature extraction and classification. By manually projecting pedestrian actors on a two-dimensional plane and translating screen coordinates to absolute real-world positions using the cross ratio, we provide highly accurate and complete results at the cost of increased processing time. We are able to completely avoid most errors found in other automated annotation techniques, resulting from …

Domain Adaptation For Vehicle Detection In Traffic Surveillance Images From Daytime To Nighttime, Jinlong Ji, Zhigang Xu, Hongkai Yu, Lan Fu, Xuesong Zhou

Computer Science Faculty Publications

Vehicle detection in traffic surveillance images is an important approach to obtain vehicle data and rich traffic flow parameters. Recently, deep learning based methods have been widely used in vehicle detection with high accuracy and efficiency. However, deep learning based methods require a large number of manually labeled ground truths (bounding box of each vehicle in each image) to train the Convolutional Neural Networks (CNN). In the modern urban surveillance cameras, there are already many manually labeled ground truths in daytime images for training CNN, while there are little or much less manually labeled ground truths in nighttime images. In …

Privateex: Privacy Preserving Exchange Of Crypto-Assets On Blockchain, Lei Xu, Lin Chen, Zhimin Gao, Keshav Kasichainula, Miguel Fernandez, Bogdan Carbunar, Weidong Shi

Computer Science Faculty Publications

Bitcoin introduces a new type of cryptocurrency that does not rely on a central system to maintain transactions. Inspired by the success of Bitcoin, all types of alt cryptocurrencies were invented in recent years. Some of the new cryptocurrencies focus on privacy enhancement, where transaction information such as value and sender/receiver identity can be hidden, such as Zcash and Monero. However, there are few schemes to support multiple types of cryptocurrencies/assets and offer privacy enhancement at the same time. The major challenge for a multiple asset system is that it needs to support two-way assets exchange between participants besides one-way …

A Cost Analysis Of Internet Of Things Sensor Data Storage On Blockchain Via Smart Contracts, Yesem Kurt Peker, Xavier Rodriguez, James Ericsson, Suk Jin Lee, Alfredo J. Perez

Computer Science Faculty Publications

Blockchain is a developing technology that can be utilized for secure data storage and sharing. In this work, we examine the cost of Blockchain-based data storage for constrained Internet of Things (IoT) devices. We had two phases in the study. In the first phase, we stored data retrieved from a temperature/humidity sensor connected to an Ethereum testnet blockchain using smart contracts in two different ways: first, appending the new data to the existing data, storing all sensor data; and second, overwriting the new data onto the existing data, storing only a recent portion of the data. In the second phase, …

Supporting Blockchain-Based Cryptocurrency Mobile Payment With Smart Devices, Lei Xu, Lin Chen, Zhimin Gao, Larry Carranco, Xinxin Fan, Nolah Shah

Computer Science Faculty Publications

The smart device owning rate such as smart phone and smart watch is higher than ever before and mobile payment has become one of the major payment methods in many different areas. At the same time, blockchain-based cryptocurrency is becoming a nonnegligible type of currency and the total value of all types of cryptocurrency has reached USD 200 billion. Therefore, it is a natural demand to support cryptocurrency payment on mobile devices. Considering the poor infrastructure and low penetration of financial service in developing countries, this combination is especially attractive. The high storage cost and payment processing latency are the …