OpenRaiser/Intern-Atlas huggingface dataset:
Further Results on Quadratic Permutation Polynomial-Based Interleavers for Turbo Codes
Venue: arXiv cs.IT 2011
Year: 2011

An interleaver is a critical component for the channel coding performance of turbo codes. Algebraic constructions are of particular interest because they admit analytical designs and simple, practical hardware implementation. Also, the recently proposed quadratic permutation polynomial (QPP) based interleavers by Sun and Takeshita (IEEE Trans. Inf. Theory, Jan. 2005) provide excellent performance for short-to-medium block lengths, and have been selected for the 3GPP LTE standard. In this work, we derive some upper bounds on the best achievable minimum distance dmin of QPP-based conventional binary turbo codes (with tailbiting termination, or dual termination when the interleaver length N is sufficiently large) that are tight for larger block sizes. In particular, we show that the minimum distance is at most 2(2^{ν+1}+9), independent of the interleaver length, when the QPP has a QPP inverse, where ν is the degree of the primitive feedback and monic feedforward polynomials. However, allowing the QPP to have a larger degree inverse may give strictly larger minimum distances (and lower multiplicities). In particular, we provide several QPPs with an inverse degree of at least three for some of the 3GPP LTE interleaver lengths giving a dmin with the 3GPP LTE constituent encoders which is strictly larger than 50. For instance, we have found a QPP for N=6016 which gives an estimated dmin of 57. Furthermore, we provide the exact minimum distance and the corresponding multiplicity for all 3GPP LTE turbo codes (with dual termination) which shows that the best minimum distance is 51. Finally, we compute the best achievable minimum distance with QPP interleavers for all 3GPP LTE interleaver lengths N <= 4096, and compare the minimum distance with the one we get when using the 3GPP LTE polynomials.
A Nearly-Quadratic Gap Between Adaptive and Non-Adaptive Property Testers
Venue: arXiv cs.DS 2011
Year: 2011

We show that for all integers $t\geq 8$ and arbitrarily small $ε>0$, there exists a graph property $Π$ (which depends on $ε$) such that $ε$-testing $Π$ has non-adaptive query complexity $Q=\~Θ(q^{2-2/t})$, where $q=\~Θ(ε^{-1})$ is the adaptive query complexity. This resolves the question of how beneficial adaptivity is, in the context of proximity-dependent properties (\cite{benefits-of-adaptivity}). This also gives evidence that the canonical transformation of Goldreich and Trevisan (\cite{canonical-testers}) is essentially optimal when converting an adaptive property tester to a non-adaptive property tester. To do so, we provide optimal adaptive and non-adaptive testers for the combined property of having maximum degree $O(εN)$ and being a \emph{blow-up collection} of an arbitrary base graph $H$.
Code Attestation with Compressed Instruction Code
Venue: arXiv cs.CR 2011
Year: 2011

Available purely software based code attestation protocols have recently been shown to be cheatable. In this work we propose to upload compressed instruction code to make the code attestation protocol robust against a so called compresssion attack. The described secure code attestation protocol makes use of recently proposed microcontroller architectures for reading out compressed instruction code. We point out that the proposed concept only makes sense if the provided cost/benefit ratio for the aforementioned microcontroller is higher than an alternative hardware based solution requiring a tamperresistant hardware module.
Fully Empirical Autotuned QR Factorization For Multicore Architectures
Venue: arXiv cs.DC 2011
Year: 2011

