Physical Sciences and Mathematics Commons^™

On Coresets For Fair Clustering In Metric And Euclidean Spaces And Their Applications, Sayan Bandyapadhyay, Fedor V. Fomin, Kirill Simonov

Computer Science Faculty Publications and Presentations

Fair clustering is a constrained clustering problem where we need to partition a set of colored points. The fraction of points of each color in every cluster should be more or less equal to the fraction of points of this color in the dataset. The problem was recently introduced by Chierichetti et al. (2017) [1]. We propose a new construction of coresets for fair clustering for Euclidean and general metrics based on random sampling. For the Euclidean space Rd, we provide the first coreset whose size does not depend exponentially on the dimension d. The question of whether such constructions …

Fea Simulations For Thermal Distributions Of Large Scale 3dic Packages, Suxia Chen, Qiang Wu, Wayne Xun, Jiachen Zhang, Jianping Xun

Computer Science Faculty Publications and Presentations

As the market increases for Artificial Intelligence and High-Performance Computing applications, the geometry of 3-Dimensional Integrated Circuit packages becomes more complicated; therefore, predicting the thermal distributions of the structures becomes not only more important but also more challenging. The physics governing the thermal distribution is a 3-dimensional partial differential equation. In order to predict the thermal distributions, various approaches such as the layer modeling method have been invented. While practical, these approaches solve a simplified version of the differential equation placing an inherent limitation on their capabilities which may be improved upon. In this research we solve the actual differential …

Static Reflective Surfaces For Improved Terahertz Coverage, Thanh Le, Suresh Singh

Computer Science Faculty Publications and Presentations

LoS (Line of Sight) MIMO (Multiple Input Multiple Output) is considered the best way to deliver high capacity channels for terahertz communications due to the severe attenuation suffered by reflected components. Unfortunately, terahertz links are easily blocked by any obstruction resulting in link breakage. Therefore, it is necessary to provide alternative paths via reflectors. A problem shared by LoS paths and reflected paths (via polished reflectors) is that the channel matrix is rank 1 in the far-field. As a result, the achieved capacity is lower than what can theoretically be achieved in a rich multi-path environment. In this work, we …

Mask2former With Improved Query For Semantic Segmentation In Remote-Sensing Images, Shichen Guo, Qi Wang, Shiming Xiang, Shuwen Wang, Xuezhi Wang

Computer Science Faculty Publications and Presentations

Semantic segmentation of remote sensing (RS) images is vital in various practical applications, including urban construction planning, natural disaster monitoring, and land resources investigation. However, RS images are captured by airplanes or satellites at high altitudes and long distances, resulting in ground objects of the same category being scattered in various corners of the image. Moreover, objects of different sizes appear simultaneously in RS images. For example, some objects occupy a large area in urban scenes, while others only have small regions. Technically, the above two universal situations pose significant challenges to the segmentation with a high quality for RS …

Self-Optimizing Feature Generation Via Categorical Hashing Representation And Hierarchical Reinforcement Crossing, Wangyang Ying, Dongjie Wang, Kunpeng Liu, Leilei Sun, Yanjie Fu

Computer Science Faculty Publications and Presentations

Feature generation aims to generate new and meaningful features to create a discriminative representation space. A generated feature is meaningful when the generated feature is from a feature pair with inherent feature interaction. In the real world, experienced data scientists can identify potentially useful feature-feature interactions, and generate meaningful dimensions from an exponentially large search space in an optimal crossing form over an optimal generation path. But, machines have limited human-like abilities. We generalize such learning tasks as self-optimizing feature generation. Self-optimizing feature generation imposes several under-addressed challenges on existing systems: meaningful, robust, and efficient generation. To tackle these challenges, …

Deep Adaptive Graph Clustering Via Von Mises-Fisher Distributions, Pengfei Wang, Daqing Wu, Chong Chen, Kunpeng Liu, Yanjie Fu, Jianqiang Huang, Yuanchun Zhou, Jianfeng Zhan, Xiansheng Hua

Computer Science Faculty Publications and Presentations

Graph clustering has been a hot research topic and is widely used in many fields, such as community detection in social networks. Lots of works combining auto-encoder and graph neural networks have been applied to clustering tasks by utilizing node attributes and graph structure. These works usually assumed the inherent parameters (i.e., size and variance) of different clusters in the latent embedding space are homogeneous, and hence the assigned probability is monotonous over the Euclidean distance between node embeddings and centroids. Unfortunately, this assumption usually does not hold since the size and concentration of different clusters can be quite different, …

