OpenRaiser/Intern-Atlas huggingface dataset:
Robust recoverable and two-stage selection problems
Venue: arXiv cs.DS 2017
Year: 2017

In this paper the following selection problem is discussed. A set of $n$ items is given and we wish to choose a subset of exactly $p$ items of the minimum total cost. This problem is a special case of 0-1 knapsack in which all the item weights are equal to~1. Its deterministic version has a trivial $O(n)$-time algorithm, which consists in choosing $p$ items of the smallest costs. In this paper it is assumed that the item costs are uncertain. Two robust models, namely two-stage and recoverable ones, under discrete and interval uncertainty representations, are discussed. Several positive and negative complexity results for both of them are provided.
Limit theory of discrete mathematics problems
Venue: arXiv cs.GT 2017
Year: 2017

We show a general problem-solving tool called limit theory. This is an advanced version of asymptotic analysis of discrete problems when some finite parameter tends to infinity. We will apply it on three closely related problems. Alpern's Caching Game (for 2 nuts) is defined as follows. The hider caches 2 nuts into one or two of $n$ potential holes by digging at most 1 depth in total. The goal of the searcher is to find both nuts in a limited time $h$, otherwise the hider wins. We will show that if $h$ and $n/h$ are large enough, then very counterintuitively, any optimal hiding strategy should dig less than 1 in total, with positive probability. We will prove it by defining and analyzing a limit problem. Then we will partially solve the entire problem. We will also have significant progress with two other problems: the Manickam--Miklós--Singhi Conjecture and the Kikuta--Ruckle Conjecture.
Multidimensional Binary Vector Assignment problem: standard, structural and above guarantee parameterizations
Venue: arXiv cs.DS 2017
Year: 2017

In this article we focus on the parameterized complexity of the Multidimensional Binary Vector Assignment problem (called \BVA). An input of this problem is defined by $m$ disjoint sets $V^1, V^2, \dots, V^m$, each composed of $n$ binary vectors of size $p$. An output is a set of $n$ disjoint $m$-tuples of vectors, where each $m$-tuple is obtained by picking one vector from each set $V^i$. To each $m$-tuple we associate a $p$ dimensional vector by applying the bit-wise AND operation on the $m$ vectors of the tuple. The objective is to minimize the total number of zeros in these $n$ vectors. mBVA can be seen as a variant of multidimensional matching where hyperedges are implicitly locally encoded via labels attached to vertices, but was originally introduced in the context of integrated circuit manufacturing. We provide for this problem FPT algorithms and negative results ($ETH$-based results, $W$[2]-hardness and a kernel lower bound) according to several parameters: the standard parameter $k$ i.e. the total number of zeros), as well as two parameters above some guaranteed values.
On the Design of Channel Shortening Demodulators for Iterative Receivers in MIMO and ISI Channels
Venue: arXiv cs.IT 2017
Year: 2017

We consider the problem of designing demodulators for linear vector channels with memory that use reduced-size trellis descriptions for the received signal. We assume an overall iterative receiver, and for the parts of the signal not covered by the trellis description, we use interference cancelation based on the soft information provided by the outer decoder. In order to reach a trellis description, a linear filter is applied as front-end to compress the signal structure into a small trellis. This process requires three parameters to be designed: (i) the front-end filter, (ii) the feedback filter through which the interference cancelation is done, and (iii) a target response which specifies the trellis. Demodulators of this form have been studied before under then name channel shortening (CS), but the interplay between CS and interference cancelation has not been adequately addressed in the literature. In this paper, we analyze two types of CS demodulators that are based on the Forney and Ungerboeck detection models, respectively. The parameters are jointly optimized based on a generalized mutual information (GMI) function. We also introduce a third type of CS demodulator that is in general suboptimal but has closed form solutions for all parameters. Moreover, signal to noise ratio (SNR) asymptotic properties are analyzed and we show that the third CS demodulator asymptotically converges to the optimal CS demodulator in the sense of maximizing the GMI.
Approaches for Software Verification of an Emergency Recovery System for Micro Air Vehicles
Venue: arXiv cs.SE 2017
Year: 2017

