OpenRaiser/Intern-Atlas huggingface dataset:
Automatic question generation for propositional logical equivalences
Venue: arXiv cs.CL 2024
Year: 2024

The increase in academic dishonesty cases among college students has raised concern, particularly due to the shift towards online learning caused by the pandemic. We aim to develop and implement a method capable of generating tailored questions for each student. The use of Automatic Question Generation (AQG) is a possible solution. Previous studies have investigated AQG frameworks in education, which include validity, user-defined difficulty, and personalized problem generation. Our new AQG approach produces logical equivalence problems for Discrete Mathematics, which is a core course for year-one computer science students. This approach utilizes a syntactic grammar and a semantic attribute system through top-down parsing and syntax tree transformations. Our experiments show that the difficulty level of questions generated by our AQG approach is similar to the questions presented to students in the textbook [1]. These results confirm the practicality of our AQG approach for automated question generation in education, with the potential to significantly enhance learning experiences.
Partially Ordered Sets Corresponding to the Partition Problem
Venue: arXiv cs.DM 2024
Year: 2024

The partition problem is a well-known basic NP-complete problem. We mainly consider the optimization version of it in this paper. The problem has been investigated from various perspectives for a long time and can be solved efficiently in practice. Hence, we might say that the only remaining task is to decide whether the problem can be solved in polynomial time in the number $n$ of given integers. We propose two partially ordered sets (posets) and present a novel methodology for solving the partition problem. The first poset is order-isomorphic to a well-known poset whose structures are related to the solutions of the subset sum problem, while the second is a subposet of the first and plays a crucial role in this paper. We first show several properties of the two posets, such as size, height and width (the largest size of a subset consisting of incomparable elements). Both widths are the same and $O(2^n / n^{3/2})$ for $n$ congruent to $0$ or $3$ (mod $4$). This fact indicates the hardness of the partition problem. We then prove that in general all the candidate solutions correspond to the elements of the second poset, whose size is $2^{n} - 2 \binom{n}{\lfloor n/2 \rfloor}$. Since a partition corresponds to two elements of the poset, the number of the candidate partitions is half of it, that is, $2^{n-1} - \binom{n}{\lfloor n/2 \rfloor}$. We finally prove that the candidate solutions can be reduced based on the partial order. In particular, we give several polynomially solvable cases by considering the minimal elements of the second poset. Our approach offers a valuable tool for structural analysis of the partition problem and provides a new perspective on the P versus NP problem.
Data reification in a concurrent rely-guarantee algebra
Venue: arXiv cs.LO 2024
Year: 2024

Specifications of significant systems can be made short and perspicuous by using abstract data types; data reification can provide a clear, stepwise, development history of programs that use more efficient concrete representations. Data reification (or "refinement") techniques for sequential programs are well established. This paper applies these ideas to concurrency, in particular, an algebraic theory supporting rely-guarantee reasoning about concurrency. A concurrent version of the Galler-Fischer equivalence relation data structure is used as an example.
TroLLoc: Logic Locking and Layout Hardening for IC Security Closure against Hardware Trojans
Venue: arXiv cs.CR 2024
Year: 2024

Due to cost benefits, supply chains of integrated circuits (ICs) are largely outsourced nowadays. However, passing ICs through various third-party providers gives rise to many security threats, like piracy of IC intellectual property or insertion of hardware Trojans, i.e., malicious circuit modifications. In this work, we proactively and systematically protect the physical layouts of ICs against post-design insertion of Trojans. Toward that end, we propose TroLLoc, a novel scheme for IC security closure that employs, for the first time, logic locking and layout hardening in unison. TroLLoc is fully integrated into a commercial-grade design flow, and TroLLoc is shown to be effective, efficient, and robust. Our work provides in-depth layout and security analysis considering the challenging benchmarks of the ISPD'22/23 contests for security closure. We show that TroLLoc successfully renders layouts resilient, with reasonable overheads, against (i) general prospects for Trojan insertion as in the ISPD'22 contest, (ii) actual Trojan insertion as in the ISPD'23 contest, and (iii) potential second-order attacks where adversaries would first (i.e., before Trojan insertion) try to bypass the locking defense, e.g., using advanced machine learning attacks. Finally, we release all our artifacts for independent verification [2].
Policy Gradient with Active Importance Sampling
Venue: arXiv cs.LG 2024
Year: 2024

