OpenRaiser/Intern-Atlas huggingface dataset:
Radio Tomography for Roadside Surveillance
Venue: arXiv cs.NI 2016
Year: 2016

Radio tomographic imaging (RTI) has recently been proposed for tracking object location via radio waves without requiring the objects to transmit or receive radio signals. The position is extracted by inferring which voxels are obstructing a subset of radio links in a dense wireless sensor network. This paper proposes a variety of modeling and algorithmic improvements to RTI for the scenario of roadside surveillance. These include the use of a more physically motivated weight matrix, a method for mitigating negative (aphysical) data due to noisy observations, and a method for combining frames of a moving vehicle into a single image. The proposed approaches are used to show improvement in both imaging (useful for human-in-the-loop target recognition) and automatic target recognition in a measured data set.
Efficient Multi-Dimensional Mapping Using QAM Constellations for BICM-ID
Venue: arXiv cs.IT 2016
Year: 2016

Bit-interleaved coded modulation with iterative decoding (BICM-ID) offers very good error performance over additive white Gaussian noise (AWGN) and fading channels if it uses a wisely designed signal mapping. Further, error performance of BICM-ID can significantly be improved by employing multi-dimensional (MD) modulation. However, suitable MD mappings are obtained by computer search techniques except for MD modulations that use smaller constellation e.g., binary phase shift keying (BPSK), quadrature phase shift keying (QPSK) and $8$-ary phase shift keying ($8$-PSK) as basic modulation. The alphabet size of MD modulations increases exponentially as the order of the basic modulation increases and computer search becomes intractable. In this paper, we propose a systematic mapping method for MD modulations. The innovativeness of our proposed method is that it generates MD mappings using $16$- and $64$-quadrature amplitude modulation (QAM) very efficiently. The presented numerical results show that the proposed method improves bit error rate (BER) of BICM-ID.
An Infinite Dimensional Model for a Many Server Priority Queue
Venue: arXiv cs.PF 2016
Year: 2016

We consider a Markovian many server queueing system in which customers are preemptively scheduled according to exogenously assigned priority levels. The priority levels are randomly assigned from a continuous probability measure rather than a discrete one and hence, the queue is modeled by an infinite dimensional stochastic process. We analyze the equilibrium behavior of the system and provide several results. We derive the Radon-Nikodym derivative (with respect to Lebesgue measure) of the measure that describes the average distribution of customer priority levels in the system; we provide a formula for the expected sojourn time of a customer as a function of his priority level; and we provide a formula for the expected waiting time of a customer as a function of his priority level. We verify our theoretical analysis with discrete-event simulations. We discuss how each of our results generalizes previous work on infinite dimensional models for single server priority queues.
Formal Proof of the Weak Goodstein Theorem
Venue: arXiv cs.SE 2016
Year: 2016

For many years, I have been interested in introducing students to the development of complex systems by means of modelling and refinement. To this end, I did not find anything better than presenting many examples of system developments. However, I figured out that my examples were not explicit enough on how (mechanical) proofs are performed. So, besides courses presenting these examples and also some courses in various forms of proofs (propositional calculus, first order predicate calculus, set theory), I decided to study the work of professional mathematicians, thinking that it could be good examples for students. Among the works I already studied and reconstructed are the theorem of Zermelo, the theorem of Cantor-Bernstein, the planar graph theorem of Kuratowski, the topological proof of the infinity of primes of Furstenberg, the intermediate value theorem of Bolzano, the Archimedean property of the set of Real numbers, and others. More recently, I found that the Goodstein theorem was also very interesting. The purpose of this short note is to give some information about this theorem and the way I introduce a weak form of it to students.
Beyond NGS data sharing and towards open science
Venue: arXiv cs.DC 2016
Year: 2016