This paper describes the development and verification of a competitive parachute system for Micro Air Vehicles, in particular focusing on verification of the embedded software. We first introduce the overall solution including a system level failure analysis, and then show how we minimized the influence of faulty software. This paper demonstrates that with careful abstraction and little overapproximation, the entire code running on a microprocessor can be verified using bounded model checking, and that this is a useful approach for resource-constrained embedded systems. he resulting Emergency Recovery System is to our best knowledge the first of its kind that passed formal verification, and furthermore is superior to all other existing solutions (including commercially available ones) from an operational point of view.
Automagically encoding Adverse Drug Reactions in MedDRA
Venue: arXiv cs.CL 2017
Year: 2017

Pharmacovigilance is the field of science devoted to the collection, analysis and prevention of Adverse Drug Reactions (ADRs). Efficient strategies for the extraction of information about ADRs from free text resources are essential to support the work of experts, employed in the crucial task of detecting and classifying unexpected pathologies possibly related to drug assumptions. Narrative ADR descriptions may be collected in several way, e.g. by monitoring social networks or through the so called spontaneous reporting, the main method pharmacovigilance adopts in order to identify ADRs. The encoding of free-text ADR descriptions according to MedDRA standard terminology is central for report analysis. It is a complex work, which has to be manually implemented by the pharmacovigilance experts. The manual encoding is expensive (in terms of time). Moreover, a problem about the accuracy of the encoding may occur, since the number of reports is growing up day by day. In this paper, we propose MagiCoder, an efficient Natural Language Processing algorithm able to automatically derive MedDRA terminologies from free-text ADR descriptions. MagiCoder is part of VigiWork, a web application for online ADR reporting and analysis. From a practical view-point, MagiCoder radically reduces the revision time of ADR reports: the pharmacologist has simply to revise and validate the automatic solution versus the hard task of choosing solutions in the 70k terms of MedDRA. This improvement of the expert work efficiency has a meaningful impact on the quality of data analysis. Moreover, our procedure is general purpose. We developed MagiCoder for the Italian pharmacovigilance language, but preliminarily analyses show that it is robust to language and dictionary changes.
On the Popularity of GitHub Applications: A Preliminary Note
Venue: arXiv cs.SE 2017
Year: 2017

GitHub is the world's largest collection of open source software. Therefore, it is important both to software developers and users to compare and track the popularity of GitHub repositories. In this paper, we propose a framework to assess the popularity of GitHub software, using their number of stars. We also propose a set of popularity growth patterns, which describe the evolution of the number of stars of a system over time. We show that stars tend to correlate with other measures, like forks, and with the effective usage of GitHub software by third-party programs. Throughout the paper we illustrate the application of our framework using real data extracted from GitHub.
Between plurality and proportionality: an analysis of vote transfer systems
Venue: arXiv cs.GT 2017
Year: 2017

The paper considers a general model of electoral systems combining district-based elections with a compensatory mechanism in order to create any outcome between strictly majoritarian and purely proportional seat allocation. It contains vote transfer and allows for the application of three different correction formulas. Analysis in a two-party system shows that a trade-off exists for the dominant party between its expected seat share and its chance of obtaining majority. Vote transfer rules are also investigated by focusing on the possibility of manipulation. The model is applied to the 2014 Hungarian parliamentary election. Hypothetical results reveal that the vote transfer rule cannot be evaluated in itself, only together with the share of constituency seats. With an appropriate choice of the latter, the three mechanisms may be functionally equivalent.
On the size of the largest empty box amidst a point set
Venue: arXiv cs.CG 2017
Year: 2017

