OpenRaiser/Intern-Atlas huggingface dataset:
Link Selection for Secure Cooperative Networks with Buffer-Aided Relaying
Venue: arXiv cs.IT 2018
Year: 2018

This paper investigates the secure communication in a two-hop cooperative wireless network, where a buffer-aided relay is utilized to forward data from the source to destination, and a passive eavesdropper attempts to intercept data transmission from both the source and relay. Depending on the availability of instantaneous channel state information of the source, two cases of transmission mechanisms, i.e., adaptive-rate transmission and fixed-rate transmission are considered. To enhance the security of the system, novel link selection policies are proposed for both cases to select source-to-relay, relay-to-destination, or no link transmission based on the channels qualities. Closed-form expressions are derived for the end-to-end secrecy outage probability (SOP), secrecy outage capacity (SOC), and exact secrecy throughput (EST), respectively. Furthermore, we prove the condition that EST reaches its maximum, and explore how to minimize the SOP and maximize the SOC by optimizing the link selection parameters. Finally, simulations are conducted to demonstrate the validity of our theoretical performance evaluation, and extensive numerical results are provided to illustrate the efficiency of the proposed link selection polices for the secure communication in two-hop cooperative networks.
Optimal Beamforming for Physical Layer Security in MISO Wireless Networks
Venue: arXiv cs.IT 2018
Year: 2018

A wireless network of multiple transmitter-user pairs overheard by an eavesdropper, where the transmitters are equipped with multiple antennas while the users and eavesdropper are equipped with a single antenna, is considered. At different levels of wireless channel knowledge, the problem of interest is beamforming to optimize the users' quality-of-service (QoS) in terms of their secrecy throughputs or maximize the network's energy efficiency under users' QoS. All these problems are seen as very difficult optimization problems with many nonconvex constraints and nonlinear equality constraints in beamforming vectors. The paper develops path-following computational procedures of low-complexity and rapid convergence for the optimal beamforming solution. Their practicability is demonstrated through numerical examples.
Dynamic Cloud Network Control under Reconfiguration Delay and Cost
Venue: arXiv cs.NI 2018
Year: 2018

Network virtualization and programmability allow operators to deploy a wide range of services over a common physical infrastructure and elastically allocate cloud and network resources according to changing requirements. While the elastic reconfiguration of virtual resources enables dynamically scaling capacity in order to support service demands with minimal operational cost, reconfiguration operations make resources unavailable during a given time period and may incur additional cost. In this paper, we address the dynamic cloud network control problem under non-negligible reconfiguration delay and cost. We show that while the capacity region remains unchanged regardless of the reconfiguration delay/cost values, a reconfiguration-agnostic policy may fail to guarantee throughput-optimality and minimum cost under nonzero reconfiguration delay/cost. We then present an adaptive dynamic cloud network control policy that allows network nodes to make local flow scheduling and resource allocation decisions while controlling the frequency of reconfiguration in order to support any input rate in the capacity region and achieve arbitrarily close to minimum cost for any finite reconfiguration delay/cost values.
A Natural Generalization of Stable Matching Solved via New Insights into Ideal Cuts
Venue: arXiv cs.DS 2018
Year: 2018

We study a natural generalization of stable matching to the maximum weight stable matching problem and we obtain a combinatorial polynomial time algorithm for it by reducing it to the problem of finding a maximum weight ideal cut in a DAG. We give the first polynomial time algorithm for the latter problem; this algorithm is also combinatorial. The combinatorial nature of our algorithms not only means that they are efficient but also that they enable us to obtain additional structural and algorithmic results: - We show that the set, $\cal M'$, of maximum weight stable matchings forms a sublattice $\cal L'$ of the lattice $\cal L$ of all stable matchings. - We give an efficient algorithm for finding boy-optimal and girl-optimal matchings in $\cal M'$. - We generalize the notion of rotation, a central structural notion in the context of the stable matching problem, to meta-rotation. Just as rotations help traverse the lattice of all stable matchings, macro-rotations help traverse the sublattice over $\cal M'$.
Technological research in the EU is less efficient than the world average. EU research policy risks Europeans' future
Venue: arXiv cs.DL 2018
Year: 2018

