OpenRaiser/Intern-Atlas huggingface dataset:
A Geometric Characterization of Observability in Inertial Parameter Identification
Venue: arXiv cs.RO 2023
Year: 2023

This paper presents an algorithm to geometrically characterize inertial parameter identifiability for an articulated robot. The geometric approach tests identifiability across the infinite space of configurations using only a finite set of conditions and without approximation. It can be applied to general open-chain kinematic trees ranging from industrial manipulators to legged robots, and it is the first solution for this broad set of systems that is provably correct. The high-level operation of the algorithm is based on a key observation: Undetectable changes in inertial parameters can be represented as sequences of inertial transfers across the joints. Drawing on the exponential parameterization of rigid-body kinematics, undetectable inertial transfers are analyzed in terms of observability from linear systems theory. This analysis can be applied recursively, and lends an overall complexity of $O(N)$ to characterize parameter identifiability for a system of $N$ bodies. Matlab source code for the new algorithm is provided.
Adaptive Group Testing Algorithms to Estimate the Number of Defectives
Venue: arXiv cs.DS 2023
Year: 2023

We study the problem of estimating the number of defective items in adaptive Group testing by using a minimum number of queries. We improve the existing algorithm and prove a lower bound that show that, for constant estimation, the number of tests in our algorithm is optimal.
Big Data Visualization Tools
Venue: arXiv cs.DB 2023
Year: 2023

Data visualization and analytics are nowadays one of the corner-stones of Data Science, turning the abundance of Big Data being produced through modern systems into actionable knowledge. Indeed, the Big Data era has realized the availability of voluminous datasets that are dynamic, noisy and heterogeneous in nature. Transforming a data-curious user into someone who can access and analyze that data is even more burdensome now for a great number of users with little or no support and expertise on the data processing part. Thus, the area of data visualization and analysis has gained great attention recently, calling for joint action from different research areas and communities such as information visualization, data management and mining, human-computer interaction, and computer graphics. This article presents the limitations of traditional visualization systems in the Big Data era. Additionally, it discusses the major prerequisites and challenges that should be addressed by modern visualization systems. Finally, the state-of-the-art methods that have been developed in the context of the Big Data visualization and analytics are presented, considering methods from the Data Management and Mining, Information Visualization and Human-Computer Interaction communities
Circular (Yet Sound) Proofs
Venue: arXiv cs.LO 2023
Year: 2023

Proofs in propositional logic are typically presented as trees of derived formulas or, alternatively, as directed acyclic graphs of derived formulas. This distinction between tree-like vs. dag-like structure is particularly relevant when making quantitative considerations regarding, for example, proof size. Here we analyze a more general type of structural restriction for proofs in rule-based proof systems. In this definition, proofs are directed graphs of derived formulas in which cycles are allowed as long as every formula is derived at least as many times as it is required as a premise. We call such proofs "circular". We show that, for all sets of standard inference rules with single or multiple conclusions, circular proofs are sound. We start the study of the proof complexity of circular proofs at Circular Resolution, the circular version of Resolution. We immediately see that Circular Resolution is stronger than Dag-like Resolution since, as we show, the propositional encoding of the pigeonhole principle has circular Resolution proofs of polynomial size. Furthermore, for derivations of clauses from clauses, we show that Circular Resolution is, surprisingly, equivalent to Sherali-Adams, a proof system for reasoning through polynomial inequalities that has linear programming at its base. As corollaries we get: 1) polynomial-time (LP-based) algorithms that find Circular Resolution proofs of constant width, 2) examples that separate Circular from Dag-like Resolution, such as the pigeonhole principle and its variants, and 3) exponentially hard cases for Circular Resolution. Contrary to the case of Circular Resolution, for Frege we show that circular proofs can be converted into tree-like proofs with at most polynomial overhead.
Mitigating Docker Security Issues
Venue: arXiv cs.CR 2023
Year: 2023

