OpenRaiser/Intern-Atlas huggingface dataset:
Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
Venue: arXiv cs.DS 2024
Year: 2024

In this paper we investigate the existence of subexponential parameterized algorithms of three fundamental cycle-hitting problems in geometric graph classes. The considered problems, \textsc{Triangle Hitting} (TH), \textsc{Feedback Vertex Set} (FVS), and \textsc{Odd Cycle Transversal} (OCT) ask for the existence in a graph $G$ of a set $X$ of at most $k$ vertices such that $G-X$ is, respectively, triangle-free, acyclic, or bipartite. Such subexponential parameterized algorithms are known to exist in planar and even $H$-minor free graphs from bidimensionality theory [Demaine et al., JACM 2005], and there is a recent line of work lifting these results to geometric graph classes consisting of intersection of "fat" objects ([Grigoriev et al., FOCS 2022] and [Lokshtanov et al., SODA 2022]). In this paper we focus on "thin" objects by considering intersection graphs of segments in the plane with $d$ possible slopes ($d$-DIR graphs) and contact graphs of segments in the plane. Assuming the ETH, we rule out the existence of algorithms: - solving TH in time $2^{o(n)}$ in 2-DIR graphs; and - solving TH, FVS, and OCT in time $2^{o(\sqrt{n})}$ in $K_{2,2}$-free contact 2-DIR graphs. These results indicate that additional restrictions are necessary in order to obtain subexponential parameterized algorithms for %these problems. In this direction we provide: - a $2^{O(k^{3/4}\cdot \log k)}n^{O(1)}$-time algorithm for FVS in contact segment graphs; - a $2^{O(\sqrt d\cdot t^2 \log t\cdot k^{2/3}\log k)} n^{O(1)}$-time algorithm for TH in $K_{t,t}$-free $d$-DIR graphs; and - a $2^{O(k^{7/9}\log^{3/2}k)} n^{O(1)}$-time algorithm for TH in contact segment graphs.
Circular Systems Engineering
Venue: arXiv cs.CY 2024
Year: 2024

The perception of the value and propriety of modern engineered systems is changing. In addition to their functional and extra-functional properties, nowadays' systems are also evaluated by their sustainability properties. The next generation of systems will be characterized by an overall elevated sustainability -- including their post-life, driven by efficient value retention mechanisms. Current systems engineering practices fall short of supporting these ambitions and need to be revised appropriately. In this paper, we introduce the concept of circular systems engineering, a novel paradigm for systems sustainability, and define two principles to successfully implement it: end-to-end sustainability and bipartite sustainability. We outline typical organizational evolution patterns that lead to the implementation and adoption of circularity principles, and outline key challenges and research opportunities.
FlakyFix: Using Large Language Models for Predicting Flaky Test Fix Categories and Test Code Repair
Venue: arXiv cs.SE 2024
Year: 2024

Flaky tests are problematic because they non-deterministically pass or fail for the same software version under test, causing confusion and wasting development effort. While machine learning models have been used to predict flakiness and its root causes, there is much less work on providing support to fix the problem. To address this gap, in this paper, we focus on predicting the type of fix that is required to remove flakiness and then repair the test code on that basis. We do this for a subset of flaky tests where the root cause of flakiness is in the test itself and not in the production code. One key idea is to guide the repair process with additional knowledge about the test's flakiness in the form of its predicted fix category. Thus, we first propose a framework that automatically generates labeled datasets for 13 fix categories and trains models to predict the fix category of a flaky test by analyzing the test code only. Our experimental results using code models and few-shot learning show that we can correctly predict most of the fix categories. To show the usefulness of such fix category labels for automatically repairing flakiness, we augment the prompts of GPT-3.5 Turbo, a Large Language Model (LLM), with such extra knowledge to request repair suggestions. The results show that our suggested fix category labels, complemented with in-context learning, significantly enhance the capability of GPT-3.5 Turbo in generating fixes for flaky tests. Based on the execution and analysis of a sample of GPT-repaired flaky tests, we estimate that a large percentage of such repairs (roughly between 51% and 83%) can be expected to pass. For the failing repaired tests, on average, 16% of the test code needs to be further changed for them to pass.
CasTGAN: Cascaded Generative Adversarial Network for Realistic Tabular Data Synthesis
Venue: arXiv cs.LG 2024
Year: 2024

