OpenRaiser/Intern-Atlas huggingface dataset:
FPT Algorithms and Kernels for the Directed $k$-Leaf Problem
Venue: arXiv cs.DS 2009
Year: 2009

A subgraph $T$ of a digraph $D$ is an {\em out-branching} if $T$ is an oriented spanning tree with only one vertex of in-degree zero (called the {\em root}). The vertices of $T$ of out-degree zero are {\em leaves}. In the {\sc Directed $k$-Leaf} Problem, we are given a digraph $D$ and an integral parameter $k$, and we are to decide whether $D$ has an out-branching with at least $k$ leaves. Recently, Kneis et al. (2008) obtained an algorithm for the problem of running time $4^{k}\cdot n^{O(1)}$. We describe a new algorithm for the problem of running time $3.72^{k}\cdot n^{O(1)}$. In {\sc Rooted Directed $k$-Leaf} Problem, apart from $D$ and $k$, we are given a vertex $r$ of $D$ and we are to decide whether $D$ has an out-branching rooted at $r$ with at least $k$ leaves. Very recently, Fernau et al. (2008) found an $O(k^3)$-size kernel for {\sc Rooted Directed $k$-Leaf}. In this paper, we obtain an $O(k)$ kernel for {\sc Rooted Directed $k$-Leaf} restricted to acyclic digraphs.
Effect of Tuned Parameters on a LSA MCQ Answering Model
Venue: arXiv cs.LG 2009
Year: 2009

This paper presents the current state of a work in progress, whose objective is to better understand the effects of factors that significantly influence the performance of Latent Semantic Analysis (LSA). A difficult task, which consists in answering (French) biology Multiple Choice Questions, is used to test the semantic properties of the truncated singular space and to study the relative influence of main parameters. A dedicated software has been designed to fine tune the LSA semantic space for the Multiple Choice Questions task. With optimal parameters, the performances of our simple model are quite surprisingly equal or superior to those of 7th and 8th grades students. This indicates that semantic spaces were quite good despite their low dimensions and the small sizes of training data sets. Besides, we present an original entropy global weighting of answers' terms of each question of the Multiple Choice Questions which was necessary to achieve the model's success.
Novel Blind Signal Classification Method Based on Data Compression
Venue: arXiv cs.IT 2009
Year: 2009

This paper proposes a novel algorithm for signal classification problems. We consider a non-stationary random signal, where samples can be classified into several different classes, and samples in each class are identically independently distributed with an unknown probability distribution. The problem to be solved is to estimate the probability distributions of the classes and the correct membership of the samples to the classes. We propose a signal classification method based on the data compression principle that the accurate estimation in the classification problems induces the optimal signal models for data compression. The method formulates the classification problem as an optimization problem, where a so called {"classification gain"} is maximized. In order to circumvent the difficulties in integer optimization, we propose a continuous relaxation based algorithm. It is proven in this paper that asymptotically vanishing optimality loss is incurred by the continuous relaxation. We show by simulation results that the proposed algorithm is effective, robust and has low computational complexity. The proposed algorithm can be applied to solve various multimedia signal segmentation, analysis, and pattern recognition problems.
The Complexity of Propositional Implication
Venue: arXiv cs.CC 2009
Year: 2009

The question whether a set of formulae G implies a formula f is fundamental. The present paper studies the complexity of the above implication problem for propositional formulae that are built from a systematically restricted set of Boolean connectives. We give a complete complexity classification for all sets of Boolean functions in the meaning of Post's lattice and show that the implication problem is efficentily solvable only if the connectives are definable using the constants {false,true} and only one of {and,or,xor}. The problem remains coNP-complete in all other cases. We also consider the restriction of G to singletons.
Linear Processing and Sum Throughput in the Multiuser MIMO Downlink
Venue: arXiv cs.IT 2009
Year: 2009

