OpenRaiser/Intern-Atlas huggingface dataset:
Polynomial kernels for 3-leaf power graph modification problems
Venue: arXiv cs.DM 2008
Year: 2008

A graph G=(V,E) is a 3-leaf power iff there exists a tree T whose leaves are V and such that (u,v) is an edge iff u and v are at distance at most 3 in T. The 3-leaf power graph edge modification problems, i.e. edition (also known as the closest 3-leaf power), completion and edge-deletion, are FTP when parameterized by the size of the edge set modification. However polynomial kernel was known for none of these three problems. For each of them, we provide cubic kernels that can be computed in linear time for each of these problems. We thereby answer an open problem first mentioned by Dom, Guo, Huffner and Niedermeier (2005).
Communication-Efficient Construction of the Plane Localized Delaunay Graph
Venue: arXiv cs.CG 2008
Year: 2008

Let $V$ be a finite set of points in the plane. We present a 2-local algorithm that constructs a plane $\frac{4 π\sqrt{3}}{9}$-spanner of the unit-disk graph $\UDG(V)$. This algorithm makes only one round of communication and each point of $V$ broadcasts at most 5 messages. This improves the previously best message-bound of 11 by Araújo and Rodrigues (Fast localized Delaunay triangulation, Lecture Notes in Computer Science, volume 3544, 2004).
Improved Upper Bounds for the Information Rates of the Secret Sharing Schemes Induced by the Vamos Matroid
Venue: arXiv cs.CR 2008
Year: 2008

An access structure specifying the qualified sets of a secret sharing scheme must have information rate less than or equal to one. The Vamos matroid induces two non-isomorphic access structures V1 and V6, which were shown by Marti-Farre and Padro to have information rates of at least 3/4. Beimel, Livne, and Padro showed that the information rates of V1 and V6 are bounded above by 10/11 and 9/10 respectively. Here we improve those upper bounds to 19/21 for V1 and 17/19 for V6.
Crowdsourcing, Attention and Productivity
Venue: arXiv cs.CY 2008
Year: 2008

The tragedy of the digital commons does not prevent the copious voluntary production of content that one witnesses in the web. We show through an analysis of a massive data set from \texttt{YouTube} that the productivity exhibited in crowdsourcing exhibits a strong positive dependence on attention, measured by the number of downloads. Conversely, a lack of attention leads to a decrease in the number of videos uploaded and the consequent drop in productivity, which in many cases asymptotes to no uploads whatsoever. Moreover, uploaders compare themselves to others when having low productivity and to themselves when exceeding a threshold.
SINGULAB - A Graphical user Interface for the Singularity Analysis of Parallel Robots based on Grassmann-Cayley Algebra
Venue: arXiv cs.RO 2008
Year: 2008

This paper presents SinguLab, a graphical user interface for the singularity analysis of parallel robots. The algorithm is based on Grassmann-Cayley algebra. The proposed tool is interactive and introduces the designer to the singularity analysis performed by this method, showing all the stages along the procedure and eventually showing the solution algebraically and graphically, allowing as well the singularity verification of different robot poses.
Load Balancing Strategies to Solve Flowshop Scheduling on Parallel Computing
Venue: arXiv cs.NI 2008
Year: 2008

This paper first presents a parallel solution for the Flowshop Scheduling Problem in parallel environment, and then proposes a novel load balancing strategy. The proposed Proportional Fairness Strategy (PFS) takes computational performance of computing process sets into account, and assigns additional load to computing nodes proportionally to their evaluated performance. In order to efficiently utilize the power of parallel resource, we also discuss the data structure used in communications among computational nodes and design an optimized data transfer strategy. This data transfer strategy combined with the proposed load balancing strategy have been implemented and tested on a super computer consisted of 86 CPUs using MPI as the middleware. The results show that the proposed PFS achieves better performance in terms of computing time than the existing Adaptive Contracting Within Neighborhood Strategy. We also show that the combination of both the Proportional Fairness Strategy and the proposed data transferring strategy achieves additional 13~15% improvement in efficiency of parallelism.
Generalized Prediction Intervals for Arbitrary Distributed High-Dimensional Data
Venue: arXiv cs.CV 2008
Year: 2008

