OpenRaiser/Intern-Atlas huggingface dataset:
Truncated Gaussian-Mixture Variational AutoEncoder
Venue: arXiv cs.LG 2021
Year: 2021

Variation Autoencoder (VAE) has become a powerful tool in modeling the non-linear generative process of data from a low-dimensional latent space. Recently, several studies have proposed to use VAE for unsupervised clustering by using mixture models to capture the multi-modal structure of latent representations. This strategy, however, is ineffective when there are outlier data samples whose latent representations are meaningless, yet contaminating the estimation of key major clusters in the latent space. This exact problem arises in the context of resting-state fMRI (rs-fMRI) analysis, where clustering major functional connectivity patterns is often hindered by heavy noise of rs-fMRI and many minor clusters (rare connectivity patterns) of no interest to analysis. In this paper we propose a novel generative process, in which we use a Gaussian-mixture to model a few major clusters in the data, and use a non-informative uniform distribution to capture the remaining data. We embed this truncated Gaussian-Mixture model in a Variational AutoEncoder framework to obtain a general joint clustering and outlier detection approach, called tGM-VAE. We demonstrated the applicability of tGM-VAE on the MNIST dataset and further validated it in the context of rs-fMRI connectivity analysis.
Guessing random additive noise decoding with symbol reliability information (SRGRAND)
Venue: arXiv cs.IT 2021
Year: 2021

The design and implementation of error correcting codes has long been informed by two fundamental results: Shannon's 1948 capacity theorem, which established that long codes use noisy channels most efficiently; and Berlekamp, McEliece, and Van Tilborg's 1978 theorem on the NP-hardness of decoding linear codes. These results shifted focus away from creating code-independent decoders, but recent low-latency communication applications necessitate relatively short codes, providing motivation to reconsider the development of universal decoders. We introduce a scheme for employing binarized symbol soft information within Guessing Random Additive Noise Decoding, a universal hard detection decoder. We incorporate codebook-independent quantization of soft information to indicate demodulated symbols to be reliable or unreliable. We introduce two decoding algorithms: one identifies a conditional Maximum Likelihood (ML) decoding; the other either reports a conditional ML decoding or an error. For random codebooks, we present error exponents and asymptotic complexity, and show benefits over hard detection. As empirical illustrations, we compare performance with majority logic decoding of Reed-Muller codes, with Berlekamp-Massey decoding of Bose-Chaudhuri-Hocquenghem codes, with CA-SCL decoding of CA-Polar codes, and establish the performance of Random Linear Codes, which require a universal decoder and offer a broader palette of code sizes and rates than traditional codes.
Evolutionary Algorithms for the Chance-Constrained Knapsack Problem
Venue: arXiv cs.NE 2021
Year: 2021

Evolutionary algorithms have been applied to a wide range of stochastic problems. Motivated by real-world problems where constraint violations have disruptive effects, this paper considers the chance-constrained knapsack problem (CCKP) which is a variance of the binary knapsack problem. The problem aims to maximize the profit of selected items under a constraint that the knapsack capacity bound is violated with a small probability. To tackle the chance constraint, we introduce how to construct surrogate functions by applying well-known deviation inequalities such as Chebyshev's inequality and Chernoff bounds. Furthermore, we investigate the performance of several deterministic approaches and introduce a single- and multi-objective evolutionary algorithm to solve the CCKP. In the experiment section, we evaluate and compare the deterministic approaches and evolutionary algorithms on a wide range of instances. Our experimental results show that a multi-objective evolutionary algorithm outperforms its single-objective formulation for all instances and performance better than deterministic approaches according to the computation time. Furthermore, our investigation points out in which circumstances to favour Chebyshev's inequality or the Chernoff bound when dealing with the CCKP.
The Frobenius and factor universality problems of the Kleene star of a finite set of words
Venue: arXiv cs.FL 2021
Year: 2021

