OpenRaiser/Intern-Atlas huggingface dataset:
A Smoothed Analysis of the Space Complexity of Computing a Chaotic Sequence
Venue: arXiv cs.CC 2024
Year: 2024

This work is motivated by a question whether it is possible to calculate a chaotic sequence efficiently, e.g., is it possible to get the $n$-th bit of a bit sequence generated by a chaotic map, such as $β$-expansion, tent map and logistic map in $\mathrm{o}(n)$ time/space? This paper gives an affirmative answer to the question about the space complexity of a tent map. We show that the decision problem of whether a given bit sequence is a valid tent code is solved in $\mathrm{O}(\log^{2} n)$ space in a sense of the smoothed complexity.
Integrating A.I. in Higher Education: Protocol for a Pilot Study with 'SAMCares: An Adaptive Learning Hub'
Venue: arXiv cs.CY 2024
Year: 2024

Learning never ends, and there is no age limit to grow yourself. However, the educational landscape may face challenges in effectively catering to students' inclusion and diverse learning needs. These students should have access to state-of-the-art methods for lecture delivery, online resources, and technology needs. However, with all the diverse learning sources, it becomes harder for students to comprehend a large amount of knowledge in a short period of time. Traditional assistive technologies and learning aids often lack the dynamic adaptability required for individualized education plans. Large Language Models (LLM) have been used in language translation, text summarization, and content generation applications. With rapid growth in AI over the past years, AI-powered chatbots and virtual assistants have been developed. This research aims to bridge this gap by introducing an innovative study buddy we will be calling the 'SAMCares'. The system leverages a Large Language Model (LLM) (in our case, LLaMa-2 70B as the base model) and Retriever-Augmented Generation (RAG) to offer real-time, context-aware, and adaptive educational support. The context of the model will be limited to the knowledge base of Sam Houston State University (SHSU) course notes. The LLM component enables a chat-like environment to interact with it to meet the unique learning requirements of each student. For this, we will build a custom web-based GUI. At the same time, RAG enhances real-time information retrieval and text generation, in turn providing more accurate and context-specific assistance. An option to upload additional study materials in the web GUI is added in case additional knowledge support is required. The system's efficacy will be evaluated through controlled trials and iterative feedback mechanisms.
Dual-Role AoI-based Incentive Mechanism for HD map Crowdsourcing
Venue: arXiv cs.GT 2024
Year: 2024

A high-quality fresh high-definition (HD) map is vital in enhancing transportation efficiency and safety in autonomous driving. Vehicle-based crowdsourcing offers a promising approach for updating HD maps. However, recruiting crowdsourcing vehicles involves making the challenging tradeoff between the HD map freshness and recruitment costs. Existing studies on HD map crowdsourcing often (1) prioritize maximizing spatial coverage and (2) overlook the dual role of crowdsourcing vehicles in HD maps, as vehicles serve both as contributors and customers of HD maps. This motivates us to propose the Dual-Role Age of Information (AoI) based Incentive Mechanism (DRAIM) to address these issues. % Specifically, we propose the trajectory age of information, incorporating the expected AoI of the HD map and the trajectory, to quantify a vehicle's HD map usage utility, which is freshness- and trajectory-dependent. DRAIM aims to achieve the company's tradeoff between freshness and recruitment costs.
Conformal Risk Control for Ordinal Classification
Venue: arXiv cs.LG 2024
Year: 2024

As a natural extension to the standard conformal prediction method, several conformal risk control methods have been recently developed and applied to various learning problems. In this work, we seek to control the conformal risk in expectation for ordinal classification tasks, which have broad applications to many real problems. For this purpose, we firstly formulated the ordinal classification task in the conformal risk control framework, and provided theoretic risk bounds of the risk control method. Then we proposed two types of loss functions specially designed for ordinal classification tasks, and developed corresponding algorithms to determine the prediction set for each case to control their risks at a desired level. We demonstrated the effectiveness of our proposed methods, and analyzed the difference between the two types of risks on three different datasets, including a simulated dataset, the UTKFace dataset and the diabetic retinopathy detection dataset.
On the Potential of Re-configurable Intelligent Surface (RIS)-assisted Physical Layer Authentication (PLA)
Venue: arXiv cs.CR 2024
Year: 2024