Biosciences have been revolutionized by next generation sequencing (NGS) technologies in last years, leading to new perspectives in medical, industrial and environmental applications. And although our motivation comes from biosciences, the following is true for many areas of science: published results are usually hard to reproduce either because data is not available or tools are not readily available, which delays the adoption of new methodologies and hinders innovation. Our focus is on tool readiness and pipelines availability. Even though most tools are freely available, pipelines for data analysis are in general barely described and their configuration is far from trivial, with many parameters to be tuned. In this paper we discuss how to effectively build and use pipelines, relying on state of the art computing technologies to execute them without users need to configure, install and manage tools, servers and complex workflow management systems. We perform an in depth comparative analysis of state of the art frameworks and systems. The NGSPipes framework is proposed showing that we can have public pipelines ready to process and analyse experimental data, produced for instance by high-throughput technologies, but without relying on centralized servers or Web services. The NGSPipes framework and underlying architecture provides a major step towards open science and true collaboration in what concerns tools and pipelines among computational biology researchers and practitioners. We show that it is possible to execute data analysis pipelines in a decentralized and platform independent way. Approaches like the one proposed are crucial for archiving and reusing data analysis pipelines at medium/long-term. NGSPipes framework is freely available at http://ngspipes.github.io/.
Tackling Corruption With Agents & ICT: A Vision
Venue: arXiv cs.CY 2016
Year: 2016

Corruption is universally considered as an undesirable characteristic of public services. But despite attempts to simplify and automate such services, there is very little prior work to detect, handle or prevent corruption in computation literature. This is particularly surprising given the significant advances made in detecting fraud, a relevant but different form of public impropriety afflicting businesses. In this paper, we paint a vision of how information and communications technology (ICT), and specifically agent-based methods, can help tackle corruption in public services and identify challenges to achieve the vision.
Urban Attractors: Discovering Patterns in Regions of Attraction in Cities
Venue: arXiv cs.SI 2016
Year: 2016

Understanding the dynamics by which urban areas attract visitors is significant for urban development in cities. In addition, identifying services that relate to highly attractive districts is useful to make policies regarding the placement of such places. Thus, we present a framework for classifying districts in cities by their attractiveness to visitors, and relating Points of Interests (POIs) types to districts' attraction patterns. We used Origin-Destination matrices (ODs) mined from cell phone data that capture the flow of trips between each pair of places in Riyadh, Saudi Arabia. We define the attraction profile for a place based on three main statistical features: The amount of visitors a place received, the distribution of distance traveled by visitors on the road network, and the spatial spread of where visitors come from. We use a hierarchical clustering algorithm to classify all places in the city by their features of attraction. We detect three types of Urban Attractors in Riyadh during the morning period: Global which are significant places in the city, Downtown which the central business district and Residential attractors. In addition, we uncover what makes these places different in terms of attraction patterns. We used a statistical significance testing approach to rigorously quantify the relationship between Points of Interests (POIs) types (services) and the 3 patterns of Urban Attractors we detected. The proposed framework can be used for detecting the attraction patterns given by type of services related to each pattern. This is a critical piece of information to inform trip distribution models.
An Extension of the Permutation Group Enumeration Technique (Collapse of the Polynomial Hierarchy: $\mathbf{NP = P}$)
Venue: arXiv cs.CC 2017
Year: 2017

