OpenRaiser/Intern-Atlas huggingface dataset:
A probabilistic version of the game of Zombies and Survivors on graphs
Venue: arXiv cs.DM 2015
Year: 2015

We consider a new probabilistic graph searching game played on graphs, inspired by the familiar game of Cops and Robbers. In Zombies and Survivors, a set of zombies attempts to eat a lone survivor loose on a given graph. The zombies randomly choose their initial location, and during the course of the game, move directly toward the survivor. At each round, they move to the neighbouring vertex that minimizes the distance to the survivor; if there is more than one such vertex, then they choose one uniformly at random. The survivor attempts to escape from the zombies by moving to a neighbouring vertex or staying on his current vertex. The zombies win if eventually one of them eats the survivor by landing on their vertex; otherwise, the survivor wins. The zombie number of a graph is the minimum number of zombies needed to play such that the probability that they win is strictly greater than 1/2. We present asymptotic results for the zombie numbers of several graph families, such as cycles, hypercubes, incidence graphs of projective planes, and Cartesian and toroidal grids.
Globally Tuned Cascade Pose Regression via Back Propagation with Application in 2D Face Pose Estimation and Heart Segmentation in 3D CT Images
Venue: arXiv cs.CV 2015
Year: 2015

Recently, a successful pose estimation algorithm, called Cascade Pose Regression (CPR), was proposed in the literature. Trained over Pose Index Feature, CPR is a regressor ensemble that is similar to Boosting. In this paper we show how CPR can be represented as a Neural Network. Specifically, we adopt a Graph Transformer Network (GTN) representation and accordingly train CPR with Back Propagation (BP) that permits globally tuning. In contrast, previous CPR literature only took a layer wise training without any post fine tuning. We empirically show that global training with BP outperforms layer-wise (pre-)training. Our CPR-GTN adopts a Multi Layer Percetron as the regressor, which utilized sparse connection to learn local image feature representation. We tested the proposed CPR-GTN on 2D face pose estimation problem as in previous CPR literature. Besides, we also investigated the possibility of extending CPR-GTN to 3D pose estimation by doing experiments using 3D Computed Tomography dataset for heart segmentation.
Performance Analysis of Energy-Detection-Based Massive SIMO
Venue: arXiv cs.IT 2015
Year: 2015

Recently, communications systems that are both energy efficient and reliable are under investigation. In this paper, we concentrate on an energy-detection-based transmission scheme where a communication scenario between a transmitter with one antenna and a receiver with significantly many antennas is considered. We assume that the receiver initially calculates the average energy across all antennas, and then decodes the transmitted data by exploiting the average energy level. Then, we calculate the average symbol error probability by means of a maximum a-posteriori probability detector at the receiver. Following that, we provide the optimal decision regions. Furthermore, we develop an iterative algorithm that reaches the optimal constellation diagram under a given average transmit power constraint. Through numerical analysis, we explore the system performance.
Compressed Channel Feedback for Correlated Massive MIMO Systems
Venue: arXiv cs.IT 2015
Year: 2015

Massive multiple-input multiple-output (MIMO) is a promising approach for cellular communication due to its energy efficiency and high achievable data rate. These advantages, however, can be realized only when channel state information (CSI) is available at the transmitter. Since there are many antennas, CSI is too large to feed back without compression. To compress CSI, prior work has applied compressive sensing (CS) techniques and the fact that CSI can be sparsified. The adopted sparsifying bases fail, however, to reflect the spatial correlation and channel conditions or to be feasible in practice. In this paper, we propose a new sparsifying basis that reflects the long-term characteristics of the channel, and needs no change as long as the spatial correlation model does not change. We propose a new reconstruction algorithm for CS, and also suggest dimensionality reduction as a compression method. To feed back compressed CSI in practice, we propose a new codebook for the compressed channel quantization assuming no other-cell interference. Numerical results confirm that the proposed channel feedback mechanisms show better performance in point-to-point (single-user) and point-to-multi-point (multi-user) scenarios.
Improving Collaborations in Neuroscientist Community
Venue: arXiv cs.CY 2015
Year: 2015