The problem of finding the largest empty axis-parallel box amidst a point configuration is a classical problem in computational geometry. It is known that the volume of the largest empty box is of asymptotic order $1/n$ for $n\to\infty$ and fixed dimension $d$. However, it is natural to assume that the volume of the largest empty box increases as $d$ gets larger. In the present paper we prove that this actually is the case: for every set of $n$ points in $[0, 1]^d$ there exists an empty box of volume at least $c_d n^{-1}$ , where $c_d \to \infty$ as $d\to \infty$. More precisely, $c_d$ is at least of order roughly $\log d$.
On interference among moving sensors and related problems
Venue: arXiv cs.CG 2017
Year: 2017

We show that for any set of $n$ points moving along "simple" trajectories (i.e., each coordinate is described with a polynomial of bounded degree) in $\Re^d$ and any parameter $2 \le k \le n$, one can select a fixed non-empty subset of the points of size $O(k \log k)$, such that the Voronoi diagram of this subset is "balanced" at any given time (i.e., it contains $O(n/k)$ points per cell). We also show that the bound $O(k \log k)$ is near optimal even for the one dimensional case in which points move linearly in time. As applications, we show that one can assign communication radii to the sensors of a network of $n$ moving sensors so that at any given time their interference is $O(\sqrt{n\log n})$. We also show some results in kinetic approximate range counting and kinetic discrepancy. In order to obtain these results, we extend well-known results from $\varepsilon$-net theory to kinetic environments.
Measuring Secrecy by the Probability of a Successful Guess
Venue: arXiv cs.IT 2017
Year: 2017

The secrecy of a communication system in which both the legitimate receiver and an eavesdropper are allowed some distortion is investigated. The secrecy metric considered is the exponent of the probability that the eavesdropper estimates the source sequence successfully within an acceptable distortion level. The problem is first studied when the transmitter and the legitimate receiver do not share any key and the transmitter is not subject to a rate constraint, which corresponds to a stylized model of a side channel and reveals connections to source coding with side information. The setting is then generalized to include a shared secret key between the transmitter and the legitimate receiver and a rate constraint on the transmitter, which corresponds to the Shannon cipher system. A single-letter characterization of the highest achievable exponent is provided, and asymptotically-optimal strategies for both the primary user and the eavesdropper are demonstrated.
On vanishing of Kronecker coefficients
Venue: arXiv cs.CC 2017
Year: 2017

We show that the problem of deciding positivity of Kronecker coefficients is NP-hard. Previously, this problem was conjectured to be in P, just as for the Littlewood-Richardson coefficients. Our result establishes in a formal way that Kronecker coefficients are more difficult than Littlewood-Richardson coefficients, unless P=NP. We also show that there exists a #P-formula for a particular subclass of Kronecker coefficients whose positivity is NP-hard to decide. This is an evidence that, despite the hardness of the positivity problem, there may well exist a positive combinatorial formula for the Kronecker coefficients. Finding such a formula is a major open problem in representation theory and algebraic combinatorics. Finally, we consider the existence of the partition triples $(λ, μ, π)$ such that the Kronecker coefficient $k^λ_{μ, π} = 0$ but the Kronecker coefficient $k^{l λ}_{l μ, l π} > 0$ for some integer $l>1$. Such "holes" are of great interest as they witness the failure of the saturation property for the Kronecker coefficients, which is still poorly understood. Using insight from computational complexity theory, we turn our hardness proof into a positive result: We show that not only do there exist many such triples, but they can also be found efficiently. Specifically, we show that, for any $0<ε\leq1$, there exists $0<a<1$ such that, for all $m$, there exist $Ω(2^{m^a})$ partition triples $(λ,μ,μ)$ in the Kronecker cone such that: (a) the Kronecker coefficient $k^λ_{μ,μ}$ is zero, (b) the height of $μ$ is $m$, (c) the height of $λ$ is $\le m^ε$, and (d) $|λ|=|μ| \le m^3$. The proof of the last result illustrates the effectiveness of the explicit proof strategy of GCT.
Robust Estimation of Self-Exciting Generalized Linear Models with Application to Neuronal Modeling
Venue: arXiv cs.NE 2017
Year: 2017