This paper generalizes the traditional statistical concept of prediction intervals for arbitrary probability density functions in high-dimensional feature spaces by introducing significance level distributions, which provides interval-independent probabilities for continuous random variables. The advantage of the transformation of a probability density function into a significance level distribution is that it enables one-class classification or outlier detection in a direct manner.
Achievability of the Rate ${1/2}\log(1+\es)$ in the Discrete-Time Poisson Channel
Venue: arXiv cs.IT 2008
Year: 2008

A simple lower bound to the capacity of the discrete-time Poisson channel with average energy $\es$ is derived. The rate ${1/2}\log(1+\es)$ is shown to be the generalized mutual information of a modified minimum-distance decoder, when the input follows a gamma distribution of parameter 1/2 and mean $\es$.
On the Capacity Improvement of Multicast Traffic with Network Coding
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we study the contribution of network coding (NC) in improving the multicast capacity of random wireless ad hoc networks when nodes are endowed with multi-packet transmission (MPT) and multi-packet reception (MPR) capabilities. We show that a per session throughput capacity of $Θ(nT^{3}(n))$, where $n$ is the total number of nodes and T(n) is the communication range, can be achieved as a tight bound when each session contains a constant number of sinks. Surprisingly, an identical order capacity can be achieved when nodes have only MPR and MPT capabilities. This result proves that NC does not contribute to the order capacity of multicast traffic in wireless ad hoc networks when MPR and MPT are used in the network. The result is in sharp contrast to the general belief (conjecture) that NC improves the order capacity of multicast. Furthermore, if the communication range is selected to guarantee the connectivity in the network, i.e., $T(n)\ge Θ(\sqrt{\log n/n})$, then the combination of MPR and MPT achieves a throughput capacity of $Θ(\frac{\log^{3/2} n}{\sqrt{n}})$ which provides an order capacity gain of $Θ(\log^2 n)$ compared to the point-to-point multicast capacity with the same number of destinations.
Information and Data Quality in Spreadsheets
Venue: arXiv cs.SE 2008
Year: 2008

The quality of the data in spreadsheets is less discussed than the structural integrity of the formulas. Yet it is an area of great interest to the owners and users of the spreadsheet. This paper provides an overview of Information Quality (IQ) and Data Quality (DQ) with specific reference to how data is sourced, structured, and presented in spreadsheets.
Target Localization Accuracy Gain in MIMO Radar Based Systems
Venue: arXiv cs.IT 2008
Year: 2008

This paper presents an analysis of target localization accuracy, attainable by the use of MIMO (Multiple-Input Multiple-Output) radar systems, configured with multiple transmit and receive sensors, widely distributed over a given area. The Cramer-Rao lower bound (CRLB) for target localization accuracy is developed for both coherent and non-coherent processing. Coherent processing requires a common phase reference for all transmit and receive sensors. The CRLB is shown to be inversely proportional to the signal effective bandwidth in the non-coherent case, but is approximately inversely proportional to the carrier frequency in the coherent case. We further prove that optimization over the sensors' positions lowers the CRLB by a factor equal to the product of the number of transmitting and receiving sensors. The best linear unbiased estimator (BLUE) is derived for the MIMO target localization problem. The BLUE's utility is in providing a closed form localization estimate that facilitates the analysis of the relations between sensors locations, target location, and localization accuracy. Geometric dilution of precision (GDOP) contours are used to map the relative performance accuracy for a given layout of radars over a given geographic area.
The Equivalence of Semidefinite Relaxation MIMO Detectors for Higher-Order QAM
Venue: arXiv cs.IT 2008
Year: 2008

