OpenRaiser/Intern-Atlas huggingface dataset:
Towards Low-Complexity Linear-Programming Decoding
Venue: arXiv cs.IT 2006
Year: 2006

We consider linear-programming (LP) decoding of low-density parity-check (LDPC) codes. While it is clear that one can use any general-purpose LP solver to solve the LP that appears in the decoding problem, we argue in this paper that the LP at hand is equipped with a lot of structure that one should take advantage of. Towards this goal, we study the dual LP and show how coordinate-ascent methods lead to very simple update rules that are tightly connected to the min-sum algorithm. Moreover, replacing minima in the formula of the dual LP with soft-minima one obtains update rules that are tightly connected to the sum-product algorithm. This shows that LP solvers with complexity similar to the min-sum algorithm and the sum-product algorithm are feasible. Finally, we also discuss some sub-gradient-based methods.
On the Approximation and Smoothed Complexity of Leontief Market Equilibria
Venue: arXiv cs.GT 2006
Year: 2006

We show that the problem of finding an ε-approximate Nash equilibrium of an n by n two-person games can be reduced to the computation of an (ε/n)^2-approximate market equilibrium of a Leontief economy. Together with a recent result of Chen, Deng and Teng, this polynomial reduction implies that the Leontief market exchange problem does not have a fully polynomial-time approximation scheme, that is, there is no algorithm that can compute an ε-approximate market equilibrium in time polynomial in m, n, and 1/ε, unless PPAD is not in P, We also extend the analysis of our reduction to show, unless PPAD is not in RP, that the smoothed complexity of the Scarf's general fixed-point approximation algorithm (when applying to solve the approximate Leontief market exchange problem) or of any algorithm for computing an approximate market equilibrium of Leontief economies is not polynomial in n and 1/σ, under Gaussian or uniform perturbations with magnitude σ.
Inconsistent parameter estimation in Markov random fields: Benefits in the computation-limited setting
Venue: arXiv cs.LG 2006
Year: 2006

Consider the problem of joint parameter estimation and prediction in a Markov random field: i.e., the model parameters are estimated on the basis of an initial set of data, and then the fitted model is used to perform prediction (e.g., smoothing, denoising, interpolation) on a new noisy observation. Working under the restriction of limited computation, we analyze a joint method in which the \emph{same convex variational relaxation} is used to construct an M-estimator for fitting parameters, and to perform approximate marginalization for the prediction step. The key result of this paper is that in the computation-limited setting, using an inconsistent parameter estimator (i.e., an estimator that returns the ``wrong'' model even in the infinite data limit) can be provably beneficial, since the resulting errors can partially compensate for errors made by using an approximate prediction technique. En route to this result, we analyze the asymptotic properties of M-estimators based on convex variational relaxations, and establish a Lipschitz stability property that holds for a broad class of variational methods. We show that joint estimation/prediction based on the reweighted sum-product algorithm substantially outperforms a commonly used heuristic based on ordinary sum-product.
Difficulties in the Implementation of Quantum Computers
Venue: arXiv cs.AR 2006
Year: 2006

This paper reviews various engineering hurdles facing the field of quantum computing. Specifically, problems related to decoherence, state preparation, error correction, and implementability of gates are considered.
The Cubic Public-Key Transformation
Venue: arXiv cs.CR 2006
Year: 2006

We propose the use of the cubic transformation for public-key applications and digital signatures. Transformations modulo a prime p or a composite n=pq, where p and q are primes, are used in such a fashion that each transformed value has only 3 roots that makes it a more efficient transformation than the squaring transformation of Rabin, which has 4 roots. Such a transformation, together with additional tag information, makes it possible to uniquely invert each transformed value. The method may be used for other exponents as well.
Asymptotic constant-factor approximation algorithm for the Traveling Salesperson Problem for Dubins' vehicle
Venue: arXiv cs.RO 2006
Year: 2006

