OpenRaiser/Intern-Atlas huggingface dataset:
Clique-width of Graph Classes Defined by Two Forbidden Induced Subgraphs
Venue: arXiv cs.DM 2015
Year: 2015

If a graph has no induced subgraph isomorphic to any graph in a finite family $\{H_1,\ldots,H_p\}$, it is said to be $(H_1,\ldots,H_p)$-free. The class of $H$-free graphs has bounded clique-width if and only if $H$ is an induced subgraph of the 4-vertex path $P_4$. We study the (un)boundedness of the clique-width of graph classes defined by two forbidden induced subgraphs $H_1$ and $H_2$. Prior to our study it was not known whether the number of open cases was finite. We provide a positive answer to this question. To reduce the number of open cases we determine new graph classes of bounded clique-width and new graph classes of unbounded clique-width. For obtaining the latter results we first present a new, generic construction for graph classes of unbounded clique-width. Our results settle the boundedness or unboundedness of the clique-width of the class of $(H_1,H_2)$-free graphs (i) for all pairs $(H_1,H_2)$, both of which are connected, except two non-equivalent cases, and (ii) for all pairs $(H_1,H_2)$, at least one of which is not connected, except 11 non-equivalent cases. We also consider classes characterized by forbidding a finite family of graphs $\{H_1,\ldots,H_p\}$ as subgraphs, minors and topological minors, respectively, and completely determine which of these classes have bounded clique-width. Finally, we show algorithmic consequences of our results for the graph colour
Efficient and Reasonable Object-Oriented Concurrency
Venue: arXiv cs.DC 2015
Year: 2015

Making threaded programs safe and easy to reason about is one of the chief difficulties in modern programming. This work provides an efficient execution model for SCOOP, a concurrency approach that provides not only data race freedom but also pre/postcondition reasoning guarantees between threads. The extensions we propose influence both the underlying semantics to increase the amount of concurrent execution that is possible, exclude certain classes of deadlocks, and enable greater performance. These extensions are used as the basis an efficient runtime and optimization pass that improve performance 15x over a baseline implementation. This new implementation of SCOOP is also 2x faster than other well-known safe concurrent languages. The measurements are based on both coordination-intensive and data-manipulation-intensive benchmarks designed to offer a mixture of workloads.
On the equivalence between low rank matrix completion and tensor rank
Venue: arXiv cs.NA 2015
Year: 2015

The Rank Minimization Problem asks to find a matrix of lowest rank inside a linear variety of the space of n x n matrices. The Low Rank Matrix Completion problem asks to complete a partially filled matrix such that the resulting matrix has smallest possible rank. The Tensor Rank Problem asks to determine the rank of a tensor. We show that these three problems are equivalent: each one of the problems can be reduced to the other two.
Recursive Neural Networks Can Learn Logical Semantics
Venue: arXiv cs.CL 2015
Year: 2015

Tree-structured recursive neural networks (TreeRNNs) for sentence meaning have been successful for many applications, but it remains an open question whether the fixed-length representations that they learn can support tasks as demanding as logical deduction. We pursue this question by evaluating whether two such models---plain TreeRNNs and tree-structured neural tensor networks (TreeRNTNs)---can correctly learn to identify logical relationships such as entailment and contradiction using these representations. In our first set of experiments, we generate artificial data from a logical grammar and use it to evaluate the models' ability to learn to handle basic relational reasoning, recursive structures, and quantification. We then evaluate the models on the more natural SICK challenge data. Both models perform competitively on the SICK data and generalize well in all three experiments on simulated data, suggesting that they can learn suitable representations for logical inference in natural language.
Exploring Algorithmic Limits of Matrix Rank Minimization under Affine Constraints
Venue: arXiv cs.LG 2015
Year: 2015

Many applications require recovering a matrix of minimal rank within an affine constraint set, with matrix completion a notable special case. Because the problem is NP-hard in general, it is common to replace the matrix rank with the nuclear norm, which acts as a convenient convex surrogate. While elegant theoretical conditions elucidate when this replacement is likely to be successful, they are highly restrictive and convex algorithms fail when the ambient rank is too high or when the constraint set is poorly structured. Non-convex alternatives fare somewhat better when carefully tuned; however, convergence to locally optimal solutions remains a continuing source of failure. Against this backdrop we derive a deceptively simple and parameter-free probabilistic PCA-like algorithm that is capable, over a wide battery of empirical tests, of successful recovery even at the theoretical limit where the number of measurements equal the degrees of freedom in the unknown low-rank matrix. Somewhat surprisingly, this is possible even when the affine constraint set is highly ill-conditioned. While proving general recovery guarantees remains evasive for non-convex algorithms, Bayesian-inspired or otherwise, we nonetheless show conditions whereby the underlying cost function has a unique stationary point located at the global optimum; no existing cost function we are aware of satisfies this same property. We conclude with a simple computer vision application involving image rectification and a standard collaborative filtering benchmark.
Hadamard Coded Modulation for Visible Light Communications
Venue: arXiv cs.IT 2015
Year: 2015