Re-configurable Intelligent Surfaces (RIS) technology is increasingly becoming a potential component for next-generation wireless networks, offering enhanced performance in terms of throughput, spectral, and energy efficiency. However, the broadcast nature of RIS-assisted wireless communication makes it vulnerable to malicious attacks at the physical layer. At the same time, physical layer authentication is gaining popularity as a solution to secure wireless networks, thwarting different attacks such as cloning, spoofing, and impersonation by using the random features of the physical layer. In this paper, we investigate RIS-assisted wireless communication systems to unlock the potential of using RIS for physical layer authentication (PLA). In particular, we exploit two distinct features of the physical layer: pathloss and channel impulse response (CIR) for PLA in RIS-assisted wireless communication. We construct hypothesis tests for the estimated features and derive closed-form error expressions. Further, we consider the critical error, i.e., missed detection, as our objective function to minimize by optimizing the phase shift of the RIS pannel. We compare the performance of our proposed mechanisms with PLA schemes using the same features but with no RIS. Furthermore, we thoroughly evaluate our proposed schemes using performance metrics such as the probability of false alarm (PFA), the probability of missed detection (PMD), and the receiver operating characteristic (ROC) curves. The results demonstrate a clear positive impact of RIS on PLA, as it effectively reduces PMD values to zero when determining the optimal phase shift.
CC2Vec: Combining Typed Tokens with Contrastive Learning for Effective Code Clone Detection
Venue: arXiv cs.SE 2024
Year: 2024

With the development of the open source community, the code is often copied, spread, and evolved in multiple software systems, which brings uncertainty and risk to the software system (e.g., bug propagation and copyright infringement). Therefore, it is important to conduct code clone detection to discover similar code pairs. Many approaches have been proposed to detect code clones where token-based tools can scale to big code. However, due to the lack of program details, they cannot handle more complicated code clones, i.e., semantic code clones. In this paper, we introduce CC2Vec, a novel code encoding method designed to swiftly identify simple code clones while also enhancing the capability for semantic code clone detection. To retain the program details between tokens, CC2Vec divides them into different categories (i.e., typed tokens) according to the syntactic types and then applies two self-attention mechanism layers to encode them. To resist changes in the code structure of semantic code clones, CC2Vec performs contrastive learning to reduce the differences introduced by different code implementations. We evaluate CC2Vec on two widely used datasets (i.e., BigCloneBench and Google Code Jam) and the results report that our method can effectively detect simple code clones. In addition, CC2Vec not only attains comparable performance to widely used semantic code clone detection systems such as ASTNN, SCDetector, and FCCA by simply fine-tuning, but also significantly surpasses these methods in both detection efficiency.
Clique-free t-matchings in degree-bounded graphs
Venue: arXiv cs.DS 2024
Year: 2024

We consider problems of finding a maximum size/weight $t$-matching without forbidden subgraphs in an undirected graph $G$ with the maximum degree bounded by $t+1$, where $t$ is an integer greater than $2$. Depending on the variant forbidden subgraphs denote certain subsets of $t$-regular complete partite subgraphs of $G$. A graph is complete partite if there exists a partition of its vertex set such that every pair of vertices from different sets is connected by an edge and vertices from the same set form an independent set. A clique $K_t$ and a bipartite clique $K_{t,t}$ are examples of complete partite graphs. These problems are natural generalizations of the triangle-free and square-free $2$-matching problems in subcubic graphs. In the weighted setting we assume that the weights of edges of $G$ are vertex-induced on every forbidden subgraph. We present simple and fast combinatorial algorithms for these problems. The presented algorithms are the first ones for the weighted versions, and for the unweighted ones, are faster than those known previously. Our approach relies on the use of gadgets with so-called half-edges. A half-edge of edge $e$ is, informally speaking, a half of $e$ containing exactly one of its endpoints.
Porting HPC Applications to AMD Instinct$^\text{TM}$ MI300A Using Unified Memory and OpenMP
Venue: arXiv cs.DC 2024
Year: 2024