This article proposes the first known algorithm that achieves a constant-factor approximation of the minimum length tour for a Dubins' vehicle through $n$ points on the plane. By Dubins' vehicle, we mean a vehicle constrained to move at constant speed along paths with bounded curvature without reversing direction. For this version of the classic Traveling Salesperson Problem, our algorithm closes the gap between previously established lower and upper bounds; the achievable performance is of order $n^{2/3}$.
On Separation, Randomness and Linearity for Network Codes over Finite Fields
Venue: arXiv cs.IT 2006
Year: 2006

We examine the issue of separation and code design for networks that operate over finite fields. We demonstrate that source-channel (or source-network) separation holds for several canonical network examples like the noisy multiple access channel and the erasure degraded broadcast channel, when the whole network operates over a common finite field. This robustness of separation is predicated on the fact that noise and inputs are independent, and we examine the failure of separation when noise is dependent on inputs in multiple access channels. Our approach is based on the sufficiency of linear codes. Using a simple and unifying framework, we not only re-establish with economy the optimality of linear codes for single-transmitter, single-receiver channels and for Slepian-Wolf source coding, but also establish the optimality of linear codes for multiple access and for erasure degraded broadcast channels. The linearity allows us to obtain simple optimal code constructions and to study capacity regions of the noisy multiple access and the degraded broadcast channel. The linearity of both source and network coding blurs the delineation between source and network codes. While our results point to the fact that separation of source coding and channel coding is optimal in some canonical networks, we show that decomposing networks into canonical subnetworks may not be effective. Thus, we argue that it may be the lack of decomposability of a network into canonical network modules, rather than the lack of separation between source and channel coding, that presents major challenges for coding over networks.
Market Equilibrium for Bundle Auctions and the Matching Core of Nonnegative TU Games
Venue: arXiv cs.GT 2006
Year: 2006

We discuss bundle auctions within the framework of an integer allocation problem. We show that for multi-unit auctions, of which bundle auctions are a special case, market equilibrium and constrained market equilibrium are equivalent concepts. This equivalence, allows us to obtain a computable necessary and sufficient condition for the existence of constrained market equilibrium for bundle auctions. We use this result to obtain a necessary and sufficient condition for the existence of market equilibrium for multi-unit auctions. After obtaining the induced bundle auction of a nonnegative TU game, we show that the existence of market equilibrium implies the existence of a possibly different market equilibrium as well, which corresponds very naturally to an outcome in the matching core of the TU game. Consequently we show that the matching core of the nonnegative TU game is non-empty if and only if the induced market game has a market equilibrium.
Health-e-Child : An Integrated Biomedical Platform for Grid-Based Paediatric Applications
Venue: arXiv cs.DC 2006
Year: 2006

There is a compelling demand for the integration and exploitation of heterogeneous biomedical information for improved clinical practice, medical research, and personalised healthcare across the EU. The Health-e-Child project aims at developing an integrated healthcare platform for European Paediatrics, providing seamless integration of traditional and emerging sources of biomedical information. The long-term goal of the project is to provide uninhibited access to universal biomedical knowledge repositories for personalised and preventive healthcare, large-scale information-based biomedical research and training, and informed policy making. The project focus will be on individualised disease prevention, screening, early diagnosis, therapy and follow-up of paediatric heart diseases, inflammatory diseases, and brain tumours. The project will build a Grid-enabled European network of leading clinical centres that will share and annotate biomedical data, validate systems clinically, and diffuse clinical excellence across Europe by setting up new technologies, clinical workflows, and standards. This paper outlines the design approach being adopted in Health-e-Child to enable the delivery of an integrated biomedical information platform.
Estimation of linear, non-gaussian causal models in the presence of confounding latent variables
Venue: arXiv cs.AI 2006
Year: 2006