We consider linear precoding and decoding in the downlink of a multiuser multiple-input, multiple-output (MIMO) system, wherein each user may receive more than one data stream. We propose several mean squared error (MSE) based criteria for joint transmit-receive optimization and establish a series of relationships linking these criteria to the signal-to-interference-plus-noise ratios of individual data streams and the information theoretic channel capacity under linear minimum MSE decoding. In particular, we show that achieving the maximum sum throughput is equivalent to minimizing the product of MSE matrix determinants (PDetMSE). Since the PDetMSE minimization problem does not admit a computationally efficient solution, a simplified scalar version of the problem is considered that minimizes the product of mean squared errors (PMSE). An iterative algorithm is proposed to solve the PMSE problem, and is shown to provide near-optimal performance with greatly reduced computational complexity. Our simulations compare the achievable sum rates under linear precoding strategies to the sum capacity for the broadcast channel.
Necessary Conditions for Discontinuities of Multidimensional Size Functions
Venue: arXiv cs.CG 2009
Year: 2009

Some new results about multidimensional Topological Persistence are presented, proving that the discontinuity points of a k-dimensional size function are necessarily related to the pseudocritical or special values of the associated measuring function.
Exact Exponential Time Algorithms for Max Internal Spanning Tree
Venue: arXiv cs.DS 2009
Year: 2009

We consider the NP-hard problem of finding a spanning tree with a maximum number of internal vertices. This problem is a generalization of the famous Hamiltonian Path problem. Our dynamic-programming algorithms for general and degree-bounded graphs have running times of the form O*(c^n) (c <= 3). The main result, however, is a branching algorithm for graphs with maximum degree three. It only needs polynomial space and has a running time of O*(1.8669^n) when analyzed with respect to the number of vertices. We also show that its running time is 2.1364^k n^O(1) when the goal is to find a spanning tree with at least k internal vertices. Both running time bounds are obtained via a Measure & Conquer analysis, the latter one being a novel use of this kind of analyses for parameterized algorithms.
Gaussian Belief Propagation: Theory and Aplication
Venue: arXiv cs.IT 2009
Year: 2009

The canonical problem of solving a system of linear equations arises in numerous contexts in information theory, communication theory, and related fields. In this contribution, we develop a solution based upon Gaussian belief propagation (GaBP) that does not involve direct matrix inversion. The iterative nature of our approach allows for a distributed message-passing implementation of the solution algorithm. In the first part of this thesis, we address the properties of the GaBP solver. We characterize the rate of convergence, enhance its message-passing efficiency by introducing a broadcast version, discuss its relation to classical solution methods including numerical examples. We present a new method for forcing the GaBP algorithm to converge to the correct solution for arbitrary column dependent matrices. In the second part we give five applications to illustrate the applicability of the GaBP algorithm to very large computer networks: Peer-to-Peer rating, linear detection, distributed computation of support vector regression, efficient computation of Kalman filter and distributed linear programming. Using extensive simulations on up to 1,024 CPUs in parallel using IBM Bluegene supercomputer we demonstrate the attractiveness and applicability of the GaBP algorithm, using real network topologies with up to millions of nodes and hundreds of millions of communication links. We further relate to several other algorithms and explore their connection to the GaBP algorithm.
Broadcasting in Prefix Space: P2P Data Dissemination with Predictable Performance
Venue: arXiv cs.NI 2009
Year: 2009

A broadcast mode may augment peer-to-peer overlay networks with an efficient, scalable data replication function, but may also give rise to a virtual link layer in VPN-type solutions. We introduce a simple broadcasting mechanism that operates in the prefix space of distributed hash tables without signaling. This paper concentrates on the performance analysis of the prefix flooding scheme. Starting from simple models of recursive $k$-ary trees, we analytically derive distributions of hop counts and the replication load. Extensive simulation results are presented further on, based on an implementation within the OverSim framework. Comparisons are drawn to Scribe, taken as a general reference model for group communication according to the shared, rendezvous-point-centered distribution paradigm. The prefix flooding scheme thereby confirmed its widely predictable performance and consistently outperformed Scribe in all metrics. Reverse path selection in overlays is identified as a major cause of performance degradation.
Adaptive Fault Masking With Incoherence Scoring
Venue: arXiv cs.OH 2009
Year: 2009

