OpenRaiser/Intern-Atlas huggingface dataset:
Deletion to Scattered Graph Classes II -- Improved FPT Algorithms for Deletion to Pairs of Graph Classes
Venue: arXiv cs.DS 2023
Year: 2023

Let $Π$ be a hereditary graph class. The problem of deletion to $Π$, takes as input a graph $G$ and asks for a minimum number (or a fixed integer $k$) of vertices to be deleted from $G$ so that the resulting graph belongs to $Π$. This is a well-studied problem in paradigms including approximation and parameterized complexity. Recently, the study of a natural extension of the problem was initiated where we are given a finite set of hereditary graph classes, and the goal is to determine whether $k$ vertices can be deleted from a given graph so that the connected components of the resulting graph belong to one of the given hereditary graph classes. The problem is shown to be FPT as long as the deletion problem to each of the given hereditary graph classes is fixed-parameter tractable, and the property of being in any of the graph classes is expressible in the counting monodic second order (CMSO) logic. While this was shown using some black box theorems, faster algorithms were shown when each of the hereditary graph classes has a finite forbidden set. In this paper, we do a deep dive on pairs of specific graph classes ($Π_1, Π_2$) in which we would like the connected components of the resulting graph to belong to, and design simpler and more efficient FPT algorithms. We design a general FPT algorithm and approximation algorithm for pairs of graph classes (possibly having infinite forbidden sets) satisfying certain conditions. These algorithms cover several pairs of popular graph classes. Our algorithm makes non-trivial use of the branching technique and as a black box, FPT algorithms for deletion to individual graph classes.
STIR$^2$: Reward Relabelling for combined Reinforcement and Imitation Learning on sparse-reward tasks
Venue: arXiv cs.LG 2023
Year: 2023

In the search for more sample-efficient reinforcement-learning (RL) algorithms, a promising direction is to leverage as much external off-policy data as possible. For instance, expert demonstrations. In the past, multiple ideas have been proposed to make good use of the demonstrations added to the replay buffer, such as pretraining on demonstrations only or minimizing additional cost functions. We present a new method, able to leverage both demonstrations and episodes collected online in any sparse-reward environment with any off-policy algorithm. Our method is based on a reward bonus given to demonstrations and successful episodes (via relabeling), encouraging expert imitation and self-imitation. Our experiments focus on several robotic-manipulation tasks across two different simulation environments. We show that our method based on reward relabeling improves the performance of the base algorithm (SAC and DDPG) on these tasks. Finally, our best algorithm STIR$^2$ (Self and Teacher Imitation by Reward Relabeling), which integrates into our method multiple improvements from previous works, is more data-efficient than all baselines.
Long induced paths in minor-closed graph classes and beyond
Venue: arXiv cs.DM 2023
Year: 2023

In this paper we show that every graph of pathwidth less than $k$ that has a path of order $n$ also has an induced path of order at least $\frac{1}{3} n^{1/k}$. This is an exponential improvement and a generalization of the polylogarithmic bounds obtained by Esperet, Lemoine and Maffray (2016) for interval graphs of bounded clique number. We complement this result with an upper-bound. This result is then used to prove the two following generalizations: - every graph of treewidth less than $k$ that has a path of order $n$ contains an induced path of order at least $\frac{1}{4} (\log n)^{1/k}$; - for every non-trivial graph class that is closed under topological minors there is a constant $d \in (0,1)$ such that every graph from this class that has a path of order $n$ contains an induced path of order at least $(\log n)^d$. We also describe consequences of these results beyond graph classes that are closed under topological minors.
Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms
Venue: arXiv cs.GT 2023
Year: 2023

