OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive Submodular Influence Maximization with Myopic Feedback
Venue: arXiv cs.SI 2018
Year: 2018

This paper examines the problem of adaptive influence maximization in social networks. As adaptive decision making is a time-critical task, a realistic feedback model has been considered, called myopic. In this direction, we propose the myopic adaptive greedy policy that is guaranteed to provide a (1 - 1/e)-approximation of the optimal policy under a variant of the independent cascade diffusion model. This strategy maximizes an alternative utility function that has been proven to be adaptive monotone and adaptive submodular. The proposed utility function considers the cumulative number of active nodes through the time, instead of the total number of the active nodes at the end of the diffusion. Our empirical analysis on real-world social networks reveals the benefits of the proposed myopic strategy, validating our theoretical results.
Translating Neuralese
Venue: arXiv cs.CL 2018
Year: 2018

Several approaches have recently been proposed for learning decentralized deep multiagent policies that coordinate via a differentiable communication channel. While these policies are effective for many tasks, interpretation of their induced communication strategies has remained a challenge. Here we propose to interpret agents' messages by translating them. Unlike in typical machine translation problems, we have no parallel data to learn from. Instead we develop a translation model based on the insight that agent messages and natural language strings mean the same thing if they induce the same belief about the world in a listener. We present theoretical guarantees and empirical evidence that our approach preserves both the semantics and pragmatics of messages by ensuring that players communicating through a translation layer do not suffer a substantial loss in reward relative to players with a common language.
The Art Gallery Problem is $\exists \mathbb{R}$-complete
Venue: arXiv cs.CG 2018
Year: 2018

We prove that the art gallery problem is equivalent under polynomial time reductions to deciding whether a system of polynomial equations over the real numbers has a solution. The art gallery problem is a classical problem in computational geometry. Given a simple polygon $P$ and an integer $k$, the goal is to decide if there exists a set $G$ of $k$ guards within $P$ such that every point $p\in P$ is seen by at least one guard $g\in G$. Each guard corresponds to a point in the polygon $P$, and we say that a guard $g$ sees a point $p$ if the line segment $pg$ is contained in $P$. The art gallery problem has stimulated extensive research in geometry and in algorithms. However, the complexity status of the art gallery problem has not been resolved. It has long been known that the problem is $\text{NP}$-hard, but no one has been able to show that it lies in $\text{NP}$. Recently, the computational geometry community became more aware of the complexity class $\exists \mathbb{R}$. The class $\exists \mathbb{R}$ consists of problems that can be reduced in polynomial time to the problem of deciding whether a system of polynomial equations with integer coefficients and any number of real variables has a solution. It can be easily seen that $\text{NP}\subseteq \exists \mathbb{R}$. We prove that the art gallery problem is $\exists \mathbb{R}$-complete, implying that (1) any system of polynomial equations over the real numbers can be encoded as an instance of the art gallery problem, and (2) the art gallery problem is not in the complexity class $\text{NP}$ unless $\text{NP}=\exists \mathbb{R}$. As a corollary of our construction, we prove that for any real algebraic number $α$ there is an instance of the art gallery problem where one of the coordinates of the guards equals $α$ in any guard set of minimum cardinality. That rules out many geometric approaches to the problem.
Fast Space Optimal Leader Election in Population Protocols
Venue: arXiv cs.DC 2018
Year: 2018

The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this paper the emphasis is on the space complexity in fast leader election via population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions within the population of n agents. The main result of this paper is a new fast and space optimal leader election protocol. The new protocol utilises O(log^2 n) parallel time (which is equivalent to O(n log^2 n) sequential pairwise interactions), and each agent operates on O(log log n) states. This double logarithmic space usage matches asymptotically the lower bound 1/2 log log n on the minimal number of states required by agents in any leader election algorithm with the running time o(n/polylog n). Our solution takes an advantage of the concept of phase clocks, a fundamental synchronisation and coordination tool in distributed computing. We propose a new fast and robust population protocol for initialisation of phase clocks to be run simultaneously in multiple modes and intertwined with the leader election process. We also provide the reader with the relevant formal argumentation indicating that our solution is always correct, and fast with high probability.
A Novel Hybrid Quicksort Algorithm Vectorized using AVX-512 on Intel Skylake
Venue: arXiv cs.MS 2018
Year: 2018

