OpenRaiser/Intern-Atlas huggingface dataset:
Stackelberg-Pareto Synthesis (Extended Version)
Venue: arXiv cs.GT 2022
Year: 2022

We study the framework of two-player Stackelberg games played on graphs in which Player 0 announces a strategy and Player 1 responds rationally with a strategy that is an optimal response. While it is usually assumed that Player 1 has a single objective, we consider here the new setting where he has several. In this context, after responding with his strategy, Player 1 gets a payoff in the form of a vector of Booleans corresponding to his satisfied objectives. Rationality of Player 1 is encoded by the fact that his response must produce a Pareto-optimal payoff given the strategy of Player 0. We study for several kinds of $ω$-regular objectives the Stackelberg-Pareto Synthesis problem which asks whether Player 0 can announce a strategy which satisfies his objective, whatever the rational response of Player 1. We show that this problem is fixed-parameter tractable for games in which objectives are all reachability, safety, Büchi, co-Büchi, Boolean Büchi, parity, Muller, Streett or Rabin objectives. We also show that this problem is NEXPTIME-complete except for the cases of Büchi objectives for which it is NP-complete and co-Büchi objectives for which it is in NEXPTIME and NP-hard. The problem is already NP-complete in the simple case of reachability objectives and graphs that are trees.
Dynamic Coupling Strategy for Interdependent Network Systems Against Cascading Failures
Venue: arXiv cs.NI 2022
Year: 2022

Cascading failures are a common phenomenon in complex networked systems where failures at only a few nodes may trigger a process of sequential failure. We applied a flow redistribution model to investigate the robustness against cascading failures in modern systems carrying flows/loads (i.e. power grid, transportation system, etc.) that contain multiple interdependent networks. In such a system, the coupling coefficients between networks, which determine how much flows/loads are redistributed between networks, are a key factor determining the robustness to cascading failures. We derive recursive expressions to characterize the evolution of such a system under dynamic network coupling. Using these expressions, we enhance the robustness of interdependent network systems by dynamically adjusting the coupling coefficients based on current system situations, minimizing the subsequent failures. The analytical and simulation results show a significant improvement in robustness compared to prior work, which considers only fixed coupling coefficients. Our proposed Step-wise Optimization (SWO) method not only shows good performance against cascading failures, but also offers better computational complexity, scalability to multiple networks, and flexibility to different attack types. We show in simulation that SWO provides robustness against cascading failures for multiple different network topologies.
Sparse Matrix Multiplication in the Low-Bandwidth Model
Venue: arXiv cs.DC 2022
Year: 2022

We study matrix multiplication in the low-bandwidth model: There are $n$ computers, and we need to compute the product of two $n \times n$ matrices. Initially computer $i$ knows row $i$ of each input matrix. In one communication round each computer can send and receive one $O(\log n)$-bit message. Eventually computer $i$ has to output row $i$ of the product matrix. We seek to understand the complexity of this problem in the uniformly sparse case: each row and column of each input matrix has at most $d$ non-zeros and in the product matrix we only need to know the values of at most $d$ elements in each row or column. This is exactly the setting that we have, e.g., when we apply matrix multiplication for triangle detection in graphs of maximum degree $d$. We focus on the supported setting: the structure of the matrices is known in advance; only the numerical values of nonzero elements are unknown. There is a trivial algorithm that solves the problem in $O(d^2)$ rounds, but for a large $d$, better algorithms are known to exist; in the moderately dense regime the problem can be solved in $O(dn^{1/3})$ communication rounds, and for very large $d$, the dominant solution is the fast matrix multiplication algorithm using $O(n^{1.158})$ communication rounds (for matrix multiplication over fields and rings supporting fast matrix multiplication). In this work we show that it is possible to overcome quadratic barrier for all values of $d$: we present an algorithm that solves the problem in $O(d^{1.907})$ rounds for fields and rings supporting fast matrix multiplication and $O(d^{1.927})$ rounds for semirings, independent of $n$.
Two Attacks On Proof-of-Stake GHOST/Ethereum
Venue: arXiv cs.CR 2022
Year: 2022