We solve open problems concerning the Kleene star $L^*$ of a finite set $L$ of words over an alphabet $Σ$. The \emph{Frobenius monoid} problem is the question for a given finite set of words $L$, whether the language $L^*$ is cofinite. We show that it is PSPACE-complete. We also exhibit an infinite family of sets $L$ such that the length of the longest words not in $L^*$ (when $L^*$ is cofinite) is exponential in the length of the longest words in $L$ and subexponential in the sum of the lengths of words in $L$. The \emph{factor universality} problem is the question for a given finite set of words $L$, whether every word over $Σ$ is a factor (substring) of some word from $L^*$. We show that it is also PSPACE-complete. Besides that, we exhibit an infinite family of sets $L$ such that the length of the shortest words not being a factor of any word in $L^*$ is exponential in the length of the longest words in $L$ and subexponential in the sum of the lengths of words in $L$. This essentially settles in the negative the longstanding Restivo's conjecture (1981) and its weak variations. All our solutions base on one shared construction, and as an auxiliary general tool, we introduce the concept of \emph{set rewriting systems}. Finally, we complement the results with upper bounds.
Expect More from the Networking: DDoS Mitigation by FITT in Named Data Networking
Venue: arXiv cs.CR 2021
Year: 2021

Distributed Denial of Service (DDoS) attacks have plagued the Internet for decades, but the basic defense approaches have not fundamentally changed. Rather, the size and rate of growth in attacks have actually outpaced carriers' and DDoS mitigation services' growth, calling for new solutions that can be, partially or fully, deployed imminently and exhibit effectiveness. In this paper, we examine the basic functions in Named Data Networking (NDN), a newly proposed Internet architecture, that can address the principle weaknesses in today's IP networks. We demonstrate by a new DDoS mitigation solution over NDN, Fine-grained Interest Traffic Throttling FITT, that NDN's architectural changes, even when incrementally deployed, can make DDoS attacks fundamentally more difficult to launch and less effective. FITT leverages the NDN design to enable the network to detect DDoS from victim's feedback, throttles DDoS traffic by reverse its exact paths through the network, and enforces control over the misbehaving entities at their sources. Our extensive simulation results show that FITT can throttle attack traffic with one-way time delay from the victim to the NDN gateway; upon activation, FITT effectively stop attack traffic from impacting benign flows, resulting in over 99\% of packets reaching victims being legitimate ones. We further demonstrate that service providers may implement NDN/FITT on existing CDN nodes as an incrementally deployable solution to effectuate the application level remediation at the sources, which remains unattainable in today's DDoS mitigation approaches.
Ahead of Time Mutation Based Fault Localisation using Statistical Inference
Venue: arXiv cs.SE 2021
Year: 2021

Mutation analysis can effectively capture the dependency between source code and test results. This has been exploited by Mutation Based Fault Localisation (MBFL) techniques. However, MBFL techniques suffer from the need to expend the high cost of mutation analysis after the observation of failures, which may present a challenge for its practical adoption. We introduce SIMFL (Statistical Inference for Mutation-based Fault Localisation), an MBFL technique that allows users to perform the mutation analysis in advance before a failure is observed, allowing the amortisation of the analysis cost. SIMFL uses mutants as artificial faults and aims to learn the failure patterns among test cases against different locations of mutations. Once a failure is observed, SIMFL requires either almost no or very small additional cost for analysis, depending on the used inference model. An empirical evaluation using Defects4J shows that SIMFL can successfully localise up to 113 out of 203 studied faults (55%) at the top, and 159 (78%) faults within the top five, significantly outperforming existing MBFL techniques while using the results of mutation analysis that has been undertaken before the test failure. The amortised cost of mutation analysis can be further reduced by mutation sampling: SIMFL retains 80% of its localisation accuracy at the top rank when using only 10% of generated mutants, compared to results obtained without sampling.
Colourful components in $k$-caterpillars and planar graphs
Venue: arXiv cs.DM 2021
Year: 2021

