pwc-archive/papers-with-abstracts huggingface dataset:
Reconstructing semi-directed level-1 networks using few quarnets
Authors: Martin Frohn, Niels Holtgrefe, Leo van Iersel, Mark Jones, Steven Kelk
Date: 2024-09-09 00:00:00

Semi-directed networks are partially directed graphs that model evolution where the directed edges represent reticulate evolutionary events. We present an algorithm that reconstructs binary $n$-leaf semi-directed level-1 networks in $O( n^2)$ time from its quarnets (4-leaf subnetworks). Our method assumes we have direct access to all quarnets, yet uses only an asymptotically optimal number of $O(n \log n)$ quarnets. When the network is assumed to contain no triangles, our method instead relies only on four-cycle quarnets and the splits of the other quarnets. A variant of our algorithm works with quartets rather than quarnets and we show that it reconstructs most of a semi-directed level-1 network from an asymptotically optimal $O(n \log n)$ of the quartets it displays. Additionally, we provide an $O(n^3)$ time algorithm that reconstructs the tree-of-blobs of any binary $n$-leaf semi-directed network with unbounded level from $O(n^3)$ splits of its quarnets.
A Performance Bound for the Greedy Algorithm in a Generalized Class of String Optimization Problems
Authors: Brandon Van Over, Bowen Li, Edwin K. P. Chong, Ali Pezeshki
Date: 2024-09-08 00:00:00

We present a simple performance bound for the greedy scheme in string optimization problems that obtains strong results. Our approach vastly generalizes the group of previously established greedy curvature bounds by Conforti and Cornu\'{e}jols (1984). We consider three constants, $\alpha_G$, $\alpha_G'$, and $\alpha_G''$ introduced by Conforti and Cornu\'{e}jols (1984), that are used in performance bounds of greedy schemes in submodular set optimization. We first generalize both of the $\alpha_G$ and $\alpha_G''$ bounds to string optimization problems in a manner that includes maximizing submodular set functions over matroids as a special case. We then derive a much simpler and computable bound that allows for applications to a far more general class of functions with string domains. We prove that our bound is superior to both the $\alpha_G$ and $\alpha_G''$ bounds and provide a counterexample to show that the $\alpha_G'$ bound is incorrect under the assumptions in Conforti and Cornu\'{e}jols (1984). We conclude with two applications. The first is an application of our result to sensor coverage problems. We demonstrate our performance bound in cases where the objective function is set submodular and string submodular. The second is an application to a social welfare maximization problem with black-box utility functions.
Diffusion Map Autoencoder
Authors: Julio Candanedo
Date: 2024-09-05 00:00:00

In this work, we explore various modifications to diffusion maps (DMAP), including their incorporation into a layered sequential neural network model trained with gradient descent. The result is a sequential neural network that inherits the interpretability of diffusion maps.
Gradient-Free Method for Heavily Constrained Nonconvex Optimization
Authors: Wanli Shi, Hongchang Gao, Bin Gu
Date: 2024-08-31 00:00:00

Zeroth-order (ZO) method has been shown to be a powerful method for solving the optimization problem where explicit expression of the gradients is difficult or infeasible to obtain. Recently, due to the practical value of the constrained problems, a lot of ZO Frank-Wolfe or projected ZO methods have been proposed. However, in many applications, we may have a very large number of nonconvex white/black-box constraints, which makes the existing zeroth-order methods extremely inefficient (or even not working) since they need to inquire function value of all the constraints and project the solution to the complicated feasible set. In this paper, to solve the nonconvex problem with a large number of white/black-box constraints, we proposed a doubly stochastic zeroth-order gradient method (DSZOG) with momentum method and adaptive step size. Theoretically, we prove DSZOG can converge to the $\epsilon$-stationary point of the constrained problem. Experimental results in two applications demonstrate the superiority of our method in terms of training time and accuracy compared with other ZO methods for the constrained problem.
Five Key Enablers for Communication during and after Disasters
Authors: Mohammad Shehab, Mustafa Kishk, Maurilio Matracia, Mehdi Bennis, Mohamed-Slim Alouini
Date: 2024-09-10 00:00:00