We present two attacks targeting the Proof-of-Stake (PoS) Ethereum consensus protocol. The first attack suggests a fundamental conceptual incompatibility between PoS and the Greedy Heaviest-Observed Sub-Tree (GHOST) fork choice paradigm employed by PoS Ethereum. In a nutshell, PoS allows an adversary with a vanishing amount of stake to produce an unlimited number of equivocating blocks. While most equivocating blocks will be orphaned, such orphaned `uncle blocks' still influence fork choice under the GHOST paradigm, bestowing upon the adversary devastating control over the canonical chain. While the Latest Message Driven (LMD) aspect of current PoS Ethereum prevents a straightforward application of this attack, our second attack shows how LMD specifically can be exploited to obtain a new variant of the balancing attack that overcomes a recent protocol addition that was intended to mitigate balancing-type attacks. Thus, in its current form, PoS Ethereum without and with LMD is vulnerable to our first and second attack, respectively.
A Fully Memristive Spiking Neural Network with Unsupervised Learning
Venue: arXiv cs.NE 2022
Year: 2022

We present a fully memristive spiking neural network (MSNN) consisting of physically-realizable memristive neurons and memristive synapses to implement an unsupervised Spiking Time Dependent Plasticity (STDP) learning rule. The system is fully memristive in that both neuronal and synaptic dynamics can be realized by using memristors. The neuron is implemented using the SPICE-level memristive integrate-and-fire (MIF) model, which consists of a minimal number of circuit elements necessary to achieve distinct depolarization, hyperpolarization, and repolarization voltage waveforms. The proposed MSNN uniquely implements STDP learning by using cumulative weight changes in memristive synapses from the voltage waveform changes across the synapses, which arise from the presynaptic and postsynaptic spiking voltage signals during the training process. Two types of MSNN architectures are investigated: 1) a biologically plausible memory retrieval system, and 2) a multi-class classification system. Our circuit simulation results verify the MSNN's unsupervised learning efficacy by replicating biological memory retrieval mechanisms, and achieving 97.5% accuracy in a 4-pattern recognition problem in a large scale discriminative MSNN.
Label Leakage and Protection from Forward Embedding in Vertical Federated Learning
Venue: arXiv cs.LG 2022
Year: 2022

Vertical federated learning (vFL) has gained much attention and been deployed to solve machine learning problems with data privacy concerns in recent years. However, some recent work demonstrated that vFL is vulnerable to privacy leakage even though only the forward intermediate embedding (rather than raw features) and backpropagated gradients (rather than raw labels) are communicated between the involved participants. As the raw labels often contain highly sensitive information, some recent work has been proposed to prevent the label leakage from the backpropagated gradients effectively in vFL. However, these work only identified and defended the threat of label leakage from the backpropagated gradients. None of these work has paid attention to the problem of label leakage from the intermediate embedding. In this paper, we propose a practical label inference method which can steal private labels effectively from the shared intermediate embedding even though some existing protection methods such as label differential privacy and gradients perturbation are applied. The effectiveness of the label attack is inseparable from the correlation between the intermediate embedding and corresponding private labels. To mitigate the issue of label leakage from the forward embedding, we add an additional optimization goal at the label party to limit the label stealing ability of the adversary by minimizing the distance correlation between the intermediate embedding and corresponding private labels. We conducted massive experiments to demonstrate the effectiveness of our proposed protection methods.
The RATTLE Motion Planning Algorithm for Robust Online Parametric Model Improvement with On-Orbit Validation
Venue: arXiv cs.RO 2022
Year: 2022

Certain forms of uncertainty that robotic systems encounter can be explicitly learned within the context of a known model, like parametric model uncertainties such as mass and moments of inertia. Quantifying such parametric uncertainty is important for more accurate prediction of the system behavior, leading to safe and precise task execution. In tandem, providing a form of robustness guarantee against prevailing uncertainty levels like environmental disturbances and current model knowledge is also desirable. To that end, the authors' previously proposed RATTLE algorithm, a framework for online information-aware motion planning, is outlined and extended to enhance its applicability to real robotic systems. RATTLE provides a clear tradeoff between information-seeking motion and traditional goal-achieving motion and features online-updateable models. Additionally, online-updateable low level control robustness guarantees and a new method for automatic adjustment of information content down to a specified estimation precision is proposed. Results of extensive experimentation in microgravity using the Astrobee robots aboard the International Space Station and practical implementation details are presented, demonstrating RATTLE's capabilities for real-time, robust, online-updateable, and model information-seeking motion planning capabilities under parametric uncertainty.
A Characterization of Multiclass Learnability
Venue: arXiv cs.LG 2022
Year: 2022

A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz (2014). The classical characterization of the binary case boils down to empirical risk minimization. In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas; these include a natural setting we call list PAC learning. In the list learning setting, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of predictions. Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability. This dimension was introduced by Natarajan (1988) as a barrier for PAC learning. Whether the Natarajan dimension characterizes PAC learnability in general has been posed as an open question in several papers since. This work provides a negative answer: we construct a non-learnable class with Natarajan dimension one. For the construction, we identify a fundamental connection between concept classes and topology (i.e., colorful simplicial complexes). We crucially rely on a deep and involved construction of hyperbolic pseudo-manifolds by Januszkiewicz and Swiatkowski. It is interesting that hyperbolicity is directly related to learning problems that are difficult to solve although no obvious barriers exist. This is another demonstration of the fruitful links machine learning has with different areas in mathematics.
A Deep Neural Framework for Image Caption Generation Using GRU-Based Attention Mechanism
Venue: arXiv cs.CL 2022
Year: 2022

Image captioning is a fast-growing research field of computer vision and natural language processing that involves creating text explanations for images. This study aims to develop a system that uses a pre-trained convolutional neural network (CNN) to extract features from an image, integrates the features with an attention mechanism, and creates captions using a recurrent neural network (RNN). To encode an image into a feature vector as graphical attributes, we employed multiple pre-trained convolutional neural networks. Following that, a language model known as GRU is chosen as the decoder to construct the descriptive sentence. In order to increase performance, we merge the Bahdanau attention model with GRU to allow learning to be focused on a specific portion of the image. On the MSCOCO dataset, the experimental results achieve competitive performance against state-of-the-art approaches.
A theory of cut-restriction: first steps
Venue: arXiv cs.LO 2022
Year: 2022

Cut-elimination is the bedrock of proof theory. It is the algorithm that eliminates cuts from a sequent calculus proof that leads to cut-free calculi and applications. Cut-elimination applies to many logics irrespective of their semantics. Such is its influence that whenever cut-elimination is not provable in a sequent calculus the invariable response has been a move to a richer proof system to regain it. In this paper we investigate a radically different approach to the latter: adapting age-old cut-elimination to restrict the shape of the cut-formulas when elimination is not possible. We tackle the "first level" above cut-free: analytic cuts. Our methodology is applied to the sequent calculi for bi-intuitionistic logic and S5 where analytic cuts are already known to be required. This marks the first steps in a theory of cut-restriction.
AdaFamily: A family of Adam-like adaptive gradient methods
Venue: arXiv cs.LG 2022
Year: 2022

We propose AdaFamily, a novel method for training deep neural networks. It is a family of adaptive gradient methods and can be interpreted as sort of a blend of the optimization algorithms Adam, AdaBelief and AdaMomentum. We perform experiments on standard datasets for image classification, demonstrating that our proposed method outperforms these algorithms.
Endogenous Security of Computation Offloading in Blockchain-Empowered Internet of Things
Venue: arXiv cs.IT 2022
Year: 2022

This paper investigates an endogenous security architecture for computation offloading in the Internet of Things (IoT), where the blockchain technology enables the traceability of malicious behaviors, and the task data uploading link from sensors to small base station (SBS) is protected by intelligent reflecting surface (IRS)-assisted physical layer security (PLS). After receiving task data, the SBS allocates computational resources to help sensors perform the task. The existing computation offloading schemes usually focus on network performance improvement, such as energy consumption minimization, and neglect the Gas fee paid by sensors, resulting in the discontent of high Gas payers. Here, we design a Gas-oriented computation offloading scheme that guarantees the degree of satisfaction of sensors, while aiming to reduce energy consumption. Also, we deduce the ergodic secrecy rate of IRS-assisted PLS transmission that can represent the global secrecy performance to allocate computational resources. The simulations show that the proposed scheme ensures that the node paying higher Gas gets stronger computational resources, and just raises $4\%$ energy consumption in comparison with energy consumption minimization schemes.
On generating parametrised structural data using conditional generative adversarial networks
Venue: arXiv cs.LG 2022
Year: 2022

A powerful approach, and one of the most common ones in structural health monitoring (SHM), is to use data-driven models to make predictions and inferences about structures and their condition. Such methods almost exclusively rely on the quality of the data. Within the SHM discipline, data do not always suffice to build models with satisfactory accuracy for given tasks. Even worse, data may be completely missing from one's dataset, regarding the behaviour of a structure under different environmental conditions. In the current work, with a view to confronting such issues, the generation of artificial data using a variation of the generative adversarial network (GAN) algorithm, is used. The aforementioned variation is that of the conditional GAN or cGAN. The algorithm is not only used to generate artificial data, but also to learn transformations of manifolds according to some known parameters. Assuming that the structure's response is represented by points in a manifold, part of the space will be formed due to variations in external conditions affecting the structure. This idea proves efficient in SHM, as it is exploited to generate structural data for specific values of environmental coefficients. The scheme is applied here on a simulated structure which operates under different temperature and humidity conditions. The cGAN is trained on data for some discrete values of the temperature within some range, and is able to generate data for every temperature in this range with satisfactory accuracy. The novelty, compared to classic regression in similar problems, is that the cGAN allows unknown environmental parameters to affect the structure and can generate whole manifolds of data for every value of the known parameters, while the unknown ones vary within the generated manifolds.
Monitoring Diversity of AI Conferences: Lessons Learnt and Future Challenges in the DivinAI Project
Venue: arXiv cs.AI 2022
Year: 2022

DivinAI is an open and collaborative initiative promoted by the European Commission's Joint Research Centre to measure and monitor diversity indicators related to AI conferences, with special focus on gender balance, geographical representation, and presence of academia vs companies. This paper summarizes the main achievements and lessons learnt during the first year of life of the DivinAI project, and proposes a set of recommendations for its further development and maintenance by the AI community.
SoK: SCT Auditing in Certificate Transparency
Venue: arXiv cs.CR 2022
Year: 2022

The Web public key infrastructure is essential to providing secure communication on the Internet today, and certificate authorities play a crucial role in this ecosystem by issuing certificates. These authorities may misissue certificates or suffer misuse attacks, however, which has given rise to the Certificate Transparency (CT) project. The goal of CT is to store all issued certificates in public logs, which can then be checked for the presence of potentially misissued certificates. Thus, the requirement that a given certificate is indeed in one (or several) of these logs lies at the core of CT. In its current deployment, however, most individual clients do not check that the certificates they see are in logs, as requesting a proof of inclusion directly reveals the certificate and thus creates the clear potential for a violation of that client's privacy. In this paper, we explore the techniques that have been proposed for privacy-preserving auditing of certificate inclusion, focusing on their effectiveness, efficiency, and suitability in a near-term deployment. In doing so, we also explore the parallels with related problems involving browser clients. Guided by a set of constraints that we develop, we ultimately observe several key limitations in many proposals, ranging from their privacy provisions to the fact that they focus on the interaction between a client and a log but leave open the question of how a client could privately report any certificates that are missing.
A Simpler Alternative: Minimizing Transition Systems Modulo Alternating Simulation Equivalence
Venue: arXiv cs.FL 2022
Year: 2022

This paper studies the reduction (abstraction) of finite-state transition systems for control synthesis problems. We revisit the notion of alternating simulation equivalence (ASE), a more relaxed condition than alternating bisimulations, to relate systems and their abstractions. As with alternating bisimulations, ASE preserves the property that the existence of a controller for the abstraction is necessary and sufficient for a controller to exist for the original system. Moreover, being a less stringent condition, ASE can reduce systems further to produce smaller abstractions. We provide an algorithm that produces minimal AS equivalent abstractions. The theoretical results are then applied to obtain (un)schedulability certificates of periodic event-triggered control systems sharing a communication channel. A numerical example illustrates the results.
Experimental demonstration of Single-Level and Multi-Level-Cell RRAM-based In-Memory Computing with up to 16 parallel operations
Venue: arXiv cs.ET 2022
Year: 2022

Crossbar arrays of resistive memories (RRAM) hold the promise of enabling In-Memory Computing (IMC), but essential challenges due to the impact of device imperfection and device endurance have yet to be overcome. In this work, we demonstrate experimentally an RRAM-based IMC logic concept with strong resilience to RRAM variability, even after one million endurance cycles. Our work relies on a generalization of the concept of in-memory Scouting Logic, and we demonstrate it experimentally with up to 16 parallel devices (operands), a new milestone for RRAM in-memory logic. Moreover, we combine IMC with Multi-Level-Cell programming and demonstrate experimentally, for the first time, an IMC RRAM-based MLC 2-bit adder.
Relative distance matters for one-shot landmark detection
Venue: arXiv cs.CV 2022
Year: 2022

Contrastive learning based methods such as cascade comparing to detect (CC2D) have shown great potential for one-shot medical landmark detection. However, the important cue of relative distance between landmarks is ignored in CC2D. In this paper, we upgrade CC2D to version II by incorporating a simple-yet-effective relative distance bias in the training stage, which is theoretically proved to encourage the encoder to project the relatively distant landmarks to the embeddings with low similarities. As consequence, CC2Dv2 is less possible to detect a wrong point far from the correct landmark. Furthermore, we present an open-source, landmark-labeled dataset for the measurement of biomechanical parameters of the lower extremity to alleviate the burden of orthopedic surgeons. The effectiveness of CC2Dv2 is evaluated on the public dataset from the ISBI 2015 Grand-Challenge of cephalometric radiographs and our new dataset, which greatly outperforms the state-of-the-art one-shot landmark detection approaches.
Exact Price of Anarchy for Weighted Congestion Games with Two Players
Venue: arXiv cs.GT 2022
Year: 2022

This paper gives a complete analysis of worst-case equilibria for various versions of weighted congestion games with two players and affine cost functions. The results are exact price of anarchy bounds which are parametric in the weights of the two players, and establish exactly how the primitives of the game enter into the quality of equilibria. Interestingly, some of the worst-cases are attained when the players' weights only differ slightly. Our findings also show that sequential play improves the price of anarchy in all cases, however, this effect vanishes with an increasing difference in the players' weights. Methodologically, we obtain exact price of anarchy bounds by a duality based proof mechanism, based on a compact linear programming formulation that computes worst-case instances. This mechanism yields duality-based optimality certificates which can eventually be turned into purely algebraic proofs.