Generative adversarial networks (GANs) have drawn considerable attention in recent years for their proven capability in generating synthetic data which can be utilised for multiple purposes. While GANs have demonstrated tremendous successes in producing synthetic data samples that replicate the dynamics of the original datasets, the validity of the synthetic data and the underlying privacy concerns represent major challenges which are not sufficiently addressed. In this work, we design a cascaded tabular GAN framework (CasTGAN) for generating realistic tabular data with a specific focus on the validity of the output. In this context, validity refers to the the dependency between features that can be found in the real data, but is typically misrepresented by traditional generative models. Our key idea entails that employing a cascaded architecture in which a dedicated generator samples each feature, the synthetic output becomes more representative of the real data. Our experimental results demonstrate that our model is capable of generating synthetic tabular data that can be used for fitting machine learning models. In addition, our model captures well the constraints and the correlations between the features of the real data, especially the high dimensional datasets. Furthermore, we evaluate the risk of white-box privacy attacks on our model and subsequently show that applying some perturbations to the auxiliary learners in CasTGAN increases the overall robustness of our model against targeted attacks.
Fairness Scheduling in User-Centric Cell-Free Massive MIMO Wireless Networks
Venue: arXiv cs.IT 2024
Year: 2024

We consider a user-centric cell-free massive MIMO wireless network with $L$ remote radio units, each with $M$ antennas, serving $K_{\rm tot}$ user equipments (UEs). Most of the literature considers the regime $LM \gg K_{\rm tot}$, where the $K$ UEs are active on each time-frequency slot, and evaluates the system performance in terms of ergodic rates. In this paper, we take a quite different viewpoint. We observe that the regime of $LM \gg K_{\rm tot}$ corresponds to a lightly loaded system with low sum spectral efficiency (SE). In contrast, in most relevant scenarios, the number of UEs is much larger than the total number of antennas, but users are not all active at the same time. To achieve high sum SE and handle $K_{\rm tot} \gg ML$, users must be scheduled over the time-frequency resource. The number of active users $K_{\rm act} \leq K_{\rm tot}$ must be chosen such that: 1) the network operates close to its maximum SE; 2) the active user set must be chosen dynamically over time in order to enforce fairness in terms of per-user time-averaged throughput rates. The fairness scheduling problem is formulated as the maximization of a concave componentwise non-decreasing network utility function of the per-user rates. Intermittent user activity imposes slot-by-slot coding/decoding which prevents the achievability of ergodic rates. Hence, we model the per-slot service rates using information outage probability. To obtain a tractable problem, we make a decoupling assumption on the CDF of the instantaneous mutual information seen at each UE $k$ receiver. We approximately enforce this condition with a conflict graph that prevents the simultaneous scheduling of users with large pilot contamination and propose an adaptive scheme for instantaneous service rate scheduling. Overall, the proposed dynamic scheduling is robust to system model uncertainties and can be easily implemented in practice.
New Prophet Inequalities via Poissonization and Sharding
Venue: arXiv cs.DS 2024
Year: 2024

This work introduces \emph{sharding} and \emph{Poissonization} as a unified framework for analyzing prophet inequalities. Sharding involves splitting a random variable into several independent random variables, shards, that collectively mimic the original variable's behavior. We combine this with Poissonization, where these shards are modeled using a Poisson distribution. Despite the simplicity of our framework, we improve the competitive ratio analysis of a dozen well studied prophet inequalities in the literature, some of which have been studied for decades. This includes the \textsc{Top-$1$-of-$k$} prophet inequality, prophet secretary inequality, and semi-online prophet inequality, among others. This approach not only refines the constants but also offers a more intuitive and streamlined analysis for many prophet inequalities in the literature. Furthermore, it simplifies proofs of several known results and may be of independent interest for other variants of the prophet inequality, such as order-selection.
A Synthetic Benchmarking Pipeline to Compare Camera Calibration Algorithms
Venue: arXiv cs.CV 2024
Year: 2024