Tuning numerical libraries has become more difficult over time, as systems get more sophisticated. In particular, modern multicore machines make the behaviour of algorithms hard to forecast and model. In this paper, we tackle the issue of tuning a dense QR factorization on multicore architectures. We show that it is hard to rely on a model, which motivates us to design a fully empirical approach. We exhibit few strong empirical properties that enable us to efficiently prune the search space. Our method is automatic, fast and reliable. The tuning process is indeed fully performed at install time in less than one and ten minutes on five out of seven platforms. We achieve an average performance varying from 97% to 100% of the optimum performance depending on the platform. This work is a basis for autotuning the PLASMA library and enabling easy performance portability across hardware systems.
Energy Efficiency and Goodput Analysis in Two-Way Wireless Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we study two-way relay networks (TWRNs) in which two source nodes exchange their information via a relay node indirectly in Rayleigh fading channels. Both Amplify-and-Forward (AF) and Decode-and-Forward (DF) techniques have been analyzed in the TWRN employing a Markov chain model through which the network operation is described and investigated in depth. Automatic Repeat-reQuest (ARQ) retransmission has been applied to guarantee the successful packet delivery. The bit energy consumption and goodput expressions have been derived as functions of transmission rate in a given AF or DF TWRN. Numerical results are used to identify the optimal transmission rates where the bit energy consumption is minimized or the goodput is maximized. The network performances are compared in terms of energy and transmission efficiency in AF and DF modes.
Tight Bounds for Parallel Randomized Load Balancing
Venue: arXiv cs.CC 2011
Year: 2011

We explore the fundamental limits of distributed balls-into-bins algorithms. We present an adaptive symmetric algorithm that achieves a bin load of two in log* n+O(1) communication rounds using O(n) messages in total. Larger bin loads can be traded in for smaller time complexities. We prove a matching lower bound of (1-o(1))log* n on the time complexity of symmetric algorithms that guarantee small bin loads at an asymptotically optimal message complexity of O(n). For each assumption of the lower bound, we provide an algorithm violating it, in turn achieving a constant maximum bin load in constant time. As an application, we consider the following problem. Given a fully connected graph of n nodes, where each node needs to send and receive up to n messages, and in each round each node may send one message over each link, deliver all messages as quickly as possible to their destinations. We give a simple and robust algorithm of time complexity O(log* n) for this task and provide a generalization to the case where all nodes initially hold arbitrary sets of messages. A less practical algorithm terminates within asymptotically optimal O(1) rounds. All these bounds hold with high probability.
Obtaining a Bipartite Graph by Contracting Few Edges
Venue: arXiv cs.DS 2011
Year: 2011

We initiate the study of the Bipartite Contraction problem from the perspective of parameterized complexity. In this problem we are given a graph $G$ and an integer $k$, and the task is to determine whether we can obtain a bipartite graph from $G$ by a sequence of at most $k$ edge contractions. Our main result is an $f(k) n^{O(1)}$ time algorithm for Bipartite Contraction. Despite a strong resemblance between Bipartite Contraction and the classical Odd Cycle Transversal (OCT) problem, the methods developed to tackle OCT do not seem to be directly applicable to Bipartite Contraction. Our algorithm is based on a novel combination of the irrelevant vertex technique, introduced by Robertson and Seymour, and the concept of important separators. Both techniques have previously been used as key components of algorithms for fundamental problems in parameterized complexity. However, to the best of our knowledge, this is the first time the two techniques are applied in unison.
Continuous Multiclass Labeling Approaches and Algorithms
Venue: arXiv cs.CV 2011
Year: 2011

We study convex relaxations of the image labeling problem on a continuous domain with regularizers based on metric interaction potentials. The generic framework ensures existence of minimizers and covers a wide range of relaxations of the originally combinatorial problem. We focus on two specific relaxations that differ in flexibility and simplicity -- one can be used to tightly relax any metric interaction potential, while the other one only covers Euclidean metrics but requires less computational effort. For solving the nonsmooth discretized problem, we propose a globally convergent Douglas-Rachford scheme, and show that a sequence of dual iterates can be recovered in order to provide a posteriori optimality bounds. In a quantitative comparison to two other first-order methods, the approach shows competitive performance on synthetical and real-world images. By combining the method with an improved binarization technique for nonstandard potentials, we were able to routinely recover discrete solutions within 1%--5% of the global optimum for the combinatorial image labeling problem.
Improving Image Search based on User Created Communities
Venue: arXiv cs.IR 2011
Year: 2011