AMD Instinct$^\text{TM}$ MI300A is the world's first data center accelerated processing unit (APU) with memory shared between the AMD "Zen 4" EPYC$^\text{TM}$ cores and third generation CDNA$^\text{TM}$ compute units. A single memory space offers several advantages: i) it eliminates the need for data replication and costly data transfers, ii) it substantially simplifies application development and allows an incremental acceleration of applications, iii) is easy to maintain, and iv) its potential can be well realized via the abstractions in the OpenMP 5.2 standard, where the host and the device data environments can be unified in a more performant way. In this article, we provide a blueprint of the APU programming model leveraging unified memory and highlight key distinctions compared to the conventional approach with discrete GPUs. OpenFOAM, an open-source C++ library for computational fluid dynamics, is presented as a case study to emphasize the flexibility and ease of offloading a full-scale production-ready application on MI300 APUs using directive-based OpenMP programming.
Modeling Linear and Non-linear Layers: An MILP Approach Towards Finding Differential and Impossible Differential Propagations
Venue: arXiv cs.CR 2024
Year: 2024

Symmetric key cryptography stands as a fundamental cornerstone in ensuring security within contemporary electronic communication frameworks. The cryptanalysis of classical symmetric key ciphers involves traditional methods and techniques aimed at breaking or analyzing these cryptographic systems. In the evaluation of new ciphers, the resistance against linear and differential cryptanalysis is commonly a key design criterion. The wide trail design technique for block ciphers facilitates the demonstration of security against linear and differential cryptanalysis. Assessing the scheme's security against differential attacks often involves determining the minimum number of active SBoxes for all rounds of a cipher. The propagation characteristics of a cryptographic component, such as an SBox, can be expressed using Boolean functions. Mixed Integer Linear Programming (MILP) proves to be a valuable technique for solving Boolean functions. We formulate a set of inequalities to model a Boolean function, which is subsequently solved by an MILP solver. To efficiently model a Boolean function and select a minimal set of inequalities, two key challenges must be addressed. We propose algorithms to address the second challenge, aiming to find more optimized linear and non-linear components. Our approaches are applied to modeling SBoxes (up to six bits) and EXOR operations with any number of inputs. Additionally, we introduce an MILP-based automatic tool for exploring differential and impossible differential propagations within a cipher. The tool is successfully applied to five lightweight block ciphers: Lilliput, GIFT64, SKINNY64, Klein, and MIBS.
Robust Semi-supervised Learning via $f$-Divergence and $α$-Rényi Divergence
Venue: arXiv cs.LG 2024
Year: 2024

This paper investigates a range of empirical risk functions and regularization methods suitable for self-training methods in semi-supervised learning. These approaches draw inspiration from various divergence measures, such as $f$-divergences and $α$-Rényi divergences. Inspired by the theoretical foundations rooted in divergences, i.e., $f$-divergences and $α$-Rényi divergence, we also provide valuable insights to enhance the understanding of our empirical risk functions and regularization techniques. In the pseudo-labeling and entropy minimization techniques as self-training methods for effective semi-supervised learning, the self-training process has some inherent mismatch between the true label and pseudo-label (noisy pseudo-labels) and some of our empirical risk functions are robust, concerning noisy pseudo-labels. Under some conditions, our empirical risk functions demonstrate better performance when compared to traditional self-training methods.
U.S. Election Hardens Hate Universe
Venue: arXiv cs.SI 2024
Year: 2024