Gated Recurrent Units For Blockage Mitigation In Mmwave Wireless, Ahmed H. Almutairi, Alireza Keshavarz-Haddad, Ehsan Aryafar

Computer Science Faculty Publications and Presentations

Millimeter-Wave (mmWave) communication is susceptible to blockages, which can significantly reduce the signal strength at the receiver. Mitigating the negative impacts of blockages is a key requirement to ensure reliable and high throughput mmWave communication links. Previous research on blockage mitigation has introduced several model and protocol based blockage mitigation solutions that focus on one technique at a time, such as handoff to a different base station or beam adaptation to the same base station. In this paper, we address the overarching problem: what blockage mitigation method should be employed? and what is the optimal sub-selection within that method? To …

Preventing Inferences Through Data Dependencies On Sensitive Data, Primal Pappachan, Shufan Zhang, Xi He, Sharad Mehrotra

Computer Science Faculty Publications and Presentations

Simply restricting the computation to non-sensitive part of the data may lead to inferences on sensitive data through data dependencies. Inference control from data dependencies has been studied in the prior work. However, existing solutions either detect and deny queries which may lead to leakage – resulting in poor utility, or only protects against exact reconstruction of the sensitive data – resulting in poor security. In this paper, we present a novel security model called full deniability. Under this stronger security model, any information inferred about sensitive data from non-sensitive data is considered as a leakage. We describe algorithms for …

Parameterized Complexity Of Feature Selection For Categorical Data Clustering, Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Kirill Simonov

Computer Science Faculty Publications and Presentations