An adaptive voting algorithm for digital media was introduced in this study. Availability was improved by incoherence scoring in voting mechanism of Multi-Modular Redundancy. Regulation parameters give the algorithm flexibility of adjusting priorities in decision process. Proposed adaptive voting algorithm was shown to be more aware of fault status of redundant modules
Performance of Hybrid-ARQ in Block-Fading Channels: A Fixed Outage Probability Analysis
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the performance of hybrid-ARQ (automatic repeat request) in Rayleigh block fading channels. The long-term average transmitted rate is analyzed in a fast-fading scenario where the transmitter only has knowledge of channel statistics, and, consistent with contemporary wireless systems, rate adaptation is performed such that a target outage probability (after a maximum number of H-ARQ rounds) is maintained. H-ARQ allows for early termination once decoding is possible, and thus is a coarse, and implicit, mechanism for rate adaptation to the instantaneous channel quality. Although the rate with H-ARQ is not as large as the ergodic capacity, which is achievable with rate adaptation to the instantaneous channel conditions, even a few rounds of H-ARQ make the gap to ergodic capacity reasonably small for operating points of interest. Furthermore, the rate with H-ARQ provides a significant advantage compared to systems that do not use H-ARQ and only adapt rate based on the channel statistics.
Homomorphism Preservation on Quasi-Wide Classes
Venue: arXiv cs.LO 2009
Year: 2009

A class of structures is said to have the homomorphism-preservation property just in case every first-order formula that is preserved by homomorphisms on this class is equivalent to an existential-positive formula. It is known by a result of Rossman that the class of finite structures has this property and by previous work of Atserias et al. that various of its subclasses do. We extend the latter results by introducing the notion of a quasi-wide class and showing that any quasi-wide class that is closed under taking substructures and disjoint unions has the homomorphism-preservation property. We show, in particular, that classes of structures of bounded expansion and that locally exclude minors are quasi-wide. We also construct an example of a class of finite structures which is closed under substructures and disjoint unions but does not admit the homomorphism-preservation property.
Mapping Images with the Coherence Length Diagrams
Venue: arXiv cs.CV 2009
Year: 2009

Statistical pattern recognition methods based on the Coherence Length Diagram (CLD) have been proposed for medical image analyses, such as quantitative characterisation of human skin textures, and for polarized light microscopy of liquid crystal textures. Further investigations are made on image maps originated from such diagram and some examples related to irregularity of microstructures are shown.
Pushing BitTorrent Locality to the Limit
Venue: arXiv cs.NI 2009
Year: 2009

Peer-to-peer (P2P) locality has recently raised a lot of interest in the community. Indeed, whereas P2P content distribution enables financial savings for the content providers, it dramatically increases the traffic on inter-ISP links. To solve this issue, the idea to keep a fraction of the P2P traffic local to each ISP was introduced a few years ago. Since then, P2P solutions exploiting locality have been introduced. However, several fundamental issues on locality still need to be explored. In particular, how far can we push locality, and what is, at the scale of the Internet, the reduction of traffic that can be achieved with locality? In this paper, we perform extensive experiments on a controlled environment with up to 10 000 BitTorrent clients to evaluate the impact of high locality on inter-ISP links traffic and peers download completion time. We introduce two simple mechanisms that make high locality possible in challenging scenarios and we show that we save up to several orders of magnitude inter-ISP traffic compared to traditional locality without adversely impacting peers download completion time. In addition, we crawled 214 443 torrents representing 6 113 224 unique peers spread among 9 605 ASes. We show that whereas the torrents we crawled generated 11.6 petabytes of inter-ISP traffic, our locality policy implemented for all torrents would have reduced the global inter-ISP traffic by 40%.
Dynamic spectrum sharing game by lease
Venue: arXiv cs.GT 2009
Year: 2009