We have studied the efficiency of research in the EU by a percentile-based citation approach that analyzes the distribution of country papers among the world papers. Going up in the citation scale, the frequency of papers from efficient countries increases while the frequency from inefficient countries decreases. In the percentile-based approach, this trend, which is permanent at any citation level, is measured by the ep index that equals the Ptop 1%/Ptop 10% ratio. By using the ep index we demonstrate that EU research on fast-evolving technological topics is less efficient than the world average and that the EU is far from being able to compete with the most advanced countries. The ep index also shows that the USA is well ahead of the EU in both fast- and slow-evolving technologies, which suggests that the advantage of the USA over the EU in innovation is due to low research efficiency in the EU. In accord with some previous studies, our results show that the European Commission's ongoing claims about the excellence of EU research are based on a wrong diagnosis. The EU must focus its research policy on the improvement of its inefficient research. Otherwise, the future of Europeans is at risk.
Linear Equations with Ordered Data
Venue: arXiv cs.LO 2018
Year: 2018

Following a recently considered generalization of linear equations to unordered data vectors, we perform a further generalization to ordered data vectors. These generalized equations naturally appear in the analysis of vector addition systems (or Petri nets) extended with ordered data. We show that nonnegative-integer solvability of linear equations is computationally equivalent (up to an exponential blowup) with the reachability problem for (plain) vector addition systems. This high complexity is surprising, and contrasts with NP-completeness for unordered data vectors. Also surprisingly, we achieve polynomial time complexity of the solvability problem when the nonnegative-integer restriction on solutions is dropped.
Stability of meanings versus rate of replacement of words: an experimental test
Venue: arXiv cs.CL 2018
Year: 2018

The words of a language are randomly replaced in time by new ones, but it has long been known that words corresponding to some items (meanings) are less frequently replaced than others. Usually, the rate of replacement for a given item is not directly observable, but it is inferred by the estimated stability which, on the contrary, is observable. This idea goes back a long way in the lexicostatistical literature, nevertheless nothing ensures that it gives the correct answer. The family of Romance languages allows for a direct test of the estimated stabilities against the replacement rates since the proto-language (Latin) is known and the replacement rates can be explicitly computed. The output of the test is threefold:first, we prove that the standard approach which tries to infer the replacement rates trough the estimated stabilities is sound; second, we are able to rewrite the fundamental formula of Glottochronology for a non universal replacement rate (a rate which depends on the item); third, we give indisputable evidence that the stability ranking is far from being the same for different families of languages. This last result is also supported by comparison with the Malagasy family of dialects. As a side result we also provide some evidence that Vulgar Latin and not Late Classical Latin is at the root of modern Romance languages.
Multi-resolution Tensor Learning for Large-Scale Spatial Data
Venue: arXiv cs.LG 2018
Year: 2018

High-dimensional tensor models are notoriously computationally expensive to train. We present a meta-learning algorithm, MMT, that can significantly speed up the process for spatial tensor models. MMT leverages the property that spatial data can be viewed at multiple resolutions, which are related by coarsening and finegraining from one resolution to another. Using this property, MMT learns a tensor model by starting from a coarse resolution and iteratively increasing the model complexity. In order to not "over-train" on coarse resolution models, we investigate an information-theoretic fine-graining criterion to decide when to transition into higher-resolution models. We provide both theoretical and empirical evidence for the advantages of this approach. When applied to two real-world large-scale spatial datasets for basketball player and animal behavior modeling, our approach demonstrate 3 key benefits: 1) it efficiently captures higher-order interactions (i.e., tensor latent factors), 2) it is orders of magnitude faster than fixed resolution learning and scales to very fine-grained spatial resolutions, and 3) it reliably yields accurate and interpretable models.
Accurate Contact Localization and Indentation Depth Prediction With an Optics-based Tactile Sensor
Venue: arXiv cs.RO 2018
Year: 2018