Civilian communication during disasters such as earthquakes, floods, and military conflicts is crucial for saving lives. Nevertheless, several challenges exist during these circumstances such as the destruction of cellular communication and electricity infrastructure, lack of line of sight (LoS), and difficulty of localization under the rubble. In this article, we discuss key enablers that can boost communication during disasters, namely, satellite and aerial platforms, redundancy, silencing, and sustainable networks aided with wireless energy transfer (WET). The article also highlights how these solutions can be implemented in order to solve the failure of communication during disasters. Finally, it sheds light on unresolved challenges, as well as future research directions.
Integration of Beyond Diagonal RIS and UAVs in 6G NTNs: Enhancing Aerial Connectivity
Authors: Wali Ullah Khan, Eva Lagunas, Asad Mahmood, Muhammad Asif, Manzoor Ahmed, Symeon Chatzinotas
Date: 2024-09-09 00:00:00

The reconfigurable intelligent surface (RIS) technology shows great potential in sixth-generation (6G) terrestrial and non-terrestrial networks (NTNs) since it can effectively change wireless settings to improve connectivity. Extensive research has been conducted on traditional RIS systems with diagonal phase response matrices. The straightforward RIS architecture, while cost-effective, has restricted capabilities in manipulating the wireless channels. The beyond diagonal reconfigurable intelligent surface (BD-RIS) greatly improves control over the wireless environment by utilizing interconnected phase response elements. This work proposes the integration of unmanned aerial vehicle (UAV) communications and BD-RIS in 6G NTNs, which has the potential to further enhance wireless coverage and spectral efficiency. We begin with the preliminaries of UAV communications and then discuss the fundamentals of BD-RIS technology. Subsequently, we discuss the potential of BD-RIS and UAV communications integration. We then proposed a case study based on UAV-mounted transmissive BD-RIS communication. Finally, we highlight future research directions and conclude this work.
Memristors based Computation and Synthesis
Authors: Prashant Gupta, Priscilla Jennifer
Date: 2024-09-05 00:00:00

Memristor has been identified as the fourth fundamental circuit element by Dr. Leon Chua in 1971 and since then it has gathered a lot of interest because of its non-volatility and are considered as a viable solution to the beyond CMOS era computation. Recently, memristor have been used to perform basic logic operations like AND, OR, NAND, NOR, XOR etc. and are also used in applications like Dot Product Engine, Convolution Neural Networks etc. This paper presents a new behavioural model of memristor then using it to build a 32-bit ripple carry adder. The paper later compares the area, power and time delay of the 32 bit Ripple Carry Adder using memristor with the 45nm CMOS technology and highlights its advantages and pitfalls.
Self-Adaptive Quantum Kernel Principal Components Analysis for Compact Readout of Chemiresistive Sensor Arrays
Authors: Zeheng Wang, Timothy van der Laan, Muhammad Usman
Date: 2024-08-28 00:00:00
Tasks: Data Compression, Dimensionality Reduction

The rapid growth of Internet of Things (IoT) devices necessitates efficient data compression techniques to handle the vast amounts of data generated by these devices. Chemiresistive sensor arrays (CSAs), a simple-to-fabricate but crucial component in IoT systems, generate large volumes of data due to their simultaneous multi-sensor operations. Classical principal component analysis (cPCA) methods, a common solution to the data compression challenge, face limitations in preserving critical information during dimensionality reduction. In this study, we present self-adaptive quantum kernel (SAQK) PCA as a superior alternative to enhance information retention. Our findings demonstrate that SAQK PCA outperforms cPCA in various back-end machine-learning tasks, especially in low-dimensional scenarios where access to quantum bits is limited. These results highlight the potential of noisy intermediate-scale quantum (NISQ) computers to revolutionize data processing in real-world IoT applications by improving the efficiency and reliability of CSA data compression and readout, despite the current constraints on qubit availability.
Toward Large Language Models as a Therapeutic Tool: Comparing Prompting Techniques to Improve GPT-Delivered Problem-Solving Therapy
Authors: Daniil Filienko, Yinzhou Wang, Caroline El Jazmi, Serena Xie, Trevor Cohen, Martine De Cock, Weichao Yuwen
Date: 2024-08-27 00:00:00
Tasks: Prompt Engineering