Local or national politics can trigger potentially dangerous hate in someone. But with a third of the world's population eligible to vote in elections in 2024 alone, we lack understanding of how individual-level hate multiplies up to hate behavior at the collective global scale. Here we show, based on the most recent U.S. election, that offline events are associated with a rapid adaptation of the global online hate universe that hardens (strengthens) both its network-of-networks structure and the 'flavors' of hate content that it collectively produces. Approximately 50 million potential voters in hate communities are drawn closer to each other and to the broad mainstream of approximately 2 billion others. It triggers new hate content at scale around immigration, ethnicity, and antisemitism that aligns with conspiracy theories about Jewish-led replacement before blending in hate around gender identity/sexual orientation, and religion. Telegram acts as a key hardening agent - yet is overlooked by U.S. Congressional hearings and new E.U. legislation. Because the hate universe has remained robust since 2020, anti-hate messaging surrounding not only upcoming elections but also other events like the war in Gaza, should pivot to blending multiple hate 'flavors' while targeting previously untouched social media structures.
BiomedRAG: A Retrieval Augmented Large Language Model for Biomedicine
Venue: arXiv cs.CL 2024
Year: 2024

Large Language Models (LLMs) have swiftly emerged as vital resources for different applications in the biomedical and healthcare domains; however, these models encounter issues such as generating inaccurate information or hallucinations. Retrieval-augmented generation provided a solution for these models to update knowledge and enhance their performance. In contrast to previous retrieval-augmented LMs, which utilize specialized cross-attention mechanisms to help LLM encode retrieved text, BiomedRAG adopts a simpler approach by directly inputting the retrieved chunk-based documents into the LLM. This straightforward design is easily applicable to existing retrieval and language models, effectively bypassing noise information in retrieved documents, particularly in noise-intensive tasks. Moreover, we demonstrate the potential for utilizing the LLM to supervise the retrieval model in the biomedical domain, enabling it to retrieve the document that assists the LM in improving its predictions. Our experiments reveal that with the tuned scorer,\textsc{ BiomedRAG} attains superior performance across 5 biomedical NLP tasks, encompassing information extraction (triple extraction, relation extraction), text classification, link prediction, and question-answering, leveraging over 9 datasets. For instance, in the triple extraction task, \textsc{BiomedRAG} outperforms other triple extraction systems with micro-F1 scores of 81.42 and 88.83 on GIT and ChemProt corpora, respectively.
Exploiting Positional Bias for Query-Agnostic Generative Content in Search
Venue: arXiv cs.IR 2024
Year: 2024

In recent years, neural ranking models (NRMs) have been shown to substantially outperform their lexical counterparts in text retrieval. In traditional search pipelines, a combination of features leads to well-defined behaviour. However, as neural approaches become increasingly prevalent as the final scoring component of engines or as standalone systems, their robustness to malicious text and, more generally, semantic perturbation needs to be better understood. We posit that the transformer attention mechanism can induce exploitable defects through positional bias in search models, leading to an attack that could generalise beyond a single query or topic. We demonstrate such defects by showing that non-relevant text--such as promotional content--can be easily injected into a document without adversely affecting its position in search results. Unlike previous gradient-based attacks, we demonstrate these biases in a query-agnostic fashion. In doing so, without the knowledge of topicality, we can still reduce the negative effects of non-relevant content injection by controlling injection position. Our experiments are conducted with simulated on-topic promotional text automatically generated by prompting LLMs with topical context from target documents. We find that contextualisation of a non-relevant text further reduces negative effects whilst likely circumventing existing content filtering mechanisms. In contrast, lexical models are found to be more resilient to such content injection attacks. We then investigate a simple yet effective compensation for the weaknesses of the NRMs in search, validating our hypotheses regarding transformer bias.
On Convergence of Discrete Schemes for Computing the Rate-Distortion Function of Continuous Source
Venue: arXiv cs.IT 2024
Year: 2024