Visible light communication (VLC) systems using the indoor lighting system to also provide downlink communications require high average optical powers in order to satisfy the illumination needs. This can cause high amplitude signals common in higher-order modulation schemes to be clipped by the peak power constraint of the light emitting diode (LED) and lead to high signal distortion. In this paper we introduce Hadamard coded modulation (HCM) to achieve low error probabilities in LED-based VLC systems needing high average optical powers. This technique uses a fast Walsh-Hadamard transform (FWHT) to modulate the data as an alternative modulation technique to orthogonal frequency division multiplexing (OFDM). HCM achieves a better performance for high illumination levels because of its small peak to average power ratio (PAPR). The power efficiency of HCM can be improved by reducing the DC part of the transmitted signals without losing any information. The resulting so-called DC-reduced HCM (DCR-HCM) is well suited to environments requiring dimmer lighting as it transmits signals with lower peak amplitudes compared to HCM, which are thus subject to less nonlinear distortion. Interleaving can be applied to HCM to make the resulting signals more resistant against inter-symbol interference (ISI) in dispersive VLC links.
Reconstruction/Non-reconstruction Thresholds for Colourings of General Galton-Watson Trees
Venue: arXiv cs.DM 2015
Year: 2015

The broadcasting models on trees arise in many contexts such as discrete mathematics, biology statistical physics and cs. In this work, we consider the colouring model. A basic question here is whether the root's assignment affects the distribution of the colourings at the vertices at distance h from the root. This is the so-called "reconstruction problem". For a d-ary tree it is well known that d/ln (d) is the reconstruction threshold. That is, for k=(1+eps)d/ln(d) we have non-reconstruction while for k=(1-eps)d/ln(d) we have. Here, we consider the largely unstudied case where the underlying tree is chosen according to a predefined distribution. In particular, our focus is on the well-known Galton-Watson trees. This model arises naturally in many contexts, e.g. the theory of spin-glasses and its applications on random Constraint Satisfaction Problems (rCSP). The aforementioned study focuses on Galton-Watson trees with offspring distribution B(n,d/n), i.e. the binomial with parameters n and d/n, where d is fixed. Here we consider a broader version of the problem, as we assume general offspring distribution, which includes B(n,d/n) as a special case. Our approach relates the corresponding bounds for (non)reconstruction to certain concentration properties of the offspring distribution. This allows to derive reconstruction thresholds for a very wide family of offspring distributions, which includes B(n,d/n). A very interesting corollary is that for distributions with expected offspring d, we get reconstruction threshold d/ln(d) under weaker concentration conditions than what we have in B(n,d/n). Furthermore, our reconstruction threshold for the random colorings of Galton-Watson with offspring B(n,d/n), implies the reconstruction threshold for the random colourings of G(n,d/n).
A Divide-and-Conquer Algorithm for Betweenness Centrality
Venue: arXiv cs.DS 2015
Year: 2015

The problem of efficiently computing the betweenness centrality of nodes has been researched extensively. To date, the best known exact and centralized algorithm for this task is an algorithm proposed in 2001 by Brandes. The contribution of our paper is Brandes++, an algorithm for exact efficient computation of betweenness centrality. The crux of our algorithm is that we create a sketch of the graph, that we call the skeleton, by replacing subgraphs with simpler graph structures. Depending on the underlying graph structure, using this skeleton and by keeping appropriate summaries Brandes++ we can achieve significantly low running times in our computations. Extensive experimental evaluation on real life datasets demonstrate the efficacy of our algorithm for different types of graphs. We release our code for benefit of the research community.
MGF Approach to the Analysis of Generalized Two-Ray Fading Models
Venue: arXiv cs.IT 2015
Year: 2015

We analyze a class of Generalized Two-Ray (GTR) fading channels that consist of two line of sight (LOS) components with random phase plus a diffuse component. We derive a closed form expression for the moment generating function (MGF) of the signal-to-noise ratio (SNR) for this model, which greatly simplifies its analysis. This expression arises from the observation that the GTR fading model can be expressed in terms of a conditional underlying Rician distribution. We illustrate the approach to derive simple expressions for statistics and performance metrics of interest such as the amount of fading, the level crossing rate, the symbol error rate, and the ergodic capacity in GTR fading channels. We also show that the effect of considering a more general distribution for the phase difference between the LOS components has an impact on the average SNR.
Zipf's law holds for phrases, not words
Venue: arXiv cs.CL 2015
Year: 2015