We consider the problem of estimating self-exciting generalized linear models from limited binary observations, where the history of the process serves as the covariate. We analyze the performance of two classes of estimators, namely the $\ell_1$-regularized maximum likelihood and greedy estimators, for a canonical self-exciting process and characterize the sampling tradeoffs required for stable recovery in the non-asymptotic regime. Our results extend those of compressed sensing for linear and generalized linear models with i.i.d. covariates to those with highly inter-dependent covariates. We further provide simulation studies as well as application to real spiking data from the mouse's lateral geniculate nucleus and the ferret's retinal ganglion cells which agree with our theoretical predictions.
Every Moment Counts: Dense Detailed Labeling of Actions in Complex Videos
Venue: arXiv cs.CV 2017
Year: 2017

Every moment counts in action recognition. A comprehensive understanding of human activity in video requires labeling every frame according to the actions occurring, placing multiple labels densely over a video sequence. To study this problem we extend the existing THUMOS dataset and introduce MultiTHUMOS, a new dataset of dense labels over unconstrained internet videos. Modeling multiple, dense labels benefits from temporal relations within and across classes. We define a novel variant of long short-term memory (LSTM) deep networks for modeling these temporal relations via multiple input and output connections. We show that this model improves action labeling accuracy and further enables deeper understanding tasks ranging from structured retrieval to action prediction.
The Cumulative Distribution Transform and Linear Pattern Classification
Venue: arXiv cs.CV 2017
Year: 2017

Discriminating data classes emanating from sensors is an important problem with many applications in science and technology. We describe a new transform for pattern identification that interprets patterns as probability density functions, and has special properties with regards to classification. The transform, which we denote as the Cumulative Distribution Transform (CDT) is invertible, with well defined forward and inverse operations. We show that it can be useful in `parsing out' variations (confounds) that are `Lagrangian' (displacement and intensity variations) by converting these to `Eulerian' (intensity variations) in transform space. This conversion is the basis for our main result that describes when the CDT can allow for linear classification to be possible in transform space. We also describe several properties of the transform and show, with computational experiments that used both real and simulated data, that the CDT can help render a variety of real world problems simpler to solve.
Offline Handwritten Signature Verification - Literature Review
Venue: arXiv cs.CV 2017
Year: 2017

The area of Handwritten Signature Verification has been broadly researched in the last decades, but remains an open research problem. The objective of signature verification systems is to discriminate if a given signature is genuine (produced by the claimed individual), or a forgery (produced by an impostor). This has demonstrated to be a challenging task, in particular in the offline (static) scenario, that uses images of scanned signatures, where the dynamic information about the signing process is not available. Many advancements have been proposed in the literature in the last 5-10 years, most notably the application of Deep Learning methods to learn feature representations from signature images. In this paper, we present how the problem has been handled in the past few decades, analyze the recent advancements in the field, and the potential directions for future research.
Explicit Frames for Deterministic Phase Retrieval via PhaseLift
Venue: arXiv cs.IT 2017
Year: 2017

We explicitly give a frame of cardinality $5n-6$ such that every signal in $\mathbb{C}^n$ can be recovered up to a phase from its associated intensity measurements via the PhaseLift approach. Furthermore, we give explicit linear measurements with $4r(n-r)+n-2r$ outcomes that enable the recovery of every positive semidefinite $n\times n$ matrix of rank at most $r$.
Feedback and Partial Message Side-Information on the Semideterministic Broadcast Channel
Venue: arXiv cs.IT 2017
Year: 2017

The capacity of the semideterministic discrete memoryless broadcast channel (SD-BC) with partial message side-information (P-MSI) at the receivers is established. In the setting without a common message, it is shown that P-MSI to the stochastic receiver alone can increase capacity, whereas P-MSI to the deterministic receiver can only increase capacity if also the stochastic receiver has P-MSI. The latter holds only for the setting without a common message: if the encoder also conveys a common message, then P-MSI to the deterministic receiver alone can increase capacity. These capacity results are used to show that feedback from the stochastic receiver can increase the capacity of the SD-BC without P-MSI and the sum-rate capacity of the SD-BC with P-MSI at the deterministic receiver. The link between P-MSI and feedback is a feedback code, which---roughly speaking---turns feedback into P-MSI at the stochastic receiver and hence helps the stochastic receiver mitigate experienced interference. For the case where the stochastic receiver has full MSI (F-MSI) and can thus fully mitigate experienced interference also in the absence of feedback, it is shown that feedback cannot increase capacity.
Network Issues in Virtual Machine Migration
Venue: arXiv cs.NI 2017
Year: 2017