A connected component of a vertex-coloured graph is said to be colourful if all its vertices have different colours. By extension, a graph is colourful if all its connected components are colourful. Given a vertex-coloured graph $G$ and an integer $p$, the Colourful Components problem asks whether there exist at most $p$ edges whose removal makes $G$ colourful and the Colourful Partition problem asks whether there exists a partition of $G$ into at most $p$ colourful components. In order to refine our understanding of the complexity of the problems on trees, we study both problems on $k$-caterpillars, which are trees with a central path $P$ such that every vertex not in $P$ is within distance $k$ from a vertex in $P$. We prove that Colourful Components and Colourful Partition are NP-complete on $4$-caterpillars with maximum degree $3$, $3$-caterpillars with maximum degree $4$ and $2$-caterpillars with maximum degree $5$. On the other hand, we show that the problems are linear-time solvable on $1$-caterpillars. Hence, our results imply two complexity dichotomies on trees: Colourful Components and Colourful Partition are linear-time solvable on trees with maximum degree $d$ if $d \leq 2$ (that is, on paths), and NP-complete otherwise; Colourful Components and Colourful Partition are linear-time solvable on $k$-caterpillars if $k \leq 1$, and NP-complete otherwise. We leave three open cases which, if solved, would provide a complexity dichotomy for both problems on $k$-caterpillars, for every non-negative integer $k$, with respect to the maximum degree. We also show that Colourful Components is NP-complete on $5$-coloured planar graphs with maximum degree $4$ and on $12$-coloured planar graphs with maximum degree $3$. Our results answer two open questions of Bulteau et al. mentioned in [30th Annual Symposium on Combinatorial Pattern Matching, 2019].
Parallel Weighted Random Sampling
Venue: arXiv cs.DS 2021
Year: 2021

Data structures for efficient sampling from a set of weighted items are an important building block of many applications. However, few parallel solutions are known. We close many of these gaps both for shared-memory and distributed-memory machines. We give efficient, fast, and practicable parallel algorithms for building data structures that support sampling single items (alias tables, compressed data structures). This also yields a simplified and more space-efficient sequential algorithm for alias table construction. Our approaches to sampling $k$ out of $n$ items with/without replacement and to subset (Poisson) sampling are output-sensitive, i.e., the sampling algorithms use work linear in the number of different samples. This is also interesting in the sequential case. Weighted random permutation can be done by sorting appropriate random deviates. We show that this is possible with linear work using a nonlinear transformation of these deviates. Finally, we give a communication-efficient, highly scalable approach to (weighted and unweighted) reservoir sampling. This algorithm is based on a fully distributed model of streaming algorithms that might be of independent interest. Experiments for alias tables and sampling with replacement show near linear speedups both for construction and queries using up to 158 threads of shared-memory machines. An experimental evaluation of distributed weighted reservoir sampling on up to 256 nodes (5120 cores) also shows good speedups.
Parameterized Distributed Complexity Theory: A logical approach
Venue: arXiv cs.DC 2021
Year: 2021

Parameterized complexity theory offers a framework for a refined analysis of hard algorithmic problems. Instead of expressing the running time of an algorithm as a function of the input size only, running times are expressed with respect to one or more parameters of the input instances. In this work we follow the approach of parameterized complexity to provide a framework of parameterized distributed complexity. The central notion of efficiency in parameterized complexity is fixed-parameter tractability and we define the distributed analogue Distributed-FPT (for Distributed in $\{Local, Congest, Congested-Clique\}$) as the class of problems that can be solved in $f(k)$ communication rounds in the Distributed model of distributed computing, where $k$ is the parameter of the problem instance and $f$ is an arbitrary computable function. To classify hardness we introduce three hierarchies. The Distributed-WEFT-hierarchy is defined analogously to the W-hierarchy in parameterized complexity theory via reductions to the weighted circuit satisfiability problem, but it turns out that this definition does not lead to satisfying frameworks for the Local and Congest models. We then follow a logical approach that leads to a more robust theory. We define the levels of the Distributed-W-hierarchy and the Distributed-A-hierarchy that have first-order model-checking problems as their complete problems via suitable reductions.
Oxide: The Essence of Rust
Venue: arXiv cs.PL 2021
Year: 2021