Importance sampling (IS) represents a fundamental technique for a large surge of off-policy reinforcement learning approaches. Policy gradient (PG) methods, in particular, significantly benefit from IS, enabling the effective reuse of previously collected samples, thus increasing sample efficiency. However, classically, IS is employed in RL as a passive tool for re-weighting historical samples. However, the statistical community employs IS as an active tool combined with the use of behavioral distributions that allow the reduction of the estimate variance even below the sample mean one. In this paper, we focus on this second setting by addressing the behavioral policy optimization (BPO) problem. We look for the best behavioral policy from which to collect samples to reduce the policy gradient variance as much as possible. We provide an iterative algorithm that alternates between the cross-entropy estimation of the minimum-variance behavioral policy and the actual policy optimization, leveraging on defensive IS. We theoretically analyze such an algorithm, showing that it enjoys a convergence rate of order $O(ε^{-4})$ to a stationary point, but depending on a more convenient variance term w.r.t. standard PG methods. We then provide a practical version that is numerically validated, showing the advantages in the policy gradient estimation variance and on the learning speed.
Supercomputers as a Continous Medium
Venue: arXiv cs.DC 2024
Year: 2024

As supercomputers' complexity has grown, the traditional boundaries between processor, memory, network, and accelerators have blurred, making a homogeneous computer model, in which the overall computer system is modeled as a continuous medium with homogeneously distributed computational power, memory, and data movement transfer capabilities, an intriguing and powerful abstraction. By applying a homogeneous computer model to algorithms with a given I/O complexity, we recover from first principles, other discrete computer models, such as the roofline model, parallel computing laws, such as Amdahl's and Gustafson's laws, and phenomenological observations, such as super-linear speedup. One of the homogeneous computer model's distinctive advantages is the capability of directly linking the performance limits of an application to the physical properties of a classical computer system. Applying the homogeneous computer model to supercomputers, such as Frontier, Fugaku, and the Nvidia DGX GH200, shows that applications, such as Conjugate Gradient (CG) and Fast Fourier Transforms (FFT), are rapidly approaching the fundamental classical computational limits, where the performance of even denser systems in terms of compute and memory are fundamentally limited by the speed of light.
Experience and Analysis of Scalable High-Fidelity Computational Fluid Dynamics on Modular Supercomputing Architectures
Venue: arXiv cs.DC 2024
Year: 2024

The never-ending computational demand from simulations of turbulence makes computational fluid dynamics (CFD) a prime application use case for current and future exascale systems. High-order finite element methods, such as the spectral element method, have been gaining traction as they offer high performance on both multicore CPUs and modern GPU-based accelerators. In this work, we assess how high-fidelity CFD using the spectral element method can exploit the modular supercomputing architecture at scale through domain partitioning, where the computational domain is split between a Booster module powered by GPUs and a Cluster module with conventional CPU nodes. We investigate several different flow cases and computer systems based on the modular supercomputing architecture (MSA). We observe that for our simulations, the communication overhead and load balancing issues incurred by incorporating different computing architectures are seldom worthwhile, especially when I/O is also considered, but when the simulation at hand requires more than the combined global memory on the GPUs, utilizing additional CPUs to increase the available memory can be fruitful. We support our results with a simple performance model to assess when running across modules might be beneficial. As MSA is becoming more widespread and efforts to increase system utilization are growing more important our results give insight into when and how a monolithic application can utilize and spread out to more than one module and obtain a faster time to solution.
Fractional Payment Transactions: Executing Payment Transactions in Parallel with Less than f+1 Validations
Venue: arXiv cs.DC 2024
Year: 2024

We consider the problem of supporting payment transactions in an asynchronous system in which up to $f$ validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that, in the case of a single owner, this problem can be solved without consensus by using byzantine quorum systems (requiring a quorum of $2f+1$ validations per transaction). Nonetheless, the process of validating transactions remains sequential. For example, if one has a balance of ten coins and intends to make separate payments of two coins each to two distinct recipients, both transactions must undergo processing by a common correct validator. On the other hand, these two transactions are non-conflicting as they do not lead to double spending, allowing in principle for parallel validation. In this paper, we show that it is possible to validate payment transactions in parallel with less than $f$ validations per transaction in an asynchronous system, provided that each transaction spends only a small fraction of a balance. Our solution relies on a novel class of probabilistic quorum systems that we introduce in this paper, termed \textit{$(k_1,k_2)$-quorum systems}. In the absence of an adaptive adversary, \textit{$(k_1,k_2)$-quorum systems} can be used to enable concurrent and asynchronous validation of up to $k_1$ transactions while preventing validation of more than $k_2$ transactions. Employing a $(k_1, k_2)$-quorum system, we introduce protocols enabling a payer to validate multiple \textit{fractional spending} transactions in parallel with less than $f+1$ validations per transaction. Subsequently, the payer reclaims any remaining funds through a fully validated transaction, referred to as a \textit{settlement} transaction.
Guess the Drift with LOP-UKF: LiDAR Odometry and Pacejka Model for Real-Time Racecar Sideslip Estimation
Venue: arXiv cs.RO 2024
Year: 2024