In this paper, we present our approach, called SATIS (Semantically AnnotaTed Intentions for Services), relying on intentional process modeling and semantic web technologies and models, to assist collaboration among the members of a neurosciences community. The main expected result of this work is to derive and share semantic web service specifications from a neuro-scientists point of view in order to operationalise image analysis pipelines with web services.
Weakly Supervised Learning of Objects, Attributes and their Associations
Venue: arXiv cs.CV 2015
Year: 2015

When humans describe images they tend to use combinations of nouns and adjectives, corresponding to objects and their associated attributes respectively. To generate such a description automatically, one needs to model objects, attributes and their associations. Conventional methods require strong annotation of object and attribute locations, making them less scalable. In this paper, we model object-attribute associations from weakly labelled images, such as those widely available on media sharing sites (e.g. Flickr), where only image-level labels (either object or attributes) are given, without their locations and associations. This is achieved by introducing a novel weakly supervised non-parametric Bayesian model. Once learned, given a new image, our model can describe the image, including objects, attributes and their associations, as well as their locations and segmentation. Extensive experiments on benchmark datasets demonstrate that our weakly supervised model performs at par with strongly supervised models on tasks such as image description and retrieval based on object-attribute associations.
Joint Belief and Intent Prediction for Collision Avoidance in Autonomous Vehicles
Venue: arXiv cs.RO 2015
Year: 2015

This paper describes a novel method for allowing an autonomous ground vehicle to predict the intent of other agents in an urban environment. This method, termed the cognitive driving framework, models both the intent and the potentially false beliefs of an obstacle vehicle. By modeling the relationships between these variables as a dynamic Bayesian network, filtering can be performed to calculate the intent of the obstacle vehicle as well as its belief about the environment. This joint knowledge can be exploited to plan safer and more efficient trajectories when navigating in an urban environment. Simulation results are presented that demonstrate the ability of the proposed method to calculate the intent of obstacle vehicles as an autonomous vehicle navigates a road intersection such that preventative maneuvers can be taken to avoid imminent collisions.
A Unified Scheme for Two-Receiver Broadcast Channels with Receiver Message Side Information
Venue: arXiv cs.IT 2015
Year: 2015

This paper investigates the capacity regions of two-receiver broadcast channels where each receiver (i) has both common and private-message requests, and (ii) knows part of the private message requested by the other receiver as side information. We first propose a transmission scheme and derive an inner bound for the two-receiver memoryless broadcast channel. We next prove that this inner bound is tight for the deterministic channel and the more capable channel, thereby establishing their capacity regions. We show that this inner bound is also tight for all classes of two-receiver broadcast channels whose capacity regions were known prior to this work. Our proposed scheme is consequently a unified capacity-achieving scheme for these classes of broadcast channels.
Knowledge reduction of dynamic covering decision information systems with immigration of more objects
Venue: arXiv cs.AI 2015
Year: 2015

In practical situations, it is of interest to investigate computing approximations of sets as an important step of knowledge reduction of dynamic covering decision information systems. In this paper, we present incremental approaches to computing the type-1 and type-2 characteristic matrices of dynamic coverings whose cardinalities increase with immigration of more objects. We also present the incremental algorithms of computing the second and sixth lower and upper approximations of sets in dynamic covering approximation spaces.
Discovering Restricted Regular Expressions with Interleaving
Venue: arXiv cs.DB 2015
Year: 2015

Discovering a concise schema from given XML documents is an important problem in XML applications. In this paper, we focus on the problem of learning an unordered schema from a given set of XML examples, which is actually a problem of learning a restricted regular expression with interleaving using positive example strings. Schemas with interleaving could present meaningful knowledge that cannot be disclosed by previous inference techniques. Moreover, inference of the minimal schema with interleaving is challenging. The problem of finding a minimal schema with interleaving is shown to be NP-hard. Therefore, we develop an approximation algorithm and a heuristic solution to tackle the problem using techniques different from known inference algorithms. We do experiments on real-world data sets to demonstrate the effectiveness of our approaches. Our heuristic algorithm is shown to produce results that are very close to optimal.
Bi-polynomial rank and determinantal complexity
Venue: arXiv cs.CC 2015
Year: 2015