Accurate camera calibration is crucial for various computer vision applications. However, measuring calibration accuracy in the real world is challenging due to the lack of datasets with ground truth to evaluate them. In this paper, we present SynthCal, a synthetic camera calibration benchmarking pipeline that generates images of calibration patterns to measure and enable accurate quantification of calibration algorithm performance in camera parameter estimation. We present a SynthCal generated calibration dataset with four common patterns, two camera types, and two environments with varying view, distortion, lighting, and noise levels for both monocular and multi-camera systems. The dataset evaluates both single and multi-view calibration algorithms by measuring re-projection and root-mean-square errors for identical patterns and camera settings. Additionally, we analyze the significance of different patterns using different calibration configurations. The experimental results demonstrate the effectiveness of SynthCal in evaluating various calibration algorithms and patterns.
Advancing O-RAN to Facilitate Intelligence in V2X
Venue: arXiv cs.NI 2024
Year: 2024

Vehicular communications integrated with the Radio Access Network (RAN) are envisioned as a breakthrough application for the 6th generation (6G) cellular systems. However, traditional RANs lack the flexibility to enable sophisticated control mechanisms that are demanded by the strict performance requirements of the vehicle-to-everything (V2X) environment. In contrast, the features of Open RAN (O-RAN) can be exploited to support advanced use cases, as its core paradigms represent an ideal framework for orchestrating vehicular communication. Although the high potential stemming from their integration can be easily seen and recognized, the effective combination of the two ecosystems is an open issue. Conceptual and architectural advances are required for O-RAN to be capable of facilitating network intelligence in V2X. This article pioneers the integration of the two strategies for seamlessly incorporating V2X control within O-RAN ecosystem. First, an enabling architecture that tightly integrates V2X and O-RAN is proposed and discussed. Then, a set of key V2X challenges is identified, and O-RAN-based solutions are proposed, paired with extensive numerical analysis to support their effectiveness. Results showcase the superior performance of such an approach in terms of raw throughput, network resilience, and control overhead. Finally, these results validate the proposed enabling architecture and confirm the potential of O-RAN in support of V2X communications.
Synthesising Full-Information Protocols
Venue: arXiv cs.LO 2024
Year: 2024

We lay out a model of games with imperfect information that features explicit communication actions, by which the entire observation history of a player is revealed to another player. Such full-information protocols are common in asynchronous distributed systems; here, we consider a synchronous setting with a single active player who may communicate with multiple passive observers in an indeterminate environment. We present a procedure for solving the basic strategy-synthesis problem under regular winning conditions. We present our solution in an abstract framework of games with imperfect information and we split the proof in two conceptual parts: (i) a generic reduction schema from imperfect-information to perfect-information games, and (ii) a specific construction for full-information protocols that satisfies the requirement of the reduction schema. Furthermore we show that the number of passive observers induces a strict hierarchy, both in terms of expressiveness and complexity: with n observers, a full-information protocol can express indistinguishability relations (defining imperfect information for the player in the protocol) that are not expressible with n-1 observers, and the strategy-synthesis problem is (n+1)-EXPTIME-complete.
Immersive Media and Massive Twinning: Advancing Towards the Metaverse
Venue: arXiv cs.MM 2024
Year: 2024