Docker offers an ecosystem that offers a platform for application packaging, distributing, and managing within containers. However, the Docker platform has not yet matured. Presently, Docker is less secured than virtual machines (VM) and most of the other cloud technologies. The key to Dockers inadequate security protocols is container sharing of Linux kernel, which can lead to the risk of privileged escalations. This research will outline some significant security vulnerabilities at Docker and counter solutions to neutralize such attacks. There are a variety of security attacks like insider and outsider. This research will outline both types of attacks and their mitigations strategies. Taking some precautionary measures can save from massive disasters. This research will also present Docker secure deployment guidelines. These guidelines will suggest different configurations to deploy Docker containers in a more secure way.
A $ϕ$-Competitive Algorithm for Scheduling Packets with Deadlines
Venue: arXiv cs.DS 2023
Year: 2023

In the online packet scheduling problem with deadlines (PacketSchD, for short), the goal is to schedule transmissions of packets that arrive over time in a network switch and need to be sent across a link. Each packet has a deadline, representing its urgency, and a non-negative weight, that represents its priority. Only one packet can be transmitted in any time slot, so if the system is overloaded, some packets will inevitably miss their deadlines and be dropped. In this scenario, the natural objective is to compute a transmission schedule that maximizes the total weight of packets that are successfully transmitted. The problem is inherently online, with the scheduling decisions made without the knowledge of future packet arrivals. The central problem concerning PacketSchD, that has been a subject of intensive study since 2001, is to determine the optimal competitive ratio of online algorithms, namely the worst-case ratio between the optimum total weight of a schedule (computed by an offline algorithm) and the weight of a schedule computed by a (deterministic) online algorithm. We solve this open problem by presenting a $ϕ$-competitive online algorithm for PacketSchD (where $ϕ\approx 1.618$ is the golden ratio), matching the previously established lower bound.
Jointly Identifying and Fixing Inconsistent Readings from Information Extraction Systems
Venue: arXiv cs.CL 2023
Year: 2023

KGCleaner is a framework to identify and correct errors in data produced and delivered by an information extraction system. These tasks have been understudied and KGCleaner is the first to address both. We introduce a multi-task model that jointly learns to predict if an extracted relation is credible and repair it if not. We evaluate our approach and other models as instance of our framework on two collections: a Wikidata corpus of nearly 700K facts and 5M fact-relevant sentences and a collection of 30K facts from the 2015 TAC Knowledge Base Population task. For credibility classification, parameter efficient simple shallow neural network can achieve an absolute performance gain of 30 $F_1$ points on Wikidata and comparable performance on TAC. For the repair task, significant performance (at more than twice) gain can be obtained depending on the nature of the dataset and the models.
Comparative Study of Virtual Machines and Containers for DevOps Developers
Venue: arXiv cs.OS 2023
Year: 2023

This paper presents a comparative study of virtual machines (VMs) and containers for DevOps developers. The study explores the benefits and drawbacks of each technology in terms of their functionality, performance, security, and resource utilization. The paper examines the underlying architecture of VMs and containers, and how they differ from each other. The study includes a series of experiments that compare the performance and resource utilization of VMs and containers in different scenarios. The experiments evaluate factors such as startup time, memory usage, disk I/O, network latency, scalability, and administrative overhead. Finally, the paper provides recommendations for DevOps developers on which technology to choose based on their specific requirements and use cases. Overall, the study aims to provide a comprehensive understanding of the strengths and limitations of VMs and containers, helping developers to make informed decisions when choosing between them.
A new approach to the Kasami codes of type 2
Venue: arXiv cs.IT 2023
Year: 2023

The dual of the Kasami code of length $q^2-1$, with $q$ a power of $2$, is constructed by concatenating a cyclic MDS code of length $q+1$ over $F_q$ with a Simplex code of length $q-1$. This yields a new derivation of the weight distribution of the Kasami code, a new description of its coset graph, and a new proof that the Kasami code is completely regular. The automorphism groups of the Kasami code and the related $q$-ary MDS code are determined. New cyclic completely regular codes over finite fields a power of $2$, generalized Kasami codes, are constructed; they have coset graphs isomorphic to that of the Kasami codes. Another wide class of completely regular codes, including additive codes, as well as unrestricted codes, is obtained by combining cosets of the Kasami or generalized Kasami code.
New bounds on the anti-Ramsey numbers of star graphs
Venue: arXiv cs.DM 2023
Year: 2023