We propose and analyze a dynamic implementation of the property-rights model of cognitive radio. A primary link has the possibility to lease the owned spectrum to a MAC network of secondary nodes, in exchange for cooperation in the form of distributed space-time coding (DSTC). The cooperation and competition between the primary and secondary network are cast in the framework of sequential game. On one hand, the primary link attempts to maximize its quality of service in terms of signal-to-interference-plus-noise ratio (SINR); on the other hand, nodes in the secondary network compete for transmission within the leased time-slot following a power control mechanism. We consider both a baseline model with complete information and a more practical version with incomplete information, using the backward induction approach for the former and providing approximate algorithm for the latter. Analysis and numerical results show that our models and algorithms provide a promising framework for fair and effective spectrum sharing, both between primary and secondary networks and among secondary nodes.
Self-stabilizing K-out-of-L exclusion on tree network
Venue: arXiv cs.NI 2009
Year: 2009

In this paper, we address the problem of K-out-of-L exclusion, a generalization of the mutual exclusion problem, in which there are $\ell$ units of a shared resource, and any process can request up to $\mathtt k$ units ($1\leq\mathtt k\leq\ell$). We propose the first deterministic self-stabilizing distributed K-out-of-L exclusion protocol in message-passing systems for asynchronous oriented tree networks which assumes bounded local memory for each process.
Scarf is Ppad-Complete
Venue: arXiv cs.CC 2009
Year: 2009

Scarf's lemma is one of the fundamental results in combinatorics, originally introduced to study the core of an N-person game. Over the last four decades, the usefulness of Scarf's lemma has been demonstrated in several important combinatorial problems seeking "stable" solutions. However, the complexity of the computational version of Scarf's lemma (SCARF) remained open. In this paper, we prove that SCARF is complete for the complexity class PPAD. This proves that SCARF is as hard as the computational versions of Brouwer's fixed point theorem and Sperner's lemma. Hence, there is no polynomial-time algorithm for SCARF unless PPAD \subseteq P. We also show that fractional stable paths problem and finding strong fractional kernels in digraphs are PPAD-hard.
Diversity-Multiplexing Tradeoff for the MIMO Static Half-Duplex Relay
Venue: arXiv cs.IT 2009
Year: 2009

In this work, we investigate the diversity-multiplexing tradeoff (DMT) of the multiple-antenna (MIMO) static half-duplex relay channel. A general expression is derived for the DMT upper bound, which can be achieved by a compress-and-forward protocol at the relay, under certain assumptions. The DMT expression is given as the solution of a minimization problem in general, and an explicit expression is found when the relay channel is symmetric in terms of number of antennas, i.e. the source and the destination have n antennas each, and the relay has m antennas. It is observed that the static half-duplex DMT matches the full-duplex DMT when the relay has a single antenna, and is strictly below the full-duplex DMT when the relay has multiple antennas. Besides, the derivation of the upper bound involves a new asymptotic study of spherical integrals (that is, integrals with respect to the Haar measure on the unitary group U(n)), which is a topic of mathematical interest in itself.
Questions & Answers for TEI Newcomers
Venue: arXiv cs.DL 2009
Year: 2009

This paper provides an introduction to the Text Encoding Initia-tive (TEI), focused at bringing in newcomers who have to deal with a digital document project and are looking at the capacity that the TEI environment may have to fulfil his needs. To this end, we avoid a strictly technical presentation of the TEI and concentrate on the actual issues that such projects face, with parallel made on the situation within two institutions. While a quick walkthrough the TEI technical framework is provided, the papers ends up by showing the essential role of the community in the actual technical contributions that are being brought to the TEI.
Diversity-Multiplexing Tradeoff of Network Coding with Bidirectional Random Relaying
Venue: arXiv cs.IT 2009
Year: 2009

This paper develops a diversity-multiplexing tradeoff (DMT) over a bidirectional random relay set in a wireless network where the distribution of all nodes is a stationary Poisson point process. This is a nontrivial extension of the DMT because it requires consideration of the cooperation (or lack thereof) of relay nodes, the traffic pattern and the time allocation between the forward and reverse traffic directions. We then use this tradeoff to compare the DMTs of traditional time-division multihop (TDMH) and network coding (NC). Our main results are the derivations of the DMT for both TDMH and NC. This shows, surprisingly, that if relay nodes collaborate NC does not always have a better DMT than TDMH since it is difficult to simultaneously achieve bidirectional transmit diversity for both source nodes. In fact, for certain traffic patterns NC can have a worse DMT due to suboptimal time allocation between the forward and reverse transmission directions.
Random Projections for the Nonnegative Least-Squares Problem
Venue: arXiv cs.DS 2009
Year: 2009