While Large Language Models (LLMs) are being quickly adapted to many domains, including healthcare, their strengths and pitfalls remain under-explored. In our study, we examine the effects of prompt engineering to guide Large Language Models (LLMs) in delivering parts of a Problem-Solving Therapy (PST) session via text, particularly during the symptom identification and assessment phase for personalized goal setting. We present evaluation results of the models' performances by automatic metrics and experienced medical professionals. We demonstrate that the models' capability to deliver protocolized therapy can be improved with the proper use of prompt engineering methods, albeit with limitations. To our knowledge, this study is among the first to assess the effects of various prompting techniques in enhancing a generalist model's ability to deliver psychotherapy, focusing on overall quality, consistency, and empathy. Exploring LLMs' potential in delivering psychotherapy holds promise with the current shortage of mental health professionals amid significant needs, enhancing the potential utility of AI-based and AI-enhanced care services.
Neural CRNs: A Natural Implementation of Learning in Chemical Reaction Networks
Authors: Rajiv Teja Nagipogu, John H. Reif
Date: 2024-08-18 00:00:00
Tasks: Multi-class Classification

We present Neural CRNs, an efficient, autonomous, and general-purpose implementation of learning within mass action chemical reaction systems. Unlike prior works, which transliterate discrete neural networks into chemical systems, Neural CRNs are a purely analog chemical system, which encodes neural computations in the concentration dynamics of its chemical species. Consequently, the chemical reactions in this system stay true to their nature, behaving as atomic end-to-end computational units, resulting in concise and efficient reaction network implementations. We demonstrate this efficiency by assembling a highly streamlined supervised learning procedure that requires only two clock phases. We further validate the robustness of our framework by constructing Neural CRN circuits for several linear and nonlinear regression and classification tasks. Furthermore, a minimal linear regression circuit is assembled using only 13 reactions and 15 species. Our nonlinear modeling circuits significantly advance the state-of-the-art through compact and simple implementations. The synergistic nature of our framework with the analog chemical computing hardware leaves ample room for optimizations and approximations in the computational model, several of which are discussed in this work. Our work introduces a novel paradigm for chemical computing and learning, providing a foundational platform for future adaptive biochemical circuits with applications in fields such as synthetic biology, bioengineering, and adaptive biomedicine.
Quantized neural network for complex hologram generation
Authors: Yutaka Endo, Minoru Oikawa, Timothy D. Wilkinson, Tomoyoshi Shimobaba, Tomoyoshi Ito
Date: 2024-08-25 00:00:00
Tasks: Quantization

Computer-generated holography (CGH) is a promising technology for augmented reality displays, such as head-mounted or head-up displays. However, its high computational demand makes it impractical for implementation. Recent efforts to integrate neural networks into CGH have successfully accelerated computing speed, demonstrating the potential to overcome the trade-off between computational cost and image quality. Nevertheless, deploying neural network-based CGH algorithms on computationally limited embedded systems requires more efficient models with lower computational cost, memory footprint, and power consumption. In this study, we developed a lightweight model for complex hologram generation by introducing neural network quantization. Specifically, we built a model based on tensor holography and quantized it from 32-bit floating-point precision (FP32) to 8-bit integer precision (INT8). Our performance evaluation shows that the proposed INT8 model achieves hologram quality comparable to that of the FP32 model while reducing the model size by approximately 70% and increasing the speed fourfold. Additionally, we implemented the INT8 model on a system-on-module to demonstrate its deployability on embedded platforms and high power efficiency.
McGrids: Monte Carlo-Driven Adaptive Grids for Iso-Surface Extraction
Authors: Daxuan Ren, Hezi Shi, Jianmin Zheng, Jianfei Cai
Date: 2024-08-25 00:00:00

Iso-surface extraction from an implicit field is a fundamental process in various applications of computer vision and graphics. When dealing with geometric shapes with complicated geometric details, many existing algorithms suffer from high computational costs and memory usage. This paper proposes McGrids, a novel approach to improve the efficiency of iso-surface extraction. The key idea is to construct adaptive grids for iso-surface extraction rather than using a simple uniform grid as prior art does. Specifically, we formulate the problem of constructing adaptive grids as a probability sampling problem, which is then solved by Monte Carlo process. We demonstrate McGrids' capability with extensive experiments from both analytical SDFs computed from surface meshes and learned implicit fields from real multiview images. The experiment results show that our McGrids can significantly reduce the number of implicit field queries, resulting in significant memory reduction, while producing high-quality meshes with rich geometric details.
Efficient Scene Appearance Aggregation for Level-of-Detail Rendering
Authors: Yang Zhou, Tao Huang, Ravi Ramamoorthi, Pradeep Sen, Ling-Qi Yan
Date: 2024-08-19 00:00:00