The modern CPU's design, which is composed of hierarchical memory and SIMD/vectorization capability, governs the potential for algorithms to be transformed into efficient implementations. The release of the AVX-512 changed things radically, and motivated us to search for an efficient sorting algorithm that can take advantage of it. In this paper, we describe the best strategy we have found, which is a novel two parts hybrid sort, based on the well-known Quicksort algorithm. The central partitioning operation is performed by a new algorithm, and small partitions/arrays are sorted using a branch-free Bitonic-based sort. This study is also an illustration of how classical algorithms can be adapted and enhanced by the AVX-512 extension. We evaluate the performance of our approach on a modern Intel Xeon Skylake and assess the different layers of our implementation by sorting/partitioning integers, double floating-point numbers, and key/value pairs of integers. Our results demonstrate that our approach is faster than two libraries of reference: the GNU \emph{C++} sort algorithm by a speedup factor of 4, and the Intel IPP library by a speedup factor of 1.4.
Learning the structure of Bayesian Networks: A quantitative assessment of the effect of different algorithmic schemes
Venue: arXiv cs.LG 2018
Year: 2018

One of the most challenging tasks when adopting Bayesian Networks (BNs) is the one of learning their structure from data. This task is complicated by the huge search space of possible solutions, and by the fact that the problem is NP-hard. Hence, full enumeration of all the possible solutions is not always feasible and approximations are often required. However, to the best of our knowledge, a quantitative analysis of the performance and characteristics of the different heuristics to solve this problem has never been done before. For this reason, in this work, we provide a detailed comparison of many different state-of-the-arts methods for structural learning on simulated data considering both BNs with discrete and continuous variables, and with different rates of noise in the data. In particular, we investigate the performance of different widespread scores and algorithmic approaches proposed for the inference and the statistical pitfalls within them.
Matrix Completion and Related Problems via Strong Duality
Venue: arXiv cs.DS 2018
Year: 2018

This work studies the strong duality of non-convex matrix factorization problems: we show that under certain dual conditions, these problems and its dual have the same optimum. This has been well understood for convex optimization, but little was known for non-convex problems. We propose a novel analytical framework and show that under certain dual conditions, the optimal solution of the matrix factorization program is the same as its bi-dual and thus the global optimality of the non-convex program can be achieved by solving its bi-dual which is convex. These dual conditions are satisfied by a wide class of matrix factorization problems, although matrix factorization problems are hard to solve in full generality. This analytical framework may be of independent interest to non-convex optimization more broadly. We apply our framework to two prototypical matrix factorization problems: matrix completion and robust Principal Component Analysis (PCA). These are examples of efficiently recovering a hidden matrix given limited reliable observations of it. Our framework shows that exact recoverability and strong duality hold with nearly-optimal sample complexity guarantees for matrix completion and robust PCA.
SIT: A Lightweight Encryption Algorithm for Secure Internet of Things
Venue: arXiv cs.CR 2018
Year: 2018

The Internet of Things (IoT) being a promising technology of the future is expected to connect billions of devices. The increased number of communication is expected to generate mountains of data and the security of data can be a threat. The devices in the architecture are essentially smaller in size and low powered. Conventional encryption algorithms are generally computationally expensive due to their complexity and requires many rounds to encrypt, essentially wasting the constrained energy of the gadgets. Less complex algorithm, however, may compromise the desired integrity. In this paper we propose a lightweight encryption algorithm named as Secure IoT (SIT). It is a 64-bit block cipher and requires 64-bit key to encrypt the data. The architecture of the algorithm is a mixture of feistel and a uniform substitution-permutation network. Simulations result shows the algorithm provides substantial security in just five encryption rounds. The hardware implementation of the algorithm is done on a low cost 8-bit micro-controller and the results of code size, memory utilization and encryption/decryption execution cycles are compared with benchmark encryption algorithms. The MATLAB code for relevant simulations is available online at https://goo.gl/Uw7E0W.
Structural Parameters, Tight Bounds, and Approximation for (k,r)-Center
Venue: arXiv cs.CC 2018
Year: 2018