The advent of the Metaverse concept has further expedited the evolution of haptic, tactile internet, and multimedia applications with their VR/AR/XR services, and therefore, fully-immersive sensing is most likely to define the next generation of wireless networks as a key to realize the speculative vision of the Metaverse. In this magazine, we articulate different types of media that we envision will be communicated between the cyber and physical twins in the Metaverse. In particular, we explore the advantages grasped by exploiting each kind, and we point out critical challenges pertinent to 3D data processing, coding, transporting, and rendering. We further shed light on the role of future wireless networks in delivering the anticipated quality of immersion through the reliable streaming of multimedia signals between the digital twin and its physical counterpart. Specifically, we explore emergent communication paradigms, including semantic, holographic, and goal-oriented communication, which we expect to realize energy and spectrally efficient Metaverse while ensuring ultra-low latency.
EdgeFace: Efficient Face Recognition Model for Edge Devices
Venue: arXiv cs.CV 2024
Year: 2024

In this paper, we present EdgeFace, a lightweight and efficient face recognition network inspired by the hybrid architecture of EdgeNeXt. By effectively combining the strengths of both CNN and Transformer models, and a low rank linear layer, EdgeFace achieves excellent face recognition performance optimized for edge devices. The proposed EdgeFace network not only maintains low computational costs and compact storage, but also achieves high face recognition accuracy, making it suitable for deployment on edge devices. Extensive experiments on challenging benchmark face datasets demonstrate the effectiveness and efficiency of EdgeFace in comparison to state-of-the-art lightweight models and deep face recognition models. Our EdgeFace model with 1.77M parameters achieves state of the art results on LFW (99.73%), IJB-B (92.67%), and IJB-C (94.85%), outperforming other efficient models with larger computational complexities. The code to replicate the experiments will be made available publicly.
Learning ECG Signal Features Without Backpropagation Using Linear Laws
Venue: arXiv cs.LG 2024
Year: 2024

This paper introduces LLT-ECG, a novel method for electrocardiogram (ECG) signal classification that leverages concepts from theoretical physics to automatically generate features from time series data. Unlike traditional deep learning approaches, LLT-ECG operates in a forward manner, eliminating the need for backpropagation and hyperparameter tuning. By identifying linear laws that capture shared patterns within specific classes, the proposed method constructs a compact and verifiable representation, enhancing the effectiveness of downstream classifiers. We demonstrate LLT-ECG's state-of-the-art performance on real-world ECG datasets from PhysioNet, underscoring its potential for medical applications where speed and verifiability are crucial.
Optimal Transmit Antenna Deployment and Power Allocation for Wireless Power Supply in an Indoor Space
Venue: arXiv cs.IT 2024
Year: 2024

As Internet of Things (IoT) devices proliferate, sustainable methods for powering them are becoming indispensable. The wireless provision of power enables battery-free operation and is crucial for complying with weight and size restrictions. For the energy harvesting (EH) components of these devices to be small, a high operating frequency is necessary. In conjunction with a large transmit antenna, the receivers may be located in the radiating near-field (Fresnel) region, e.g., in indoor scenarios. In this paper, we propose a wireless power transfer (WPT) system ensuring reliable supply of power to an arbitrary number of mobile, low-power, and single-antenna receivers, whose locations in a three-dimensional cuboid room are unknown. A max-min optimisation problem is formulated to determine the optimal transmit power distribution. We rigorously prove that the optimal transmit power distribution's support has a lower dimensionality than its domain and thus, the employment of a continuous aperture antenna, utilised in Holographic MIMO (HMIMO), is unnecessary in the context of the considered WPT problem. Indeed, deploying a discrete transmit antenna architecture, i.e., a transmit antenna array, is sufficient and our proposed solution provides the optimal transmit antenna deployment and power allocation. Moreover, for a one-dimensional transmit antenna architecture, a finite number of transmit antennas is proven to be optimal. The proposed optimal solution is validated through computer simulations. Our simulation results indicate that the optimal transmit antenna architecture requires a finite number of transmit antennas and depends on the geometry of the environment and the dimensionality of the transmit antenna array.
Joint Hierarchical Priors and Adaptive Spatial Resolution for Efficient Neural Image Compression
Venue: arXiv cs.CV 2024
Year: 2024

