OpenRaiser/Intern-Atlas huggingface dataset:
On Computational Completeness of Semi-Conditional Matrix Grammars
Venue: arXiv cs.FL 2024
Year: 2024

Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. Originally, they have been introduced by Ábrahám on linguistic grounds. In traditional regulated rewriting, the most interesting case shows up when all rules are context-free. Typical descriptional complexity measures incorporate the number of nonterminals or the matrix length, i.e., the number of rules per matrix. When viewing matrices as program fragments, it becomes natural to consider additional applicability conditions for such matrices. Here, we focus on attaching a permitting and a forbidden string to every matrix in a matrix grammar. The matrix is applicable to a sentential form~$w$ only if the permitting string is a subword in~$w$ and the forbidden string is not a subword in~$w$. We call such a grammar, where the application of a matrix is conditioned as described, a semi-conditional matrix grammar. We consider $(1)$ the maximal lengths of permitting and forbidden strings, $(2)$ the number of nonterminals, $(3)$ the number of conditional matrices, $(4)$ the maximal length of any matrix and $(5)$ the number of conditional matrices with nonempty permitting and forbidden strings, as the resources (descriptional complexity measures) of a semi-conditional matrix grammar. In this paper, we show that certain semi-conditional matrix grammar families defined by restricting resources can generate all of the recursively enumerable languages.
Exploring Facets of Language Generation in the Limit
Venue: arXiv cs.DS 2024
Year: 2024

The recent work of Kleinberg & Mullainathan [KM24] provides a concrete model for language generation in the limit: given a sequence of examples from an unknown target language, the goal is to generate new examples from the target language such that no incorrect examples are generated beyond some point. In sharp contrast to strong negative results for the closely related problem of language identification, they establish positive results for language generation in the limit for all countable collections of languages. Follow-up work by Raman & Tewari [RT24] studies bounds on the number of distinct inputs required by an algorithm before correct language generation is achieved -- namely, whether this is a constant for all languages in the collection (uniform generation) or a language-dependent constant (non-uniform generation). We show that every countable language collection has a generator which has the stronger property of non-uniform generation in the limit. However, while the generation algorithm of [KM24] can be implemented using membership queries, we show that any algorithm cannot non-uniformly generate even for collections of just two languages, using only membership queries. We also formalize the tension between validity and breadth in the generation algorithm of [KM24] by introducing a definition of exhaustive generation, and show a strong negative result for exhaustive generation. Our result shows that a tradeoff between validity and breadth is inherent for generation in the limit. We also provide a precise characterization of the language collections for which exhaustive generation is possible. Finally, inspired by algorithms that can choose to obtain feedback, we consider a model of uniform generation with feedback, completely characterizing language collections for which such uniform generation with feedback is possible in terms of a complexity measure of the collection.
Advances in Algorithmic Meta Theorems
Venue: arXiv cs.LO 2024
Year: 2024

Tractability results for the model checking problem of logics yield powerful algorithmic meta theorems of the form: Every computational problem expressible in a logic $L$ can be solved efficiently on every class $\mathscr{C}$ of structures satisfying certain conditions. The most prominent logics studied in the field are (counting) monadic second-order logic (C)MSO, and first-order logic FO and its extensions. The complexity of CMSO model checking in general and of FO model checking on monotone graph classes is very well understood. In recent years there has been a rapid and exciting development of new algorithmic meta theorems. On the one hand there has been major progress for FO model checking on hereditary graph classes. This progress was driven by the development of a combinatorial structure theory for the logically defined monadically stable and monadically dependent graph classes, as well as by the advent of the new width measure twinwidth. On the other hand, new algorithmic meta theorems for new logics with expressive power between FO and CMSO offer a new unifying view on methods like the irrelevant vertex technique and recursive understanding. In this paper we overview the recent advances in algorithmic meta theorems and provide rough sketches for the methods to prove them.
Exploiting Watermark-Based Defense Mechanisms in Text-to-Image Diffusion Models for Unauthorized Data Usage
Venue: arXiv cs.CV 2024
Year: 2024

