OpenRaiser/Intern-Atlas huggingface dataset:
Sequential Decision Algorithms for Measurement-Based Impromptu Deployment of a Wireless Relay Network along a Line
Venue: arXiv cs.NI 2017
Year: 2017

We are motivated by the need, in some applications, for impromptu or as-you-go deployment of wireless sensor networks. A person walks along a line, starting from a sink node (e.g., a base-station), and proceeds towards a source node (e.g., a sensor) which is at an a priori unknown location. At equally spaced locations, he makes link quality measurements to the previous relay, and deploys relays at some of these locations, with the aim to connect the source to the sink by a multihop wireless path. In this paper, we consider two approaches for impromptu deployment: (i) the deployment agent can only move forward (which we call a pure as-you-go approach), and (ii) the deployment agent can make measurements over several consecutive steps before selecting a placement location among them (which we call an explore-forward approach). We consider a light traffic regime, and formulate the problem as a Markov decision process, where the trade-off is among the power used by the nodes, the outage probabilities in the links, and the number of relays placed per unit distance. We obtain the structures of the optimal policies for the pure as-you-go approach as well as for the explore-forward approach. We also consider natural heuristic algorithms, for comparison. Numerical examples show that the explore-forward approach significantly outperforms the pure as-you-go approach. Next, we propose two learning algorithms for the explore-forward approach, based on Stochastic Approximation, which asymptotically converge to the set of optimal policies, without using any knowledge of the radio propagation model. We demonstrate numerically that the learning algorithms can converge (as deployment progresses) to the set of optimal policies reasonably fast and, hence, can be practical, model-free algorithms for deployment over large regions.
Author Name Disambiguation by Using Deep Neural Network
Venue: arXiv cs.DL 2017
Year: 2017

Author name ambiguity decreases the quality and reliability of information retrieved from digital libraries. Existing methods have tried to solve this problem by predefining a feature set based on expert's knowledge for a specific dataset. In this paper, we propose a new approach which uses deep neural network to learn features automatically from data. Additionally, we propose the general system architecture for author name disambiguation on any dataset. In this research, we evaluate the proposed method on a dataset containing Vietnamese author names. The results show that this method significantly outperforms other methods that use predefined feature set. The proposed method achieves 99.31% in terms of accuracy. Prediction error rate decreases from 1.83% to 0.69%, i.e., it decreases by 1.14%, or 62.3% relatively compared with other methods that use predefined feature set (Table 3).
Signal Processing on Graphs: Causal Modeling of Unstructured Data
Venue: arXiv cs.IT 2017
Year: 2017

Many applications collect a large number of time series, for example, the financial data of companies quoted in a stock exchange, the health care data of all patients that visit the emergency room of a hospital, or the temperature sequences continuously measured by weather stations across the US. These data are often referred to as unstructured. A first task in its analytics is to derive a low dimensional representation, a graph or discrete manifold, that describes well the interrelations among the time series and their intrarelations across time. This paper presents a computationally tractable algorithm for estimating this graph that structures the data. The resulting graph is directed and weighted, possibly capturing causal relations, not just reciprocal correlations as in many existing approaches in the literature. A convergence analysis is carried out. The algorithm is demonstrated on random graph datasets and real network time series datasets, and its performance is compared to that of related methods. The adjacency matrices estimated with the new method are close to the true graph in the simulated data and consistent with prior physical knowledge in the real dataset tested.
On Geometry of Interaction for Polarized Linear Logic
Venue: arXiv cs.LO 2017
Year: 2017