Recently, the performance of neural image compression (NIC) has steadily improved thanks to the last line of study, reaching or outperforming state-of-the-art conventional codecs. Despite significant progress, current NIC methods still rely on ConvNet-based entropy coding, limited in modeling long-range dependencies due to their local connectivity and the increasing number of architectural biases and priors, resulting in complex underperforming models with high decoding latency. Motivated by the efficiency investigation of the Tranformer-based transform coding framework, namely SwinT-ChARM, we propose to enhance the latter, as first, with a more straightforward yet effective Tranformer-based channel-wise auto-regressive prior model, resulting in an absolute image compression transformer (ICT). Through the proposed ICT, we can capture both global and local contexts from the latent representations and better parameterize the distribution of the quantized latents. Further, we leverage a learnable scaling module with a sandwich ConvNeXt-based pre-/post-processor to accurately extract more compact latent codes while reconstructing higher-quality images. Extensive experimental results on benchmark datasets showed that the proposed framework significantly improves the trade-off between coding efficiency and decoder complexity over the versatile video coding (VVC) reference encoder (VTM-18.0) and the neural codec SwinT-ChARM. Moreover, we provide model scaling studies to verify the computational efficiency of our approach and conduct several objective and subjective analyses to bring to the fore the performance gap between the adaptive image compression transformer (AICT) and the neural codec SwinT-ChARM.
Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
Venue: arXiv cs.DS 2024
Year: 2024

Vizing's theorem asserts the existence of a $(Δ+1)$-edge coloring for any graph $G$, where $Δ= Δ(G)$ denotes the maximum degree of $G$. Several polynomial time $(Δ+1)$-edge coloring algorithms are known, and the state-of-the-art running time (up to polylogarithmic factors) is $\tilde{O}(\min\{m \cdot \sqrt{n}, m \cdot Δ\})$, by Gabow et al.\ from 1985, where $n$ and $m$ denote the number of vertices and edges in the graph, respectively. (The $\tilde{O}$ notation suppresses polylogarithmic factors.) Recently, Sinnamon shaved off a polylogarithmic factor from the time bound of Gabow et al. The {arboricity} $α= α(G)$ of a graph $G$ is the minimum number of edge-disjoint forests into which its edge set can be partitioned, and it is a measure of the graph's "uniform density". While $α\le Δ$ in any graph, many natural and real-world graphs exhibit a significant separation between $α$ and $Δ$. In this work we design a $(Δ+1)$-edge coloring algorithm with a running time of $\tilde{O}(\min\{m \cdot \sqrt{n}, m \cdot Δ\})\cdot \fracαΔ$, thus improving the longstanding time barrier by a factor of $\fracαΔ$. In particular, we achieve a near-linear runtime for bounded arboricity graphs (i.e., $α= \tilde{O}(1)$) as well as when $α= \tilde{O}(\fracΔ{\sqrt{n}})$. Our algorithm builds on Sinnamon's algorithm, and can be viewed as a density-sensitive refinement of it.
Offline Reinforcement Learning with Imbalanced Datasets
Venue: arXiv cs.LG 2024
Year: 2024

The prevalent use of benchmarks in current offline reinforcement learning (RL) research has led to a neglect of the imbalance of real-world dataset distributions in the development of models. The real-world offline RL dataset is often imbalanced over the state space due to the challenge of exploration or safety considerations. In this paper, we specify properties of imbalanced datasets in offline RL, where the state coverage follows a power law distribution characterized by skewed policies. Theoretically and empirically, we show that typically offline RL methods based on distributional constraints, such as conservative Q-learning (CQL), are ineffective in extracting policies under the imbalanced dataset. Inspired by natural intelligence, we propose a novel offline RL method that utilizes the augmentation of CQL with a retrieval process to recall past related experiences, effectively alleviating the challenges posed by imbalanced datasets. We evaluate our method on several tasks in the context of imbalanced datasets with varying levels of imbalance, utilizing the variant of D4RL. Empirical results demonstrate the superiority of our method over other baselines.