OpenRaiser/Intern-Atlas huggingface dataset:
Subexponential parameterized algorithms for graphs of polynomial growth
Venue: arXiv cs.DS 2016
Year: 2016

We show that for a number of parameterized problems for which only $2^{O(k)} n^{O(1)}$ time algorithms are known on general graphs, subexponential parameterized algorithms with running time $2^{O(k^{1-\frac{1}{1+δ}} \log^2 k)} n^{O(1)}$ are possible for graphs of polynomial growth with growth rate (degree) $δ$, that is, if we assume that every ball of radius $r$ contains only $O(r^δ)$ vertices. The algorithms use the technique of low-treewidth pattern covering, introduced by Fomin et al. [FOCS 2016] for planar graphs; here we show how this strategy can be made to work for graphs with polynomial growth. Formally, we prove that, given a graph $G$ of polynomial growth with growth rate $δ$ and an integer $k$, one can in randomized polynomial time find a subset $A \subseteq V(G)$ such that on one hand the treewidth of $G[A]$ is $O(k^{1-\frac{1}{1+δ}} \log k)$, and on the other hand for every set $X \subseteq V(G)$ of size at most $k$, the probability that $X \subseteq A$ is $2^{-O(k^{1-\frac{1}{1+δ}} \log^2 k)}$. Together with standard dynamic programming techniques on graphs of bounded treewidth, this statement gives subexponential parameterized algorithms for a number of subgraph search problems, such as Long Path or Steiner Tree, in graphs of polynomial growth. We complement the algorithm with an almost tight lower bound for Long Path: unless the Exponential Time Hypothesis fails, no parameterized algorithm with running time $2^{k^{1-\frac{1}δ-\varepsilon}}n^{O(1)}$ is possible for any $\varepsilon > 0$ and an integer $δ\geq 3$.
A work-efficient parallel sparse matrix-sparse vector multiplication algorithm
Venue: arXiv cs.DC 2016
Year: 2016

We design and develop a work-efficient multithreaded algorithm for sparse matrix-sparse vector multiplication (SpMSpV) where the matrix, the input vector, and the output vector are all sparse. SpMSpV is an important primitive in the emerging GraphBLAS standard and is the workhorse of many graph algorithms including breadth-first search, bipartite graph matching, and maximal independent set. As thread counts increase, existing multithreaded SpMSpV algorithms can spend more time accessing the sparse matrix data structure than doing arithmetic. Our shared-memory parallel SpMSpV algorithm is work efficient in the sense its total work is proportional to the number of arithmetic operations required. The key insight is to avoid each thread individually scan the list of matrix columns. Our algorithm is simple to implement and operates on existing column-based sparse matrix formats. It performs well on diverse matrices and vectors with heterogeneous sparsity patterns. A high-performance implementation of the algorithm attains up to 15x speedup on a 24-core Intel Ivy Bridge processor and up to 49x speedup on a 64-core Intel KNL manycore processor. In contrast to implementations of existing algorithms, the performance of our algorithm is sustained on a variety of different input types include matrices representing scale-free and high-diameter graphs.
A pumping lemma for non-cooperative self-assembly
Venue: arXiv cs.CC 2016
Year: 2016

We prove a result which strongly hints at the computational weakness of a model of tile assembly that has so far resisted many attempts of formal analysis or positive constructions. Specifically, we prove that, in Winfree's abstract Tile Assembly Model, when restricted to use only noncooperative bindings, any long enough path starting from the seed that can grow in all terminal assemblies is pumpable, meaning that this path can be extended into an infinite, ultimately periodic path. This result can be seen as a geometric generalization of the pumping lemma of finite state automata, and closes the question of what can be computed deterministically in this model. Moreover, this question has motivated the development of a new method called visible glues. We believe that this method can also be used to tackle other long-standing problems in computational geometry, in relation for instance with self-avoiding paths. Tile assembly (including non-cooperative tile assembly) was originally introduced by Winfree and Rothemund in STOC 2000 to understand how to program shapes. The non-cooperative variant, also known as temperature 1 tile assembly, is the model where tiles are allowed to bind as soon as they match on one side, whereas in cooperative tile assembly, some tiles need to match on several sides in order to bind. Previously, exactly one known result (SODA 2014) showed a restriction on the assemblies general non-cooperative self-assembly could achieve, without any implication on its computational expressiveness. With non-square tiles (like polyominos, SODA 2015), other recent works have shown that the model quickly becomes computationally powerful.
Distributed Spatial Multiplexing Systems with Hardware Impairments and Imperfect Channel Estimation under Rank-$1$ Rician Fading Channels
Venue: arXiv cs.IT 2016
Year: 2016