Text-to-image diffusion models, such as Stable Diffusion, have shown exceptional potential in generating high-quality images. However, recent studies highlight concerns over the use of unauthorized data in training these models, which may lead to intellectual property infringement or privacy violations. A promising approach to mitigate these issues is to apply a watermark to images and subsequently check if generative models reproduce similar watermark features. In this paper, we examine the robustness of various watermark-based protection methods applied to text-to-image models. We observe that common image transformations are ineffective at removing the watermark effect. Therefore, we propose RATTAN, that leverages the diffusion process to conduct controlled image generation on the protected input, preserving the high-level features of the input while ignoring the low-level details utilized by watermarks. A small number of generated images are then used to fine-tune protected models. Our experiments on three datasets and 140 text-to-image diffusion models reveal that existing state-of-the-art protections are not robust against RATTAN.
Less is More: Optimizing Function Calling for LLM Execution on Edge Devices
Venue: arXiv cs.PF 2024
Year: 2024

The advanced function-calling capabilities of foundation models open up new possibilities for deploying agents to perform complex API tasks. However, managing large amounts of data and interacting with numerous APIs makes function calling hardware-intensive and costly, especially on edge devices. Current Large Language Models (LLMs) struggle with function calling at the edge because they cannot handle complex inputs or manage multiple tools effectively. This results in low task-completion accuracy, increased delays, and higher power consumption. In this work, we introduce Less-is-More, a novel fine-tuning-free function-calling scheme for dynamic tool selection. Our approach is based on the key insight that selectively reducing the number of tools available to LLMs significantly improves their function-calling performance, execution time, and power efficiency on edge devices. Experimental results with state-of-the-art LLMs on edge hardware show agentic success rate improvements, with execution time reduced by up to 70% and power consumption by up to 40%.
FG-CXR: A Radiologist-Aligned Gaze Dataset for Enhancing Interpretability in Chest X-Ray Report Generation
Venue: arXiv cs.CV 2024
Year: 2024

Developing an interpretable system for generating reports in chest X-ray (CXR) analysis is becoming increasingly crucial in Computer-aided Diagnosis (CAD) systems, enabling radiologists to comprehend the decisions made by these systems. Despite the growth of diverse datasets and methods focusing on report generation, there remains a notable gap in how closely these models' generated reports align with the interpretations of real radiologists. In this study, we tackle this challenge by initially introducing Fine-Grained CXR (FG-CXR) dataset, which provides fine-grained paired information between the captions generated by radiologists and the corresponding gaze attention heatmaps for each anatomy. Unlike existing datasets that include a raw sequence of gaze alongside a report, with significant misalignment between gaze location and report content, our FG-CXR dataset offers a more grained alignment between gaze attention and diagnosis transcript. Furthermore, our analysis reveals that simply applying black-box image captioning methods to generate reports cannot adequately explain which information in CXR is utilized and how long needs to attend to accurately generate reports. Consequently, we propose a novel explainable radiologist's attention generator network (Gen-XAI) that mimics the diagnosis process of radiologists, explicitly constraining its output to closely align with both radiologist's gaze attention and transcript. Finally, we perform extensive experiments to illustrate the effectiveness of our method. Our datasets and checkpoint is available at https://github.com/UARK-AICV/FG-CXR.
Semi-supervised Single-view 3D Reconstruction via Multi Shape Prior Fusion Strategy and Self-Attention
Venue: arXiv cs.CV 2024
Year: 2024