The anti-Ramsey number $ar(G,H)$ with input graph $G$ and pattern graph $H$, is the maximum positive integer $k$ such that there exists an edge coloring of $G$ using $k$ colors, in which there are no rainbow subgraphs isomorphic to $H$ in $G$. ($H$ is rainbow if all its edges get distinct colors). The concept of anti-Ramsey number was introduced by Erdös, Simanovitz, and Sós in 1973. Thereafter several researchers investigated this concept in the combinatorial setting. Recently, Feng et al. revisited the anti-Ramsey problem for the pattern graph $K_{1,t}$ (for $t \geq 3$) purely from an algorithmic point of view due to its applications in interference modeling of wireless networks. They posed it as an optimization problem, the maximum edge $q$-coloring problem. For a graph $G$ and an integer $q\geq 2$, an edge $q$-coloring of $G$ is an assignment of colors to edges of $G$, such that edges incident on a vertex span at most $q$ distinct colors. The maximum edge $q$-coloring problem seeks to maximize the number of colors in an edge $q$-coloring of the graph $G$. Note that the optimum value of the edge $q$-coloring problem of $G$ equals $ar(G,K_{1,q+1})$. In this paper, we study $ar(G,K_{1,t})$, the anti-Ramsey number of stars, for each fixed integer $t\geq 3$, both from combinatorial and algorithmic point of view. The first of our main results presents an upper bound for $ar(G,K_{1,q+1})$, in terms of number of vertices and the minimum degree of $G$. The second one improves this result for the case of triangle-free input graphs. For a positive integer $t$, let $H_t$ denote a subgraph of $G$ with maximum number of possible edges and maximum degree $t$. Our third main result presents an upper bound for $ar(G,K_{1,q+1})$ in terms of $|E(H_{q-1})|$. All our results have algorithmic consequences.
An empirical evaluation of imbalanced data strategies from a practitioner's point of view
Venue: arXiv cs.LG 2023
Year: 2023

This paper evaluates six strategies for mitigating imbalanced data: oversampling, undersampling, ensemble methods, specialized algorithms, class weight adjustments, and a no-mitigation approach referred to as the baseline. These strategies were tested on 58 real-life binary imbalanced datasets with imbalance rates ranging from 3 to 120. We conducted a comparative analysis of 10 under-sampling algorithms, 5 over-sampling algorithms, 2 ensemble methods, and 3 specialized algorithms across eight different performance metrics: accuracy, area under the ROC curve (AUC), balanced accuracy, F1-measure, G-mean, Matthew's correlation coefficient, precision, and recall. Additionally, we assessed the six strategies on altered datasets, derived from real-life data, with both low (3) and high (100 or 300) imbalance ratios (IR). The principal finding indicates that the effectiveness of each strategy significantly varies depending on the metric used. The paper also examines a selection of newer algorithms within the categories of specialized algorithms, oversampling, and ensemble methods. The findings suggest that the current hierarchy of best-performing strategies for each metric is unlikely to change with the introduction of newer algorithms.
Algorithmic information distortions and incompressibility in uniform multidimensional networks
Venue: arXiv cs.DM 2023
Year: 2023

This article presents a theoretical investigation of generalized encoded forms of networks in a uniform multidimensional space. First, we study encoded networks with (finite) arbitrary node dimensions (or aspects), such as time instants or layers. In particular, we study these networks that are formalized in the form of multiaspect graphs. In the context of node-aligned non-uniform (or node-unaligned non-uniform and uniform) multidimensional spaces, previous results has shown that, unlike classical graphs, the algorithmic information of a multidimensional network is not in general dominated by the algorithmic information of the binary sequence that determines the presence or absence of edges. In the present work, first we demonstrate the existence of such algorithmic information distortions for node-aligned uniform multidimensional networks. Secondly, we show that there are particular cases of infinite nesting families of finite uniform multidimensional networks such that each member of these families is incompressible. From these results, we also recover the network topological properties and equivalences in irreducible information content of multidimensional networks in comparison to their isomorphic classical graph counterpart in the previous literature. These results together establish a universal algorithmic approach and set limitations and conditions for irreducible information content analysis in comparing arbitrary networks with a large number of dimensions, such as multilayer networks.
Modality-based Factorization for Multimodal Fusion
Venue: arXiv cs.LG 2023
Year: 2023