The estimation of linear causal models (also known as structural equation models) from data is a well-known problem which has received much attention in the past. Most previous work has, however, made an explicit or implicit assumption of gaussianity, limiting the identifiability of the models. We have recently shown (Shimizu et al, 2005; Hoyer et al, 2006) that for non-gaussian distributions the full causal model can be estimated in the no hidden variables case. In this contribution, we discuss the estimation of the model when confounding latent variables are present. Although in this case uniqueness is no longer guaranteed, there is at most a finite set of models which can fit the data. We develop an algorithm for estimating this set, and describe numerical simulations which confirm the theoretical arguments and demonstrate the practical viability of the approach. Full Matlab code is provided for all simulations.
The NoN Approach to Autonomic Face Recognition
Venue: arXiv cs.NE 2006
Year: 2006

A method of autonomic face recognition based on the biologically plausible network of networks (NoN) model of information processing is presented. The NoN model is based on locally parallel and globally coordinated transformations in which the neurons or computational units form distributed networks, which themselves link to form larger networks. This models the structures in the cerebral cortex described by Mountcastle and the architecture based on that proposed for information processing by Sutton. In the proposed implementation, face images are processed by a nested family of locally operating networks along with a hierarchically superior network that classifies the information from each of the local networks. The results of the experiments yielded a maximum of 98.5% recognition accuracy and an average of 97.4% recognition accuracy on a benchmark database.
Information and Errors in Quantum Teleportation
Venue: arXiv cs.IT 2006
Year: 2006

This article considers the question of the teleportation protocol from an engineering perspective. The protocol ideally requires an authority that ensures that the two communicating parties have a perfectly entangled pair of particles available to them. But this cannot be unconditionally established to the satisfaction of the parties due to the fact that an unknown quantum state cannot be copied. This supports the view that quantum information cannot be treated on the same basis as classical information.
Homogeneity vs. Adjacency: generalising some graph decomposition algorithms
Venue: arXiv cs.DS 2006
Year: 2006

In this paper, a new general decomposition theory inspired from modular graph decomposition is presented. Our main result shows that, within this general theory, most of the nice algorithmic tools developed for modular decomposition are still efficient. This theory not only unifies the usual modular decomposition generalisations such as modular decomposition of directed graphs or decomposition of 2-structures, but also star cutsets and bimodular decomposition. Our general framework provides a decomposition algorithm which improves the best known algorithms for bimodular decomposition.
Testing Graph Isomorphism in Parallel by Playing a Game
Venue: arXiv cs.CC 2006
Year: 2006

Our starting point is the observation that if graphs in a class C have low descriptive complexity in first order logic, then the isomorphism problem for C is solvable by a fast parallel algorithm (essentially, by a simple combinatorial algorithm known as the multidimensional Weisfeiler-Lehman algorithm). Using this approach, we prove that isomorphism of graphs of bounded treewidth is testable in TC1, answering an open question posed by Chandrasekharan. Furthermore, we obtain an AC1 algorithm for testing isomorphism of rotation systems (combinatorial specifications of graph embeddings). The AC1 upper bound was known before, but the fact that this bound can be achieved by the simple Weisfeiler-Lehman algorithm is new. Combined with other known results, it also yields a new AC1 isomorphism algorithm for planar graphs.
An Improved Exact Algorithm for the Domatic Number Problem
Venue: arXiv cs.CC 2006
Year: 2006

The 3-domatic number problem asks whether a given graph can be partitioned intothree dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695^n (up to polynomial factors). This result improves the previous bound of 2.8805^n, which is due to Fomin, Grandoni, Pyatkin, and Stepanov. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta(G) by a randomized algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta(G) >= 5. Our new randomized algorithm employs Schoening's approach to constraint satisfaction problems.
Quasi-Orthogonal STBC With Minimum Decoding Complexity
Venue: arXiv cs.IT 2006
Year: 2006