We consider a platform's problem of collecting data from privacy sensitive users to estimate an underlying parameter of interest. We formulate this question as a Bayesian-optimal mechanism design problem, in which an individual can share her (verifiable) data in exchange for a monetary reward or services, but at the same time has a (private) heterogeneous privacy cost which we quantify using differential privacy. We consider two popular differential privacy settings for providing privacy guarantees for the users: central and local. In both settings, we establish minimax lower bounds for the estimation error and derive (near) optimal estimators for given heterogeneous privacy loss levels for users. Building on this characterization, we pose the mechanism design problem as the optimal selection of an estimator and payments that will elicit truthful reporting of users' privacy sensitivities. Under a regularity condition on the distribution of privacy sensitivities we develop efficient algorithmic mechanisms to solve this problem in both privacy settings. Our mechanism in the central setting can be implemented in time $\mathcal{O}(n \log n)$ where $n$ is the number of users and our mechanism in the local setting admits a Polynomial Time Approximation Scheme (PTAS).
In Defense of the Unitary Scalarization for Deep Multi-Task Learning
Venue: arXiv cs.LG 2023
Year: 2023

Recent multi-task learning research argues against unitary scalarization, where training simply minimizes the sum of the task losses. Several ad-hoc multi-task optimization algorithms have instead been proposed, inspired by various hypotheses about what makes multi-task settings difficult. The majority of these optimizers require per-task gradients, and introduce significant memory, runtime, and implementation overhead. We show that unitary scalarization, coupled with standard regularization and stabilization techniques from single-task learning, matches or improves upon the performance of complex multi-task optimizers in popular supervised and reinforcement learning settings. We then present an analysis suggesting that many specialized multi-task optimizers can be partly interpreted as forms of regularization, potentially explaining our surprising results. We believe our results call for a critical reevaluation of recent research in the area.
Safe Equilibrium
Venue: arXiv cs.GT 2023
Year: 2023

The standard game-theoretic solution concept, Nash equilibrium, assumes that all players behave rationally. If we follow a Nash equilibrium and opponents are irrational (or follow strategies from a different Nash equilibrium), then we may obtain an extremely low payoff. On the other hand, a maximin strategy assumes that all opposing agents are playing to minimize our payoff (even if it is not in their best interest), and ensures the maximal possible worst-case payoff, but results in exceedingly conservative play. We propose a new solution concept called safe equilibrium that models opponents as behaving rationally with a specified probability and behaving potentially arbitrarily with the remaining probability. We prove that a safe equilibrium exists in all strategic-form games (for all possible values of the rationality parameters), and prove that its computation is PPAD-hard. We present exact algorithms for computing a safe equilibrium in both 2 and $n$-player games, as well as scalable approximation algorithms.
Cooperative Security Against Interdependent Risks
Venue: arXiv cs.GT 2023
Year: 2023

Firms in inter-organizational networks such as supply chains or strategic alliances are exposed to interdependent risks. These are risks that are transferable across partner firms. They can be decomposed into intrinsic risks a firm faces from its own operations and extrinsic risks transferred from its partners. Firms broadly have access to two security strategies: either they can independently eliminate both intrinsic and extrinsic risks by securing their links with partners, or alternatively, firms can cooperate with partners to eliminate sources of intrinsic risk in the network. We develop a graph-theoretic model of interdependent security and demonstrate that the network-optimal security strategy can be computed in polynomial time. Then, we use cooperative game-theoretic tools to examine whether and when firms can sustain the network-optimal security strategy via cost-sharing mechanisms that are stable, fair, computable, and implementable via a series of bilateral cost-sharing arrangements. We consider different informational assumptions in the network and show that, when the players know only their own costs, firms have a clear incentive to cooperate globally whereas, in the presence of public information, there may not exist cost-sharing mechanisms that can sustain network-wide cooperation. We then design a novel cost-sharing mechanism: the agreeable allocation, that is easy to compute, bilaterally implementable, ensures stability, and is fair in a well-defined sense. However, the agreeable allocation need not always exist. We then generalize levels of agreeable allocation, with weaker implementability properties but greater existence guarantees.
Sound-Dr: Reliable Sound Dataset and Baseline Artificial Intelligence System for Respiratory Illnesses
Venue: arXiv cs.SD 2023
Year: 2023