Computing the rate-distortion function for continuous sources is commonly regarded as a standard continuous optimization problem. When numerically addressing this problem, a typical approach involves discretizing the source space and subsequently solving the associated discrete problem. However, existing literature has predominantly concentrated on the convergence analysis of solving discrete problems, usually neglecting the convergence relationship between the original continuous optimization and its associated discrete counterpart. This neglect is not rigorous, since the solution of a discrete problem does not necessarily imply convergence to the solution of the original continuous problem, especially for non-linear problems. To address this gap, our study employs rigorous mathematical analysis, which constructs a series of finite-dimensional spaces approximating the infinite-dimensional space of the probability measure, establishing that solutions from discrete schemes converge to those from the continuous problems.
Better Bounded Bisimulation Contractions (Preprint)
Venue: arXiv cs.LO 2024
Year: 2024

Bisimulations are standard in modal logic and, more generally, in the theory of state-transition systems. The quotient structure of a Kripke model with respect to the bisimulation relation is called a bisimulation contraction. The bisimulation contraction is a minimal model bisimilar to the original model, and hence, for (image-)finite models, a minimal model modally equivalent to the original. Similar definitions exist for bounded bisimulations ($k$-bisimulations) and bounded bisimulation contractions. Two finite models are $k$-bisimilar if and only if they are modally equivalent up to modal depth $k$. However, the quotient structure with respect to the $k$-bisimulation relation does not guarantee a minimal model preserving modal equivalence to depth $k$. In this paper, we remedy this asymmetry to standard bisimulations and provide a novel definition of bounded contractions called rooted $k$-contractions. We prove that rooted $k$-contractions preserve $k$-bisimilarity and are minimal with this property. Finally, we show that rooted $k$-contractions can be exponentially more succinct than standard $k$-contractions.
GOLD: Geometry Problem Solver with Natural Language Description
Venue: arXiv cs.AI 2024
Year: 2024

Addressing the challenge of automated geometry math problem-solving in artificial intelligence (AI) involves understanding multi-modal information and mathematics. Current methods struggle with accurately interpreting geometry diagrams, which hinders effective problem-solving. To tackle this issue, we present the Geometry problem sOlver with natural Language Description (GOLD) model. GOLD enhances the extraction of geometric relations by separately processing symbols and geometric primitives within the diagram. Subsequently, it converts the extracted relations into natural language descriptions, efficiently utilizing large language models to solve geometry math problems. Experiments show that the GOLD model outperforms the Geoformer model, the previous best method on the UniGeo dataset, by achieving accuracy improvements of 12.7% and 42.1% in calculation and proving subsets. Additionally, it surpasses the former best model on the PGPS9K and Geometry3K datasets, PGPSNet, by obtaining accuracy enhancements of 1.8% and 3.2%, respectively.
Byzantine-Secure Relying Party for Resilient RPKI
Venue: arXiv cs.CR 2024
Year: 2024

To protect against prefix hijacks, Resource Public Key Infrastructure (RPKI) has been standardized. To enjoy the security guarantees of RPKI validation, networks need to install a new component, the relying party validator, which fetches and validates RPKI objects and provides them to border routers. However, recent work shows that relying parties experience failures when retrieving RPKI objects and are vulnerable to attacks, all of which can disable RPKI validation. Therefore even the few adopters are not necessarily secure. We make the first proposal that significantly improves the resilience and security of RPKI. We develop BRP, a Byzantine-Secure relying party implementation. In BRP the relying party nodes redundantly validate RPKI objects and reach a global consensus through voting. BRP provides an RPKI equivalent of public DNS, removing the need for networks to install, operate, and upgrade their own relying party instances while avoiding the need to trust operators of BRP nodes. We show through simulations and experiments that BRP, as an intermediate RPKI service, results in less load on RPKI publication points and a robust output despite RPKI repository failures, jitter, and attacks. We engineer BRP to be fully backward compatible and readily deployable - it does not require any changes to the border routers and the RPKI repositories. We demonstrate that BRP can protect many networks transparently, with either a decentralized or centralized deployment. BRP can be set up as a network of decentralized volunteer deployments, similarly to NTP and TOR, where different operators participate in the peering process with their node, and provide resilient and secure relying party validation to the Internet. BRP can also be hosted by a single operator as a centralized service, e.g., on one cloud or CDN, and provides RPKI validation benefits even when hosted on a single network.