Traditional methods to achieve high localization accuracy with tactile sensors usually use a matrix of miniaturized individual sensors distributed on the area of interest. This approach usually comes at a price of increased complexity in fabrication and circuitry, and can be hard to adapt for non planar geometries. We propose to use low cost optic components mounted on the edges of the sensing area to measure how light traveling through an elastomer is affected by touch. Multiple light emitters and receivers provide us with a rich signal set that contains the necessary information to pinpoint both the location and depth of an indentation with high accuracy. We demonstrate sub-millimeter accuracy on location and depth on a 20mm by 20mm active sensing area. Our sensor provides high depth sensitivity as a result of two different modalities in how light is guided through our elastomer. This method results in a low cost, easy to manufacture sensor. We believe this approach can be adapted to cover non-planar surfaces, simplifying future integration in robot skin applications.
Expert System for Diagnosis of Chest Diseases Using Neural Networks
Venue: arXiv cs.AI 2018
Year: 2018

This article represents one of the contemporary trends in the application of the latest methods of information and communication technology for medicine through an expert system helps the doctor to diagnose some chest diseases which is important because of the frequent spread of chest diseases nowadays in addition to the overlap symptoms of these diseases, which is difficult to right diagnose by doctors with several algorithms: Forward Chaining, Backward Chaining, Neural Network(Back Propagation). However, this system cannot replace the doctor function, but it can help the doctor to avoid wrong diagnosis and treatments. It can also be developed in such a way to help the novice doctors.
Almost logarithmic-time space optimal leader election in population protocols
Venue: arXiv cs.DC 2018
Year: 2018

The model of population protocols refers to a large collection of simple indistinguishable entities, frequently called {\em agents}. The agents communicate and perform computation through pairwise interactions. We study fast and space efficient leader election in population of cardinality $n$ governed by a random scheduler, where during each time step the scheduler uniformly at random selects for interaction exactly one pair of agents. We propose the first $o(\log^2 n)$-time leader election protocol. Our solution operates in expected parallel time $O(\log n\log\log n)$ which is equivalent to $O(n \log n\log\log n)$ pairwise interactions. This is the fastest currently known leader election algorithm in which each agent utilises asymptotically optimal number of $O(\log\log n)$ states. The new protocol incorporates and amalgamates successfully the power of assorted {\em synthetic coins} with variable rate {\em phase clocks}.
A Deterministic Protocol for Sequential Asymptotic Learning
Venue: arXiv cs.GT 2018
Year: 2018

In the classic herding model, agents receive private signals about an underlying binary state of nature, and act sequentially to choose one of two possible actions, after observing the actions of their predecessors. We investigate what types of behaviors lead to asymptotic learning, where agents will eventually converge to the right action in probability. It is known that for rational agents and bounded signals, there will not be asymptotic learning. Does it help if the agents can be cooperative rather than act selfishly? This is simple to achieve if the agents are allowed to use randomized protocols. In this paper, we provide the first deterministic protocol under which asymptotic learning occurs. In addition, our protocol has the advantage of being much simpler than previous protocols.
Automated Playtesting with Procedural Personas through MCTS with Evolved Heuristics
Venue: arXiv cs.AI 2018
Year: 2018

This paper describes a method for generative player modeling and its application to the automatic testing of game content using archetypal player models called procedural personas. Theoretically grounded in psychological decision theory, procedural personas are implemented using a variation of Monte Carlo Tree Search (MCTS) where the node selection criteria are developed using evolutionary computation, replacing the standard UCB1 criterion of MCTS. Using these personas we demonstrate how generative player models can be applied to a varied corpus of game levels and demonstrate how different play styles can be enacted in each level. In short, we use artificially intelligent personas to construct synthetic playtesters. The proposed approach could be used as a tool for automatic play testing when human feedback is not readily available or when quick visualization of potential interactions is necessary. Possible applications include interactive tools during game development or procedural content generation systems where many evaluations must be conducted within a short time span.
Layer-wise synapse optimization for implementing neural networks on general neuromorphic architectures
Venue: arXiv cs.NE 2018
Year: 2018