In the domain of single-view 3D reconstruction, traditional techniques have frequently relied on expensive and time-intensive 3D annotation data. Facing the challenge of annotation acquisition, semi-supervised learning strategies offer an innovative approach to reduce the dependence on labeled data. Despite these developments, the utilization of this learning paradigm in 3D reconstruction tasks remains relatively constrained. In this research, we created an innovative semi-supervised framework for 3D reconstruction that distinctively uniquely introduces a multi shape prior fusion strategy, intending to guide the creation of more realistic object structures. Additionally, to improve the quality of shape generation, we integrated a self-attention module into the traditional decoder. In benchmark tests on the ShapeNet dataset, our method substantially outperformed existing supervised learning methods at diverse labeled ratios of 1\%, 10\%, and 20\%. Moreover, it showcased excellent performance on the real-world Pix3D dataset. Through comprehensive experiments on ShapeNet, our framework demonstrated a 3.3\% performance improvement over the baseline. Moreover, stringent ablation studies further confirmed the notable effectiveness of our approach. Our code has been released on https://github.com/NWUzhouwei/SSMP
HPCAdvisor: A Tool for Assisting Users in Selecting HPC Resources in the Cloud
Venue: arXiv cs.DC 2024
Year: 2024

Cloud platforms are increasingly being used to run HPC workloads. Major cloud providers offer a wide variety of virtual machine (VM) types, enabling users to find the optimal balance between performance and cost. However, this extensive selection of VM types can also present challenges, as users must decide not only which VM types to use but also how many nodes are required for a given workload. Although benchmarking data is available for well-known applications from major cloud providers, the choice of resources is also influenced by the specifics of the user's application input. This paper presents the vision and current implementation of HPCAdvisor, a tool designed to assist users in defining their HPC clusters in the cloud. It considers the application's input and utilizes a major cloud provider as a use case for its back-end component.
Energy-efficient Federated Learning with Dynamic Model Size Allocation
Venue: arXiv cs.DC 2024
Year: 2024

Federated Learning (FL) presents a paradigm shift towards distributed model training across isolated data repositories or edge devices without explicit data sharing. Despite of its advantages, FL is inherently less efficient than centralized training models, leading to increased energy consumption and, consequently, higher carbon emissions. In this paper, we propose CAMA, a carbon-aware FL framework, promoting the operation on renewable excess energy and spare computing capacity, aiming to minimize operational carbon emissions. CAMA introduces a dynamic model adaptation strategy which adapts the model sizes based on the availability of energy and computing resources. Ordered dropout is integratged to enable the aggregation with varying model sizes. Empirical evaluations on real-world energy and load traces demonstrate that our method achieves faster convergence and ensures equitable client participation, while scaling efficiently to handle large numbers of clients. The source code of CAMA is available at https://github.com/denoslab/CAMA.
A Flexible Infrastructure-Sharing 5G Network Architecture Based on Network Slicing and Roaming
Venue: arXiv cs.NI 2024
Year: 2024

The sharing of mobile network infrastructure has become a key topic with the introduction of 5G due to the high costs of deploying such infrastructures, with neutral host models coupled with features such as network function virtualization (NFV) and network slicing emerging as viable solutions for the challenges in this area. With this in mind, this work presents the design, implementation, and test of a flexible infrastructure-sharing 5G network architecture capable of providing services to any type of client, whether an operator or not. The proposed architecture leverages 5G's network slicing for traffic isolation and compliance with the policies of different clients, with roaming employed for the authentication of users of operator clients. The proposed architecture was implemented and tested in a simulation environment using the UERANSIM and Open5GS open-source tools. Qualitative tests successfully validated the authentication and the traffic isolation features provided by the slices for the two types of clients. Results also demonstrate that the proposed architecture has a positive impact on the performance of the neutral host network infrastructure, achieving 61.8% higher throughput and 96.8% lower packet loss ratio (PLR) in a scenario sharing the infrastructure among four clients and eight users when compared to a single client with all the network resources.
Metamathematics of Resolution Lower Bounds: A TFNP Perspective
Venue: arXiv cs.CC 2024
Year: 2024