The sideslip angle, crucial for vehicle safety and stability, is determined using both longitudinal and lateral velocities. However, measuring the lateral component often necessitates costly sensors, leading to its common estimation, a topic thoroughly explored in existing literature. This paper introduces LOP-UKF, a novel method for estimating vehicle lateral velocity by integrating Lidar Odometry with the Pacejka tire model predictions, resulting in a robust estimation via an Unscendent Kalman Filter (UKF). This combination represents a distinct alternative to more traditional methodologies, resulting in a reliable solution also in edge cases. We present experimental results obtained using the Dallara AV-21 across diverse circuits and track conditions, demonstrating the effectiveness of our method.
Beyond Prompts: Learning from Human Communication for Enhanced AI Intent Alignment
Venue: arXiv cs.HC 2024
Year: 2024

AI intent alignment, ensuring that AI produces outcomes as intended by users, is a critical challenge in human-AI interaction. The emergence of generative AI, including LLMs, has intensified the significance of this problem, as interactions increasingly involve users specifying desired results for AI systems. In order to support better AI intent alignment, we aim to explore human strategies for intent specification in human-human communication. By studying and comparing human-human and human-LLM communication, we identify key strategies that can be applied to the design of AI systems that are more effective at understanding and aligning with user intent. This study aims to advance toward a human-centered AI system by bringing together human communication strategies for the design of AI systems.
Detecting Statements in Text: A Domain-Agnostic Few-Shot Solution
Venue: arXiv cs.CL 2024
Year: 2024

Many tasks related to Computational Social Science and Web Content Analysis involve classifying pieces of text based on the claims they contain. State-of-the-art approaches usually involve fine-tuning models on large annotated datasets, which are costly to produce. In light of this, we propose and release a qualitative and versatile few-shot learning methodology as a common paradigm for any claim-based textual classification task. This methodology involves defining the classes as arbitrarily sophisticated taxonomies of claims, and using Natural Language Inference models to obtain the textual entailment between these and a corpus of interest. The performance of these models is then boosted by annotating a minimal sample of data points, dynamically sampled using the well-established statistical heuristic of Probabilistic Bisection. We illustrate this methodology in the context of three tasks: climate change contrarianism detection, topic/stance classification and depression-relates symptoms detection. This approach rivals traditional pre-train/fine-tune approaches while drastically reducing the need for data annotation.
LatentColorization: Latent Diffusion-Based Speaker Video Colorization
Venue: arXiv cs.CV 2024
Year: 2024

While current research predominantly focuses on image-based colorization, the domain of video-based colorization remains relatively unexplored. Most existing video colorization techniques operate on a frame-by-frame basis, often overlooking the critical aspect of temporal coherence between successive frames. This approach can result in inconsistencies across frames, leading to undesirable effects like flickering or abrupt color transitions between frames. To address these challenges, we harness the generative capabilities of a fine-tuned latent diffusion model designed specifically for video colorization, introducing a novel solution for achieving temporal consistency in video colorization, as well as demonstrating strong improvements on established image quality metrics compared to other existing methods. Furthermore, we perform a subjective study, where users preferred our approach to the existing state of the art. Our dataset encompasses a combination of conventional datasets and videos from television/movies. In short, by leveraging the power of a fine-tuned latent diffusion-based colorization system with a temporal consistency mechanism, we can improve the performance of automatic video colorization by addressing the challenges of temporal inconsistency. A short demonstration of our results can be seen in some example videos available at https://youtu.be/vDbzsZdFuxM.
A Newton Method for Hausdorff Approximations of the Pareto Front within Multi-objective Evolutionary Algorithms
Venue: arXiv cs.NE 2024
Year: 2024

A common goal in evolutionary multi-objective optimization is to find suitable finite-size approximations of the Pareto front of a given multi-objective optimization problem. While many multi-objective evolutionary algorithms have proven to be very efficient in finding good Pareto front approximations, they may need quite a few resources or may even fail to obtain optimal or nearly approximations. Hereby, optimality is implicitly defined by the chosen performance indicator. In this work, we propose a set-based Newton method for Hausdorff approximations of the Pareto front to be used within multi-objective evolutionary algorithms. To this end, we first generalize the previously proposed Newton step for the performance indicator for the treatment of constrained problems for general reference sets. To approximate the target Pareto front, we propose a particular strategy for generating the reference set that utilizes the data gathered by the evolutionary algorithm during its run. Finally, we show the benefit of the Newton method as a post-processing step on several benchmark test functions and different base evolutionary algorithms.
End-to-End Generative Semantic Communication Powered by Shared Semantic Knowledge Base
Venue: arXiv cs.IT 2024
Year: 2024