Deep artificial neural networks (ANNs) can represent a wide range of complex functions. Implementing ANNs in Von Neumann computing systems, though, incurs a high energy cost due to the bottleneck created between CPU and memory. Implementation on neuromorphic systems may help to reduce energy demand. Conventional ANNs must be converted into equivalent Spiking Neural Networks (SNNs) in order to be deployed on neuromorphic chips. This paper presents a way to perform this translation. We map the ANN weights to SNN synapses layer-by-layer by forming a least-square-error approximation problem at each layer. An optimal set of synapse weights may then be found for a given choice of ANN activation function and SNN neuron. Using an appropriate constrained solver, we can generate SNNs compatible with digital, analog, or hybrid chip architectures. We present an optimal node pruning method to allow SNN layer sizes to be set by the designer. To illustrate this process, we convert three ANNs, including one convolutional network, to SNNs. In all three cases, a simple linear program solver was used. The experiments show that the resulting networks maintain agreement with the original ANN and excellent performance on the evaluation tasks. The networks were also reduced in size with little loss in task performance.
Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors)
Venue: arXiv cs.DS 2018
Year: 2018

We examine the problem of almost-uniform sampling proper $q$-colorings of a graph whose maximum degree is $Δ$. A famous result, discovered independently by Jerrum(1995) and Salas and Sokal(1997), is that, assuming $q > (2+δ) Δ$, the Glauber dynamics (a.k.a. single-site dynamics) for this problem has mixing time $O(n \log n)$, where $n$ is the number of vertices, and thus provides a nearly linear time sampling algorithm for this problem. A natural question is the extent to which this algorithm can be parallelized. Previous work Feng, Sun and Yin [PODC'17] has shown that a $O(Δ\log n)$ time parallelized algorithm is possible, and that $Ω(\log n)$ time is necessary. We give a distributed sampling algorithm, which we call the Lazy Local Metropolis Algorithm, that achieves an optimal parallelization of this classic algorithm. It improves its predecessor, the Local Metropolis algorithm of Feng, Sun and Yin [PODC'17], by introducing a step of distributed symmetry breaking that helps the mixing of the distributed sampling algorithm. For sampling almost-uniform proper $q$-colorings of graphs $G$ on $n$ vertices, we show that the Lazy Local Metropolis algorithm achieves an optimal $O(\log n)$ mixing time if either of the following conditions is true for an arbitrary constant $δ>0$: $\bullet$ $q\ge(2+δ)Δ$, on general graphs with maximum degree $Δ$; $\bullet$ $q \geq (α^* + δ)Δ$, where $α^* \approx 1.763$ satisfies $α^* = \mathrm{e}^{1/α^*}$, on graphs with sufficiently large maximum degree $Δ\ge Δ_0(δ)$ and girth at least $9$.
Deep Reinforcement Learning for Dynamic Multichannel Access in Wireless Networks
Venue: arXiv cs.NI 2018
Year: 2018

We consider a dynamic multichannel access problem, where multiple correlated channels follow an unknown joint Markov model. A user at each time slot selects a channel to transmit data and receives a reward based on the success or failure of the transmission. The objective is to find a policy that maximizes the expected long-term reward. The problem is formulated as a partially observable Markov decision process (POMDP) with unknown system dynamics. To overcome the challenges of unknown system dynamics as well as prohibitive computation, we apply the concept of reinforcement learning and implement a Deep Q-Network (DQN) that can deal with large state space without any prior knowledge of the system dynamics. We provide an analytical study on the optimal policy for fixed-pattern channel switching with known system dynamics and show through simulations that DQN can achieve the same optimal performance without knowing the system statistics. We compare the performance of DQN with a Myopic policy and a Whittle Index-based heuristic through both simulations as well as real-data trace and show that DQN achieves near-optimal performance in more complex situations. Finally, we propose an adaptive DQN approach with the capability to adapt its learning in time-varying, dynamic scenarios.
Agile Amulet: Real-Time Salient Object Detection with Contextual Attention
Venue: arXiv cs.CV 2018
Year: 2018