Constrained least-squares regression problems, such as the Nonnegative Least Squares (NNLS) problem, where the variables are restricted to take only nonnegative values, often arise in applications. Motivated by the recent development of the fast Johnson-Lindestrauss transform, we present a fast random projection type approximation algorithm for the NNLS problem. Our algorithm employs a randomized Hadamard transform to construct a much smaller NNLS problem and solves this smaller problem using a standard NNLS solver. We prove that our approach finds a nonnegative solution vector that, with high probability, is close to the optimum nonnegative solution in a relative error approximation sense. We experimentally evaluate our approach on a large collection of term-document data and verify that it does offer considerable speedups without a significant loss in accuracy. Our analysis is based on a novel random projection type result that might be of independent interest. In particular, given a tall and thin matrix $Φ\in \mathbb{R}^{n \times d}$ ($n \gg d$) and a vector $y \in \mathbb{R}^d$, we prove that the Euclidean length of $Φy$ can be estimated very accurately by the Euclidean length of $\tildeΦy$, where $\tildeΦ$ consists of a small subset of (appropriately rescaled) rows of $Φ$.
Resolution-based Query Answering for Semantic Access to Relational Databases: A Research Note
Venue: arXiv cs.LO 2009
Year: 2009

We address the problem of semantic querying of relational databases (RDB) modulo knowledge bases using very expressive knowledge representation formalisms, such as full first-order logic or its various fragments. We propose to use a first-order logic (FOL) reasoner for computing schematic answers to deductive queries, with the subsequent instantiation of these schematic answers using a conventional relational DBMS. In this research note, we outline the main idea of this technique -- using abstractions of databases and constrained clauses for deriving schematic answers. The proposed method can be directly used with regular RDB, including legacy databases. Moreover, we propose it as a potential basis for an efficient Web-scale semantic search technology.
Towards the characterization of individual users through Web analytics
Venue: arXiv cs.HC 2009
Year: 2009

We perform an analysis of the way individual users navigate in the Web. We focus primarily in the temporal patterns of they return to a given page. The return probability as a function of time as well as the distribution of time intervals between consecutive visits are measured and found to be independent of the level of activity of single users. The results indicate a rich variety of individual behaviors and seem to preclude the possibility of defining a characteristic frequency for each user in his/her visits to a single site.
On Multipath Fading Channels at High SNR
Venue: arXiv cs.IT 2009
Year: 2009

This work studies the capacity of multipath fading channels. A noncoherent channel model is considered, where neither the transmitter nor the receiver is cognizant of the realization of the path gains, but both are cognizant of their statistics. It is shown that if the delay spread is large in the sense that the variances of the path gains decay exponentially or slower, then capacity is bounded in the signal-to-noise ratio (SNR). For such channels, capacity does not tend to infinity as the SNR tends to infinity. In contrast, if the variances of the path gains decay faster than exponentially, then capacity is unbounded in the SNR. It is further demonstrated that if the number of paths is finite, then at high SNR capacity grows double-logarithmically with the SNR, and the capacity pre-loglog, defined as the limiting ratio of capacity to log(log(SNR)) as SNR tends to infinity, is 1 irrespective of the number of paths.
Fault Masking By Probabilistic Voting
Venue: arXiv cs.OH 2009
Year: 2009

In this study, we introduced a probabilistic voter, regarding symbol probabilities in decision process besides majority consensus. Conventional majority voter is independent of functionality of redundant modules. In our study, proposed probabilistic voter is designed corresponding to functionality of the redundant module. We tested probabilistic voter for 3 and 5 redundant modules with random transient errors inserted the wires and it was seen from simulation results that Multi-Modular Redundancy (M-MR) with Probabilistic Voting (PV) had been shown better availability performance than conventional majority voter.