In multi-input-multi-output (MIMO) detection, semidefinite relaxation (SDR) has been shown to be an efficient high-performance approach. Developed initially for BPSK and QPSK, SDR has been found to be capable of providing near-optimal performance (for those constellations). This has stimulated a number of recent research endeavors that aim to apply SDR to the high-order QAM cases. These independently developed SDRs are different in concept and structure, and presently no serious analysis has been given to compare these methods. This paper analyzes the relationship of three such SDR methods, namely the polynomial-inspired SDR (PI-SDR) by Wiesel et al., the bound-constrained SDR (BC-SDR) by Sidiropoulos and Luo, and the virtually-antipodal SDR (VA-SDR) by Mao et al. The result that we have proven is somehow unexpected: the three SDRs are equivalent. Simply speaking, we show that solving any one SDR is equivalent to solving the other SDRs. This paper also discusses some implications arising from the SDR equivalence, and provides simulation results to verify our theoretical findings.
Surrogate Learning - An Approach for Semi-Supervised Classification
Venue: arXiv cs.LG 2008
Year: 2008

We consider the task of learning a classifier from the feature space $\mathcal{X}$ to the set of classes $\mathcal{Y} = \{0, 1\}$, when the features can be partitioned into class-conditionally independent feature sets $\mathcal{X}_1$ and $\mathcal{X}_2$. We show the surprising fact that the class-conditional independence can be used to represent the original learning task in terms of 1) learning a classifier from $\mathcal{X}_2$ to $\mathcal{X}_1$ and 2) learning the class-conditional distribution of the feature set $\mathcal{X}_1$. This fact can be exploited for semi-supervised learning because the former task can be accomplished purely from unlabeled samples. We present experimental evaluation of the idea in two real world applications.
Mechanistic Behavior of Single-Pass Instruction Sequences
Venue: arXiv cs.PL 2008
Year: 2008

Earlier work on program and thread algebra detailed the functional, observable behavior of programs under execution. In this article we add the modeling of unobservable, mechanistic processing, in particular processing due to jump instructions. We model mechanistic processing preceding some further behavior as a delay of that behavior; we borrow a unary delay operator from discrete time process algebra. We define a mechanistic improvement ordering on threads and observe that some threads do not have an optimal implementation.
On normal odd partitions in cubic graphs
Venue: arXiv cs.DM 2008
Year: 2008

A normal partition of the edges of a cubic graph is a partition into trails (no repeated edge) such that each vertex is the end vertex of exactly one trail of the partition. We investigate this notion and give some results and problems.
Robustness of MIMO-OFDM Schemes for Future Digital TV to Carrier Frequency Offset
Venue: arXiv cs.NI 2008
Year: 2008

This paper investigates the impact of carrier frequency offset (CFO) on the performance of different MIMO-OFDM schemes with high spectral efficiency for next generation of terrestrial digital TV. We show that all studied MIMO-OFDM schemes are sensitive to CFO when it is greater than 1% of inter-carrier spacing. We show also that the Alamouti scheme is the most sensitive MIMO scheme to CFO
Network coding meets TCP
Venue: arXiv cs.NI 2008
Year: 2008

We propose a mechanism that incorporates network coding into TCP with only minor changes to the protocol stack, thereby allowing incremental deployment. In our scheme, the source transmits random linear combinations of packets currently in the congestion window. At the heart of our scheme is a new interpretation of ACKs - the sink acknowledges every degree of freedom (i.e., a linear combination that reveals one unit of new information) even if it does not reveal an original packet immediately. Such ACKs enable a TCP-like sliding-window approach to network coding. Our scheme has the nice property that packet losses are essentially masked from the congestion control algorithm. Our algorithm therefore reacts to packet drops in a smooth manner, resulting in a novel and effective approach for congestion control over networks involving lossy links such as wireless links. Our experiments show that our algorithm achieves higher throughput compared to TCP in the presence of lossy wireless links. We also establish the soundness and fairness properties of our algorithm.
2D Linear Precoded OFDM for future mobile Digital Video Broadcasting
Venue: arXiv cs.NI 2008
Year: 2008

In this paper, we propose a novel channel estimation technique based on 2D spread pilots. The merits of this technique are its simplicity, its flexibility regarding the transmission scenarios, and the spectral efficiency gain obtained compared to the classical pilot based estimation schemes used in DVB standards. We derive the analytical expression of the mean square error of the estimator and show it is a function of the autocorrelation of the channel in both time and frequency domains. The performance evaluated over a realistic channel model shows the efficiency of this technique which turns out to be a promising channel estimation for the future mobile video broadcasting systems.
Linear Universal Decoding for Compound Channels: a Local to Global Geometric Approach
Venue: arXiv cs.IT 2008
Year: 2008