As the burden of respiratory diseases continues to fall on society worldwide, this paper proposes a high-quality and reliable dataset of human sounds for studying respiratory illnesses, including pneumonia and COVID-19. It consists of coughing, mouth breathing, and nose breathing sounds together with metadata on related clinical characteristics. We also develop a proof-of-concept system for establishing baselines and benchmarking against multiple datasets, such as Coswara and COUGHVID. Our comprehensive experiments show that the Sound-Dr dataset has richer features, better performance, and is more robust to dataset shifts in various machine learning tasks. It is promising for a wide range of real-time applications on mobile devices. The proposed dataset and system will serve as practical tools to support healthcare professionals in diagnosing respiratory disorders. The dataset and code are publicly available here: https://github.com/ReML-AI/Sound-Dr/.
The Dark Side of the Language: Pre-trained Transformers in the DarkNet
Venue: arXiv cs.CL 2023
Year: 2023

Pre-trained Transformers are challenging human performances in many NLP tasks. The massive datasets used for pre-training seem to be the key to their success on existing tasks. In this paper, we explore how a range of pre-trained Natural Language Understanding models perform on definitely unseen sentences provided by classification tasks over a DarkNet corpus. Surprisingly, results show that syntactic and lexical neural networks perform on par with pre-trained Transformers even after fine-tuning. Only after what we call extreme domain adaptation, that is, retraining with the masked language model task on all the novel corpus, pre-trained Transformers reach their standard high results. This suggests that huge pre-training corpora may give Transformers unexpected help since they are exposed to many of the possible sentences.
HARQ Optimization for Real-Time Remote Estimation in Wireless Networked Control
Venue: arXiv cs.IT 2023
Year: 2023

This paper analyzes wireless network control for remote estimation of linear time-invariant dynamical systems under various Hybrid Automatic Repeat Request (HARQ) packet retransmission schemes. In conventional HARQ, packet reliability increases gradually with additional packets; however, each retransmission maximally increases the Age of Information and causes severe degradation in estimation mean squared error (MSE) performance. We optimize standard HARQ schemes by allowing partial retransmissions to increase the packet reliability gradually and limit the AoI growth. In incremental redundancy HARQ, we optimize the retransmission time to enable the early arrival of the next status updates. In Chase combining HARQ, since packet length remains fixed, we allow retransmission and new updates in a single time slot using non-orthogonal signaling. Non-orthogonal retransmissions increase packet reliability without delaying the fresh updates. We formulate bi-objective optimization with the proposed variance of the MSE-based cost function and standard long-term average MSE cost function to guarantee short-term performance stability. Using the Markov decision process formulation, we find the optimal static and dynamic policies under the proposed HARQ schemes to improve MSE performance further. The simulation results show that the proposed HARQ-based policies are more robust and achieve significantly better and more stable MSE performance than standard HARQ-based policies.
UDC: Unified DNAS for Compressible TinyML Models
Venue: arXiv cs.LG 2023
Year: 2023

Deploying TinyML models on low-cost IoT hardware is very challenging, due to limited device memory capacity. Neural processing unit (NPU) hardware address the memory challenge by using model compression to exploit weight quantization and sparsity to fit more parameters in the same footprint. However, designing compressible neural networks (NNs) is challenging, as it expands the design space across which we must make balanced trade-offs. This paper demonstrates Unified DNAS for Compressible (UDC) NNs, which explores a large search space to generate state-of-the-art compressible NNs for NPU. ImageNet results show UDC networks are up to $3.35\times$ smaller (iso-accuracy) or 6.25% more accurate (iso-model size) than previous work.
Defeating Eavesdroppers with Ambient Backscatter Communications
Venue: arXiv cs.IT 2023
Year: 2023