Tag-based retrieval of multimedia content is a difficult problem, not only because of the shorter length of tags associated with images and videos, but also due to mismatch in the terminologies used by searcher and content creator. To alleviate this problem, we propose a simple concept-driven probabilistic model for improving text-based rich-media search. While our approach is similar to existing topic-based retrieval and cluster-based language modeling work, there are two important differences: (1) our proposed model considers not only the query-generation likelihood from cluster, but explicitly accounts for the overall "popularity" of the cluster or underlying concept, and (2) we explore the possibility of inferring the likely concept relevant to a rich-media content through the user-created communities that the content belongs to. We implement two methods of concept extraction: a traditional cluster based approach, and the proposed community based approach. We evaluate these two techniques for how effectively they capture the intended meaning of a term from the content creator and searcher, and their overall value in improving image search. Our results show that concept-driven search, though simple, clearly outperforms plain search. Among the two techniques for concept-driven search, community-based approach is more successful, as the concepts generated from user communities are found to be more intuitive and appealing.
Distributed Opportunistic Channel Access in Wireless Relay Networks
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, the problem of distributed opportunistic channel access in wireless relaying is investigated. A relay network with multiple source-destination pairs and multiple relays is considered. All the source nodes contend through a random access procedure. A winner source node may give up its transmission opportunity if its link quality is poor. In this research, we apply the optimal stopping theory to analyze when a winner node should give up its transmission opportunity. By assuming the winner node has information of channel gains of links from itself to relays and from relays to its destination, the existence and uniqueness of an optimal stopping rule are rigorously proved. It is also found that the optimal stopping rule is a pure-threshold strategy. The case when the winner node does not have information of channel gains of links from relays to its destination is also studied. Two stopping problems exist, one in the main layer (for channel access of source nodes), and the other in the sub-layer (for channel access of relay nodes). An intuitive stopping rule, where the sub-layer and the main layer maximize their throughput respectively, is shown to be a semi-pure-threshold strategy. The intuitive stopping rule turns out to be non-optimal. An optimal stopping rule is then derived theoretically. Our research reveals that multi-user (including multi-source and multi-relay) diversity and time diversity can be fully utilized in a relay network by our proposed strategies.
A new bound for parsimonious edge-colouring of graphs with maximum degree three
Venue: arXiv cs.DM 2011
Year: 2011

In a graph $G$ of maximum degree 3, let $γ(G)$ denote the largest fraction of edges that can be 3 edge-coloured. Rizzi \cite{Riz09} showed that $γ(G) \geq 1-\frac{2\strut}{\strut 3 g_{odd}(G)}$ where $g_{odd}(G)$ is the odd girth of $G$, when $G$ is triangle-free. In \cite{FouVan10a} we extended that result to graph with maximum degree 3. We show here that $γ(G) \geq 1-\frac{2 \strut}{\strut 3 g_{odd}(G)+2}$, which leads to $γ(G) \geq 15/17$ when considering graphs with odd girth at least 5, distinct from the Petersen graph.
Fast and Faster: A Comparison of Two Streamed Matrix Decomposition Algorithms
Venue: arXiv cs.NA 2011
Year: 2011

With the explosion of the size of digital dataset, the limiting factor for decomposition algorithms is the \emph{number of passes} over the input, as the input is often stored out-of-core or even off-site. Moreover, we're only interested in algorithms that operate in \emph{constant memory} w.r.t. to the input size, so that arbitrarily large input can be processed. In this paper, we present a practical comparison of two such algorithms: a distributed method that operates in a single pass over the input vs. a streamed two-pass stochastic algorithm. The experiments track the effect of distributed computing, oversampling and memory trade-offs on the accuracy and performance of the two algorithms. To ensure meaningful results, we choose the input to be a real dataset, namely the whole of the English Wikipedia, in the application settings of Latent Semantic Analysis.
Practical inventory routing: A problem definition and an optimization method
Venue: arXiv cs.AI 2011
Year: 2011