The performance of a multiuser communication system with single-antenna transmitting terminals and a multi-antenna base-station receiver is analytically investigated. The system operates under independent and non-identically distributed rank-$1$ Rician fading channels with imperfect channel estimation and residual hardware impairments (compensation algorithms are assumed, which mitigate the main impairments) at the transceiver. The spatial multiplexing mode of operation is considered where all the users are simultaneously transmitting their streams to the receiver. Zero-forcing is applied along with successive interference cancellation (SIC) as a means for efficient detection of the received streams. New analytical closed-form expressions are derived for some important performance metrics, namely, the outage probability and ergodic capacity of the entire system. Both the analytical expressions and simulation results show the impact of imperfect channel estimation and hardware impairments to the overall system performance in the usage scenarios of massive MIMO and mmWave communication systems.
An Enhanced Model for Stochastic Coordination
Venue: arXiv cs.DC 2016
Year: 2016

Applications developed over the cloud coordinate several, often anonymous, computational resources, distributed over different execution nodes, within flexible architectures. Coordination models able to represent quantitative data provide a powerful basis for their analysis and validation. This paper extends IMCreo, a semantic model for Stochastic reo based on interactive Markov chains, to enhance its scalability, by regarding each channel and node, as well as interface components, as independent stochastic processes that may (or may not) synchronise with the rest of the coordination circuit.
Modeling peer and external influence in online social networks
Venue: arXiv cs.SI 2016
Year: 2016

Opinion polls mediated through a social network can give us, in addition to usual demographics data like age, gender and geographic location, a friendship structure between voters and the temporal dynamics of their activity during the voting process. Using a Facebook application we collected friendship relationships, demographics and votes of over ten thousand users on the referendum on the definition of marriage in Croatia held on 1st of December 2013. We also collected data on online news articles mentioning our application. Publication of these articles align closely with large peaks of voting activity, indicating that these external events have a crucial influence in engaging the voters. Also, existence of strongly connected friendship communities where majority of users vote during short time period, and the fact that majority of users in general tend to friend users that voted the same suggest that peer influence also has its role in engaging the voters. As we are not able to track activity of our users at all times, and we do not know their motivations for expressing their votes through our application, the question is whether we can infer peer and external influence using friendship network of users and the times of their voting. We propose a new method for estimation of magnitude of peer and external influence in friendship network and demonstrate its validity on both simulated and actual data.
Multi-Agent Planning under Local LTL Specifications and Event-Based Synchronization
Venue: arXiv cs.SY 2016
Year: 2016

We study the problem of plan synthesis for multi-agent systems, to achieve complex, high-level, long-term goals that are assigned to each agent individually. As the agents might not be capable of satisfying their respective goals by themselves, requests for other agents' collaborations are a part of the task descriptions. We consider that each agent is modeled as a discrete state-transition system and its task specification takes a form of a linear temporal logic formula, which may contain requirements and constraints on the other agent's behavior. A traditional automata-based approach to multi-agent plan synthesis from such specifications builds on centralized team planning and full team synchronization after each agents' discrete step, and thus suffers from extreme computational demands. We aim at reducing the computational complexity by decomposing the plan synthesis problem into finite horizon planning problems that are solved iteratively, upon the run of the agents. As opposed to full synchronization, we introduce an event-based synchronization that allows our approach to efficiently adapt to different time durations of different agents' discrete steps. We discuss the correctness of the solution and find assumptions, under which the proposed iterative algorithm leads to provable eventual satisfaction of the desired specifications.
Video Analysis of "YouTube Funnies" to Aid the Study of Human Gait and Falls - Preliminary Results and Proof of Concept
Venue: arXiv cs.CV 2016
Year: 2016

Because falls are funny, YouTube and other video sharing sites contain a large repository of real-life falls. We propose extracting gait and balance information from these videos to help us better understand some of the factors that contribute to falls. Proof-of-concept is explored in a single video containing multiple (n=14) falls/non-falls in the presence of an unexpected obstacle. The analysis explores: computing spatiotemporal parameters of gait in a video captured from an arbitrary viewpoint; the relationship between parameters of gait from the last few steps before the obstacle and falling vs. not falling; and the predictive capacity of a multivariate model in predicting a fall in the presence of an unexpected obstacle. Homography transformations correct the perspective projection distortion and allow for the consistent tracking of gait parameters as an individual walks in an arbitrary direction in the scene. A synthetic top view allows for computing the average stride length and a synthetic side view allows for measuring up and down motions of the head. In leave-one-out cross-validation, we were able to correctly predict whether a person would fall or not in 11 out of the 14 cases (78.6%), just by looking at the average stride length and the range of vertical head motion during the 1-4 most recent steps prior to reaching the obstacle.
Sum-networks: Dependency on Characteristic of the Finite Field under Linear Network Coding
Venue: arXiv cs.IT 2016
Year: 2016