Creating an appearance-preserving level-of-detail (LoD) representation for arbitrary 3D scenes is a challenging problem. The appearance of a scene is an intricate combination of both geometry and material models, and is further complicated by correlation due to the spatial configuration of scene elements. We present a novel volumetric representation for the aggregated appearance of complex scenes and an efficient pipeline for LoD generation and rendering. The core of our representation is the Aggregated Bidirectional Scattering Distribution Function (ABSDF) that summarizes the far-field appearance of all surfaces inside a voxel. We propose a closed-form factorization of the ABSDF that accounts for spatially varying and orientation-varying material parameters. We tackle the challenge of capturing the correlation existing locally within a voxel and globally across different parts of the scene. Our method faithfully reproduces appearance and achieves higher quality than existing scene filtering methods while being inherently efficient to render. The memory footprint and rendering cost of our representation are independent of the original scene complexity.
Glyph-Based Uncertainty Visualization and Analysis of Time-Varying Vector Fields
Authors: Timbwaoga A. J. Ouermi, Jixian Li, Zachary Morrow, Bart van Bloemen Waanders, Chris R. Johnson
Date: 2024-08-18 00:00:00
Tasks: Management, Uncertainty Visualization

Uncertainty is inherent to most data, including vector field data, yet it is often omitted in visualizations and representations. Effective uncertainty visualization can enhance the understanding and interpretability of vector field data. For instance, in the context of severe weather events such as hurricanes and wildfires, effective uncertainty visualization can provide crucial insights about fire spread or hurricane behavior and aid in resource management and risk mitigation. Glyphs are commonly used for representing vector uncertainty but are often limited to 2D. In this work, we present a glyph-based technique for accurately representing 3D vector uncertainty and a comprehensive framework for visualization, exploration, and analysis using our new glyphs. We employ hurricane and wildfire examples to demonstrate the efficacy of our glyph design and visualization tool in conveying vector field uncertainty.
Speeding up deferred acceptance
Authors: Gregory Z. Gutin, Daniel Karapetyan, Philip R. Neary, Alexander Vickery, Anders Yeo
Date: 2024-09-10 00:00:00

A run of the deferred acceptance (DA) algorithm may contain proposals that are sure to be rejected. We introduce the accelerated deferred acceptance algorithm that proceeds in a similar manner to DA but with sure-to-be rejected proposals ruled out. Accelerated deferred acceptance outputs the same stable matching as DA but does so more efficiently: it terminates in weakly fewer rounds, requires weakly fewer proposals, and final pairs match no later. Computational experiments show that these efficiency savings can be strict.
On Mechanism Underlying Algorithmic Collusion
Authors: Zhang Xu, Wei Zhao
Date: 2024-09-02 00:00:00

Two issues of algorithmic collusion are addressed in this paper. First, we show that in a general class of symmetric games, including Prisoner's Dilemma, Bertrand competition, and any (nonlinear) mixture of first and second price auction, only (strict) Nash Equilibrium (NE) is stochastically stable. Therefore, the tacit collusion is driven by failure to learn NE due to insufficient learning, instead of learning some strategies to sustain collusive outcomes. Second, we study how algorithms adapt to collusion in real simulations with insufficient learning. Extensive explorations in early stages and discount factors inflates the Q-value, which interrupts the sequential and alternative price undercut and leads to bilateral rebound. The process is iterated, making the price curves like Edgeworth cycles. When both exploration rate and Q-value decrease, algorithms may bilaterally rebound to relatively high common price level by coincidence, and then get stuck. Finally, we accommodate our reasoning to simulation outcomes in the literature, including optimistic initialization, market design and algorithm design.
Satisficing Equilibrium
Authors: Bary S. R. Pradelski, Bassel Tarbush
Date: 2024-09-01 00:00:00
Tasks: All