Over discrete memoryless channels (DMC), linear decoders (maximizing additive metrics) afford several nice properties. In particular, if suitable encoders are employed, the use of decoding algorithm with manageable complexities is permitted. Maximum likelihood is an example of linear decoder. For a compound DMC, decoders that perform well without the channel's knowledge are required in order to achieve capacity. Several such decoders have been studied in the literature. However, there is no such known decoder which is linear. Hence, the problem of finding linear decoders achieving capacity for compound DMC is addressed, and it is shown that under minor concessions, such decoders exist and can be constructed. This paper also develops a "local geometric analysis", which allows in particular, to solve the above problem. By considering very noisy channels, the original problem is reduced, in the limit, to an inner product space problem, for which insightful solutions can be found. The local setting can then provide counterexamples to disproof claims, but also, it is shown how in this problem, results proven locally can be "lifted" to results proven globally.
Acerca del Algoritmo de Dijkstra
Venue: arXiv cs.DS 2008
Year: 2008

In this paper we prove the correctness of Dijkstra's algorithm. We also discuss it and at the end we show an application.
Occupancy distributions of homogeneous queueing systems under opportunistic scheduling
Venue: arXiv cs.PF 2008
Year: 2008

We analyze opportunistic schemes for transmission scheduling from one of $n$ homogeneous queues whose channel states fluctuate independently. Considered schemes consist of the LCQ policy, which transmits from a longest connected queue in the entire system, and its low-complexity variants that transmit from a longest queue within a randomly chosen subset of connected queues. A Markovian model is studied where mean packet transmission time is $n^{-1}$ and packet arrival rate is $λ<1$ per queue. Transient and equilibrium distributions of queue occupancies are obtained in the limit as the system size $n$ tends to infinity.
Distribution of complexities in the Vai script
Venue: arXiv cs.CL 2008
Year: 2008

In the paper, we analyze the distribution of complexities in the Vai script, an indigenous syllabic writing system from Liberia. It is found that the uniformity hypothesis for complexities fails for this script. The models using Poisson distribution for the number of components and hyper-Poisson distribution for connections provide good fits in the case of the Vai script.
Collision Resolution by Exploiting Symbol Misalignment
Venue: arXiv cs.NI 2008
Year: 2008

This paper presents CRESM, a novel collision resolution method for decoding collided packets in random-access wireless networks. In a collision, overlapping signals from several sources are received simultaneously at a receiver. CRESM exploits symbol misalignment among the overlapping signals to recover the individual packets. CRESM can be adopted in 802.11 networks without modification of the transmitter design; only a simple DSP technique is needed at the receiver to decode the overlapping signals. Our simulations indicate that CRESM has better BER performance than the simplistic Successive Interference Cancellation (SIC) technique that treats interference as noise, for almost all SNR regimes. The implication of CRESM for random-access networking is significant: in general, using CRESM to resolve collisions of up to n packets, network throughput can be boosted by more than n times if the transmitters are allowed to transmit more aggressively in the MAC protocol.
Reed-Solomon Subcodes with Nontrivial Traces: Distance Properties and Soft-Decision Decoding
Venue: arXiv cs.IT 2008
Year: 2008

Reed-Solomon (RS) codes over GF$(2^m)$ have traditionally been the most popular non-binary codes in almost all practical applications. The distance properties of RS codes result in excellent performance under hard-decision bounded-distance decoding. However, efficient and implementable soft decoding for high-rate (about 0.9) RS codes over large fields (GF(256), say) continues to remain a subject of research with a promise of further coding gains. In this work, our objective is to propose and investigate $2^m$-ary codes with non-trivial binary trace codes as an alternative to RS codes. We derive bounds on the rate of a $2^m$-ary code with a non-trivial binary trace code. Then we construct certain subcodes of RS codes over GF($2^m$) that have a non-trivial binary trace with distances and rates meeting the derived bounds. The properties of these subcodes are studied and low-complexity hard-decision and soft-decision decoders are proposed. The decoders are analyzed, and their performance is compared with that of comparable RS codes. Our results suggest that these subcodes of RS codes could be viable alternatives for RS codes in applications.
Stiffness Analysis Of Multi-Chain Parallel Robotic Systems
Venue: arXiv cs.RO 2008
Year: 2008