Software Defined Networking (SDN) is based basically on three features: centralization of the control plane, programmability of network functions and traffic engineering. The network function migration poses interesting problems that we try to expose and solve in this paper. Content Distribution Network virtualization is presented as use case.
Doubly Stochastic Primal-Dual Coordinate Method for Bilinear Saddle-Point Problem
Venue: arXiv cs.LG 2017
Year: 2017

We propose a doubly stochastic primal-dual coordinate optimization algorithm for empirical risk minimization, which can be formulated as a bilinear saddle-point problem. In each iteration, our method randomly samples a block of coordinates of the primal and dual solutions to update. The linear convergence of our method could be established in terms of 1) the distance from the current iterate to the optimal solution and 2) the primal-dual objective gap. We show that the proposed method has a lower overall complexity than existing coordinate methods when either the data matrix has a factorized structure or the proximal mapping on each block is computationally expensive, e.g., involving an eigenvalue decomposition. The efficiency of the proposed method is confirmed by empirical studies on several real applications, such as the multi-task large margin nearest neighbor problem.
Efficient Redundancy Techniques for Latency Reduction in Cloud Systems
Venue: arXiv cs.DC 2017
Year: 2017

In cloud computing systems, assigning a task to multiple servers and waiting for the earliest copy to finish is an effective method to combat the variability in response time of individual servers, and reduce latency. But adding redundancy may result in higher cost of computing resources, as well as an increase in queueing delay due to higher traffic load. This work helps understand when and how redundancy gives a cost-efficient reduction in latency. For a general task service time distribution, we compare different redundancy strategies in terms of the number of redundant tasks, and time when they are issued and canceled. We get the insight that the log-concavity of the task service time creates a dichotomy of when adding redundancy helps. If the service time distribution is log-convex (i.e. log of the tail probability is convex) then adding maximum redundancy reduces both latency and cost. And if it is log-concave (i.e. log of the tail probability is concave), then less redundancy, and early cancellation of redundant tasks is more effective. Using these insights, we design a general redundancy strategy that achieves a good latency-cost trade-off for an arbitrary service time distribution. This work also generalizes and extends some results in the analysis of fork-join queues.
On the Packet Allocation of Multi-Band Aggregation Wireless Networks
Venue: arXiv cs.NI 2017
Year: 2017

The use of heterogeneous networks with multiple radio access technologies (RATs) is a system concept that both academia and industry are studying. In such system, integrated use of available multiple RATs is essential to achieve beyond additive throughput and connectivity gains using multi-dimensional diversity. This paper considers an aggregation module called opportunistic multi-MAC aggregation (OMMA). It resides between the IP layer and the air interface protocol stacks, common to all RATs in the device. We present a theoretical framework for such system while considering a special case of multi-RAT systems, i.e., a multi-band wireless LAN (WLAN) system. An optimal packet distribution approach is derived which minimizes the average packet latency (the sum of queueing delay and serving delay) over multiple bands. It supports multiple user terminals with different QoS classes simultaneously. We further propose a packet scheduling algorithm, OMMA Leaky Bucket, which minimizes the packet end-to-end delay, i.e., the sum of average packet latency and average packet reordering delay. We also describe the system architecture of the proposed OMMA system, which is applicable for the general case of the multi- RAT devices. It includes functional description, discovery and association processes, and dynamic RAT update management. We finally present simulation results for a multi-band WLAN system. It shows the performance gains of the proposed OMMA Leaky Bucket scheme in comparison to other existing packet scheduling mechanisms.