With Zipf's law being originally and most famously observed for word frequency, it is surprisingly limited in its applicability to human language, holding over no more than three to four orders of magnitude before hitting a clear break in scaling. Here, building on the simple observation that phrases of one or more words comprise the most coherent units of meaning in language, we show empirically that Zipf's law for phrases extends over as many as nine orders of rank magnitude. In doing so, we develop a principled and scalable statistical mechanical method of random text partitioning, which opens up a rich frontier of rigorous text analysis via a rank ordering of mixed length phrases.
Identifying Influential Nodes in Bipartite Networks Using the Clustering Coefficient
Venue: arXiv cs.SI 2015
Year: 2015

The identification of influential nodes in complex network can be very challenging. If the network has a community structure, centrality measures may fail to identify the complete set of influential nodes, as the hubs and other central nodes of the network may lie inside only one community. Here we define a bipartite clustering coefficient that, by taking differently structured clusters into account, can find important nodes across communities.
On Deterministic Linear Network Coded Broadcast and Its Relation to Matroid Theory
Venue: arXiv cs.IT 2015
Year: 2015

Deterministic linear network coding (DLNC) is an important family of network coding techniques for wireless packet broadcast. In this paper, we show that DLNC is strongly related to and can be effectively studied using matroid theory without bridging index coding. We prove the equivalence between the DLNC solution and matrix matroid. We use this equivalence to study the performance limits of DLNC in terms of the number of transmissions and its dependence on the finite field size. Specifically, we derive the sufficient and necessary condition for the existence of perfect DLNC solutions and prove that such solutions may not exist over certain finite fields. We then show that identifying perfect solutions over any finite field is still an open problem in general. To fill this gap, we develop a heuristic algorithm which employs graphic matroids to find perfect DLNC solutions over any finite field. Numerical results show that its performance in terms of minimum number of transmissions is close to the lower bound, and is better than random linear network coding when the field size is not so large.
Compressive Imaging and Characterization of Sparse Light Deflection Maps
Venue: arXiv cs.CV 2015
Year: 2015

Light rays incident on a transparent object of uniform refractive index undergo deflections, which uniquely characterize the surface geometry of the object. Associated with each point on the surface is a deflection map (or spectrum) which describes the pattern of deflections in various directions. This article presents a novel method to efficiently acquire and reconstruct sparse deflection spectra induced by smooth object surfaces. To this end, we leverage the framework of Compressed Sensing (CS) in a particular implementation of a schlieren deflectometer, i.e., an optical system providing linear measurements of deflection spectra with programmable spatial light modulation patterns. We design those modulation patterns on the principle of spread spectrum CS for reducing the number of observations. The ability of our device to simultaneously observe the deflection spectra on a dense discretization of the object surface is related to a Multiple Measurement Vector (MMV) model. This scheme allows us to estimate both the noise power and the instrumental point spread function. We formulate the spectrum reconstruction task as the solving of a linear inverse problem regularized by an analysis sparsity prior using a translation invariant wavelet frame. Our results demonstrate the capability and advantages of using a CS based approach for deflectometric imaging both on simulated data and experimental deflectometric data. Finally, the paper presents an extension of our method showing how we can extract the main deflection direction in each point of the object surface from a few compressive measurements, without needing any costly reconstruction procedures. This compressive characterization is then confirmed with experimental results on simple plano-convex and multifocal intra-ocular lenses studying the evolution of the main deflection as a function of the object point location.
Fixed-Parameter Tractability of Token Jumping on Planar Graphs
Venue: arXiv cs.DM 2015
Year: 2015

Suppose that we are given two independent sets $I_0$ and $I_r$ of a graph such that $|I_0| = |I_r|$, and imagine that a token is placed on each vertex in $I_0$. The token jumping problem is to determine whether there exists a sequence of independent sets which transforms $I_0$ into $I_r$ so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. This problem is known to be PSPACE-complete even for planar graphs of maximum degree three, and W[1]-hard for general graphs when parameterized by the number of tokens. In this paper, we present a fixed-parameter algorithm for the token jumping problem on planar graphs, where the parameter is only the number of tokens. Furthermore, the algorithm can be modified so that it finds a shortest sequence for a yes-instance. The same scheme of the algorithms can be applied to a wider class of graphs, $K_{3,t}$-free graphs for any fixed integer $t \ge 3$, and it yields fixed-parameter algorithms.
Complexity Measures and Concept Learning
Venue: arXiv cs.IT 2015
Year: 2015