The paper presents a new stiffness modelling method for multi-chain parallel robotic manipulators with flexible links and compliant actuating joints. In contrast to other works, the method involves a FEA-based link stiffness evaluation and employs a new solution strategy of the kinetostatic equations, which allows computing the stiffness matrix for singular postures and to take into account influence of the internal forces. The advantages of the developed technique are confirmed by application examples, which deal with stiffness analysis of the Orthoglide manipulator.
A simple constant-probability RP reduction from NP to Parity P
Venue: arXiv cs.CC 2008
Year: 2008

The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $¶^{# P}$ relies on the fact that, under mild technical conditions on the complexity class $C$, we have $\exists C \subset BP \cdot \oplus C$. More concretely, there is a randomized reduction which transforms nonempty sets and the empty set, respectively, into sets of odd or even size. The customary method is to invoke Valiant's and Vazirani's randomized reduction from NP to UP, followed by amplification of the resulting success probability from $1/\poly(n)$ to a constant by combining the parities of $\poly(n)$ trials. Here we give a direct algebraic reduction which achieves constant success probability without the need for amplification. Our reduction is very simple, and its analysis relies on well-known properties of the Legendre symbol in finite fields.
Low-Density Parity-Check Codes Which Can Correct Three Errors Under Iterative Decoding
Venue: arXiv cs.IT 2008
Year: 2008

In this paper, we give necessary and sufficient conditions for low-density parity-check (LDPC) codes with column-weight three to correct three errors when decoded using hard-decision message-passing decoding. Additionally, we give necessary and sufficient conditions for column-weight-four codes to correct three errors in four iterations of hard-decision message-passing decoding. We then give a construction technique which results in codes satisfying these conditions. We also provide numerical assessment of code performance via simulation results.
Interference Alignment for Secrecy
Venue: arXiv cs.IT 2008
Year: 2008

This paper studies the frequency/time selective $K$-user Gaussian interference channel with secrecy constraints. Two distinct models, namely the interference channel with confidential messages and the one with an external eavesdropper, are analyzed. The key difference between the two models is the lack of channel state information (CSI) about the external eavesdropper. Using interference alignment along with secrecy pre-coding, it is shown that each user can achieve non-zero secure Degrees of Freedom (DoF) for both cases. More precisely, the proposed coding scheme achieves $\frac{K-2}{2K-2}$ secure DoF {\em with probability one} per user in the confidential messages model. For the external eavesdropper scenario, on the other hand, it is shown that each user can achieve $\frac{K-2}{2K}$ secure DoF {\em in the ergodic setting}. Remarkably, these results establish the {\em positive impact} of interference on the secrecy capacity region of wireless networks.
A Central Limit Theorem for the SINR at the LMMSE Estimator Output for Large Dimensional Signals
Venue: arXiv cs.IT 2008
Year: 2008

This paper is devoted to the performance study of the Linear Minimum Mean Squared Error estimator for multidimensional signals in the large dimension regime. Such an estimator is frequently encountered in wireless communications and in array processing, and the Signal to Interference and Noise Ratio (SINR) at its output is a popular performance index. The SINR can be modeled as a random quadratic form which can be studied with the help of large random matrix theory, if one assumes that the dimension of the received and transmitted signals go to infinity at the same pace. This paper considers the asymptotic behavior of the SINR for a wide class of multidimensional signal models that includes general multi-antenna as well as spread spectrum transmission models. The expression of the deterministic approximation of the SINR in the large dimension regime is recalled and the SINR fluctuations around this deterministic approximation are studied. These fluctuations are shown to converge in distribution to the Gaussian law in the large dimension regime, and their variance is shown to decrease as the inverse of the signal dimension.
1.25 Approximation Algorithm for the Steiner Tree Problem with Distances One and Two
Venue: arXiv cs.CC 2008
Year: 2008

We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances one and two, improving on the best known bound for that problem.