This paper studies the *refuter* problems, a family of decision-tree $\mathsf{TFNP}$ problems capturing the metamathematical difficulty of proving proof complexity lower bounds. Suppose $φ$ is a hard tautology that does not admit any length-$s$ proof in some proof system $P$. In the corresponding refuter problem, we are given (query access to) a purported length-$s$ proof $π$ in $P$ that claims to have proved $φ$, and our goal is to find an invalid derivation inside $π$. As suggested by witnessing theorems in bounded arithmetic, the *computational complexity* of these refuter problems is closely tied to the *metamathematics* of the underlying proof complexity lower bounds. We focus on refuter problems corresponding to lower bounds for *resolution*, which is arguably the single most studied system in proof complexity. We introduce a new class $\mathrm{rwPHP}(\mathsf{PLS})$ in decision-tree $\mathsf{TFNP}$, which can be seen as a randomized version of $\mathsf{PLS}$, and argue that this class effectively captures the metamathematics of proving resolution lower bounds. We view these results as a contribution to the *bounded reverse mathematics* of complexity lower bounds: when interpreted in relativized bounded arithmetic, our results show that the theory $\mathsf{T}^1_2(α) + \mathrm{dwPHP}(\mathsf{PV}(α))$ characterizes the "reasoning power" required to prove (the "easiest") resolution lower bounds. An intriguing corollary of our results is that the combinatorial principle, "the pigeonhole principle requires exponential-size resolution proofs", captures the class of $\mathsf{TFNP}$ problems whose totality is provable in $\mathsf{T}^1_2 + \mathrm{dwPHP}(\mathsf{PV})$.
When Image Generation Goes Wrong: A Safety Analysis of Stable Diffusion Models
Venue: arXiv cs.CY 2024
Year: 2024

Text-to-image models are increasingly popular and impactful, yet concerns regarding their safety and fairness remain. This study investigates the ability of ten popular Stable Diffusion models to generate harmful images, including NSFW, violent, and personally sensitive material. We demonstrate that these models respond to harmful prompts by generating inappropriate content, which frequently displays troubling biases, such as the disproportionate portrayal of Black individuals in violent contexts. Our findings demonstrate a complete lack of any refusal behavior or safety measures in the models observed. We emphasize the importance of addressing this issue as image generation technologies continue to become more accessible and incorporated into everyday applications.
An Affordable Experimental Technique for SRAM Write Margin Characterization for Nanometer CMOS Technologies
Venue: arXiv cs.AR 2024
Year: 2024

Increased process variability and reliability issues present a major challenge for future SRAM trends. Non-intrusive and accurate SRAM stability measurement is crucial for estimating yield in large SRAM arrays. Conventional SRAM variability metrics require including test structures that cannot be used to investigate cell bit fails in functional SRAM arrays. This work proposes the Word Line Voltage Margin (WLVM), defined as the maximum allowed word-line voltage drop during write operations, as a metric for the experimental characterization of write stability of SRAM cells. Their experimental measurement can be attained with minimal design modifications, while achieving good correlation with existing writability metrics. To demonstrate its feasibility, the distribution of WLVM values has been measured in an SRAM prototype implemented in 65 nm CMOS technology. The dependence of the metric with the width of the transistors has been also analysed, demonstrating their utility in post-process write stability characterization.
Botfip-LLM: An Enhanced Multimodal Scientific Computing Framework Leveraging Knowledge Distillation from Large Language Models
Venue: arXiv cs.SC 2024
Year: 2024

In recent years, the introduction of AI technologies has brought transformative changes to scientific computing. However, AI models typically focus on single-task and single-modal data processing, limiting their application. To address this, multimodal scientific computing frameworks have become a trend. The Botfip framework aligns function images with symbolic operation trees through multimodal training, extracting deep scientific information. However, Botfip struggles with processing Formula Strings, leading to inadequate understanding in multimodal learning. To enhance Botfip's learning of Formula Strings and expand its applicability to related tasks, we propose the Botfip-LLM framework based on knowledge distillation, incorporating pre-trained large language models for aligning symbolic tree data. Experimental analysis shows that the choice of LLM is crucial, with ChatGLM-2 outperforming others in training and testing. Botfip-LLM not only improves performance, generalization, and extrapolation over the original Botfip model but also significantly enhances applicability to Formula String-related tasks, enabling more diverse task handling.
Hierarchical Cross-Attention Network for Virtual Try-On
Venue: arXiv cs.CV 2024
Year: 2024