In $(k,r)$-Center we are given a (possibly edge-weighted) graph and are asked to select at most $k$ vertices (centers), so that all other vertices are at distance at most $r$ from a center. In this paper we provide a number of tight fine-grained bounds on the complexity of this problem with respect to various standard graph parameters. Specifically: - For any $r\ge 1$, we show an algorithm that solves the problem in $O^*((3r+1)^{\textrm{cw}})$ time, where $\textrm{cw}$ is the clique-width of the input graph, as well as a tight SETH lower bound matching this algorithm's performance. As a corollary, for $r=1$, this closes the gap that previously existed on the complexity of Dominating Set parameterized by $\textrm{cw}$. - We strengthen previously known FPT lower bounds, by showing that $(k,r)$-Center is W[1]-hard parameterized by the input graph's vertex cover (if edge weights are allowed), or feedback vertex set, even if $k$ is an additional parameter. Our reductions imply tight ETH-based lower bounds. Finally, we devise an algorithm parameterized by vertex cover for unweighted graphs. - We show that the complexity of the problem parameterized by tree-depth is $2^{Θ(\textrm{td}^2)}$ by showing an algorithm of this complexity and a tight ETH-based lower bound. We complement these mostly negative results by providing FPT approximation schemes parameterized by clique-width or treewidth which work efficiently independently of the values of $k,r$. In particular, we give algorithms which, for any $ε>0$, run in time $O^*((\textrm{tw}/ε)^{O(\textrm{tw})})$, $O^*((\textrm{cw}/ε)^{O(\textrm{cw})})$ and return a $(k,(1+ε)r)$-center, if a $(k,r)$-center exists, thus circumventing the problem's W-hardness.
Autocorrelation Function for Dispersion-Free Fiber Channels with Distributed Amplification
Venue: arXiv cs.IT 2018
Year: 2018

Optical fiber signals with high power exhibit spectral broadening that seems to limit capacity. To study spectral broadening, the autocorrelation function of the output signal given the input signal is derived for a simplified fiber model that has zero dispersion, distributed optical amplification (OA), and idealized spatial noise processes. The autocorrelation function is used to upper bound the output power of bandlimited or time-resolution limited receivers, and thereby to bound spectral broadening and the capacity of receivers with thermal noise. The output power scales at most as the square-root of the launch power, and thus capacity scales at most as one-half the logarithm of the launch power. The propagating signal bandwidth scales at least as the square-root of the launch power. However, in practice the OA bandwidth should exceed the signal bandwidth to compensate attenuation. Hence, there is a launch power threshold beyond which the fiber model loses practical relevance. Nevertheless, for the mathematical model an upper bound on capacity is developed when the OA bandwidth scales as the square-root of the launch power, in which case capacity scales at most as the inverse fourth root of the launch power.
Channel Estimation for Diffusive MIMO Molecular Communications
Venue: arXiv cs.IT 2018
Year: 2018

In diffusion-based communication, as for molecular systems, the achievable data rate is very low due to the slow nature of diffusion and the existence of severe inter-symbol interference (ISI). Multiple-input multiple-output (MIMO) technique can be used to improve the data rate. Knowledge of channel impulse response (CIR) is essential for equalization and detection in MIMO systems. This paper presents a training-based CIR estimation for diffusive MIMO (D-MIMO) channels. Maximum likelihood and least-squares estimators are derived, and the training sequences are designed to minimize the corresponding Cramér-Rao bound. Sub-optimal estimators are compared to Cramér-Rao bound to validate their performance.
Remaining Idle Time Aware Intelligent Channel Bonding Schemes for Cognitive Radio Sensor Networks
Venue: arXiv cs.NI 2018
Year: 2018