Sum-networks are networks where all the terminals demand the sum of the symbols generated at the sources. It has been shown that for any finite set/co-finite set of prime numbers, there exists a sum-network which has a vector linear solution if and only if the characteristic of the finite field belongs to the given set. It has also been shown that for any positive rational number $k/n$, there exists a sum-network which has capacity equal to $k/n$. It is a natural question whether, for any positive rational number $k/n$, and for any finite set/co-finite set of primes $\{p_1,p_2,\ldots,p_l\}$, there exists a sum-network which has a capacity achieving rate $k/n$ fractional linear network coding solution if and only if the characteristic of the finite field belongs to the given set. We show that indeed there exists such a sum-network by constructing such a sum-network.
Inferring individual attributes from search engine queries and auxiliary information
Venue: arXiv cs.IR 2016
Year: 2016

Internet data has surfaced as a primary source for investigation of different aspects of human behavior. A crucial step in such studies is finding a suitable cohort (i.e., a set of users) that shares a common trait of interest to researchers. However, direct identification of users sharing this trait is often impossible, as the data available to researchers is usually anonymized to preserve user privacy. To facilitate research on specific topics of interest, especially in medicine, we introduce an algorithm for identifying a trait of interest in anonymous users. We illustrate how a small set of labeled examples, together with statistical information about the entire population, can be aggregated to obtain labels on unseen examples. We validate our approach using labeled data from the political domain. We provide two applications of the proposed algorithm to the medical domain. In the first, we demonstrate how to identify users whose search patterns indicate they might be suffering from certain types of cancer. In the second, we detail an algorithm to predict the distribution of diseases given their incidence in a subset of the population at study, making it possible to predict disease spread from partial epidemiological data.
Distraction-Based Neural Networks for Document Summarization
Venue: arXiv cs.CL 2016
Year: 2016

Distributed representation learned with neural networks has recently shown to be effective in modeling natural languages at fine granularities such as words, phrases, and even sentences. Whether and how such an approach can be extended to help model larger spans of text, e.g., documents, is intriguing, and further investigation would still be desirable. This paper aims to enhance neural network models for such a purpose. A typical problem of document-level modeling is automatic summarization, which aims to model documents in order to generate summaries. In this paper, we propose neural models to train computers not just to pay attention to specific regions and content of input documents with attention models, but also distract them to traverse between different content of a document so as to better grasp the overall meaning for summarization. Without engineering any features, we train the models on two large datasets. The models achieve the state-of-the-art performance, and they significantly benefit from the distraction modeling, particularly when input documents are long.
Mask-off: Synthesizing Face Images in the Presence of Head-mounted Displays
Venue: arXiv cs.CV 2016
Year: 2016

A head-mounted display (HMD) could be an important component of augmented reality system. However, as the upper face region is seriously occluded by the device, the user experience could be affected in applications such as telecommunication and multi-player video games. In this paper, we first present a novel experimental setup that consists of two near-infrared (NIR) cameras to point to the eye regions and one visible-light RGB camera to capture the visible face region. The main purpose of this paper is to synthesize realistic face images without occlusions based on the images captured by these cameras. To this end, we propose a novel synthesis framework that contains four modules: 3D head reconstruction, face alignment and tracking, face synthesis, and eye synthesis. In face synthesis, we propose a novel algorithm that can robustly align and track a personalized 3D head model given a face that is severely occluded by the HMD. In eye synthesis, in order to generate accurate eye movements and dynamic wrinkle variations around eye regions, we propose another novel algorithm to colorize the NIR eye images and further remove the "red eye" effects caused by the colorization. Results show that both hardware setup and system framework are robust to synthesize realistic face images in video sequences.
Adaptive matching pursuit for sparse signal recovery
Venue: arXiv cs.LG 2016
Year: 2016

Spike and Slab priors have been of much recent interest in signal processing as a means of inducing sparsity in Bayesian inference. Applications domains that benefit from the use of these priors include sparse recovery, regression and classification. It is well-known that solving for the sparse coefficient vector to maximize these priors results in a hard non-convex and mixed integer programming problem. Most existing solutions to this optimization problem either involve simplifying assumptions/relaxations or are computationally expensive. We propose a new greedy and adaptive matching pursuit (AMP) algorithm to directly solve this hard problem. Essentially, in each step of the algorithm, the set of active elements would be updated by either adding or removing one index, whichever results in better improvement. In addition, the intermediate steps of the algorithm are calculated via an inexpensive Cholesky decomposition which makes the algorithm much faster. Results on simulated data sets as well as real-world image recovery challenges confirm the benefits of the proposed AMP, particularly in providing a superior cost-quality trade-off over existing alternatives.
Type oriented parallel programming for Exascale
Venue: arXiv cs.PL 2016
Year: 2016