Unlike conventional anti-eavesdropping methods that always require additional energy or computing resources (e.g., in friendly jamming and cryptography-based solutions), this work proposes a novel anti-eavesdropping solution that comes with mostly no extra power nor computing resource requirement. This is achieved by leveraging the ambient backscatter communications in which secret information can be transmitted by backscattering it over ambient radio signals. Specifically, the original message at the transmitter is first encoded into two parts: (i) active transmit message and (ii) backscatter message. The active transmit message is then transmitted by using the conventional wireless transmission method while the backscatter message is transmitted by backscattering it on the active transmit signals via an ambient backscatter tag. As the backscatter tag does not generate any active RF signals, it is intractable for the eavesdropper to detect the backscatter message. Therefore, secret information, e.g., secret key for decryption, can be carried by the backscattered message, making the adversary unable to decode the original message. Simulation results demonstrate that our proposed solution can significantly enhance security protection for communication systems.
Correlation Cube Attack Revisited: Improved Cube Search and Superpoly Recovery Techniques
Venue: arXiv cs.CR 2023
Year: 2023

In this paper, we improve the cube attack by exploiting low-degree factors of the superpoly w.r.t. certain "special" index set of cube (ISoC). This can be viewed as a special case of the correlation cube attack proposed at Eurocrypt 2018, but under our framework more beneficial equations on the key variables can be obtained in the key-recovery phase. To mount our attack, one has two challenging problems: effectively recover algebraic normal form of the superpoly and extract out its low-degree factors; and efficiently search a large quantity of good ISoCs. We bring in new techniques to solve both of them. First, we propose the variable substitution technique for middle rounds of a cipher, in which polynomials on the key variables in the algebraic expressions of internal states are substituted by new variables. This will improve computational complexity of the superpoly recovery and promise more compact superpolys that can be easily decomposed with respect to the new variables. Second, we propose the vector numeric mapping technique, which seeks out a tradeoff between efficiency of the numeric mapping technique and accuracy of the monomial prediction technique in degree evaluation of superpolys. Combining with this technique, a fast pruning method is given and modeled by MILP to filter good ISoCs of which the algebraic degree satisfies some fixed threshold. Thanks to automated MILP solvers, it becomes practical to comprehensively search for good cubes across the entire search space. To illustrate the power of our techniques, we apply all of them to Trivium stream cipher. The previous best practical key recovery attack was on 820-round Trivium with complexity $2^{53.17}$. We put forward 820-, 825- and 830-round practical key-recovery attacks, in which there are 2^{80}\times 87.8%, 2^{80}\times 83% and 2^{80}\times 65.7% keys that could be practically recovered, respectively.
Dynamic Blockage Pre-Avoidance using Reconfigurable Intelligent Surfaces
Venue: arXiv cs.IT 2023
Year: 2023

Internet-of-vehicle (IoV) is a general concept referring to, e.g., autonomous drive based vehicle-to-everything (V2X) communications or moving relays. Here, high rate and reliability demands call for advanced multi-antenna techniques and millimeter-wave (mmw) based communications. However, the sensitivity of the mmw signals to blockage may limit the system performance, especially in highways/rural areas with limited building reflectors/base station deployments and high-speed devices. To avoid the blockage, various techniques have been proposed among which reconfigurable intelligent surface (RIS) is a candidate. RIS, however, has been mainly of interest in stationary/low mobility scenarios, due to the associated channel state information acquisition and beam management overhead as well as imperfect reflection. In this article, we study the potentials and challenges of RIS-assisted dynamic blockage avoidance in IoV networks. Particularly, by designing region-based RIS pre-selection as well as blockage prediction schemes, we show that RIS-assisted communication has the potential to boost the performance of IoV networks. However, there are still issues to be solved before RIS can be practically deployed in IoV networks.
SoK: Blockchain Governance
Venue: arXiv cs.CR 2023
Year: 2023