In this paper, we present an innovative solution for the challenges of the virtual try-on task: our novel Hierarchical Cross-Attention Network (HCANet). HCANet is crafted with two primary stages: geometric matching and try-on, each playing a crucial role in delivering realistic virtual try-on outcomes. A key feature of HCANet is the incorporation of a novel Hierarchical Cross-Attention (HCA) block into both stages, enabling the effective capture of long-range correlations between individual and clothing modalities. The HCA block enhances the depth and robustness of the network. By adopting a hierarchical approach, it facilitates a nuanced representation of the interaction between the person and clothing, capturing intricate details essential for an authentic virtual try-on experience. Our experiments establish the prowess of HCANet. The results showcase its performance across both quantitative metrics and subjective evaluations of visual realism. HCANet stands out as a state-of-the-art solution, demonstrating its capability to generate virtual try-on results that excel in accuracy and realism. This marks a significant step in advancing virtual try-on technologies.
Single Antenna Tracking and Localization of RIS-enabled Vehicular Users
Venue: arXiv cs.IT 2024
Year: 2024

Reconfigurable Intelligent Surfaces (RISs) are envisioned to be employed in next generation wireless networks to enhance the communication and radio localization services. In this paper, we propose novel localization and tracking algorithms exploiting reflections through RISs at multiple receivers. We utilize a single antenna transmitter (Tx) and multiple single antenna receivers (Rxs) to estimate the position and the velocity of users (e.g. vehicles) equipped with RISs. Then, we design the RIS phase shifts to separate the signals from different users. The proposed algorithms exploit the geometry information of the signal at the RISs to localize and track the users. We also conduct a comprehensive analysis of the Cramer-Rao lower bound (CRLB) of the localization system. Compared to the time of arrival (ToA)-based localization approach, the proposed method reduces the localization error by a factor up to three. Also, the simulation results show the accuracy of the proposed tracking approach.
From MTEB to MTOB: Retrieval-Augmented Classification for Descriptive Grammars
Venue: arXiv cs.CL 2024
Year: 2024

Recent advances in language modeling have demonstrated significant improvements in zero-shot capabilities, including in-context learning, instruction following, and machine translation for extremely under-resourced languages (Tanzer et al., 2024). However, many languages with limited written resources rely primarily on formal descriptions of grammar and vocabulary. In this paper, we introduce a set of benchmarks to evaluate how well models can extract and classify information from the complex descriptions found in linguistic grammars. We present a Retrieval-Augmented Generation (RAG)-based approach that leverages these descriptions for downstream tasks such as machine translation. Our benchmarks encompass linguistic descriptions for 248 languages across 142 language families, focusing on typological features from WALS and Grambank. This set of benchmarks offers the first comprehensive evaluation of language models' in-context ability to accurately interpret and extract linguistic features, providing a critical resource for scaling NLP to low-resource languages. The code and data are publicly available at \url{https://github.com/al-the-eigenvalue/RAG-on-grammars}.
Transparent but Powerful: Explainability, Accuracy, and Generalizability in ADHD Detection from Social Media Data
Venue: arXiv cs.CL 2024
Year: 2024

Attention-deficit/hyperactivity disorder (ADHD) is a prevalent mental health condition affecting both children and adults, yet it remains severely underdiagnosed. Recent advances in artificial intelligence, particularly in Natural Language Processing (NLP) and Machine Learning (ML), offer promising solutions for scalable and non-invasive ADHD screening methods using social media data. This paper presents a comprehensive study on ADHD detection, leveraging both shallow machine learning models and deep learning approaches, including BiLSTM and transformer-based models, to analyze linguistic patterns in ADHD-related social media text. Our results highlight the trade-offs between interpretability and performance across different models, with BiLSTM offering a balance of transparency and accuracy. Additionally, we assess the generalizability of these models using cross-platform data from Reddit and Twitter, uncovering key linguistic features associated with ADHD that could contribute to more effective digital screening tools.