Whilst there have been great advances in HPC hardware and software in recent years, the languages and models that we use to program these machines have remained much more static. This is not from a lack of effort, but instead by virtue of the fact that the foundation that many programming languages are built on is not sufficient for the level of expressivity required for parallel work. The result is an implicit trade-off between programmability and performance which is made worse due to the fact that, whilst many scientific users are experts within their own fields, they are not HPC experts. Type oriented programming looks to address this by encoding the complexity of a language via the type system. Most of the language functionality is contained within a loosely coupled type library that can be flexibly used to control many aspects such as parallelism. Due to the high level nature of this approach there is much information available during compilation which can be used for optimisation and, in the absence of type information, the compiler can apply sensible default options thus supporting both the expert programmer and novice alike. We demonstrate that, at no performance or scalability penalty when running on up to 8196 cores of a Cray XE6 system, codes written in this type oriented manner provide improved programmability. The programmer is able to write simple, implicit parallel, HPC code at a high level and then explicitly tune by adding additional type information if required.
Perspectives and Networks
Venue: arXiv cs.OH 2016
Year: 2016

The perspective we take on a system determines the features and properties of this system that we are focusing on. It determines where we search for causes to explain the effects on the system that we observe. It determines the terms in which we expect the information about the system to be expressed. And it can also influence the choice of formalism that will be used to convey the information. using Boolean Automata Networks as prototypes of interaction systems, this paper means to start making these considerations concrete in order to draw a practical benefit out of them.
On linear rewriting systems for Boolean logic and some applications to proof theory
Venue: arXiv cs.LO 2016
Year: 2016

Linear rules have played an increasing role in structural proof theory in recent years. It has been observed that the set of all sound linear inference rules in Boolean logic is already coNP-complete, i.e. that every Boolean tautology can be written as a (left- and right-)linear rewrite rule. In this paper we study properties of systems consisting only of linear inferences. Our main result is that the length of any 'nontrivial' derivation in such a system is bound by a polynomial. As a consequence there is no polynomial-time decidable sound and complete system of linear inferences, unless coNP=NP. We draw tools and concepts from term rewriting, Boolean function theory and graph theory in order to access some required intermediate results. At the same time we make several connections between these areas that, to our knowledge, have not yet been presented and constitute a rich theoretical framework for reasoning about linear TRSs for Boolean logic.
Automated Management of Pothole related Disasters Using Image Processing and Geotagging
Venue: arXiv cs.CV 2016
Year: 2016

Potholes though seem inconsequential, may cause accidents resulting in loss of human life. In this paper, we present an automated system to efficiently manage the potholes in a ward by deploying geotagging and image processing techniques that overcomes the drawbacks associated with the existing survey-oriented systems. Image processing is used for identification of target pothole regions in the 2D images using edge detection and morphological image processing operations. A method is developed to accurately estimate the dimensions of the potholes from their images, analyze their area and depth, estimate the quantity of filling material required and therefore enabling pothole attendance on a priority basis. This will further enable the government official to have a fully automated system for effectively managing pothole related disasters.
Personalized Risk Scoring for Critical Care Prognosis using Mixtures of Gaussian Processes
Venue: arXiv cs.AI 2016
Year: 2016

Objective: In this paper, we develop a personalized real-time risk scoring algorithm that provides timely and granular assessments for the clinical acuity of ward patients based on their (temporal) lab tests and vital signs; the proposed risk scoring system ensures timely intensive care unit (ICU) admissions for clinically deteriorating patients. Methods: The risk scoring system learns a set of latent patient subtypes from the offline electronic health record data, and trains a mixture of Gaussian Process (GP) experts, where each expert models the physiological data streams associated with a specific patient subtype. Transfer learning techniques are used to learn the relationship between a patient's latent subtype and her static admission information (e.g. age, gender, transfer status, ICD-9 codes, etc). Results: Experiments conducted on data from a heterogeneous cohort of 6,321 patients admitted to Ronald Reagan UCLA medical center show that our risk score significantly and consistently outperforms the currently deployed risk scores, such as the Rothman index, MEWS, APACHE and SOFA scores, in terms of timeliness, true positive rate (TPR), and positive predictive value (PPV). Conclusion: Our results reflect the importance of adopting the concepts of personalized medicine in critical care settings; significant accuracy and timeliness gains can be achieved by accounting for the patients' heterogeneity. Significance: The proposed risk scoring methodology can confer huge clinical and social benefits on more than 200,000 critically ill inpatient who exhibit cardiac arrests in the US every year.