We propose a novel method, Modality-based Redundancy Reduction Fusion (MRRF), for understanding and modulating the relative contribution of each modality in multimodal inference tasks. This is achieved by obtaining an $(M+1)$-way tensor to consider the high-order relationships between $M$ modalities and the output layer of a neural network model. Applying a modality-based tensor factorization method, which adopts different factors for different modalities, results in removing information present in a modality that can be compensated by other modalities, with respect to model outputs. This helps to understand the relative utility of information in each modality. In addition it leads to a less complicated model with less parameters and therefore could be applied as a regularizer avoiding overfitting. We have applied this method to three different multimodal datasets in sentiment analysis, personality trait recognition, and emotion recognition. We are able to recognize relationships and relative importance of different modalities in these tasks and achieves a 1\% to 4\% improvement on several evaluation measures compared to the state-of-the-art for all three tasks.
SmartOTPs: An Air-Gapped 2-Factor Authentication for Smart-Contract Wallets (Extended Version)
Venue: arXiv cs.CR 2023
Year: 2023

With the recent rise of cryptocurrencies' popularity, the security and management of crypto-tokens have become critical. We have witnessed many attacks on users and providers, which have resulted in significant financial losses. To remedy these issues, several wallet solutions have been proposed. However, these solutions often lack either essential security features, usability, or do not allow users to customize their spending rules. In this paper, we propose SmartOTPs, a smart-contract wallet framework that gives a flexible, usable, and secure way of managing crypto-tokens in a self-sovereign fashion. The proposed framework consists of four components (i.e., an authenticator, a client, a hardware wallet, and a smart contract), and it provides 2-factor authentication (2FA) performed in two stages of interaction with the blockchain. To the best of our knowledge, our framework is the first one that utilizes one-time passwords (OTPs) in the setting of the public blockchain. In SmartOTPs, the OTPs are aggregated by a Merkle tree and hash chains whereby for each authentication only a short OTP (e.g., 16B-long) is transferred from the authenticator to the client. Such a novel setting enables us to make a fully air-gapped authenticator by utilizing small QR codes or a few mnemonic words, while additionally offering resilience against quantum cryptanalysis. We have made a proof-of-concept based on the Ethereum platform. Our cost analysis shows that the average cost of a transfer operation is comparable to existing 2FA solutions using smart contracts with multi-signatures.
End-to-End Multi-Task Denoising for joint SDR and PESQ Optimization
Venue: arXiv cs.SD 2023
Year: 2023

Supervised learning based on a deep neural network recently has achieved substantial improvement on speech enhancement. Denoising networks learn mapping from noisy speech to clean one directly, or to a spectrum mask which is the ratio between clean and noisy spectra. In either case, the network is optimized by minimizing mean square error (MSE) between ground-truth labels and time-domain or spectrum output. However, existing schemes have either of two critical issues: spectrum and metric mismatches. The spectrum mismatch is a well known issue that any spectrum modification after short-time Fourier transform (STFT), in general, cannot be fully recovered after inverse short-time Fourier transform (ISTFT). The metric mismatch is that a conventional MSE metric is sub-optimal to maximize our target metrics, signal-to-distortion ratio (SDR) and perceptual evaluation of speech quality (PESQ). This paper presents a new end-to-end denoising framework with the goal of joint SDR and PESQ optimization. First, the network optimization is performed on the time-domain signals after ISTFT to avoid spectrum mismatch. Second, two loss functions which have improved correlations with SDR and PESQ metrics are proposed to minimize metric mismatch. The experimental result showed that the proposed denoising scheme significantly improved both SDR and PESQ performance over the existing methods.
New Results on Directed Edge Dominating Set
Venue: arXiv cs.CC 2023
Year: 2023