The global objective of this work is to provide practical optimization methods to companies involved in inventory routing problems, taking into account this new type of data. Also, companies are sometimes not able to deal with changing plans every period and would like to adopt regular structures for serving customers.
Joint Beamforming and Power Allocation for MIMO Relay Broadcast Channel with Individual SINR Constraints
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, system design for the multi-input multi-output (MIMO) relay broadcast channel with individual signal-to-interference-plus-noise ratio (SINR) constraints at the mobile stations (MS) is considered. By exploring the structure of downlink (DL) uplink (UL) duality at either the base station (BS) or the relay station (RS), we propose two schemes of joint power allocation and beamforming design at the BS and the RS. The problem of existence of feasible solutions under practical power constraints at the BS and the RS with given SINR targets is considered first. Then the problem of sum power minimization is considered. Each design problem can be solved efficiently using optimal joint power allocation and beamforming under the framework of convex optimization. We also show that with subchannel pairing at the RS, the transmission power can be reduced by channel compensation at either hop. Finally, an extension to more general multi-hop applications is provided to further improve the power efficiency.
On minimising automata with errors
Venue: arXiv cs.FL 2011
Year: 2011

The problem of k-minimisation for a DFA M is the computation of a smallest DFA N (where the size |M| of a DFA M is the size of the domain of the transition function) such that their recognized languages differ only on words of length less than k. The previously best algorithm, which runs in time O(|M| log^2 n) where n is the number of states, is extended to DFAs with partial transition functions. Moreover, a faster O(|M| log n) algorithm for DFAs that recognise finite languages is presented. In comparison to the previous algorithm for total DFAs, the new algorithm is much simpler and allows the calculation of a k-minimal DFA for each k in parallel. Secondly, it is demonstrated that calculating the least number of introduced errors is hard: Given a DFA M and numbers k and m, it is NP-hard to decide whether there exists a k-minimal DFA N differing from DFA M on at most m words. A similar result holds for hyper-minimisation of DFAs in general: Given a DFA M and numbers s and m, it is NP-hard to decide whether there exists a DFA N with at most s states such that DFA M and N differ on at msot m words.
Multimedia Database Applications: Issues and Concerns for Classroom Teaching
Venue: arXiv cs.MM 2011
Year: 2011

The abundance of multimedia data and information is challenging educators to effectively search, browse, access, use, and store the data for their classroom teaching. However, many educators could still be accustomed to teaching or searching for information using conventional methods, but often the conventional methods may not function well with multimedia data. Educators need to efficiently interact and manage a variety of digital media files too. The purpose of this study is to review current multimedia database applications in teaching and learning, and further discuss some of the issues or concerns that educators may have while incorporating multimedia data into their classrooms. Some strategies and recommendations are also provided in order for educators to be able to use multimedia data more effectively in their teaching environments.
On the Economics of Cloud Markets
Venue: arXiv cs.NI 2011
Year: 2011

Cloud computing is a paradigm that has the potential to transform and revolutionalize the next generation IT industry by making software available to end-users as a service. A cloud, also commonly known as a cloud network, typically comprises of hardware (network of servers) and a collection of softwares that is made available to end-users in a pay-as-you-go manner. Multiple public cloud providers (ex., Amazon) co-existing in a cloud computing market provide similar services (software as a service) to its clients, both in terms of the nature of an application, as well as in quality of service (QoS) provision. The decision of whether a cloud hosts (or finds it profitable to host) a service in the long-term would depend jointly on the price it sets, the QoS guarantees it provides to its customers, and the satisfaction of the advertised guarantees. In this paper, we devise and analyze three inter-organizational economic models relevant to cloud networks. We formulate our problems as non co-operative price and QoS games between multiple cloud providers existing in a cloud market. We prove that a unique pure strategy Nash equilibrium (NE) exists in two of the three models. Our analysis paves the path for each cloud provider to 1) know what prices and QoS level to set for end-users of a given service type, such that the provider could exist in the cloud market, and 2) practically and dynamically provision appropriate capacity for satisfying advertised QoS guarantees.
Finite Element Integration on GPUs
Venue: arXiv cs.MS 2011
Year: 2011