Channel Bonding (CB) is a technique used to provide larger bandwidth to users. It has been applied to various networks such as wireless local area networks (WLANs), Wireless Sensor Networks (WSNs), Cognitive Radio Networks (CRNs), and Cognitive Radio Sensor Networks (CRSNs). The implementation of CB in CRSNs needs special attention as Primary Radio (PR) nodes traffic must be protected from any harmful interference by Cognitive Radio (CR) nodes. On the other hand, CR nodes need to communicate without interruption to meet their data rate requirements. If CR nodes perform frequent channel switching due to PR traffic then it will be difficult to meet their quality of service (QoS) and data rate requirements. So, CR nodes need to select those channels which are stable. By stable, we mean those channels which cause less harmful interference to PR nodes and having less PR activity or long remaining idle time. In this paper, we propose our two approaches Remaining Idle Time aware intelligent Channel Bonding (RITCB) and Remaining Idle Time aware Intelligent Channel Bonding with Interference Prevention (RITCB-IP) for cognitive radio sensor networks which select those channels for CB which have longest remaining idle time. We compare our approaches with four schemes PRACB, SWA, KNOWS and AGILE. Simulation results show that our proposed approaches RITCB and RITCB-IP decrease harmful interference (HIR) and increases the life time of cognitive radio sensor nodes.
The Payoff Region of a Strategic Game and Its Extreme Points
Venue: arXiv cs.GT 2018
Year: 2018

The range of a payoff function for an $n$-player finite strategic game is investigated using a novel approach, the notion of extreme points of a non-convex set. The shape of a noncooperative payoff region can be estimated using extreme points and supporting hyperplanes of the cooperative payoff region. A basic structural characteristic of a noncooperative payoff region is that any of its subregions must be non-strictly convex if the subregion contains a relative neighborhood of a point on its boundary. Besides, applying the properties of extreme points of a noncooperative payoff region is a simple and effective way to prove some results about Pareto efficiency and social efficiency in game theory.
Wireless Channel Modeling Perspectives for Ultra-Reliable Low Latency Communications
Venue: arXiv cs.IT 2018
Year: 2018

Ultra-Reliable Low Latency Communication (URLLC) is one of the distinctive features of the upcoming 5G wireless communication, going down to packet error rates (PER) of $10^{-9}$. In this paper we discuss the statistical properties of the wireless channel models that are relevant for characterization of the lower tail of the Cumulative Distribution Function (CDF). We show that, for a wide range of channel models, the outage probability at URLLC levels can be approximated by a simple power law expression, whose exponent and offset depend on the actual channel model. The main insights from the analysis can be summarized as follows: (1) the two-wave model and the impact of shadowing in combined models lead to pessimistic predictions of the fading in the URLLC region; (2) the CDFs of models that contain single cluster diffuse components have slopes that correspond to the slope of a Rayleigh fading, and (3) multi-cluster diffuse components can result in different slopes. We apply our power law approximation results to analyze the performance of receiver diversity schemes for URLLC-relevant statistics and obtain a new simplified expression for Maximum Ratio Combining (MRC) in channels with power law tail statistics.
Incidence Choosability of Graphs
Venue: arXiv cs.DM 2018
Year: 2018

An incidence of a graph G is a pair (v, e) where v is a vertex of G and e is an edge of G incident with v. Two incidences (v, e) and (w, f) of G are adjacent whenever (i) v = w, or (ii) e = f , or (iii) vw = e or f. An incidence p-colouring of G is a mapping from the set of incidences of G to the set of colours {1,. .. , p} such that every two adjacent incidences receive distinct colours. Incidence colouring has been introduced by Brualdi and Quinn Massey in 1993 and, since then, studied by several authors. In this paper, we introduce and study the list version of incidence colouring. We determine the exact value of -- or upper bounds on -- the incidence choice number of several classes of graphs, namely square grids, Halin graphs, cactuses and Hamiltonian cubic graphs.
Streaming Algorithm for Euler Characteristic Curves of Multidimensional Images
Venue: arXiv cs.CV 2018
Year: 2018