The permanent vs. determinant problem is one of the most important problems in theoretical computer science, and is the main target of geometric complexity theory proposed by Mulmuley and Sohoni. The current best lower bound for the determinantal complexity of the d by d permanent polynomial is d^2/2, due to Mignon and Ressayre in 2004. Inspired by their proof method, we introduce a natural rank concept of polynomials, called the bi-polynomial rank. The bi-polynomial rank is related to width of an arithmetic branching program. The bi-polynomial rank of a homogeneous polynomial p of even degree 2k is defined as the minimum n such that p can be written as a summation of n products of polynomials of degree k. We prove that the bi-polynomial rank gives a lower bound of the determinantal complexity. As a consequence, the above Mignon and Ressayre bound is improved to (d-1)^2 + 1 over the field of reals. We show that the computation of the bi-polynomial rank is formulated as a rank minimization problem. Applying the concave minimization technique, we reduce the problem of lower-bounding determinantal complexity to that of proving the positive semidefiniteness of matrices, and this is a new approach for the permanent vs. determinant problem. We propose a computational approach for giving a lower bound of this rank minimization, via techniques of the concave minimization. This also yields a new strategy to attack the permanent vs. determinant problem.
A Graph Algorithmic Approach to Separate Direct from Indirect Neural Interactions
Venue: arXiv cs.IT 2015
Year: 2015

Network graphs have become a popular tool to represent complex systems composed of many interacting subunits; especially in neuroscience, network graphs are increasingly used to represent and analyze functional interactions between neural sources. Interactions are often reconstructed using pairwise bivariate analyses, overlooking their multivariate nature: it is neglected that investigating the effect of one source on a target necessitates to take all other sources as potential nuisance variables into account; also combinations of sources may act jointly on a given target. Bivariate analyses produce networks that may contain spurious interactions, which reduce the interpretability of the network and its graph metrics. A truly multivariate reconstruction, however, is computationally intractable due to combinatorial explosion in the number of potential interactions. Thus, we have to resort to approximative methods to handle the intractability of multivariate interaction reconstruction, and thereby enable the use of networks in neuroscience. Here, we suggest such an approximative approach in the form of an algorithm that extends fast bivariate interaction reconstruction by identifying potentially spurious interactions post-hoc: the algorithm flags potentially spurious edges, which may then be pruned from the network. This produces a statistically conservative network approximation that is guaranteed to contain non-spurious interactions only. We describe the algorithm and present a reference implementation to test its performance. We discuss the algorithm in relation to other approximative multivariate methods and highlight suitable application scenarios. Our approach is a tractable and data-efficient way of reconstructing approximative networks of multivariate interactions. It is preferable if available data are limited or if fully multivariate approaches are computationally infeasible.
A note on linear codes and nonassociative algebras obtained from skew-polynomial rings
Venue: arXiv cs.IT 2015
Year: 2015

Different approaches to construct linear codes using skew polynomials can be unified by using the nonassociative algebras built from skew-polynomial rings by Petit.
A linear time algorithm to compute the impact of all the articulation points
Venue: arXiv cs.DS 2015
Year: 2015

The articulation points of an undirected connected graphs are those vertices whose removal increases the number of connected components of the graph, i.e. the vertices whose removal disconnects the graph. However, not all the articulation points are equal: the removal of some of them might end in a single vertex disconnected from the graph, whilst in other cases the graph can be split in several small pieces. In order to measure the effect of the removal of an articulation point, in \cite{AFL12} has been proposed the impact, defined as the number of vertices that get disconnected from the main (largest) surviving connected component (CC). In this paper we present the first linear time algorithm ($\mathcal{O}(m+n)$ for a graph with $n$ vertices and $m$ edges) to compute the impact of all the articulation points of the graph, thus improving from the $\mathcal{O}(a(m+n))\approx\mathcal{O}(nm+n^2)$ of the naïve algorithm, with $a$ being the number of articulation points of the graph.
Coordinated Multi-cell Beamforming for Massive MIMO: A Random Matrix Approach
Venue: arXiv cs.IT 2015
Year: 2015