We present Geometry of Interaction (GoI) models for Multiplicative Polarized Linear Logic, MLLP, which is the multiplicative fragment of Olivier Laurent's Polarized Linear Logic. This is done by uniformly adding multipoints to various categorical models of GoI. Multipoints are shown to play an essential role in semantically characterizing the dynamics of proof networks in polarized proof theory. For example, they permit us to characterize the key feature of polarization, focusing, as well as being fundamental to our construction of concrete polarized GoI models. Our approach to polarized GoI involves two independent studies, based on different categorical perspectives of GoI. (i) Inspired by the work of Abramsky, Haghverdi, and Scott, a polarized GoI situation is defined in which multipoints are added to a traced monoidal category equipped with a reflexive object $U$. Using this framework, categorical versions of Girard's Execution formula are defined, as well as the GoI interpretation of MLLP, proofs. Running the Execution formula is shown to characterize the focusing property (and thus polarities) as well as the dynamics of cut-elimination. (ii) The Int construction of Joyal-Street-Verity is another fundamental categorical structure for modelling GoI. Here, we investigate it in a multipointed setting. Our presentation yields a compact version of Hamano-Scott's polarized categories, and thus denotational models of MLLP. These arise from a contravariant duality between monoidal categories of positive and negative objects, along with an appropriate bimodule structure (representing "non-focused proofs") between them. Finally, as a special case of (ii) above, a compact model of MLLP is also presented based on Rel (the category of sets and relations) equipped with multi-points.
Achieving Secrecy Capacity of the Gaussian Wiretap Channel with Polar Lattices
Venue: arXiv cs.IT 2017
Year: 2017

In this work, an explicit wiretap coding scheme based on polar lattices is proposed to achieve the secrecy capacity of the additive white Gaussian noise (AWGN) wiretap channel. Firstly, polar lattices are used to construct secrecy-good lattices for the mod-$Λ_s$ Gaussian wiretap channel. Then we propose an explicit shaping scheme to remove this mod-$Λ_s$ front end and extend polar lattices to the genuine Gaussian wiretap channel. The shaping technique is based on the lattice Gaussian distribution, which leads to a binary asymmetric channel at each level for the multilevel lattice codes. By employing the asymmetric polar coding technique, we construct an AWGN-good lattice and a secrecy-good lattice with optimal shaping simultaneously. As a result, the encoding complexity for the sender and the decoding complexity for the legitimate receiver are both O(N logN log(logN)). The proposed scheme is proven to be semantically secure.
Reproducibility in Research: Systems, Infrastructure, Culture
Venue: arXiv cs.SE 2017
Year: 2017

The reproduction and replication of research results has become a major issue for a number of scientific disciplines. In computer science and related computational disciplines such as systems biology, the challenges closely revolve around the ability to implement (and exploit) novel algorithms and models. Taking a new approach from the literature and applying it to a new codebase frequently requires local knowledge missing from the published manuscripts and transient project websites. Alongside this issue, benchmarking, and the lack of open, transparent and fair benchmark sets present another barrier to the verification and validation of claimed results. In this paper, we outline several recommendations to address these issues, driven by specific examples from a range of scientific domains. Based on these recommendations, we propose a high-level prototype open automated platform for scientific software development which effectively abstracts specific dependencies from the individual researcher and their workstation, allowing easy sharing and reproduction of results. This new e-infrastructure for reproducible computational science offers the potential to incentivise a culture change and drive the adoption of new techniques to improve the quality and efficiency -- and thus reproducibility -- of scientific exploration.
Hyper Temporal Networks
Venue: arXiv cs.DS 2017
Year: 2017

Simple Temporal Networks (STNs) provide a powerful and general tool for representing conjunctions of maximum delay constraints over ordered pairs of temporal variables. In this paper we introduce Hyper Temporal Networks (HyTNs), a strict generalization of STNs, to overcome the limitation of considering only conjunctions of constraints but maintaining a practical efficiency in the consistency check of the instances. In a Hyper Temporal Network a single temporal hyperarc constraint may be defined as a set of two or more maximum delay constraints which is satisfied when at least one of these delay constraints is satisfied. HyTNs are meant as a light generalization of STNs offering an interesting compromise. On one side, there exist practical pseudo-polynomial time algorithms for checking consistency and computing feasible schedules for HyTNs. On the other side, HyTNs offer a more powerful model accommodating natural constraints that cannot be expressed by STNs like Trigger off exactly delta min before (after) the occurrence of the first (last) event in a set., which are used to represent synchronization events in some process aware information systems/workflow models proposed in the literature.
Diverse Palindromic Factorization is NP-Complete
Venue: arXiv cs.FL 2017
Year: 2017