Rust claims to advance industrial programming by bridging the gap between low-level systems programming and high-level application programming. At the heart of the argument that this enables programmers to build more reliable and efficient software is the borrow checker - a novel approach to ownership that aims to balance type system expressivity with usability. And yet, to date there is no core type system that captures Rust's notion of ownership and borrowing, and hence no foundation for research on Rust to build upon. In this work, we set out to capture the essence of this model of ownership by developing a type systems account of Rust's borrow checker. We present Oxide, a formalized programming language close to source-level Rust (but with fully-annotated types). This presentation takes a new view of lifetimes as an approximation of the provenances of references, and our type system is able to automatically compute this information through a substructural typing judgment. We provide the first syntactic proof of type safety for borrow checking using progress and preservation. Oxide is a simpler formulation of borrow checking - including recent features such as non-lexical lifetimes - that we hope researchers will be able to use as the basis for work on Rust.
PBBFMM3D: a parallel black-box algorithm for kernel matrix-vector multiplication
Venue: arXiv cs.MS 2021
Year: 2021

Kernel matrix-vector product is ubiquitous in many science and engineering applications. However, a naive method requires $O(N^2)$ operations, which becomes prohibitive for large-scale problems. We introduce a parallel method that provably requires $O(N)$ operations to reduce the computation cost. The distinct feature of our method is that it requires only the ability to evaluate the kernel function, offering a black-box interface to users. Our parallel approach targets multi-core shared-memory machines and is implemented using OpenMP. Numerical results demonstrate up to $19\times$ speedup on 32 cores. We also present a real-world application in geostatistics, where our parallel method was used to deliver fast principle component analysis of covariance matrices.
Semi-Supervised Few-Shot Learning with Prototypical Random Walks
Venue: arXiv cs.LG 2021
Year: 2021

Recent progress has shown that few-shot learning can be improved with access to unlabelled data, known as semi-supervised few-shot learning(SS-FSL). We introduce an SS-FSL approach, dubbed as Prototypical Random Walk Networks(PRWN), built on top of Prototypical Networks (PN). We develop a random walk semi-supervised loss that enables the network to learn representations that are compact and well-separated. Our work is related to the very recent development of graph-based approaches for few-shot learning. However, we show that compact and well-separated class representations can be achieved by modeling our prototypical random walk notion without needing additional graph-NN parameters or requiring a transductive setting where a collective test set is provided. Our model outperforms baselines in most benchmarks with significant improvements in some cases. Our model, trained with 40$\%$ of the data as labeled, compares competitively against fully supervised prototypical networks, trained on 100$\%$ of the labels, even outperforming it in the 1-shot mini-Imagenet case with 50.89$\%$ to 49.4$\%$ accuracy. We also show that our loss is resistant to distractors, unlabeled data that does not belong to any of the training classes, and hence reflecting robustness to labeled/unlabeled class distribution mismatch. Associated GitHub page can be found at https://prototypical-random-walk.github.io.
Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem
Venue: arXiv cs.CC 2021
Year: 2021

We study the problem of finding an exact solution to the consensus halving problem. While recent work has shown that the approximate version of this problem is PPA-complete, we show that the exact version is much harder. Specifically, finding a solution with $n$ cuts is FIXP-hard, and deciding whether there exists a solution with fewer than $n$ cuts is ETR-complete. We also give a QPTAS for the case where each agent's valuation is a polynomial. Along the way, we define a new complexity class BU, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly. We show that FIXP $\subseteq$ BU $\subseteq$ TFETR and that LinearBU $=$ PPA, where LinearBU is the subclass of BU in which the Borsuk-Ulam instance is specified by a linear arithmetic circuit.
ST-UNet: A Spatio-Temporal U-Network for Graph-structured Time Series Modeling
Venue: arXiv cs.LG 2021
Year: 2021

