OpenRaiser/Intern-Atlas huggingface dataset:
Lower Bounds on Parameter Modulation-Estimation Under Bandwidth Constraints
Venue: arXiv cs.IT 2016
Year: 2016

We consider the problem of modulating the value of a parameter onto a band-limited signal to be transmitted over a continuous-time, additive white Gaussian noise (AWGN) channel, and estimating this parameter at the receiver. The performance is measured by the mean power-$α$ error (MP$α$E), which is defined as the worst-case $α$-th order moment of the absolute estimation error. The optimal exponential decay rate of the MP$α$E as a function of the transmission time, is investigated. Two upper (converse) bounds on the MP$α$E exponent are derived, on the basis of known bounds for the AWGN channel of inputs with unlimited bandwidth. The bounds are computed for typical values of the error moment and the signal-to-noise ratio (SNR), and the SNR asymptotics of the different bounds are analyzed. The new bounds are compared to known converse and achievability bounds, which were derived from channel coding considerations.
Fine-grained dichotomies for the Tutte plane and Boolean #CSP
Venue: arXiv cs.CC 2016
Year: 2016

Jaeger, Vertigan, and Welsh [15] proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: The evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén [9] and Husfeldt and Taslaman [12], in combination with Curticapean [7], extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line $y=1$, which was left open. We complete the dichotomy theorem for the Tutte polynomial under #ETH by proving that the number of all acyclic subgraphs of a given $n$-vertex graph cannot be determined in time $exp(o(n))$ unless #ETH fails. Another dichotomy theorem we strengthen is the one of Creignou and Hermann [6] for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that all #P-hard cases are also hard under #ETH. The main ingredient is to prove that the number of independent sets in bipartite graphs with $n$ vertices cannot be computed in time $exp(o(n))$ unless #ETH fails. In order to prove our results, we use the block interpolation idea by Curticapean [7] and transfer it to systems of linear equations that might not directly correspond to interpolation.
A Distributed Newton Method for Large Scale Consensus Optimization
Venue: arXiv cs.DC 2016
Year: 2016

In this paper, we propose a distributed Newton method for consensus optimization. Our approach outperforms state-of-the-art methods, including ADMM. The key idea is to exploit the sparsity of the dual Hessian and recast the computation of the Newton step as one of efficiently solving symmetric diagonally dominant linear equations. We validate our algorithm both theoretically and empirically. On the theory side, we demonstrate that our algorithm exhibits superlinear convergence within a neighborhood of optimality. Empirically, we show the superiority of this new method on a variety of machine learning problems. The proposed approach is scalable to very large problems and has a low communication overhead.
How DNA Cryptography can help whistleblowers and refugees
Venue: arXiv cs.CR 2016
Year: 2016

The recent progress in DNA sequencing will probably revolutionize the world of electronic. Hence, we went from DNA sequencing that only research centers could realize, to portable, tiny and inexpensive tools. So, it is likely that in a few years these DNA sequencers will be included in our smartphones. The purpose of this paper is to support this revolution, by using the DNA cryptography, hash functions and social networks. The first application will introduce a mutual entity authentication protocol in order to help waifs, refugees, and victims of human trafficking to find their biological parents online. The second application will also use the DNA cryptography and the social networks to protect whistleblowers' actions. For example, this method will allow whistleblowers to securely broadcast on social networks, their information with one grape.
A Delay Optimal MAC and Packet Scheduler for Heterogeneous M2M Uplink
Venue: arXiv cs.IT 2016
Year: 2016

The uplink data arriving at the Machine-to-Machine (M2M) Application Server (AS) via M2M Aggregators (MAs) is fairly heterogeneous along several dimensions such as maximum tolerable packet delay, payload size and arrival rate, thus necessitating the design of Quality-of-Service (QoS) aware packet scheduler. In this paper, we classify the M2M uplink data into multiple QoS classes and use sigmoidal function to map the delay requirements of each class onto utility functions. We propose a proportionally fair delay-optimal multiclass packet scheduler at AS that maximizes a system utility metric. We note that the average class delay under any work-conserving scheduling policy can be realized by appropriately time-sharing between all possible preemptive priority policies. Therefore the optimal scheduler is determined using an iterative process to determine the optimal time-sharing between all priority scheduling policies, such that it results in maximum system utility. The proposed scheduler can be implemented online with reduced complexity due to the iterative optimization process. We then extend this work to determine jointly optimal MA-AS channel allocation and packet scheduling scheme at the MAs and AS. We first formulate a joint optimization problem that is solved centrally at the AS and then propose a low complexity distributed optimization problem solved independently at MAs and AS. We show that the distributed optimization solution converges quickly to the centralized optimization result with minimal information exchange overhead between MAs and AS. Using Monte-Carlo simulations, we verify the optimality of the proposed scheduler and show that it outperforms other state-of-the-art packet schedulers such as weighted round robin, max-weight scheduler etc. Another desirable feature of proposed scheduler is low delay jitter for delay-sensitive traffic.
Sequent Calculus Representations for Quantum Circuits
Venue: arXiv cs.LO 2016
Year: 2016