We develop new algorithmic methods with provable guarantees for feature selection in regard to categorical data clustering. While feature selection is one of the most common approaches to reduce dimensionality in practice, most of the known feature selection methods are heuristics. We study the following mathematical model. We assume that there are some inadvertent (or undesirable) features of the input data that unnecessarily increase the cost of clustering. Consequently, we want to select a subset of the original features from the data such that there is a small-cost clustering on the selected features. More precisely, for given integers ℓ (the …

Effective Entity Augmentation By Querying External Data Sources, Christopher Buss, Jasmin Mousavi, Mikhail Tokarev, Arash Termehchy, David Maier, Stefan Lee

Computer Science Faculty Publications and Presentations

Users often want to augment and enrich entities in their datasets with relevant information from external data sources. As many external sources are accessible only via keyword-search interfaces, a user usually has to manually formulate a keyword query that extract relevant information for each entity. This approach is challenging as many data sources contain numerous tuples, only a small fraction of which may contain entity-relevant information. Furthermore, different datasets may represent the same information in distinct forms and under different terms (e.g., different data source may use different names to refer to the same person). In such cases, it is …

Auxiliary Features-Guided Super Resolution For Monte Carlo Rendering, Qiqi Hou, Feng Liu

Computer Science Faculty Publications and Presentations

This paper investigates super-resolution to reduce the number of pixels to render and thus speed up Monte Carlo rendering algorithms. While great progress has been made to super-resolution technologies, it is essentially an ill-posed problem and cannot recover high-frequency details in renderings. To address this problem, we exploit high-resolution auxiliary features to guide super-resolution of low-resolution renderings. These high-resolution auxiliary features can be quickly rendered by a rendering engine and at the same time provide valuable high-frequency details to assist super-resolution. To this end, we develop a cross-modality transformer network that consists of an auxiliary feature branch and a low-resolution …

Formalizing Stack Safety As A Security Property, Sean Noble Anderson, Roberto Blanco, Leonidas Lampropoulos, Benjamin C. Pierce, Andrew Tolmach

Computer Science Faculty Publications and Presentations

The term stack safety is used to describe a variety of compiler, runtime, and hardware mechanisms for protecting stack memory. Unlike “the heap,” the ISA-level stack does not correspond to a single high-level language concept: different compilers use it in different ways to support procedural and functional abstraction mechanisms from a wide range of languages. This protean nature makes it difficult to nail down what it means to correctly enforce stack safety.

Lossy Kernelization Of Same-Size Clustering, Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach, Nidhi Purohit, Kirill Simonov

Computer Science Faculty Publications and Presentations

In this work, we study the k-median clustering problem with an additional equal-size constraint on the clusters from the perspective of parameterized preprocessing. Our main result is the first lossy (2-approximate) polynomial kernel for this problem parameterized by the cost of clustering. We complement this result by establishing lower bounds for the problem that eliminate the existence of an (exact) kernel of polynomial size and a PTAS.

Classification Of Drainage Crossings On High-Resolution Digital Elevation Models: A Deep Learning Approach, Di Wu, Ruopu Li, Banafsheh Rekabdar, Claire Talbert, Michael Edidem, Guangxing Wang

Computer Science Faculty Publications and Presentations

High-Resolution Digital Elevation Models (HRDEMs) have been used to delineate fine-scale hydrographic features in landscapes with relatively level topography. However, artificial flow barriers associated with roads are known to cause incorrect modeled flowlines, because these barriers substantially increase the terrain elevation and often terminate flowlines. A common practice is to breach the elevation of roads near drainage crossing locations, which, however, are often unavailable. Thus, developing a reliable drainage crossing dataset is essential to improve the HRDEMs for hydrographic delineation. The purpose of this research is to develop deep learning models for classifying the images that contain the locations of …

Quantum Multi-Solution Bernoulli Search With Applications To Bitcoin’S Post-Quantum Security, Alexandru Cojocaru, Juan Garay, Fang Song, Petros Wallden

Computer Science Faculty Publications and Presentations

A proof of work (PoW) is an important cryptographic construct which enables a party to convince other parties that they have invested some effort in solving a computational task. Arguably, its main impact has been in the setting of cryptocurrencies such as Bitcoin and its underlying blockchain protocol, which have received significant attention in recent years due to its potential for various applications as well as for solving fundamental distributed computing questions in novel threat models. PoWs enable the linking of blocks in the blockchain data structure, and thus the problem of interest is the feasibility of obtaining a sequence …

Caspi: Collaborative Photon Processing For Active Single-Photon Imaging, Jongho Lee, Atul Ingle, Jenu V. Chacko, Kevin W. Eliceiri, Mohit Gupta

Computer Science Faculty Publications and Presentations

Image sensors capable of capturing individual photons have made tremendous progress in recent years. However, this technology faces a major limitation. Because they capture scene information at the individual photon level, the raw data is sparse and noisy. Here we propose CASPI: Collaborative Photon Processing for Active Single-Photon Imaging, a technology-agnostic, application-agnostic, and training-free photon processing pipeline for emerging high-resolution single-photon cameras. By collaboratively exploiting both local and non-local correlations in the spatio-temporal photon data cubes, CASPI estimates scene properties reliably even under very challenging lighting conditions. We demonstrate the versatility of CASPI with two applications: LiDAR imaging over a …

An Equivalence Checking Framework For Agile Hardware Design, Yanzhao Wang, Fei Xie, Zhenkun Yang, Pascuale Cocchini, Jin Yang

Computer Science Faculty Publications and Presentations

Agile hardware design enables designers to produce new design iterations efficiently. Equivalence checking is critical in ensuring that a new design iteration conforms to its specification. In this paper, we introduce an equivalence checking framework for hardware designs represented in HalideIR. HalideIR is a popular intermediate representation in software domains such as deep learning and image processing, and it is increasingly utilized in agile hardware design.We have developed a fully automatic equivalence checking workflow seamlessly integrated with HalideIR and several optimizations that leverage the incremental nature of agile hardware design to scale equivalence checking. Evaluations of two deep learning accelerator …

The Role Of Preprocessing For Word Representation Learning In Affective Tasks, Nastaran Babanejad, Heidar Davoudi, Ameeta Agrawal, Manos Papagelis

Computer Science Faculty Publications and Presentations

Affective tasks, including sentiment analysis, emotion classification, and sarcasm detection have drawn a lot of attention in recent years due to a broad range of useful applications in various domains. The main goal of affect detection tasks is to recognize states such as mood, sentiment, and emotions from textual data (e.g., news articles or product reviews). Despite the importance of utilizing preprocessing steps in different stages (i.e., word representation learning and building a classification model) of affect detection tasks, this topic has not been studied well. To that end, we explore whether applying various preprocessing methods (stemming, lemmatization, stopword removal, …

An Improved Lower Bound For Sparse Reconstruction From Subsampled Walsh Matrices, Jaroslaw Blasiok, Patrick Lopatto, Kyle Luh, Jake Marcinek, Shravas Rao

Computer Science Faculty Publications and Presentations

We give a short argument that yields a new lower bound on the number of uniformly and independently subsampled rows from a bounded, orthonormal matrix necessary to form a matrix with the restricted isometry property. We show that a matrix formed by uniformly and independently subsampling rows of an N ×N Walsh matrix contains a K-sparse vector in the kernel, unless the number of subsampled rows is Ω(KlogKlog(N/K)) — our lower bound applies whenever min(K,N/K) > logC N. Containing a sparse vector in the kernel precludes not only the restricted isometry property, but more generally the application of those matrices for …

Rdkg: A Reinforcement Learning Framework For Disease Diagnosis On Knowledge Graph, Shipeng Guo, Kunpeng Liu, Pengfei Wang, Weiwei Dai, Yi Du, Yuanchun Zhou, Wenjuan Cui

Computer Science Faculty Publications and Presentations

Automatic disease diagnosis from symptoms has attracted much attention in medical practices. It can assist doctors and medical practitioners in narrowing down disease candidates, reducing testing costs, improving diagnosis efficiency, and more importantly, saving human lives. Existing research has made significant progress in diagnosing disease but was limited by the gap between interpretability and accuracy. To fill this gap, in this paper, we propose a method called Reinforced Disease Diagnosis on Knowlege Graph (RDKG). Specifically, we first construct a knowledge graph containing all information from electronic medical records. To capture informative embeddings, we propose an enhanced knowledge graph embedding method …

Quantum Key-Length Extension, Joseph Jaeger, Fang Song, Stefano Tessaro

Computer Science Faculty Publications and Presentations

Should quantum computers become available, they will reduce the effective key length of basic secret-key primitives, such as blockciphers. To address this we will either need to use blockciphers with inherently longer keys or develop key-length extension techniques to amplify the security of a blockcipher to use longer keys.

We consider the latter approach and revisit the FX and double encryption constructions. Classically, FX was proven to be a secure key-length extension technique, while double encryption fails to be more secure than single encryption due to a meet-in-the-middle attack. In this work we provide positive results, with concrete and tight …

From Machine Learning To Deep Learning: A Comprehensive Study Of Alcohol And Drug Use Disorder, Banafsheh Rekabdar, David L. Albright, Haelim Jeong, Sameerah Talafha

Computer Science Faculty Publications and Presentations

This study aims to train and validate machine learning and deep learning models to identify patients with risky alcohol and drug misuse in a Screening, Brief Intervention, and Referral to Treatment (SBIRT) program. An observational cohort of 6978 adults was admitted in the western region of Alabama at three medical facilities between January and December of 2019. Data were cleaned and pre-processed using data imputation techniques and an augmented sampling data method. The primary analysis involved the multi-class classification of alcohol and drug misuse. Our study shows that accurate identification of alcohol and drug use screening instrument scores was best …

A Simpler Machine Learning Model For Acute Kidney Injury Risk Stratification In Hospitalized Patients, Yirui Hu, Kunpeng Liu, Kevin Ho, David Riviello, Jason Brown, Alex R. Chang, Gurmukteshwar Singh, H. Lester Kirchner

Computer Science Faculty Publications and Presentations

Background: Hospitalization-associated acute kidney injury (AKI), affecting one-in-five inpatients, is associated with increased mortality and major adverse cardiac/kidney endpoints. Early AKI risk stratification may enable closer monitoring and prevention. Given the complexity and resource utilization of existing machine learning models, we aimed to develop a simpler prediction model. Methods: Models were trained and validated to predict risk of AKI using electronic health record (EHR) data available at 24 h of inpatient admission. Input variables included demographics, laboratory values, medications, and comorbidities. Missing values were imputed using multiple imputation by chained equations. Results: 26,410 of 209,300 (12.6%) inpatients developed AKI during …

Motion-Adjustable Neural Implicit Video Representation, Long Mai, Feng Liu

Computer Science Faculty Publications and Presentations

Implicit neural representation (INR) has been successful in representing static images. Contemporary image-based INR, with the use of Fourier-based positional encoding, can be viewed as a mapping from sinusoidal patterns with different frequencies to image content. Inspired by that view, we hypothesize that it is possible to generate temporally varying content with a single image-based INR model by displacing its input sinusoidal patterns over time. By exploiting the relation between the phase information in sinusoidal functions and their displacements, we incorporate into the conventional image-based INR model a phase-varying positional encoding module, and couple it with a phase-shift generation module …

Quantum Algorithms For Attacking Hardness Assumptions In Classical And Post‐Quantum Cryptography, J.-F. Biasse, X. Bonnetain, E. Kirshanova, A. Schrottenloher, Fang Song

Computer Science Faculty Publications and Presentations

In this survey, the authors review the main quantum algorithms for solving the computational problems that serve as hardness assumptions for cryptosystem. To this end, the authors consider both the currently most widely used classically secure cryptosystems, and the most promising candidates for post-quantum secure cryptosystems. The authors provide details on the cost of the quantum algorithms presented in this survey. The authors furthermore discuss ongoing research directions that can impact quantum cryptanalysis in the future.

Snerf: Stylized Neural Implicit Representations For 3d Scenes, Thu Nguyen-Phuoc, Feng Liu, Lei Xiao

Computer Science Faculty Publications and Presentations

This paper presents a stylized novel view synthesis method. Applying state-of-the-art stylization methods to novel views frame by frame often causes jittering artifacts due to the lack of cross-view consistency. Therefore, this paper investigates 3D scene stylization that provides a strong inductive bias for consistent novel view synthesis. Specifically, we adopt the emerging neural radiance fields (NeRF) as our choice of 3D scene representation for their capability to render high-quality novel views for a variety of scenes. However, as rendering a novel view from a NeRF requires a large number of samples, training a stylized NeRF requires a large amount …

Extending Tensor Virtual Machine To Support Deep-Learning Accelerators With Convolution Cores, Yanzhao Wang, Fei Xie

Computer Science Faculty Publications and Presentations

Deep-learning accelerators are increasingly popular. There are two prevalent accelerator architectures: one based on general matrix multiplication units and the other on convolution cores. However, Tensor Virtual Machine (TVM), a widely used deep-learning compiler stack, does not support the latter. This paper proposes a general framework for extending TVM to support deep-learning accelerators with convolution cores. We have applied it to two well-known accelerators: Nvidia's NVDLA and Bitmain's BM1880 successfully. Deep-learning workloads can now be readily deployed to these accelerators through TVM and executed efficiently. This framework can extend TVM to other accelerators with minimum effort.

Sl-Cyclegan: Blind Motion Deblurring In Cycles Using Sparse Learning, Ali Syed Saqlain, Li-Yun Wang, Zhiyong Liu

Computer Science Faculty Publications and Presentations

In this paper, we introduce an end-to-end generative adversarial network (GAN) based on sparse learning for single image motion deblurring, which we called SL-CycleGAN. For the first time in image motion deblurring, we propose a sparse ResNet-block as a combination of sparse convolution layers and a trainable spatial pooler k-winner based on HTM (Hierarchical Temporal Memory) to replace non-linearity such as ReLU in the ResNet-block of SL-CycleGAN generators. Furthermore, we take our inspiration from the domain-to-domain translation ability of the CycleGAN, and we show that image deblurring can be cycle-consistent while achieving the best qualitative results. Finally, we perform extensive …

Rate Maximization In A Uav Based Full-Duplex Multi-User Communication Network Using Multi-Objective Optimization, Syed Muhammad Hashir, Sabyasachi Gupta, Gavin Megson, Ehsan Aryafar, Joseph Camp

Computer Science Faculty Publications and Presentations

In this paper, we study an unmanned-aerial-vehicle (UAV) based full-duplex (FD) multi-user communication network, where a UAV is deployed as a multiple-input–multiple-output (MIMO) FD base station (BS) to serve multiple FD users on the ground. We propose a multi-objective optimization framework which considers two desirable objective functions, namely sum uplink (UL) rate maximization and sum downlink (DL) rate maximization while providing quality-of-service to all the users in the communication network. A novel resource allocation multi-objective-optimization-problem (MOOP) is designed which optimizes the downlink beamformer, the beamwidth angle, and the 3D position of the UAV, and also the UL power of the …

Workflow Critical Path: A Data-Oriented Critical Path Metric For Holistic Hpc Workflows, Daniel D. Nguyen, Karen L. Karavanic

Computer Science Faculty Publications and Presentations

Current trends in HPC, such as the push to exascale, convergence with Big Data, and growing complexity of HPC applications, have created gaps that traditional performance tools do not cover. One example is Holistic HPC Workflows — HPC workflows comprising multiple codes, paradigms, or platforms that are not developed using a workflow management system. To diagnose the performance of these applications, we define a new metric called Workflow Critical Path (WCP), a data-oriented metric for Holistic HPC Workflows. WCP constructs graphs that span across the workflow codes and platforms, using data states as vertices and data mutations as edges. …