The spatio-temporal graph learning is becoming an increasingly important object of graph study. Many application domains involve highly dynamic graphs where temporal information is crucial, e.g. traffic networks and financial transaction graphs. Despite the constant progress made on learning structured data, there is still a lack of effective means to extract dynamic complex features from spatio-temporal structures. Particularly, conventional models such as convolutional networks or recurrent neural networks are incapable of revealing the temporal patterns in short or long terms and exploring the spatial properties in local or global scope from spatio-temporal graphs simultaneously. To tackle this problem, we design a novel multi-scale architecture, Spatio-Temporal U-Net (ST-UNet), for graph-structured time series modeling. In this U-shaped network, a paired sampling operation is proposed in spacetime domain accordingly: the pooling (ST-Pool) coarsens the input graph in spatial from its deterministic partition while abstracts multi-resolution temporal dependencies through dilated recurrent skip connections; based on previous settings in the downsampling, the unpooling (ST-Unpool) restores the original structure of spatio-temporal graphs and resumes regular intervals within graph sequences. Experiments on spatio-temporal prediction tasks demonstrate that our model effectively captures comprehensive features in multiple scales and achieves substantial improvements over mainstream methods on several real-world datasets.
Network topology design to influence the effects of manipulative behaviors in a social choice procedure
Venue: arXiv cs.SY 2021
Year: 2021

A social choice procedure is modeled as a repeated Nash game between the social agents, who are communicating with each other through a social communication network modeled by an undirected graph. The agents' criteria for this game are describing a trade off between self-consistent and manipulative behaviors. Their best response strategies are resulting in two dynamics rules, one for the agents' opinions and one for their actions. The stability properties of these dynamics are studied. In the case of instability, the stabilization of these dynamics through the design of the network topology is formulated as a constrained integer programming problem. The constraints have the form of a Bilinear Matrix Inequality (BMI), which is known to result in a nonconvex feasible set in the general case. To deal with this problem a Genetic Algorithm is designed. Finally, simulations are presented for several different initial topologies and conclusions are derived concerning both the functionality of the algorithm and the advisability of the problem formulation.
Bounded Synthesis of Resilient Supervisors
Venue: arXiv cs.SY 2021
Year: 2021

In this paper, we investigate the problem of synthesizing resilient supervisors against combined actuator and sensor attacks, for the subclass of cyber-physical systems that can be modelled as discrete-event systems. We assume that the attackers can carry out actuator enablement and disablement attacks as well as sensor replacement attacks. We consider both risky attackers and covert attackers in the setup where the (partial-observation) attackers may or may not eavesdrop the control commands (issued by the supervisor). A constraint-based approach for the bounded synthesis of resilient supervisors is developed, by reducing the problem to the Quantified Boolean Formulas (QBF) problem. The bounded synthesis problem can then be solved either with a QBF solver or with repeated calls to a propositional satisfiability (SAT) solver, by employing maximally permissive attackers, which can be synthesized with the existing partial-observation supervisor synthesis procedures, as counter examples in the counter example guided inductive synthesis loop.
EMTk -- The Emotion Mining Toolkit
Venue: arXiv cs.SE 2021
Year: 2021

The Emotion Mining Toolkit (EMTk) is a suite of modules and datasets offering a comprehensive solution for mining sentiment and emotions from technical text contributed by developers on communication channels. The toolkit is written in Java, Python, and R, and is released under the MIT open source license. In this paper, we describe its architecture and the benchmark against the previous, standalone versions of our sentiment analysis tools. Results show large improvements in terms of speed.