We present a novel finite element integration method for low order elements on GPUs. We achieve more than 100GF for element integration on first order discretizations of both the Laplacian and Elasticity operators.
Capacity Bounds for Relay Channels with Inter-symbol Interference and Colored Gaussian Noise
Venue: arXiv cs.IT 2011
Year: 2011

The capacity of a relay channel with inter-symbol interference (ISI) and additive colored Gaussian noise is examined under an input power constraint. Prior results are used to show that the capacity of this channel can be computed by examining the circular degraded relay channel in the limit of infinite block length. The current work provides single letter expressions for the achievable rates with decodeand- forward (DF) and compress-and-forward (CF) processing employed at the relay. Additionally, the cut-set bound for the relay channel is generalized for the ISI/colored Gaussian noise scenario. All results hinge on showing the optimality of the decomposition of the relay channel with ISI/colored Gaussian noise into an equivalent collection of coupled parallel, scalar, memoryless relay channels. The region of optimality of the DF and CF achievable rates are also discussed. Optimal power allocation strategies are also discussed for the two lower bounds and the cut-set upper bound. As the maximizing power allocations for DF and CF appear to be intractable, the desired cost functions are modified and then optimized. The resulting rates are illustrated through the computation of numerical examples.
Multi-label Learning via Structured Decomposition and Group Sparsity
Venue: arXiv cs.LG 2011
Year: 2011

In multi-label learning, each sample is associated with several labels. Existing works indicate that exploring correlations between labels improve the prediction performance. However, embedding the label correlations into the training process significantly increases the problem size. Moreover, the mapping of the label structure in the feature space is not clear. In this paper, we propose a novel multi-label learning method "Structured Decomposition + Group Sparsity (SDGS)". In SDGS, we learn a feature subspace for each label from the structured decomposition of the training data, and predict the labels of a new sample from its group sparse representation on the multi-subspace obtained from the structured decomposition. In particular, in the training stage, we decompose the data matrix $X\in R^{n\times p}$ as $X=\sum_{i=1}^kL^i+S$, wherein the rows of $L^i$ associated with samples that belong to label $i$ are nonzero and consist a low-rank matrix, while the other rows are all-zeros, the residual $S$ is a sparse matrix. The row space of $L_i$ is the feature subspace corresponding to label $i$. This decomposition can be efficiently obtained via randomized optimization. In the prediction stage, we estimate the group sparse representation of a new sample on the multi-subspace via group \emph{lasso}. The nonzero representation coefficients tend to concentrate on the subspaces of labels that the sample belongs to, and thus an effective prediction can be obtained. We evaluate SDGS on several real datasets and compare it with popular methods. Results verify the effectiveness and efficiency of SDGS.
Finite Dimensional Infinite Constellations
Venue: arXiv cs.IT 2011
Year: 2011

In the setting of a Gaussian channel without power constraints, proposed by Poltyrev, the codewords are points in an n-dimensional Euclidean space (an infinite constellation) and the tradeoff between their density and the error probability is considered. The capacity in this setting is the highest achievable normalized log density (NLD) with vanishing error probability. This capacity as well as error exponent bounds for this setting are known. In this work we consider the optimal performance achievable in the fixed blocklength (dimension) regime. We provide two new achievability bounds, and extend the validity of the sphere bound to finite dimensional infinite constellations. We also provide asymptotic analysis of the bounds: When the NLD is fixed, we provide asymptotic expansions for the bounds that are significantly tighter than the previously known error exponent results. When the error probability is fixed, we show that as n grows, the gap to capacity is inversely proportional (up to the first order) to the square-root of n where the proportion constant is given by the inverse Q-function of the allowed error probability, times the square root of 1/2. In an analogy to similar result in channel coding, the dispersion of infinite constellations is 1/2nat^2 per channel use. All our achievability results use lattices and therefore hold for the maximal error probability as well. Connections to the error exponent of the power constrained Gaussian channel and to the volume-to-noise ratio as a figure of merit are discussed. In addition, we demonstrate the tightness of the results numerically and compare to state-of-the-art coding schemes.