This paper proposes an Agile Aggregating Multi-Level feaTure framework (Agile Amulet) for salient object detection. The Agile Amulet builds on previous works to predict saliency maps using multi-level convolutional features. Compared to previous works, Agile Amulet employs some key innovations to improve training and testing speed while also increase prediction accuracy. More specifically, we first introduce a contextual attention module that can rapidly highlight most salient objects or regions with contextual pyramids. Thus, it effectively guides the learning of low-layer convolutional features and tells the backbone network where to look. The contextual attention module is a fully convolutional mechanism that simultaneously learns complementary features and predicts saliency scores at each pixel. In addition, we propose a novel method to aggregate multi-level deep convolutional features. As a result, we are able to use the integrated side-output features of pre-trained convolutional networks alone, which significantly reduces the model parameters leading to a model size of 67 MB, about half of Amulet. Compared to other deep learning based saliency methods, Agile Amulet is of much lighter-weight, runs faster (30 fps in real-time) and achieves higher performance on seven public benchmarks in terms of both quantitative and qualitative evaluation.
CASPaxos: Replicated State Machines without logs
Venue: arXiv cs.DC 2018
Year: 2018

CASPaxos is a wait-free, linearizable, multi-writer multi-reader register in unreliable, asynchronous networks supporting arbitrary update operations including compare-and-set (CAS). The register acts as a replicated state machine providing an interface for changing its value by applying an arbitrary user-provided function (a command). Unlike Multi-Paxos and Raft which replicate the log of commands, CASPaxos replicates state, thus avoiding associated complexity, reducing write amplification, increasing concurrency of disk operations and hardware utilization. The paper describes CASPaxos, proves its safety properties and evaluates the characteristics of a CASPaxos-based prototype of key-value storage.
Discovering Hidden Topical Hubs and Authorities in Online Social Networks
Venue: arXiv cs.SI 2018
Year: 2018

Finding influential users in online social networks is an important problem with many possible useful applications. HITS and other link analysis methods, in particular, have been often used to identify hub and authority users in web graphs and online social networks. These works, however, have not considered topical aspect of links in their analysis. A straightforward approach to overcome this limitation is to first apply topic models to learn the user topics before applying the HITS algorithm. In this paper, we instead propose a novel topic model known as Hub and Authority Topic (HAT) model to combine the two process so as to jointly learn the hub, authority and topical interests. We evaluate HAT against several existing state-of-the-art methods in two aspects: (i) modeling of topics, and (ii) link recommendation. We conduct experiments on two real-world datasets from Twitter and Instagram. Our experiment results show that HAT is comparable to state-of-the-art topic models in learning topics and it outperforms the state-of-the-art in link recommendation task.
Camera-based vehicle velocity estimation from monocular video
Venue: arXiv cs.CV 2018
Year: 2018

This paper documents the winning entry at the CVPR2017 vehicle velocity estimation challenge. Velocity estimation is an emerging task in autonomous driving which has not yet been thoroughly explored. The goal is to estimate the relative velocity of a specific vehicle from a sequence of images. In this paper, we present a light-weight approach for directly regressing vehicle velocities from their trajectories using a multilayer perceptron. Another contribution is an explorative study of features for monocular vehicle velocity estimation. We find that light-weight trajectory based features outperform depth and motion cues extracted from deep ConvNets, especially for far-distance predictions where current disparity and optical flow estimators are challenged significantly. Our light-weight approach is real-time capable on a single CPU and outperforms all competing entries in the velocity estimation challenge. On the test set, we report an average error of 1.12 m/s which is comparable to a (ground-truth) system that combines LiDAR and radar techniques to achieve an error of around 0.71 m/s.