We consider the problem of coordinated multi- cell downlink beamforming in massive multiple input multiple output (MIMO) systems consisting of N cells, Nt antennas per base station (BS) and K user terminals (UTs) per cell. Specifically, we formulate a multi-cell beamforming algorithm for massive MIMO systems which requires limited amount of information exchange between the BSs. The design objective is to minimize the aggregate transmit power across all the BSs subject to satisfying the user signal to interference noise ratio (SINR) constraints. The algorithm requires the BSs to exchange parameters which can be computed solely based on the channel statistics rather than the instantaneous CSI. We make use of tools from random matrix theory to formulate the decentralized algorithm. We also characterize a lower bound on the set of target SINR values for which the decentralized multi-cell beamforming algorithm is feasible. We further show that the performance of our algorithm asymptotically matches the performance of the centralized algorithm with full CSI sharing. While the original result focuses on minimizing the aggregate transmit power across all the BSs, we formulate a heuristic extension of this algorithm to incorporate a practical constraint in multi-cell systems, namely the individual BS transmit power constraints. Finally, we investigate the impact of imperfect CSI and pilot contamination effect on the performance of the decentralized algorithm, and propose a heuristic extension of the algorithm to accommodate these issues. Simulation results illustrate that our algorithm closely satisfies the target SINR constraints and achieves minimum power in the regime of massive MIMO systems. In addition, it also provides substantial power savings as compared to zero-forcing beamforming when the number of antennas per BS is of the same orders of magnitude as the number of UTs per cell.
Data Dissemination Problem in Wireless Networks
Venue: arXiv cs.IT 2015
Year: 2015

In this work, we formulate and study a data dissemination problem, which can be viewed as a generalization of the index coding problem and of the data exchange problem to networks with an arbitrary topology. We define $r$-solvable networks, in which data dissemination can be achieved in $r > 0$ communications rounds. We show that the optimum number of transmissions for any one-round communications scheme is given by the minimum rank of a certain constrained family of matrices. For a special case of this problem, called bipartite data dissemination problem, we present lower and upper graph-theoretic bounds on the optimum number of transmissions. For general $r$-solvable networks, we derive an upper bound on the minimum number of transmissions in any scheme with $\geq r$ rounds. We experimentally compare the obtained upper bound to a simple lower bound.
The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems
Venue: arXiv cs.DS 2015
Year: 2015

We consider single-sink network flow problems. An instance consists of a capacitated graph (directed or undirected), a sink node $t$ and a set of demands that we want to send to the sink. Here demand $i$ is located at a node $s_i$ and requests an amount $d_i$ of flow capacity in order to route successfully. Two standard objectives are to maximise (i) the number of demands (cardinality) and (ii) the total demand (throughput) that can be routed subject to the capacity constraints. Furthermore, we examine these maximisation problems for three specialised types of network flow: unsplittable, confluent and priority flows. In the {\em unsplittable flow} problem (UFP), we have edge capacities, and the demand for $s_i$ must be routed on a single path. In the {\em confluent flow} problem, we have node capacities, and the final flow must induce a tree. Both of these problems have been studied extensively, primarily in the single-sink setting. However, most of this work imposed the {\em no-bottleneck assumption} (that the maximum demand $d_{max}$ is at most the minimum capacity $u_{min}$). Given the no-bottleneck assumption (NBA), there is a factor $4.43$-approximation algorithm due to Dinitz et al. for the unsplittable flow problem. Under the stronger assumption of uniform capacities, there is a factor $3$-approximation algorithm due to Chen et al. for the confluent flow problem. However, unlike the UFP, we show that a constant factor approximation algorithm cannot be obtained for the single-sink confluent flows even {\bf with} the NBA. Without NBA, we show that maximum cardinality single-sink UFP is hard to approximate to within a factor $n^{.5-ε}$ even when all demands lie in a small interval $[1,1+Δ]$ where $Δ>0$ (but has polynomial input size). This is very sharp since when $Δ=0$, this becomes a maximum flow problem.
Green Wireless Power Transfer Networks
Venue: arXiv cs.NI 2015
Year: 2015