When considering a sequent-style proof system for quantum programs, there are certain elements of quantum mechanics that we may wish to capture, such as phase, dynamics of unitary transformations, and measurement probabilities. Traditional quantum logics which focus primarily on the abstract orthomodular lattice theory and structures of Hilbert spaces have not satisfactorily captured some of these elements. We can start from 'scratch' in an attempt to conceptually characterize the types of proof rules which should be in a system that represents elements necessary for quantum algorithms. This present work attempts to do this from the perspective of the quantum circuit model of quantum computation. A sequent calculus based on single quantum circuits is suggested, and its ability to incorporate important conceptual and dynamic aspects of quantum computing is discussed. In particular, preserving the representation of phase helps illustrate the role of interference as a resource in quantum computation. Interference also provides an intuitive basis for a non-monotonic calculus.
Where to Focus: Query Adaptive Matching for Instance Retrieval Using Convolutional Feature Maps
Venue: arXiv cs.CV 2016
Year: 2016

Instance retrieval requires one to search for images that contain a particular object within a large corpus. Recent studies show that using image features generated by pooling convolutional layer feature maps (CFMs) of a pretrained convolutional neural network (CNN) leads to promising performance for this task. However, due to the global pooling strategy adopted in those works, the generated image feature is less robust to image clutter and tends to be contaminated by the irrelevant image patterns. In this article, we alleviate this drawback by proposing a novel reranking algorithm using CFMs to refine the retrieval result obtained by existing methods. Our key idea, called query adaptive matching (QAM), is to first represent the CFMs of each image by a set of base regions which can be freely combined into larger regions-of-interest. Then the similarity between the query and a candidate image is measured by the best similarity score that can be attained by comparing the query feature and the feature pooled from a combined region. We show that the above procedure can be cast as an optimization problem and it can be solved efficiently with an off-the-shelf solver. Besides this general framework, we also propose two practical ways to create the base regions. One is based on the property of the CFM and the other one is based on a multi-scale spatial pyramid scheme. Through extensive experiments, we show that our reranking approaches bring substantial performance improvement and by applying them we can outperform the state of the art on several instance retrieval benchmarks.
Person Identification Based on Hand Tremor Characteristics
Venue: arXiv cs.HC 2016
Year: 2016

A plethora of biometric measures have been proposed in the past. In this paper we introduce a new potential biometric measure: the human tremor. We present a new method for identifying the user of a handheld device using characteristics of the hand tremor measured with a smartphone built-in inertial sensors (accelerometers and gyroscopes). The main challenge of the proposed method is related to the fact that human normal tremor is very subtle while we aim to address real-life scenarios. To properly address the issue, we have relied on weighted Fourier linear combiner for retrieving only the tremor data from the hand movement and random forest for actual recognition. We have evaluated our method on a database with 10 000 samples from 17 persons reaching an accuracy of 76%.
Personality, Culture, and System Factors - Impact on Affective Response to Multimedia
Venue: arXiv cs.MM 2016
Year: 2016

Whilst affective responses to various forms and genres of multimedia content have been well researched, precious few studies have investigated the combined impact that multimedia system parameters and human factors have on affect. Consequently, in this paper we explore the role that two primordial dimensions of human factors - personality and culture - in conjunction with system factors - frame rate, resolution, and bit rate - have on user affect and enjoyment of multimedia presentations. To this end, a two-site, cross-cultural study was undertaken, the results of which produced three predictve models. Personality and Culture traits were shown statistically to represent 5.6% of the variance in positive affect, 13.6% in negative affect and 9.3% in enjoyment. The correlation between affect and enjoyment, was significant. Predictive modeling incorporating human factors showed about 8%, 7% and 9% improvement in predicting positive affect, negative affect and enjoyment respectively when compared to models trained only on system factors. Results and analysis indicate the significant role played by human factors in influencing affect that users experience while watching multimedia.
Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Information
Venue: arXiv cs.AI 2016
Year: 2016