Semantic communication has drawn substantial attention as a promising paradigm to achieve effective and intelligent communications. However, efficient image semantic communication encounters challenges with a lower testing compression ratio (CR) compared to the training phase. To tackle this issue, we propose an innovative semantic knowledge base (SKB)-enabled generative semantic communication system for image classification and image generation tasks. Specifically, a lightweight SKB, comprising class-level information, is exploited to guide the semantic communication process, which enables us to transmit only the relevant indices. This approach promotes the completion of the image classification task at the source end and significantly reduces the transmission load. Meanwhile, the category-level knowledge in the SKB facilitates the image generation task by allowing controllable generation, making it possible to generate favorable images in resource-constrained scenarios. Additionally, semantic accuracy is introduced as a new metric to validate the performance of semantic transmission powered by the SKB. Evaluation results indicate that the proposed method outperforms the benchmarks and achieves superior performance with minimal transmission overhead, especially in the low SNR regime.
Efficient Pretraining Model based on Multi-Scale Local Visual Field Feature Reconstruction for PCB CT Image Element Segmentation
Venue: arXiv cs.CV 2024
Year: 2024

Element segmentation is a key step in nondestructive testing of Printed Circuit Boards (PCB) based on Computed Tomography (CT) technology. In recent years, the rapid development of self-supervised pretraining technology can obtain general image features without labeled samples, and then use a small amount of labeled samples to solve downstream tasks, which has a good potential in PCB element segmentation. At present, Masked Image Modeling (MIM) pretraining model has been initially applied in PCB CT image element segmentation. However, due to the small and regular size of PCB elements such as vias, wires, and pads, the global visual field has redundancy for a single element reconstruction, which may damage the performance of the model. Based on this issue, we propose an efficient pretraining model based on multi-scale local visual field feature reconstruction for PCB CT image element segmentation (EMLR-seg). In this model, the teacher-guided MIM pretraining model is introduced into PCB CT image element segmentation for the first time, and a multi-scale local visual field extraction (MVE) module is proposed to reduce redundancy by focusing on local visual fields. At the same time, a simple 4-Transformer-blocks decoder is used. Experiments show that EMLR-seg can achieve 88.6% mIoU on the PCB CT image dataset we proposed, which exceeds 1.2% by the baseline model, and the training time is reduced by 29.6 hours, a reduction of 17.4% under the same experimental condition, which reflects the advantage of EMLR-seg in terms of performance and efficiency.
Large Language Model-Aided Evolutionary Search for Constrained Multiobjective Optimization
Venue: arXiv cs.NE 2024
Year: 2024

Evolutionary algorithms excel in solving complex optimization problems, especially those with multiple objectives. However, their stochastic nature can sometimes hinder rapid convergence to the global optima, particularly in scenarios involving constraints. In this study, we employ a large language model (LLM) to enhance evolutionary search for solving constrained multi-objective optimization problems. Our aim is to speed up the convergence of the evolutionary population. To achieve this, we finetune the LLM through tailored prompt engineering, integrating information concerning both objective values and constraint violations of solutions. This process enables the LLM to grasp the relationship between well-performing and poorly performing solutions based on the provided input data. Solution's quality is assessed based on their constraint violations and objective-based performance. By leveraging the refined LLM, it can be used as a search operator to generate superior-quality solutions. Experimental evaluations across various test benchmarks illustrate that LLM-aided evolutionary search can significantly accelerate the population's convergence speed and stands out competitively against cutting-edge evolutionary algorithms.
FastScene: Text-Driven Fast 3D Indoor Scene Generation via Panoramic Gaussian Splatting
Venue: arXiv cs.CV 2024
Year: 2024

Text-driven 3D indoor scene generation holds broad applications, ranging from gaming and smart homes to AR/VR applications. Fast and high-fidelity scene generation is paramount for ensuring user-friendly experiences. However, existing methods are characterized by lengthy generation processes or necessitate the intricate manual specification of motion parameters, which introduces inconvenience for users. Furthermore, these methods often rely on narrow-field viewpoint iterative generations, compromising global consistency and overall scene quality. To address these issues, we propose FastScene, a framework for fast and higher-quality 3D scene generation, while maintaining the scene consistency. Specifically, given a text prompt, we generate a panorama and estimate its depth, since the panorama encompasses information about the entire scene and exhibits explicit geometric constraints. To obtain high-quality novel views, we introduce the Coarse View Synthesis (CVS) and Progressive Novel View Inpainting (PNVI) strategies, ensuring both scene consistency and view quality. Subsequently, we utilize Multi-View Projection (MVP) to form perspective views, and apply 3D Gaussian Splatting (3DGS) for scene reconstruction. Comprehensive experiments demonstrate FastScene surpasses other methods in both generation speed and quality with better scene consistency. Notably, guided only by a text prompt, FastScene can generate a 3D scene within a mere 15 minutes, which is at least one hour faster than state-of-the-art methods, making it a paradigm for user-friendly scene generation.