A Wireless Power Transfer Network (WPTN) aims to support devices with cable-less energy on-demand. Unfortunately, wireless power transfer itself-especially through radio frequency radiation rectification-is fairly inefficient due to decaying power with distance, antenna polarization, etc. Consequently, idle charging needs to be minimized to reduce already large costs of providing energy to the receivers and at the same time reduce the carbon footprint of WPTNs. In turn, energy saving in a WPTN can be boosted by simply switching off the energy transmitter when the received energy is too weak for rectification. Therefore in this paper we propose, and experimentally evaluate, two "green" protocols for the control plane of static charger/mobile receiver WPTN aimed at optimizing the charger workflow to make WPTN green. Those protocols are: 'beaconing', where receivers advertise their presence to WPTN, and 'probing' exploiting the receiver feedback from WTPN on the level of received energy. We demonstrate that both protocols reduce the unnecessary WTPN uptime, however trading it for the reduced energy provision, compared to the base case of 'WPTN charger always on'. For example, our system (in our experiments) saves at most approx. 80% of energy and increases 5.5 times the efficiency with only approx. 17% less energy possibly harvested.
Approximation of non-boolean 2CSP
Venue: arXiv cs.DS 2015
Year: 2015

We develop a polynomial time $Ω\left ( \frac 1R \log R \right)$ approximate algorithm for Max 2CSP-$R$, the problem where we are given a collection of constraints, each involving two variables, where each variable ranges over a set of size $R$, and we want to find an assignment to the variables that maximizes the number of satisfied constraints. Assuming the Unique Games Conjecture, this is the best possible approximation up to constant factors. Previously, a $1/R$-approximate algorithm was known, based on linear programming. Our algorithm is based on semidefinite programming (SDP) and on a novel rounding technique. The SDP that we use has an almost-matching integrality gap.
Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile
Venue: arXiv cs.DS 2015
Year: 2015

We prove two generalizations of the Cheeger's inequality. The first generalization relates the second eigenvalue to the edge expansion and the vertex expansion of the graph G, $λ_2 = Ω(ϕ^V(G) ϕ(G))$, where $ϕ^V(G)$ denotes the robust vertex expansion of G and $ϕ(G)$ denotes the edge expansion of G. The second generalization relates the second eigenvalue to the edge expansion and the expansion profile of G, for all $k \ge 2$, $λ_2 = Ω(ϕ_k(G) ϕ(G) / k)$, where $ϕ_k(G)$ denotes the k-way expansion of G. These show that the spectral partitioning algorithm has better performance guarantees when $ϕ^V(G)$ is large (e.g. planted random instances) or $ϕ_k(G)$ is large (instances with few disjoint non-expanding sets). Both bounds are tight up to a constant factor. Our approach is based on a method to analyze solutions of Laplacian systems, and this allows us to extend the results to local graph partitioning algorithms. In particular, we show that our approach can be used to analyze personal pagerank vectors, and to give a local graph partitioning algorithm for the small-set expansion problem with performance guarantees similar to the generalizations of Cheeger's inequality. We also present a spectral approach to prove similar results for the truncated random walk algorithm. These show that local graph partitioning algorithms almost match the performance of the spectral partitioning algorithm, with the additional advantages that they apply to the small-set expansion problem and their running time could be sublinear. Our techniques provide common approaches to analyze the spectral partitioning algorithm and local graph partitioning algorithms.