Zero-sum stochastic games provide a rich model for competitive decision making. However, under general forms of state uncertainty as considered in the Partially Observable Stochastic Game (POSG), such decision making problems are still not very well understood. This paper makes a contribution to the theory of zero-sum POSGs by characterizing structure in their value function. In particular, we introduce a new formulation of the value function for zs-POSGs as a function of the "plan-time sufficient statistics" (roughly speaking the information distribution in the POSG), which has the potential to enable generalization over such information distributions. We further delineate this generalization capability by proving a structural result on the shape of value function: it exhibits concavity and convexity with respect to appropriately chosen marginals of the statistic space. This result is a key pre-cursor for developing solution methods that may be able to exploit such structure. Finally, we show how these results allow us to reduce a zs-POSG to a "centralized" model with shared observations, thereby transferring results for the latter, narrower class, to games with individual (private) observations.
Improving the detection accuracy of unknown malware by partitioning the executables in groups
Venue: arXiv cs.CR 2016
Year: 2016

Detection of unknown malware with high accuracy is always a challenging task. Therefore, in this paper, we study the classification of unknown malware by two methods. In the first/regular method, similar to other authors [17][16][20] approaches we select the features by taking all dataset in one group and in the second method, we select the features by partitioning the dataset in the range of file 5 KB size. We find that the second method to detect the malware with ~8.7% more accurate than the first/regular method.
Using emulation to validate applications on opportunistic networks
Venue: arXiv cs.NI 2016
Year: 2016

The increasing trend on wireless-connected devices makes opportunistic networking a promising alternative to existing infrastructure-based networks. However, on these networks there is neither guarantee about the availability of the connections nor on the topology of the network. The development of opportunistic applications, i.e., applications running over opportunistic networks, is still in early stages. This is due to lack of tools to support the process in such uncertain conditions. Indeed, many tools have been introduced to study and characterize opportunistic networks, but none of them is focused on helping developers to conceive opportunistic applications. In this paper, we argue that the gap between opportunistic applications development and network characterization can be filled with network emulation. First, this position paper points out important challenges about the development of opportunistic applications. Then, in order to cope with these challenges, it details a set of requirements that an emulator should meet to allow the testing of such applications.
Computing hypergeometric functions rigorously
Venue: arXiv cs.MS 2016
Year: 2016

We present an efficient implementation of hypergeometric functions in arbitrary-precision interval arithmetic. The functions ${}_0F_1$, ${}_1F_1$, ${}_2F_1$ and ${}_2F_0$ (or the Kummer $U$-function) are supported for unrestricted complex parameters and argument, and by extension, we cover exponential and trigonometric integrals, error functions, Fresnel integrals, incomplete gamma and beta functions, Bessel functions, Airy functions, Legendre functions, Jacobi polynomials, complete elliptic integrals, and other special functions. The output can be used directly for interval computations or to generate provably correct floating-point approximations in any format. Performance is competitive with earlier arbitrary-precision software, and sometimes orders of magnitude faster. We also partially cover the generalized hypergeometric function ${}_pF_q$ and computation of high-order parameter derivatives.
Smart Grid Security: Threats, Challenges, and Solutions
Venue: arXiv cs.IT 2016
Year: 2016

The cyber-physical nature of the smart grid has rendered it vulnerable to a multitude of attacks that can occur at its communication, networking, and physical entry points. Such cyber-physical attacks can have detrimental effects on the operation of the grid as exemplified by the recent attack which caused a blackout of the Ukranian power grid. Thus, to properly secure the smart grid, it is of utmost importance to: a) understand its underlying vulnerabilities and associated threats, b) quantify their effects, and c) devise appropriate security solutions. In this paper, the key threats targeting the smart grid are first exposed while assessing their effects on the operation and stability of the grid. Then, the challenges involved in understanding these attacks and devising defense strategies against them are identified. Potential solution approaches that can help mitigate these threats are then discussed. Last, a number of mathematical tools that can help in analyzing and implementing security solutions are introduced. As such, this paper will provide the first comprehensive overview on smart grid security.
Detecting service provider alliances on the choreography enactment pricing game
Venue: arXiv cs.DC 2016
Year: 2016

We present the choreography enactment pricing game, a cooperative game-theoretic model for the study of scheduling of jobs using competitor service providers. A choreography (a peer-to-peer service composition model) needs a set of services to fulfill its jobs requirements. Users must choose, for each requirement, which service providers will be used to enact the choreography at lowest cost. Due to the lack of centralization, vendors can form alliances to control the market. We show a novel algorithm capable of detecting alliances among service providers, based on our study of the bargaining set of this game.
Automated Extraction of Number of Subjects in Randomised Controlled Trials
Venue: arXiv cs.AI 2016
Year: 2016