Blockchain systems come with a promise of decentralization that often stumbles on a roadblock when key decisions about modifying the software codebase need to be made. This is attested by the fact that both of the two major cryptocurrencies, Bitcoin and Ethereum, have undergone hard forks that resulted in the creation of alternative systems, creating confusion and opportunities for fraudulent activities. These events, and numerous others, underscore the importance of Blockchain governance, namely the set of processes that blockchain platforms utilize in order to perform decision-making and converge to a widely accepted direction for the system to evolve. While a rich topic of study in other areas, governance of blockchain platforms is lacking a well established set of methods and practices that are adopted industry wide. This makes the topic of blockchain governance a fertile domain for a thorough systematization that we undertake in this work. We start by distilling a comprehensive array of properties for sound governance systems drawn from academic sources as well as grey literature of election systems and blockchain white papers. These are divided into seven categories, confidentiality, verifiability, accountability, sustainability, Pareto efficiency, suffrage and liveness that capture the whole spectrum of desiderata of governance systems. We proceed to classify ten well-documented blockchain systems. While all properties are satisfied, even partially, by at least one system, no system that satisfies most of them. Our work lays out a foundation for assessing blockchain governance processes. While it highlights shortcomings and deficiencies in currently deployed systems, it can also be a catalyst for improving these processes to the highest possible standard with appropriate trade-offs, something direly needed for blockchain platforms to operate effectively in the long term.
FOLE Equivalence
Venue: arXiv cs.DB 2023
Year: 2023

The first-order logical environment FOLE [5] provides a rigorous and principled approach to distributed interoperable first-order information systems. FOLE has been developed in two forms: a classification form and an interpretation form. Two papers represent FOLE in a classification form corresponding to ideas of the Information Flow Framework [11],[12],[13]: the first paper [6] provides a foundation that connects elements of the ERA data model [2] with components of the first-order logical environment FOLE; the second paper [7] provides a superstructure that extends FOLE to the formalisms of first-order logic. The formalisms in the classification form of FOLE provide an appropriate framework for developing the relational calculus. Two other papers represent FOLE in an interpretation form: the first paper [8] develops the notion of the FOLE table following the relational model [3]; the second paper [9] discusses the notion of a FOLE relational database. All the operations of the relational algebra have been rigorously developed [10] using the interpretation form of FOLE. The present study demonstrates that the classification form of FOLE is informationally equivalent to the interpretation form of FOLE. In general, the FOLE representation uses a conceptual structures approach, that is completely compatible with formal concept analysis [4] and information flow [1].
UxNB-Enabled Cell-Free Massive MIMO with HAPS-Assisted Sub-THz Backhauling
Venue: arXiv cs.IT 2023
Year: 2023

In this paper, we propose a cell-free scheme for unmanned aerial vehicle (UAV) base stations (BSs) to manage the severe intercell interference between terrestrial users and UAV-BSs of neighboring cells. Since the cell-free scheme requires enormous bandwidth for backhauling, we propose to use the sub-terahertz (sub-THz) band for the backhaul links between UAV-BSs and central processing unit (CPU). Also, because the sub-THz band requires a reliable line-of-sight link, we propose to use a high altitude platform station (HAPS) as a CPU. At the first time-slot of the proposed scheme, users send their messages to UAVs at the sub-6 GHz band. The UAVs then apply match-filtering and power allocation. At the second time-slot, at each UAV, orthogonal resource blocks are allocated for each user at the sub-THz band, and the signals are sent to the HAPS after analog beamforming. In the HAPS receiver, after analog beamforming, the message of each user is decoded. We formulate an optimization problem that maximizes the minimum signal-to-interference-plus-noise ratio of users by finding the optimum allocated power as well as the optimum locations of UAVs. Simulation results demonstrate the superiority of the proposed scheme compared with aerial cellular and terrestrial cell-free baseline schemes.