We study a family of generalizations of Edge Dominating Set on directed graphs called Directed $(p,q)$-Edge Dominating Set. In this problem an arc $(u,v)$ is said to dominate itself, as well as all arcs which are at distance at most $q$ from $v$, or at distance at most $p$ to $u$. First, we give significantly improved FPT algorithms for the two most important cases of the problem, $(0,1)$-dEDS and $(1,1)$-dEDS (that correspond to versions of Dominating Set on line graphs), as well as polynomial kernels. We also improve the best-known approximation for these cases from logarithmic to constant. In addition, we show that $(p,q)$-dEDS is FPT parameterized by $p+q+tw$, but W-hard parameterized by $tw$ (even if the size of the optimal is added as a second parameter), where $tw$ is the treewidth of the underlying graph of the input. We then go on to focus on the complexity of the problem on tournaments. Here, we provide a complete classification for every possible fixed value of $p,q$, which shows that the problem exhibits a surprising behavior, including cases which are in P; cases which are solvable in quasi-polynomial time but not in P; and a single case $(p=q=1)$ which is NP-hard (under randomized reductions) and cannot be solved in sub-exponential time, under standard assumptions.
Analysing Factorizations of Action-Value Networks for Cooperative Multi-Agent Reinforcement Learning
Venue: arXiv cs.MA 2023
Year: 2023

Recent years have seen the application of deep reinforcement learning techniques to cooperative multi-agent systems, with great empirical success. However, given the lack of theoretical insight, it remains unclear what the employed neural networks are learning, or how we should enhance their learning power to address the problems on which they fail. In this work, we empirically investigate the learning power of various network architectures on a series of one-shot games. Despite their simplicity, these games capture many of the crucial problems that arise in the multi-agent setting, such as an exponential number of joint actions or the lack of an explicit coordination mechanism. Our results extend those in [4] and quantify how well various approaches can represent the requisite value functions, and help us identify the reasons that can impede good performance, like sparsity of the values or too tight coordination requirements.
VoroCrust: Voronoi Meshing Without Clipping
Venue: arXiv cs.GR 2023
Year: 2023

Polyhedral meshes are increasingly becoming an attractive option with particular advantages over traditional meshes for certain applications. What has been missing is a robust polyhedral meshing algorithm that can handle broad classes of domains exhibiting arbitrarily curved boundaries and sharp features. In addition, the power of primal-dual mesh pairs, exemplified by Voronoi-Delaunay meshes, has been recognized as an important ingredient in numerous formulations. The VoroCrust algorithm is the first provably-correct algorithm for conforming polyhedral Voronoi meshing for non-convex and non-manifold domains with guarantees on the quality of both surface and volume elements. A robust refinement process estimates a suitable sizing field that enables the careful placement of Voronoi seeds across the surface circumventing the need for clipping and avoiding its many drawbacks. The algorithm has the flexibility of filling the interior by either structured or random samples, while preserving all sharp features in the output mesh. We demonstrate the capabilities of the algorithm on a variety of models and compare against state-of-the-art polyhedral meshing methods based on clipped Voronoi cells establishing the clear advantage of VoroCrust output.
Preference Neural Network
Venue: arXiv cs.LG 2023
Year: 2023

This paper proposes a preference neural network (PNN) to address the problem of indifference preferences orders with new activation function. PNN also solves the Multi-label ranking problem, where labels may have indifference preference orders or subgroups are equally ranked. PNN follows a multi-layer feedforward architecture with fully connected neurons. Each neuron contains a novel smooth stairstep activation function based on the number of preference orders. PNN inputs represent data features and output neurons represent label indexes. The proposed PNN is evaluated using new preference mining dataset that contains repeated label values which have not experimented before. PNN outperforms five previously proposed methods for strict label ranking in terms of accurate results with high computational efficiency.