In this paper, we consider a quasi-orthogonal (QO) space-time block code (STBC) with minimum decoding complexity (MDC-QO-STBC). We formulate its algebraic structure and propose a systematic method for its construction. We show that a maximum-likelihood (ML) decoder for this MDC-QOSTBC, for any number of transmit antennas, only requires the joint detection of two real symbols. Assuming the use of a square or rectangular quadratic-amplitude modulation (QAM) or multiple phase-shift keying (MPSK) modulation for this MDC-QOSTBC, we also obtain the optimum constellation rotation angle, in order to achieve full diversity and optimum coding gain. We show that the maximum achievable code rate of these MDC-QOSTBC is 1 for three and four antennas and 3/4 for five to eight antennas. We also show that the proposed MDC-QOSTBC has several desirable properties, such as a more even power distribution among antennas and better scalability in adjusting the number of transmit antennas, compared with the coordinate interleaved orthogonal design (CIOD) and asymmetric CIOD (ACIOD) codes. For the case of an odd number of transmit antennas, MDC-QO-STBC also has better decoding performance than CIOD.
Entropy-optimal Generalized Token Bucket Regulator
Venue: arXiv cs.IT 2006
Year: 2006

We derive the maximum entropy of a flow (information utility) which conforms to traffic constraints imposed by a generalized token bucket regulator, by taking into account the covert information present in the randomness of packet lengths. Under equality constraints of aggregate tokens and aggregate bucket depth, a generalized token bucket regulator can achieve higher information utility than a standard token bucket regulator. The optimal generalized token bucket regulator has a near-uniform bucket depth sequence and a decreasing token increment sequence.
Convex Separation from Optimization via Heuristics
Venue: arXiv cs.DS 2006
Year: 2006

Let $K$ be a full-dimensional convex subset of $\mathbb{R}^n$. We describe a new polynomial-time Turing reduction from the weak separation problem for $K$ to the weak optimization problem for $K$ that is based on a geometric heuristic. We compare our reduction, which relies on analytic centers, with the standard, more general reduction.
About the domino problem in the hyperbolic plane from an algorithmic point of view
Venue: arXiv cs.CG 2006
Year: 2006

In this paper, we prove that the general problem of tiling the hyperbolic plane with à la Wang tiles is undecidable.
Enhanced Prolog Remote Predicate Call Protocol
Venue: arXiv cs.NI 2006
Year: 2006

Following the ideas of the Remote Procedure Call model, we have developed a logic programming counterpart, naturally called Prolog Remote Predicate Call (Prolog RPC). The Prolog RPC protocol facilitates the integration of Prolog code in multi-language applications as well as the development of distributed intelligent applications. One use of the protocol's most important uses could be the development of distributed applications that use Prolog at least partially to achieve their goals. Most notably the Distributed Artificial Intelligence (DAI) applications that are suitable for logic programming can profit from the use of the protocol. After proving its usefulness, we went further, developing a new version of the protocol, making it more reliable and extending its functionality. Because it has a new syntax and the new set of commands, we call this version Enhanced Prolog Remote Procedure Call. This paper describes the new features and modifications this second version introduced.
Estimating seed sensitivity on homogeneous alignments
Venue: arXiv cs.OH 2006
Year: 2006

We address the problem of estimating the sensitivity of seed-based similarity search algorithms. In contrast to approaches based on Markov models [18, 6, 3, 4, 10], we study the estimation based on homogeneous alignments. We describe an algorithm for counting and random generation of those alignments and an algorithm for exact computation of the sensitivity for a broad class of seed strategies. We provide experimental results demonstrating a bias introduced by ignoring the homogeneousness condition.
Towards an information-theoretically safe cryptographic protocol
Venue: arXiv cs.CR 2006
Year: 2006

We introduce what --if some kind of group action exists-- is a truly (information theoretically) safe cryptographic communication system: a protocol which provides \emph{zero} information to any passive adversary having full access to the channel.
Minimizing Symmetric Set Functions Faster
Venue: arXiv cs.DM 2006
Year: 2006