The distinguishing result of this paper is a $\mathbf{P}$-time enumerable partition of all the potential perfect matchings in a bipartite graph. This partition is a set of equivalence classes induced by the missing edges in the potential perfect matchings. We capture the behavior of these missing edges in a polynomially bounded representation of the exponentially many perfect matchings by a graph theoretic structure, called MinSet Sequence, where MinSet is a P-time enumerable structure derived from a graph theoretic counterpart of a generating set of the symmetric group. This leads to a polynomially bounded generating set of all the classes, enabling the enumeration of perfect matchings in polynomial time. The sequential time complexity of this $\mathbf{\#P}$-complete problem is shown to be $O(n^{45}\log n)$. And thus we prove a result even more surprising than $\mathbf{NP = P}$, that is, $\mathbf{\#P}=\mathbf{FP}$, where $\mathbf{FP}$ is the class of functions, $f: \{0, 1\}^* \rightarrow \mathbb{N} $, computable in polynomial time on a deterministic model of computation.
Unary Subset-Sum is in Logspace
Venue: arXiv cs.CC 2017
Year: 2017

We present a simple Logspace algorithm that solves the Unary Subset-Sum problem.
Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions
Venue: arXiv cs.DS 2017
Year: 2017

Submodular function minimization is a key problem in a wide variety of applications in machine learning, economics, game theory, computer vision, and many others. The general solver has a complexity of $O(n^3 \log^2 n . E +n^4 {\log}^{O(1)} n)$ where $E$ is the time required to evaluate the function and $n$ is the number of variables \cite{Lee2015}. On the other hand, many computer vision and machine learning problems are defined over special subclasses of submodular functions that can be written as the sum of many submodular cost functions defined over cliques containing few variables. In such functions, the pseudo-Boolean (or polynomial) representation \cite{BorosH02} of these subclasses are of degree (or order, or clique size) $k$ where $k \ll n$. In this work, we develop efficient algorithms for the minimization of this useful subclass of submodular functions. To do this, we define novel mapping that transform submodular functions of order $k$ into quadratic ones. The underlying idea is to use auxiliary variables to model the higher order terms and the transformation is found using a carefully constructed linear program. In particular, we model the auxiliary variables as monotonic Boolean functions, allowing us to obtain a compact transformation using as few auxiliary variables as possible.
Distributed Signal Processing via Chebyshev Polynomial Approximation
Venue: arXiv cs.DC 2017
Year: 2017

Unions of graph multiplier operators are an important class of linear operators for processing signals defined on graphs. We present a novel method to efficiently distribute the application of these operators. The proposed method features approximations of the graph multipliers by shifted Chebyshev polynomials, whose recurrence relations make them readily amenable to distributed computation. We demonstrate how the proposed method can be applied to distributed processing tasks such as smoothing, denoising, inverse filtering, and semi-supervised classification, and show that the communication requirements of the method scale gracefully with the size of the network.
Delaunay Hodge Star
Venue: arXiv cs.CG 2017
Year: 2017

We define signed dual volumes at all dimensions for circumcentric dual meshes. We show that for pairwise Delaunay triangulations with mild boundary assumptions these signed dual volumes are positive. This allows the use of such Delaunay meshes for Discrete Exterior Calculus (DEC) because the discrete Hodge star operator can now be correctly defined for such meshes. This operator is crucial for DEC and is a diagonal matrix with the ratio of primal and dual volumes along the diagonal. A correct definition requires that all entries be positive. DEC is a framework for numerically solving differential equations on meshes and for geometry processing tasks and has had considerable impact in computer graphics and scientific computing. Our result allows the use of DEC with a much larger class of meshes than was previously considered possible.
On the computation of zone and double zone diagrams
Venue: arXiv cs.CG 2017
Year: 2017

Classical objects in computational geometry are defined by explicit relations. Several years ago the pioneering works of T. Asano, J. Matousek and T. Tokuyama introduced "implicit computational geometry", in which the geometric objects are defined by implicit relations involving sets. An important member in this family is called "a zone diagram". The implicit nature of zone diagrams implies, as already observed in the original works, that their computation is a challenging task. In a continuous setting this task has been addressed (briefly) only by these authors in the Euclidean plane with point sites. We discuss the possibility to compute zone diagrams in a wide class of spaces and also shed new light on their computation in the original setting. The class of spaces, which is introduced here, includes, in particular, Euclidean spheres and finite dimensional strictly convex normed spaces. Sites of a general form are allowed and it is shown that a generalization of the iterative method suggested by Asano, Matousek and Tokuyama converges to a double zone diagram, another implicit geometric object whose existence is known in general. Occasionally a zone diagram can be obtained from this procedure. The actual (approximate) computation of the iterations is based on a simple algorithm which enables the approximate computation of Voronoi diagrams in a general setting. Our analysis also yields a few byproducts of independent interest, such as certain topological properties of Voronoi cells (e.g., that in the considered setting their boundaries cannot be "fat").
Computing in the Limit
Venue: arXiv cs.CC 2017
Year: 2017

We define a class of functions termed "Computable in the Limit", based on the Machine Learning paradigm of "Identification in the Limit". A function is Computable in the Limit if it defines a property P_p of a recursively enumerable class A of recursively enumerable data sequences S in A, such that each data sequence S is generated by a total recursive function s that enumerates . Let the index s represent the data sequence S. The property P_p(s)=x is computed by a partial recursive function f_p(s,t) such that there exists a u where f_p(s,u)=x and for all t>=u, f_p(s,t)=x if it converges. Since the index s is known, this is not an identification problem - instead it is computing a common property of the sequences in A. We give a Normal Form Theorem for properties that are Computable in the Limit, similar to Kleene's Normal Form Theorem. We also give some examples of sets that are Computable in the Limit, and derive some properties of Canonical and Complexity Bound Enumerations of classes of total functions, and show that no full enumeration of all indices of Turing machines TM_i that compute a given total function can be Computable in the Limit.
Mechanism design for resource allocation in networks with intergroup competition and intragroup sharing
Venue: arXiv cs.GT 2017
Year: 2017

We consider a network where strategic agents, who are contesting for allocation of resources, are divided into fixed groups. The network control protocol is such that within each group agents get to share the resource and across groups they contest for it. A prototypical example is the allocation of data rate on a network with multicast/multirate architecture. Compared to the unicast architecture (which is a special case), the multicast/multirate architecture can result in substantial bandwidth savings. However, design of a market mechanism in such a scenario requires dealing with both private and public good problems as opposed to just private goods in unicast. The mechanism proposed in this work ensures that social welfare maximizing allocation on such a network is realized at all Nash equilibria (NE) i.e., full implementation in NE. In addition it is individually rational, i.e., agents have an incentive to participate in the mechanism. The mechanism, which is constructed in a quasi-systematic way starting from the dual of the centralized problem, has a number of useful properties. Specifically, due to a novel allocation scheme, namely "radial projection", the proposed mechanism results in feasible allocation even off equilibrium. This is a practical necessity for any realistic mechanism since agents have to "learn" the NE through a dynamic process. Finally, it is shown how strong budget balance at equilibrium can be achieved with a minimal increase in message space as an add-on to a weakly budget balanced mechanism.
A Mean Field Game Approach to Scheduling in Cellular Systems
Venue: arXiv cs.GT 2017
Year: 2017

We study auction-theoretic scheduling in cellular networks using the idea of mean field equilibrium (MFE). Here, agents model their opponents through a distribution over their action spaces and play the best response. The system is at an MFE if this action is itself a sample drawn from the assumed distribution. In our setting, the agents are smart phone apps that generate service requests, experience waiting costs, and bid for service from base stations. We show that if we conduct a second-price auction at each base station, there exists an MFE that would schedule the app with the longest queue at each time. The result suggests that auctions can attain the same desirable results as queue-length-based scheduling. We present results on the asymptotic convergence of a system with a finite number of agents to the mean field case, and conclude with simulation results illustrating the simplicity of computation of the MFE.
Extending Partial Representations of Circle Graphs
Venue: arXiv cs.DM 2017
Year: 2017

The partial representation extension problem is a recently introduced generalization of the recognition problem. A circle graph is an intersection graph of chords of a circle. We study the partial representation extension problem for circle graphs, where the input consists of a graph $G$ and a partial representation $\cal R'$ giving some pre-drawn chords that represent an induced subgraph of $G$. The question is whether one can extend $\cal R'$ to a representation $\cal R$ of the entire graph $G$, i.e., whether one can draw the remaining chords into a partially pre-drawn representation to obtain a representation of $G$. Our main result is an $O(n^3)$ time algorithm for partial representation extension of circle graphs, where $n$ is the number of vertices. To show this, we describe the structure of all representations of a circle graph using split decomposition. This can be of independent interest.
Physical-Layer Cryptography Through Massive MIMO
Venue: arXiv cs.IT 2017
Year: 2017

We propose the new technique of physical-layer cryptography based on using a massive MIMO channel as a key between the sender and desired receiver, which need not be secret. The goal is for low-complexity encoding and decoding by the desired transmitter-receiver pair, whereas decoding by an eavesdropper is hard in terms of prohibitive complexity. The decoding complexity is analyzed by mapping the massive MIMO system to a lattice. We show that the eavesdropper's decoder for the MIMO system with M-PAM modulation is equivalent to solving standard lattice problems that are conjectured to be of exponential complexity for both classical and quantum computers. Hence, under the widely-held conjecture that standard lattice problems are hard to solve in the worst-case, the proposed encryption scheme has a more robust notion of security than that of the most common encryption methods used today such as RSA and Diffie-Hellman. Additionally, we show that this scheme could be used to securely communicate without a pre-shared secret and little computational overhead. Thus, by exploiting the physical layer properties of the radio channel, the massive MIMO system provides for low-complexity encryption commensurate with the most sophisticated forms of application-layer encryption that are currently known.
Time-dependent Hierarchical Dirichlet Model for Timeline Generation
Venue: arXiv cs.CL 2017
Year: 2017

Timeline Generation aims at summarizing news from different epochs and telling readers how an event evolves. It is a new challenge that combines salience ranking with novelty detection. For long-term public events, the main topic usually includes various aspects across different epochs and each aspect has its own evolving pattern. Existing approaches neglect such hierarchical topic structure involved in the news corpus in timeline generation. In this paper, we develop a novel time-dependent Hierarchical Dirichlet Model (HDM) for timeline generation. Our model can aptly detect different levels of topic information across corpus and such structure is further used for sentence selection. Based on the topic mined fro HDM, sentences are selected by considering different aspects such as relevance, coherence and coverage. We develop experimental systems to evaluate 8 long-term events that public concern. Performance comparison between different systems demonstrates the effectiveness of our model in terms of ROUGE metrics.
Subliminal Probing for Private Information via EEG-Based BCI Devices
Venue: arXiv cs.CR 2017
Year: 2017

Martinovic et al. proposed a Brain-Computer-Interface (BCI) -based attack in which an adversary is able to infer private information about a user, such as their bank or area-of-living, by analyzing the user's brain activities. However, a key limitation of the above attack is that it is intrusive, requiring user cooperation, and is thus easily detectable and can be reported to other users. In this paper, we identify and analyze a more serious threat for users of BCI devices. We propose a it subliminal attack in which the victim is attacked at the levels below his cognitive perception. Our attack involves exposing the victim to visual stimuli for a duration of 13.3 milliseconds -- a duration usually not sufficient for conscious perception. The attacker analyzes subliminal brain activity in response to these short visual stimuli to infer private information about the user. If carried out carefully, for example by hiding the visual stimuli within screen content that the user expects to see, the attack may remain undetected. As a consequence, the attacker can scale it to many victims and expose them to the attack for a long time. We experimentally demonstrate the feasibility of our subliminal attack via a proof-of-concept study carried out with 27 subjects. We conducted experiments on users wearing Electroencephalography-based BCI devices, and used portrait pictures of people as visual stimuli which were embedded within the background of an innocuous video for a time duration not exceeding 13.3 milliseconds. Our experimental results show that it is feasible for an attacker to learn relevant private information about the user, such as whether the user knows the identity of the person for which the attacker is probing.