We present a simple approach for automatically extracting the number of subjects involved in randomised controlled trials (RCT). Our approach first applies a set of rule-based techniques to extract candidate study sizes from the abstracts of the articles. Supervised classification is then performed over the candidates with support vector machines, using a small set of lexical, structural, and contextual features. With only a small annotated training set of 201 RCTs, we obtained an accuracy of 88\%. We believe that this system will aid complex medical text processing tasks such as summarisation and question answering.
On Improving Capacity of Full-Duplex Small Cells with D2D
Venue: arXiv cs.NI 2016
Year: 2016

The recent developments in full duplex (FD) communication promise doubling the capacity of cellular networks using self interference cancellation (SIC) techniques. FD small cells with device-to-device (D2D) communication links could achieve the expected capacity of the future cellular networks (5G). In this work, we consider joint scheduling and dynamic power algorithm (DPA) for a single cell FD small cell network with D2D links (D2DLs). We formulate the optimal user selection and power control as a non-linear programming (NLP) optimization problem to get the optimal user scheduling and transmission power in a given TTI. Our numerical results show that using DPA gives better overall throughput performance than full power transmission algorithm (FPA). Also, simultaneous transmissions (combination of uplink (UL), downlink (DL), and D2D occur 80% of the time thereby increasing the spectral efficiency and network capacity.
Energy Saving of Base Stations Sleep Scheduling for Multi-Hop Vehicular Networks
Venue: arXiv cs.NI 2016
Year: 2016

This paper investigates the energy saving of base station (BS) deployed in a 1-D multi-hop vehicular network with sleep scheduling strategy. We consider cooperative BS scheduling strategy where BSs can switch between sleep and active modes to reduce the average energy consumption utilizing the information of vehicular speeds and locations. Assuming a Poisson distribution of vehicles, we derive an appropriate probability distribution function of distance between two adjacent cluster heads, where a cluster is a maximal set of vehicles in which every two adjacent vehicles can communicate directly when their Euclidean distance is less than or equal to a threshold, known as the communication range of vehicles. Furthermore, the expected value of the sojourn time in the sleep mode and energy saving are obtained. The numerical results show that the sleep scheduling strategy significantly reduces the energy consumption of the base stations.
Toward a Deep Neural Approach for Knowledge-Based IR
Venue: arXiv cs.IR 2016
Year: 2016

This paper tackles the problem of the semantic gap between a document and a query within an ad-hoc information retrieval task. In this context, knowledge bases (KBs) have already been acknowledged as valuable means since they allow the representation of explicit relations between entities. However, they do not necessarily represent implicit relations that could be hidden in a corpora. This latter issue is tackled by recent works dealing with deep representation learn ing of texts. With this in mind, we argue that embedding KBs within deep neural architectures supporting documentquery matching would give rise to fine-grained latent representations of both words and their semantic relations. In this paper, we review the main approaches of neural-based document ranking as well as those approaches for latent representation of entities and relations via KBs. We then propose some avenues to incorporate KBs in deep neural approaches for document ranking. More particularly, this paper advocates that KBs can be used either to support enhanced latent representations of queries and documents based on both distributional and relational semantics or to serve as a semantic translator between their latent distributional representations.
Importance sampling strategy for non-convex randomized block-coordinate descent
Venue: arXiv cs.LG 2016
Year: 2016

As the number of samples and dimensionality of optimization problems related to statistics an machine learning explode, block coordinate descent algorithms have gained popularity since they reduce the original problem to several smaller ones. Coordinates to be optimized are usually selected randomly according to a given probability distribution. We introduce an importance sampling strategy that helps randomized coordinate descent algorithms to focus on blocks that are still far from convergence. The framework applies to problems composed of the sum of two possibly non-convex terms, one being separable and non-smooth. We have compared our algorithm to a full gradient proximal approach as well as to a randomized block coordinate algorithm that considers uniform sampling and cyclic block coordinate descent. Experimental evidences show the clear benefit of using an importance sampling strategy.
Covariance estimation for vertically partitioned data in a distributed environment
Venue: arXiv cs.DC 2016
Year: 2016

The major sources of abundant data are constantly expanding with the available data collection methodologies in various applications - medical, insurance, scientific, bio-informatics and business. These data sets may be distributed geographically, rich in size and as well as dimensions also. To analyze these data sets to find out the hidden patterns, it is required to down- load the data to a centralized site which is a challenging task in terms of the limited bandwidth available and computationally also expensive. The covariance matrix is one of the methods to estimate the relation between any two dimensions. In this paper, we propose a communication efficient algorithm to estimate the covariance matrix in a distributed manner. The global covariance matrix is computed by merging the local covariance matrices using a distributed approach. The results show that it is exactly same as centralized method with good speed-up in terms of computation. The reason for speed-up is because of the parallel construction of local covariances and distributing the cross-covariances among the nodes so that the load is balanced. The results are analyzed by considering Mfeat data set on the various partitions which address the scalability also.