We describe a combinatorial algorithm which, given a monotone and consistent symmetric set function d on a finite set V in the sense of Rizzi, constructs a non trivial set S minimizing d(S,V-S). This includes the possibility for the minimization of symmetric submodular functions. The presented algorithm requires at most as much time as the one described by Rizzi, but depending on the function d, it may allow several improvements.
A General Framework for Scalability and Performance Analysis of DHT Routing Systems
Venue: arXiv cs.DC 2006
Year: 2006

In recent years, many DHT-based P2P systems have been proposed, analyzed, and certain deployments have reached a global scale with nearly one million nodes. One is thus faced with the question of which particular DHT system to choose, and whether some are inherently more robust and scalable. Toward developing such a comparative framework, we present the reachable component method (RCM) for analyzing the performance of different DHT routing systems subject to random failures. We apply RCM to five DHT systems and obtain analytical expressions that characterize their routability as a continuous function of system size and node failure probability. An important consequence is that in the large-network limit, the routability of certain DHT systems go to zero for any non-zero probability of node failure. These DHT routing algorithms are therefore unscalable, while some others, including Kademlia, which powers the popular eDonkey P2P system, are found to be scalable.
On Cosets of the Generalized First-Order Reed-Muller Code with Low PMEPR
Venue: arXiv cs.IT 2006
Year: 2006

Golay sequences are well suited for the use as codewords in orthogonal frequency-division multiplexing (OFDM), since their peak-to-mean envelope power ratio (PMEPR) in q-ary phase-shift keying (PSK) modulation is at most 2. It is known that a family of polyphase Golay sequences of length 2^m organizes in m!/2 cosets of a q-ary generalization of the first-order Reed-Muller code, RM_q(1,m). In this paper a more general construction technique for cosets of RM_q(1,m) with low PMEPR is established. These cosets contain so-called near-complementary sequences. The application of this theory is then illustrated by providing some construction examples. First, it is shown that the m!/2 cosets of RM_q(1,m) comprised of Golay sequences just arise as a special case. Second, further families of cosets of RM_q(1,m) with maximum PMEPR between 2 and 4 are presented, showing that some previously unexplained phenomena can now be understood within a unified framework. A lower bound on the PMEPR of cosets of RM_q(1,m) is proved as well, and it is demonstrated that the upper bound on the PMEPR is tight in many cases. Finally it is shown that all upper bounds on the PMEPR of cosets of RM_q(1,m) also hold for the peak-to-average power ratio (PAPR) under the Walsh-Hadamard transform.
Error Rate Analysis for Coded Multicarrier Systems over Quasi-Static Fading Channels
Venue: arXiv cs.IT 2006
Year: 2006

This paper presents two methods for approximating the performance of coded multicarrier systems operating over frequency-selective, quasi-static fading channels with non-ideal interleaving. The first method is based on approximating the performance of the system over each realization of the channel, and is suitable for obtaining the outage performance of this type of system. The second method is based on knowledge of the correlation matrix of the frequency-domain channel gains and can be used to directly obtain the average performance. Both of the methods are applicable for convolutionally-coded interleaved systems employing Quadrature Amplitude Modulation (QAM). As examples, both methods are used to study the performance of the Multiband Orthogonal Frequency Division Multiplexing (OFDM) proposal for high data-rate Ultra-Wideband (UWB) communication.
The Aryabhata Algorithm Using Least Absolute Remainders
Venue: arXiv cs.CR 2006
Year: 2006

This paper presents an introduction to the Aryabhata algorithm for finding multiplicative inverses and solving linear congruences, both of which have applications in cryptography. We do so by the use of the least absolute remainders. The exposition of the Aryabhata algorithm provided here can have performance that could exceed what was described recently by Rao and Yang.
On Covering a Graph Optimally with Induced Subgraphs
Venue: arXiv cs.DM 2006
Year: 2006

We consider the problem of covering a graph with a given number of induced subgraphs so that the maximum number of vertices in each subgraph is minimized. We prove NP-completeness of the problem, prove lower bounds, and give approximation algorithms for certain graph classes.