We propose a solution concept in which each agent $i$ does not necessarily optimize but selects one of their top $k_i$ actions. Our concept accounts for heterogeneous agents' bounded rationality. We show that there exist satisficing equilibria in which all but one agent best-respond and the remaining agent plays at least a second-best action in asymptotically almost all games. Additionally, we define a class of approximate potential games in which satisficing equilibria are guaranteed to exist. Turning to foundations, we characterize satisficing equilibrium via decision theoretic axioms and we show that a simple dynamic converges to satisficing equilibria in almost all large games. Finally, we apply the satisficing lens to two classic games from the literature.
FORS-EMG: A Novel sEMG Dataset for Hand Gesture Recognition Across Multiple Forearm Orientations
Authors: Umme Rumman, Arifa Ferdousi, Bipin Saha, Md. Sazzad Hossain, Md. Johirul Islam, Shamim Ahmad, Mamun Bin Ibne Reaz, Md. Rezaul Islam
Date: 2024-09-03 00:00:00
Tasks: Gesture Recognition, Hand Gesture Recognition, Hand-Gesture Recognition

Surface electromyography (sEMG) signals hold significant potential for gesture recognition and robust prosthetic hand development. However, sEMG signals are affected by various physiological and dynamic factors, including forearm orientation, electrode displacement, and limb position. Most existing sEMG datasets lack these dynamic considerations. This study introduces a novel multichannel sEMG dataset to evaluate commonly used hand gestures across three distinct forearm orientations. The dataset was collected from nineteen able-bodied subjects performing twelve hand gestures in three forearm orientations--supination, rest, and pronation. Eight MFI EMG electrodes were strategically placed at the elbow and mid-forearm to record high-quality EMG signals. Signal quality was validated through Signal-to-Noise Ratio (SNR) and Signal-to-Motion artifact ratio (SMR) metrics. Hand gesture classification performance across forearm orientations was evaluated using machine learning classifiers, including LDA, SVM, and KNN, alongside five feature extraction methods: TDD, TSD, FTDD, AR-RMS, and SNTDF. Furthermore, deep learning models such as 1D CNN, RNN, LSTM, and hybrid architectures were employed for a comprehensive analysis. Notably, the LDA classifier achieved the highest F1 score of 88.58\% with the SNTDF feature set when trained on hand gesture data of resting and tested across gesture data of all orientations. The promising results from extensive analyses underscore the proposed dataset's potential as a benchmark for advancing gesture recognition technologies, clinical sEMG research, and human-computer interaction applications. The dataset is publicly available in MATLAB format. Dataset: \url{https://www.kaggle.com/datasets/ummerummanchaity/fors-emg-a-novel-semg-dataset}
NeuroLM: A Universal Multi-task Foundation Model for Bridging the Gap between Language and EEG Signals
Authors: Wei-Bang Jiang, Yansen Wang, Bao-liang Lu, Dongsheng Li
Date: 2024-08-27 00:00:00
Tasks: EEG, Electroencephalogram (EEG), Multi-Task Learning

Recent advancements for large-scale pre-training with neural signals such as electroencephalogram (EEG) have shown promising results, significantly boosting the development of brain-computer interfaces (BCIs) and healthcare. However, these pre-trained models often require full fine-tuning on each downstream task to achieve substantial improvements, limiting their versatility and usability, and leading to considerable resource wastage. To tackle these challenges, we propose NeuroLM, the first multi-task foundation model that leverages the capabilities of Large Language Models (LLMs) by regarding EEG signals as a foreign language, endowing the model with multi-task learning and inference capabilities. Our approach begins with learning a text-aligned neural tokenizer through vector-quantized temporal-frequency prediction, which encodes EEG signals into discrete neural tokens. These EEG tokens, generated by the frozen vector-quantized (VQ) encoder, are then fed into an LLM that learns causal EEG information via multi-channel autoregression. Consequently, NeuroLM can understand both EEG and language modalities. Finally, multi-task instruction tuning adapts NeuroLM to various downstream tasks. We are the first to demonstrate that, by specific incorporation with LLMs, NeuroLM unifies diverse EEG tasks within a single model through instruction tuning. The largest variant NeuroLM-XL has record-breaking 1.7B parameters for EEG signal processing, and is pre-trained on a large-scale corpus comprising approximately 25,000-hour EEG data. When evaluated on six diverse downstream datasets, NeuroLM showcases the huge potential of this multi-task learning paradigm.