In the Generalized Noah's Ark Problem, one is given a phylogenetic tree on a set of species $X$ and a set of conservation projects for each species. Each project comes with a cost and raises the survival probability of the corresponding species. The aim is to select for each species a conservation project such that the total cost of the selected projects does not exceed some given threshold and the expected phylogenetic diversity is as large as possible. We study Generalized Noah's Ark Problem and some of its special cases with respect to several parameters related to the input structure such as the number of different costs, the number of different survival probabilities, or the number of species, $|X|$.
In this paper, we propose Advanced Tree-algorithm with Interference Cancellation (ATIC), a variant of binary tree-algorithm with successive interference cancellation (SICTA) introduced by Yu and Giannakis. ATIC assumes that Interference Cancellation (IC) can be performed both by the access point (AP), as in SICTA, but also by the users. Specifically, after every collision slot, the AP broadcasts the observed collision as feedback. Users who participated in the collision then attempt to perform IC by subtracting their transmissions from the collision signal. This way, the users can resolve collisions of degree 2 and, using a simple distributed arbitration algorithm based on user IDs, ensure that the next slot will contain just a single transmission. We show that ATIC reaches the asymptotic throughput of 0.924 as the number of initially collided users tends to infinity and reduces the number of collisions and packet delay. We also compare ATIC with other tree algorithms and indicate the extra feedback resources it requires.
We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball-minimization oracle. In this paper, we show that for minimizing Quasi-Self-Concordant functions we can use instead the basic Newton Method with Gradient Regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the Dual Newton Method, and based on it, develop the corresponding Accelerated Newton Scheme for this problem class, which further improves the complexity factor of the basic method. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton Method applied to several practical problems, including Logistic Regression, Soft Maximum, and Matrix Scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.
Consistency regularization methods, such as R-Drop (Liang et al., 2021) and CrossConST (Gao et al., 2023), have achieved impressive supervised and zero-shot performance in the neural machine translation (NMT) field. Can we also boost end-to-end (E2E) speech-to-text translation (ST) by leveraging consistency regularization? In this paper, we conduct empirical studies on intra-modal and cross-modal consistency and propose two training strategies, SimRegCR and SimZeroCR, for E2E ST in regular and zero-shot scenarios. Experiments on the MuST-C benchmark show that our approaches achieve state-of-the-art (SOTA) performance in most translation directions. The analyses prove that regularization brought by the intra-modal consistency, instead of modality gap, is crucial for the regular E2E ST, and the cross-modal consistency could close the modality gap and boost the zero-shot E2E ST performance.
We show that the essential properties of entropy (monotonicity, additivity and subadditivity) are consequences of entropy being a monoidal natural transformation from the under category functor $-/\mathsf{LProb}_{\rho}$ (where $\mathsf{LProb}_{\rho}$ is category of $\ell_{\rho}$ discrete probability spaces) to $\Delta_{\mathbb{R}}$. Moreover, the Shannon entropy can be characterized as the universal monoidal natural transformation from $-/\mathsf{LProb}_{\rho}$ to the category of strongly Archimedean ordered vector spaces (a reflective subcategory of the lax-slice 2-category over $\mathsf{MonCat}_{\ell}$ in the 2-category of monoidal categories), providing a succinct characterization of Shannon entropy as a reflection arrow. We can likewise define entropy for every category with a monoidal structure on its under categories (e.g. the category of finite abelian groups, the category of finite inhabited sets, the category of finite dimensional vector spaces, and the augmented simplex category) via the reflection arrow to the reflective subcategory of strongly Archimedean ordered vector spaces. This implies that all these entropies over different categories are components of a single natural transformation (the unit of the idempotent monad), allowing us to connect these entropies in a natural manner. We also provide a universal characterization of the conditional Shannon entropy based on the chain rule which, unlike the characterization of information loss by Baez, Fritz and Leinster, does not require any continuity assumption.
Lawful Interception (LI) is a legal obligation of Communication Service Providers (CSPs) to provide interception capabilities to Law Enforcement Agencies (LEAs) in order to gain insightful data from network communications for criminal proceedings, e.g., network identifiers for tracking suspects. With the privacy-enhancements of network identifiers in the 5th generation of mobile networks (5G), LEAs need to interact with CSPs for network identifier resolution. This raises new privacy issues, as untrusted CSPs are able to infer sensitive information about ongoing investigations, e.g., the identities of their subscribers under suspicion. In this work, we propose P3LI5, a novel system that enables LEAs to privately query CSPs for network identifier resolution leveraging on an information retrieval protocol, SparseWPIR, that is based on private information retrieval and its weakly private version. As such, P3LI5 can be adapted to various operational scenarios with different confidentiality or latency requirements, by selectively allowing a bounded information leakage for improved performance. We implement P3LI5 on the 5G LI infrastructure using well known open-source projects and demonstrate its scalability to large databases while retaining low latency. To the best of our knowledge, P3LI5 is the first proposal for addressing the privacy issues raised by the mandatory requirement for LI on the 5G core network.
Computing planar orthogonal drawings with the minimum number of bends is one of the most relevant topics in Graph Drawing. The problem is known to be NP-hard, even when we want to test the existence of a rectilinear planar drawing, i.e., an orthogonal drawing without bends (Garg and Tamassia, 2001). From the parameterized complexity perspective, the problem is fixed-parameter tractable when parameterized by the sum of three parameters: the number of bends, the number of vertices of degree at most two, and the treewidth of the input graph (Di Giacomo et al., 2022). We improve this last result by showing that the problem remains fixed-parameter tractable when parameterized only by the number of vertices of degree at most two plus the number of bends. As a consequence, rectilinear planarity testing lies in \FPT~parameterized by the number of vertices of degree at most two.
The Natural Language Processing(NLP) community has been using crowd sourcing techniques to create benchmark datasets such as General Language Understanding and Evaluation(GLUE) for training modern Language Models such as BERT. GLUE tasks measure the reliability scores using inter annotator metrics i.e. Cohens Kappa. However, the reliability aspect of LMs has often been overlooked. To counter this problem, we explore a knowledge-guided LM ensembling approach that leverages reinforcement learning to integrate knowledge from ConceptNet and Wikipedia as knowledge graph embeddings. This approach mimics human annotators resorting to external knowledge to compensate for information deficits in the datasets. Across nine GLUE datasets, our research shows that ensembling strengthens reliability and accuracy scores, outperforming state of the art.
Internet of Things (IoT) is defined as the connection between places and physical objects (i.e., things) over the internet/network via smart computing devices. We observed that IoT software developers share solutions to programming questions as code examples on three Stack Exchange Q&A sites: Stack Overflow (SO), Arduino, and Raspberry Pi. Previous research studies found vulnerabilities/weaknesses in C/C++ code examples shared in Stack Overflow. However, the studies did not investigate C/C++ code examples related to IoT. The studies investigated SO code examples only. In this paper, we conduct a large-scale empirical study of all IoT C/C++ code examples shared in the three Stack Exchange sites, i.e., SO, Arduino, and Raspberry Pi. From the 11,329 obtained code snippets from the three sites, we identify 29 distinct CWE (Common Weakness Enumeration) types in 609 snippets. These CWE types can be categorized into 8 general weakness categories, and we observe that evaluation, memory, and initialization related weaknesses are the most common to be introduced by users when posting programming solutions. Furthermore, we find that 39.58% of the vulnerable code snippets contain instances of CWE types that can be mapped to real-world occurrences of those CWE types (i.e. CVE instances). The most number vulnerable IoT code examples was found in Arduino, followed by SO, and Raspberry Pi. Memory type vulnerabilities are on the rise in the sites. For example, from the 3595 mapped CVE instances, we find that 28.99% result in Denial of Service (DoS) errors, which is particularly harmful for network reliant IoT devices such as smart cars. Our study results can guide various IoT stakeholders to be aware of such vulnerable IoT code examples and to inform IoT researchers during their development of tools that can help prevent developers the sharing of such vulnerable code examples in the sites. [Abridged].
We introduce ChatSQC, an innovative chatbot system that combines the power of OpenAI's Large Language Models (LLM) with a specific knowledge base in Statistical Quality Control (SQC). Our research focuses on enhancing LLMs using specific SQC references, shedding light on how data preprocessing parameters and LLM selection impact the quality of generated responses. By illustrating this process, we hope to motivate wider community engagement to refine LLM design and output appraisal techniques. We also highlight potential research opportunities within the SQC domain that can be facilitated by leveraging ChatSQC, thereby broadening the application spectrum of SQC. A primary goal of our work is to equip practitioners with a tool capable of generating precise SQC-related responses, thereby democratizing access to advanced SQC knowledge. To continuously improve ChatSQC, we ask the SQC community to provide feedback, highlight potential issues, request additional features, and/or contribute via pull requests through our public GitHub repository. Additionally, the team will continue to explore adding supplementary reference material that would further improve the contextual understanding of the chatbot. Overall, ChatSQC serves as a testament to the transformative potential of AI within SQC, and we hope it will spur further advancements in the integration of AI in this field.
Explainable Artificial Intelligence (XAI) is transforming the field of Artificial Intelligence (AI) by enhancing the trust of end-users in machines. As the number of connected devices keeps on growing, the Internet of Things (IoT) market needs to be trustworthy for the end-users. However, existing literature still lacks a systematic and comprehensive survey work on the use of XAI for IoT. To bridge this lacking, in this paper, we address the XAI frameworks with a focus on their characteristics and support for IoT. We illustrate the widely-used XAI services for IoT applications, such as security enhancement, Internet of Medical Things (IoMT), Industrial IoT (IIoT), and Internet of City Things (IoCT). We also suggest the implementation choice of XAI models over IoT systems in these applications with appropriate examples and summarize the key inferences for future works. Moreover, we present the cutting-edge development in edge XAI structures and the support of sixth-generation (6G) communication services for IoT applications, along with key inferences. In a nutshell, this paper constitutes the first holistic compilation on the development of XAI-based frameworks tailored for the demands of future IoT use cases.