We present an efficient algorithm to compute Euler characteristic curves of gray scale images of arbitrary dimension. In various applications the Euler characteristic curve is used as a descriptor of an image. Our algorithm is the first streaming algorithm for Euler characteristic curves. The usage of streaming removes the necessity to store the entire image in RAM. Experiments show that our implementation handles terabyte scale images on commodity hardware. Due to lock-free parallelism, it scales well with the number of processor cores. Our software---CHUNKYEuler---is available as open source on Bitbucket. Additionally, we put the concept of the Euler characteristic curve in the wider context of computational topology. In particular, we explain the connection with persistence diagrams.
Cross-lingual Distillation for Text Classification
Venue: arXiv cs.CL 2018
Year: 2018

Cross-lingual text classification(CLTC) is the task of classifying documents written in different languages into the same taxonomy of categories. This paper presents a novel approach to CLTC that builds on model distillation, which adapts and extends a framework originally proposed for model compression. Using soft probabilistic predictions for the documents in a label-rich language as the (induced) supervisory labels in a parallel corpus of documents, we train classifiers successfully for new languages in which labeled training data are not available. An adversarial feature adaptation technique is also applied during the model training to reduce distribution mismatch. We conducted experiments on two benchmark CLTC datasets, treating English as the source language and German, French, Japan and Chinese as the unlabeled target languages. The proposed approach had the advantageous or comparable performance of the other state-of-art methods.
The Salesman's Improved Tours for Fundamental Classes
Venue: arXiv cs.DM 2018
Year: 2018

Finding the exact integrality gap $α$ for the LP relaxation of the metric Travelling Salesman Problem (TSP) has been an open problem for over thirty years, with little progress made. It is known that $4/3 \leq α\leq 3/2$, and a famous conjecture states $α= 4/3$. For this problem, essentially two "fundamental" classes of instances have been proposed. This fundamental property means that in order to show that the integrality gap is at most $ρ$ for all instances of metric TSP, it is sufficient to show it only for the instances in the fundamental class. However, despite the importance and the simplicity of such classes, no apparent effort has been deployed for improving the integrality gap bounds for them. In this paper we take a natural first step in this endeavour, and consider the $1/2$-integer points of one such class. We successfully improve the upper bound for the integrality gap from $3/2$ to $10/7$ for a superclass of these points, as well as prove a lower bound of $4/3$ for the superclass. Our methods involve innovative applications of tools from combinatorial optimization which have the potential to be more broadly applied.
Proving Correctness of Concurrent Objects by Validating Linearization Points
Venue: arXiv cs.DC 2018
Year: 2018

Concurrent data structures or CDS such as concurrent stacks, queues, sets etc. have become very popular in the past few years partly due to the rise of multi-core systems. But one of the greatest challenges with CDSs has been developing correct structures and then proving the correctness of these structures. We believe that techniques that help prove the correctness of these CDSs can also guide in developing new CDSs. An intuitive technique to prove the correctness of CDSs is using Linearization Points or LPs. An LP is an atomic event in the execution interval of each method such that the execution of the entire method seems to have taken place in the instant of that event. One of the main challenges with the LP based approach is to identify the correct LPs of a CDS. Identifying the correct LPs can be deceptively wrong in many cases. In fact, in many cases, the LP identified or even worse the CDS itself could be wrong. To address these issues, several automatic tools for verifying linearizability have been developed. But we believe that these tools don't provide insight to a programmer to develop the correct concurrent programs or identify the LPs. Considering the complexity of developing a CDS and verifying its correctness, we address the most basic problem of this domain in this paper: given the set of LPs of a CDS, how to show its correctness? We assume that we are given a CDS and its LPs. We have developed a hand-crafted technique of proving the correctness of the CDS by validating its LPs. As observed earlier, identifying the correct LPs is very tricky and erroneous. But since our technique is hand-crafted, we believe that the process of proving correctness might provide insight to identify the correct LPs, if the currently chosen LP is incorrect. We also believe that this technique might also offer the programmer some insight to develop more efficient variants of the CDS.