The nature of concept learning is a core question in cognitive science. Theories must account for the relative difficulty of acquiring different concepts by supervised learners. For a canonical set of six category types, two distinct orderings of classification difficulty have been found. One ordering, which we call paradigm-specific, occurs when adult human learners classify objects with easily distinguishable characteristics such as size, shape, and shading. The general order occurs in all other known cases: when adult humans classify objects with characteristics that are not readily distinguished (e.g., brightness, saturation, hue); for children and monkeys; and when categorization difficulty is extrapolated from errors in identification learning. The paradigm-specific order was found to be predictable mathematically by measuring the logical complexity of tasks, i.e., how concisely the solution can be represented by logical rules. However, logical complexity explains only the paradigm-specific order but not the general order. Here we propose a new difficulty measurement, information complexity, that calculates the amount of uncertainty remaining when a subset of the dimensions are specified. This measurement is based on Shannon entropy. We show that, when the metric extracts minimal uncertainties, this new measurement predicts the paradigm-specific order for the canonical six category types, and when the metric extracts average uncertainties, this new measurement predicts the general order. Moreover, for learning category types beyond the canonical six, we find that the minimal-uncertainty formulation correctly predicts the paradigm-specific order as well or better than existing metrics (Boolean complexity and GIST) in most cases.
Asymmetric Evaluations of Erasure and Undetected Error Probabilities
Venue: arXiv cs.IT 2015
Year: 2015

The problem of channel coding with the erasure option is revisited for discrete memoryless channels. The interplay between the code rate, the undetected and total error probabilities is characterized. Using the information spectrum method, a sequence of codes of increasing blocklengths $n$ is designed to illustrate this tradeoff. Furthermore, for additive discrete memoryless channels with uniform input distribution, we establish that our analysis is tight with respect to the ensemble average. This is done by analysing the ensemble performance in terms of a tradeoff between the code rate, the undetected and the total errors. This tradeoff is parametrized by the threshold in a generalized likelihood ratio test. Two asymptotic regimes are studied. First, the code rate tends to the capacity of the channel at a rate slower than $n^{-1/2}$ corresponding to the moderate deviations regime. In this case, both error probabilities decay subexponentially and asymmetrically. The precise decay rates are characterized. Second, the code rate tends to capacity at a rate of $n^{-1/2}$. In this case, the total error probability is asymptotically a positive constant while the undetected error probability decays as $\exp(- b n^{ 1/2})$ for some $b>0$. The proof techniques involve applications of a modified (or "shifted") version of the Gärtner-Ellis theorem and the type class enumerator method to characterize the asymptotic behavior of a sequence of cumulant generating functions.
Geometric Tight Frame based Stylometry for Art Authentication of van Gogh Paintings
Venue: arXiv cs.LG 2015
Year: 2015

This paper is about authenticating genuine van Gogh paintings from forgeries. The authentication process depends on two key steps: feature extraction and outlier detection. In this paper, a geometric tight frame and some simple statistics of the tight frame coefficients are used to extract features from the paintings. Then a forward stage-wise rank boosting is used to select a small set of features for more accurate classification so that van Gogh paintings are highly concentrated towards some center point while forgeries are spread out as outliers. Numerical results show that our method can achieve 86.08% classification accuracy under the leave-one-out cross-validation procedure. Our method also identifies five features that are much more predominant than other features. Using just these five features for classification, our method can give 88.61% classification accuracy which is the highest so far reported in literature. Evaluation of the five features is also performed on two hundred datasets generated by bootstrap sampling with replacement. The median and the mean are 88.61% and 87.77% respectively. Our results show that a small set of statistics of the tight frame coefficients along certain orientations can serve as discriminative features for van Gogh paintings. It is more important to look at the tail distributions of such directional coefficients than mean values and standard deviations. It reflects a highly consistent style in van Gogh's brushstroke movements, where many forgeries demonstrate a more diverse spread in these features.
Adaptive Multicell 3D Beamforming in Multi-Antenna Cellular Networks
Venue: arXiv cs.IT 2015
Year: 2015

We consider a cellular network with multi-antenna base stations (BSs) and single-antenna users, multicell cooperation, imperfect channel state information, and directional antennas each with a vertically adjustable beam. We investigate the impact of the elevation angle of the BS antenna pattern, denoted as tilt, on the performance of the considered network when employing either a conventional single-cell transmission or a fully cooperative multicell transmission. Using the results of this investigation, we propose a novel hybrid multicell cooperation technique in which the intercell interference is controlled via either cooperative beamforming in the horizontal plane or coordinated beamfroming in the vertical plane of the wireless channel, denoted as adaptive multicell 3D beamforming. The main idea is to divide the coverage area into two disjoint vertical regions and adapt the multicell cooperation strategy at the BSs when serving each region. A fair scheduler is used to share the time-slots between the vertical regions. It is shown that the proposed technique can achieve performance comparable to that of a fully cooperative transmission but with a significantly lower complexity and signaling requirements. To make the performance analysis computationally efficient, analytical expressions for the user ergodic rates under different beamforming strategies are also derived.