We prove that it is NP-complete to decide whether a given string can be factored into palindromes that are each unique in the factorization.
Building Statistical Shape Spaces for 3D Human Modeling
Venue: arXiv cs.CV 2017
Year: 2017

Statistical models of 3D human shape and pose learned from scan databases have developed into valuable tools to solve a variety of vision and graphics problems. Unfortunately, most publicly available models are of limited expressiveness as they were learned on very small databases that hardly reflect the true variety in human body shapes. In this paper, we contribute by rebuilding a widely used statistical body representation from the largest commercially available scan database, and making the resulting model available to the community (visit http://humanshape.mpi-inf.mpg.de). As preprocessing several thousand scans for learning the model is a challenge in itself, we contribute by developing robust best practice solutions for scan alignment that quantitatively lead to the best learned models. We make implementations of these preprocessing steps also publicly available. We extensively evaluate the improved accuracy and generality of our new model, and show its improved performance for human body reconstruction from sparse input data.
The Adjusted Winner Procedure: Characterizations and Equilibria
Venue: arXiv cs.GT 2017
Year: 2017

The Adjusted Winner procedure is an important fair division mechanism proposed by Brams and Taylor for allocating goods between two parties. It has been used in practice for divorce settlements and analyzing political disputes. Assuming truthful declaration of the valuations, it computes an allocation that is envy-free, equitable and Pareto optimal. We show that Adjusted Winner admits several elegant characterizations, which further shed light on the outcomes reached with strategic agents. We find that the procedure may not admit pure Nash equilibria in either the discrete or continuous variants, but is guaranteed to have $ε$-Nash equilibria for each $ε$ > 0. Moreover, under informed tie-breaking, exact pure Nash equilibria always exist, are Pareto optimal, and their social welfare is at least 3/4 of the optimal.
A Unified Stochastic Hybrid System Approach to Aggregate Modeling of Responsive Loads
Venue: arXiv cs.SY 2017
Year: 2017

Aggregate load modeling is of fundamental importance for systematic analysis and design of various demand response strategies. Instead of keeping track of the trajectories of individual loads, the aggregate modeling problem focuses on characterizing the density evolution of the load population. Most existing models are only applicable to Thermostatically Controlled Loads (TCL) with first-order linear dynamics. This paper develops a unified aggregate modeling approach that can be used for general TCLs as well as deferrable loads. We propose a deterministic hybrid system model to describe individual load dynamics under demand response rules, and develop a general stochastic hybrid system (SHS) model to capture the population dynamics. We also derive a set of partial differential equations (PDE) that governs the probability density evolution of the SHS. Our results cannot be obtained using the exiting SHS tools in the literature as the proposed SHS model involves both random and deterministic switchings with general switching surfaces in multi-dimensional domains. The derived PDE model includes many existing aggregate load modeling results as special cases and can be used in many other realistic modeling scenarios that have not been studied in the literature.
Vectorized VByte Decoding
Venue: arXiv cs.IR 2017
Year: 2017

We consider the ubiquitous technique of VByte compression, which represents each integer as a variable length sequence of bytes. The low 7 bits of each byte encode a portion of the integer, and the high bit of each byte is reserved as a continuation flag. This flag is set to 1 for all bytes except the last, and the decoding of each integer is complete when a byte with a high bit of 0 is encountered. VByte decoding can be a performance bottleneck especially when the unpredictable lengths of the encoded integers cause frequent branch mispredictions. Previous attempts to accelerate VByte decoding using SIMD vector instructions have been disappointing, prodding search engines such as Google to use more complicated but faster-to-decode formats for performance-critical code. Our decoder (Masked VByte) is 2 to 4 times faster than a conventional scalar VByte decoder, making the format once again competitive with regard to speed.
Hitting Times in Markov Chains with Restart and their Application to Network Centrality
Venue: arXiv cs.PF 2017
Year: 2017

Motivated by applications in telecommunications, computer scienceand physics, we consider a discrete-time Markov process withrestart. At each step the process eitherwith a positive probability restarts from a given distribution, orwith the complementary probability continues according to a Markovtransition kernel. The main contribution of the present work is thatwe obtain an explicit expression for the expectation of the hittingtime (to a given target set) of the process with restart.The formula is convenient when considering the problem of optimizationof the expected hitting time with respect to the restart probability.We illustrate our results with two examplesin uncountable and countable state spaces andwith an application to network centrality.
Mechanism design for aggregating energy consumption and quality of service in speed scaling scheduling
Venue: arXiv cs.GT 2017
Year: 2017

We consider a strategic game, where players submit jobs to a machine that executes all jobs in a way that minimizes energy while respecting the given deadlines. The energy consumption is then charged to the players in some way. Each player wants to minimize the sum of that charge and of their job's deadline multiplied by a priority weight. Two charging schemes are studied, the proportional cost share which does not always admit pure Nash equilibria, and the marginal cost share, which does always admit pure Nash equilibria, at the price of overcharging by a constant factor.
A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences
Venue: arXiv cs.IT 2017
Year: 2017

Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity, and that lossless compression algorithms fall short at characterizing patterns other than statistical ones not different to entropy estimations, here we explore an alternative and complementary approach. We study formal properties of a Levin-inspired measure $m$ calculated from the output distribution of small Turing machines. We introduce and justify finite approximations $m_k$ that have been used in some applications as an alternative to lossless compression algorithms for approximating algorithmic (Kolmogorov-Chaitin) complexity. We provide proofs of the relevant properties of both $m$ and $m_k$ and compare them to Levin's Universal Distribution. We provide error estimations of $m_k$ with respect to $m$. Finally, we present an application to integer sequences from the Online Encyclopedia of Integer Sequences which suggests that our AP-based measures may characterize non-statistical patterns, and we report interesting correlations with textual, function and program description lengths of the said sequences.
Combining Existential Rules and Transitivity: Next Steps
Venue: arXiv cs.AI 2017
Year: 2017

We consider existential rules (aka Datalog+) as a formalism for specifying ontologies. In recent years, many classes of existential rules have been exhibited for which conjunctive query (CQ) entailment is decidable. However, most of these classes cannot express transitivity of binary relations, a frequently used modelling construct. In this paper, we address the issue of whether transitivity can be safely combined with decidable classes of existential rules. First, we prove that transitivity is incompatible with one of the simplest decidable classes, namely aGRD (acyclic graph of rule dependencies), which clarifies the landscape of `finite expansion sets' of rules. Second, we show that transitivity can be safely added to linear rules (a subclass of guarded rules, which generalizes the description logic DL-Lite-R) in the case of atomic CQs, and also for general CQs if we place a minor syntactic restriction on the rule set. This is shown by means of a novel query rewriting algorithm that is specially tailored to handle transitivity rules. Third, for the identified decidable cases, we pinpoint the combined and data complexities of query entailment.
Efficiency Guarantees from Data
Venue: arXiv cs.GT 2017
Year: 2017

Analysis of efficiency of outcomes in game theoretic settings has been a main item of study at the intersection of economics and computer science. The notion of the price of anarchy takes a worst-case stance to efficiency analysis, considering instance independent guarantees of efficiency. We propose a data-dependent analog of the price of anarchy that refines this worst-case assuming access to samples of strategic behavior. We focus on auction settings, where the latter is non-trivial due to the private information held by participants. Our approach to bounding the efficiency from data is robust to statistical errors and mis-specification. Unlike traditional econometrics, which seek to learn the private information of players from observed behavior and then analyze properties of the outcome, we directly quantify the inefficiency without going through the private information. We apply our approach to datasets from a sponsored search auction system and find empirical results that are a significant improvement over bounds from worst-case analysis.
Enhancing Secrecy Rates in a wiretap channel
Venue: arXiv cs.IT 2017
Year: 2017

Reliable communication imposes an upper limit on the achievable rate, namely the Shannon capacity. Wyner's wiretap coding, which ensures a security constraint also, in addition to reliability, results in decrease of the achievable rate. To mitigate the loss in the secrecy rate, we propose a coding scheme where we use sufficiently old messages as key and for this scheme prove that multiple messages are secure with respect to (w.r.t.) all the information possessed by the eavesdropper. We also show that we can achieve security in the strong sense. Next we consider a fading wiretap channel with full channel state information of the eavesdropper's channel and use our coding/decoding scheme to achieve secrecy capacity close to the Shannon capacity of the main channel (in the ergodic sense). Finally we also consider the case where the transmitter does not have the instantaneous information of the channel state of the eavesdropper, but only its distribution.
Fast and Powerful Hashing using Tabulation
Venue: arXiv cs.DS 2017
Year: 2017

Randomized algorithms are often enjoyed for their simplicity, but the hash functions employed to yield the desired probabilistic guarantees are often too complicated to be practical. Here we survey recent results on how simple hashing schemes based on tabulation provide unexpectedly strong guarantees. Simple tabulation hashing dates back to Zobrist [1970]. Keys are viewed as consisting of $c$ characters and we have precomputed character tables $h_1,...,h_c$ mapping characters to random hash values. A key $x=(x_1,...,x_c)$ is hashed to $h_1[x_1] \oplus h_2[x_2].....\oplus h_c[x_c]$. This schemes is very fast with character tables in cache. While simple tabulation is not even 4-independent, it does provide many of the guarantees that are normally obtained via higher independence, e.g., linear probing and Cuckoo hashing. Next we consider twisted tabulation where one input character is "twisted" in a simple way. The resulting hash function has powerful distributional properties: Chernoff-Hoeffding type tail bounds and a very small bias for min-wise hashing. This also yields an extremely fast pseudo-random number generator that is provably good for many classic randomized algorithms and data-structures. Finally, we consider double tabulation where we compose two simple tabulation functions, applying one to the output of the other, and show that this yields very high independence in the classic framework of Carter and Wegman [1977]. In fact, w.h.p., for a given set of size proportional to that of the space consumed, double tabulation gives fully-random hashing. We also mention some more elaborate tabulation schemes getting near-optimal independence for given time and space. While these tabulation schemes are all easy to implement and use, their analysis is not.
Will the Area Spectral Efficiency Monotonically Grow as Small Cells Go Dense?
Venue: arXiv cs.NI 2017
Year: 2017

In this paper, we introduce a sophisticated path loss model into the stochastic geometry analysis incorporating both line-of-sight (LoS) and non-line-of-sight (NLoS) transmissions to study their performance impact in small cell networks (SCNs). Analytical results are obtained on the coverage probability and the area spectral efficiency (ASE) assuming both a general path loss model and a special case of path loss model recommended by the 3rd Generation Partnership Project (3GPP) standards. The performance impact of LoS and NLoS transmissions in SCNs in terms of the coverage probability and the ASE is shown to be significant both quantitatively and qualitatively, compared with previous work that does not differentiate LoS and NLoS transmissions. Particularly, our analysis demonstrates that when the density of small cells is larger than a threshold, the network coverage probability will decrease as small cells become denser, which in turn makes the ASE suffer from a slow growth or even a notable decrease. For practical regime of small cell density, the performance results derived from our analysis are distinctively different from previous results, and shed new insights on the design and deployment of future dense/ultra-dense SCNs.