OpenRaiser/Intern-Atlas huggingface dataset:
On Kernelization of Supervised Mahalanobis Distance Learners
Venue: arXiv cs.LG 2009
Year: 2009

This paper focuses on the problem of kernelizing an existing supervised Mahalanobis distance learner. The following features are included in the paper. Firstly, three popular learners, namely, "neighborhood component analysis", "large margin nearest neighbors" and "discriminant neighborhood embedding", which do not have kernel versions are kernelized in order to improve their classification performances. Secondly, an alternative kernelization framework called "KPCA trick" is presented. Implementing a learner in the new framework gains several advantages over the standard framework, e.g. no mathematical formulas and no reprogramming are required for a kernel implementation, the framework avoids troublesome problems such as singularity, etc. Thirdly, while the truths of representer theorems are just assumptions in previous papers related to ours, here, representer theorems are formally proven. The proofs validate both the kernel trick and the KPCA trick in the context of Mahalanobis distance learning. Fourthly, unlike previous works which always apply brute force methods to select a kernel, we investigate two approaches which can be efficiently adopted to construct an appropriate kernel for a given dataset. Finally, numerical results on various real-world datasets are presented.
A complexity dichotomy for partition functions with mixed signs
Venue: arXiv cs.CC 2009
Year: 2009

Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colourings or the number of independent sets of a graph and also the partition functions of certain "spin glass" models of statistical physics such as the Ising model. Building on earlier work by Dyer, Greenhill and Bulatov, Grohe, we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by a Hadamard matrices -- these turn out to be central in our proofs -- we obtain a simple algebraic tractability criterion, which says that the tractable cases are those "representable" by a quadratic polynomial over the field GF(2).
Push & Pull: autonomous deployment of mobile sensors for a complete coverage
Venue: arXiv cs.NI 2009
Year: 2009

Mobile sensor networks are important for several strategic applications devoted to monitoring critical areas. In such hostile scenarios, sensors cannot be deployed manually and are either sent from a safe location or dropped from an aircraft. Mobile devices permit a dynamic deployment reconfiguration that improves the coverage in terms of completeness and uniformity. In this paper we propose a distributed algorithm for the autonomous deployment of mobile sensors called Push&Pull. According to our proposal, movement decisions are made by each sensor on the basis of locally available information and do not require any prior knowledge of the operating conditions or any manual tuning of key parameters. We formally prove that, when a sufficient number of sensors are available, our approach guarantees a complete and uniform coverage. Furthermore, we demonstrate that the algorithm execution always terminates preventing movement oscillations. Numerous simulations show that our algorithm reaches a complete coverage within reasonable time with moderate energy consumption, even when the target area has irregular shapes. Performance comparisons between Push&Pull and one of the most acknowledged algorithms show how the former one can efficiently reach a more uniform and complete coverage under a wide range of working scenarios.
A Lower Bound on the Bayesian MSE Based on the Optimal Bias Function
Venue: arXiv cs.IT 2009
Year: 2009

A lower bound on the minimum mean-squared error (MSE) in a Bayesian estimation problem is proposed in this paper. This bound utilizes a well-known connection to the deterministic estimation setting. Using the prior distribution, the bias function which minimizes the Cramer-Rao bound can be determined, resulting in a lower bound on the Bayesian MSE. The bound is developed for the general case of a vector parameter with an arbitrary probability distribution, and is shown to be asymptotically tight in both the high and low signal-to-noise ratio regimes. A numerical study demonstrates several cases in which the proposed technique is both simpler to compute and tighter than alternative methods.
Two-enqueuer queue in Common2
Venue: arXiv cs.DC 2009
Year: 2009

The question of whether all shared objects with consensus number 2 belong to Common2, the set of objects that can be implemented in a wait-free manner by any type of consensus number 2, was first posed by Herlihy. In the absence of general results, several researchers have obtained implementations for restricted-concurrency versions of FIFO queues. We present the first Common2 algorithm for a queue with two enqueuers and any number of dequeuers.
Mnesors for databases
Venue: arXiv cs.LO 2009
Year: 2009

We add commutativity to axioms defining mnesors and substitute a bitrop for the lattice. We show that it can be applied to relational database querying: set union, intersection and selection are redifined only from the mnesor addition and the granular multiplication. Union-compatibility is not required.
Proof Search Specifications of Bisimulation and Modal Logics for the pi-Calculus
Venue: arXiv cs.LO 2009
Year: 2009

We specify the operational semantics and bisimulation relations for the finite pi-calculus within a logic that contains the nabla quantifier for encoding generic judgments and definitions for encoding fixed points. Since we restrict to the finite case, the ability of the logic to unfold fixed points allows this logic to be complete for both the inductive nature of operational semantics and the coinductive nature of bisimulation. The nabla quantifier helps with the delicate issues surrounding the scope of variables within pi-calculus expressions and their executions (proofs). We illustrate several merits of the logical specifications permitted by this logic: they are natural and declarative; they contain no side-conditions concerning names of variables while maintaining a completely formal treatment of such variables; differences between late and open bisimulation relations arise from familar logic distinctions; the interplay between the three quantifiers (for all, exists, and nabla) and their scopes can explain the differences between early and late bisimulation and between various modal operators based on bound input and output actions; and proof search involving the application of inference rules, unification, and backtracking can provide complete proof systems for one-step transitions, bisimulation, and satisfaction in modal logic. We also illustrate how one can encode the pi-calculus with replications, in an extended logic with induction and co-induction.
A simple, polynomial-time algorithm for the matrix torsion problem
Venue: arXiv cs.DM 2009
Year: 2009

The Matrix Torsion Problem (MTP) is: given a square matrix M with rational entries, decide whether two distinct powers of M are equal. It has been shown by Cassaigne and the author that the MTP reduces to the Matrix Power Problem (MPP) in polynomial time: given two square matrices A and B with rational entries, the MTP is to decide whether B is a power of A. Since the MPP is decidable in polynomial time, it is also the case of the MTP. However, the algorithm for MPP is highly non-trivial. The aim of this note is to present a simple, direct, polynomial-time algorithm for the MTP.
Neural networks in 3D medical scan visualization
Venue: arXiv cs.AI 2009
Year: 2009

For medical volume visualization, one of the most important tasks is to reveal clinically relevant details from the 3D scan (CT, MRI ...), e.g. the coronary arteries, without obscuring them with less significant parts. These volume datasets contain different materials which are difficult to extract and visualize with 1D transfer functions based solely on the attenuation coefficient. Multi-dimensional transfer functions allow a much more precise classification of data which makes it easier to separate different surfaces from each other. Unfortunately, setting up multi-dimensional transfer functions can become a fairly complex task, generally accomplished by trial and error. This paper explains neural networks, and then presents an efficient way to speed up visualization process by semi-automatic transfer function generation. We describe how to use neural networks to detect distinctive features shown in the 2D histogram of the volume data and how to use this information for data classification.
Compressed Sensing of Analog Signals in Shift-Invariant Spaces
Venue: arXiv cs.IT 2009
Year: 2009

A traditional assumption underlying most data converters is that the signal should be sampled at a rate exceeding twice the highest frequency. This statement is based on a worst-case scenario in which the signal occupies the entire available bandwidth. In practice, many signals are sparse so that only part of the bandwidth is used. In this paper, we develop methods for low-rate sampling of continuous-time sparse signals in shift-invariant (SI) spaces, generated by m kernels with period T. We model sparsity by treating the case in which only k out of the m generators are active, however, we do not know which k are chosen. We show how to sample such signals at a rate much lower than m/T, which is the minimal sampling rate without exploiting sparsity. Our approach combines ideas from analog sampling in a subspace with a recently developed block diagram that converts an infinite set of sparse equations to a finite counterpart. Using these two components we formulate our problem within the framework of finite compressed sensing (CS) and then rely on algorithms developed in that context. The distinguishing feature of our results is that in contrast to standard CS, which treats finite-length vectors, we consider sampling of analog signals for which no underlying finite-dimensional model exists. The proposed framework allows to extend much of the recent literature on CS to the analog domain.
"Minesweeper" and spectrum of discrete Laplacians
Venue: arXiv cs.DM 2009
Year: 2009

The paper is devoted to a problem inspired by the "Minesweeper" computer game. It is shown that certain configurations of open cells guarantee the existence and the uniqueness of solution. Mathematically the problem is reduced to some spectral properties of discrete differential operators. It is shown how the uniqueness can be used to create a new game which preserves the spirit of "Minesweeper" but does not require a computer.
A Sublinear Algorithm for Sparse Reconstruction with l2/l2 Recovery Guarantees
Venue: arXiv cs.IT 2009
Year: 2009

Compressed Sensing aims to capture attributes of a sparse signal using very few measurements. Candès and Tao showed that sparse reconstruction is possible if the sensing matrix acts as a near isometry on all $\boldsymbol{k}$-sparse signals. This property holds with overwhelming probability if the entries of the matrix are generated by an iid Gaussian or Bernoulli process. There has been significant recent interest in an alternative signal processing framework; exploiting deterministic sensing matrices that with overwhelming probability act as a near isometry on $\boldsymbol{k}$-sparse vectors with uniformly random support, a geometric condition that is called the Statistical Restricted Isometry Property or StRIP. This paper considers a family of deterministic sensing matrices satisfying the StRIP that are based on \srm codes (binary chirps) and a $\boldsymbol{k}$-sparse reconstruction algorithm with sublinear complexity. In the presence of stochastic noise in the data domain, this paper derives bounds on the $\boldsymbol{\ell_2}$ accuracy of approximation in terms of the $\boldsymbol{\ell_2}$ norm of the measurement noise and the accuracy of the best $\boldsymbol{k}$-sparse approximation, also measured in the $\boldsymbol{\ell_2}$ norm. This type of $\boldsymbol{\ell_2 /\ell_2}$ bound is tighter than the standard $\boldsymbol{\ell_2 /\ell_1}$ or $\boldsymbol{\ell_1/ \ell_1}$ bounds.
On Ergodic Sum Capacity of Fading Cognitive Multiple-Access and Broadcast Channels
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the information-theoretic limits of a secondary or cognitive radio (CR) network under spectrum sharing with an existing primary radio network. In particular, the fading cognitive multiple-access channel (C-MAC) is first studied, where multiple secondary users transmit to the secondary base station (BS) under both individual transmit-power constraints and a set of interference-power constraints each applied at one of the primary receivers. This paper considers the long-term (LT) or the short-term (ST) transmit-power constraint over the fading states at each secondary transmitter, combined with the LT or ST interference-power constraint at each primary receiver. In each case, the optimal power allocation scheme is derived for the secondary users to achieve the ergodic sum capacity of the fading C-MAC, as well as the conditions for the optimality of the dynamic time-division-multiple-access (D-TDMA) scheme in the secondary network. The fading cognitive broadcast channel (C-BC) that models the downlink transmission in the secondary network is then studied under the LT/ST transmit-power constraint at the secondary BS jointly with the LT/ST interference-power constraint at each of the primary receivers. It is shown that D-TDMA is indeed optimal for achieving the ergodic sum capacity of the fading C-BC for all combinations of transmit-power and interference-power constraints.
Finding Large Clique Minors is Hard
Venue: arXiv cs.DM 2009
Year: 2009

We prove that it is NP-complete, given a graph G and a parameter h, to determine whether G contains a complete graph K_h as a minor.
Source and Channel Coding for Correlated Sources Over Multiuser Channels
Venue: arXiv cs.IT 2009
Year: 2009

Source and channel coding over multiuser channels in which receivers have access to correlated source side information is considered. For several multiuser channel models necessary and sufficient conditions for optimal separation of the source and channel codes are obtained. In particular, the multiple access channel, the compound multiple access channel, the interference channel and the two-way channel with correlated sources and correlated receiver side information are considered, and the optimality of separation is shown to hold for certain source and side information structures. Interestingly, the optimal separate source and channel codes identified for these models are not necessarily the optimal codes for the underlying source coding or the channel coding problems. In other words, while separation of the source and channel codes is optimal, the nature of these optimal codes is impacted by the joint design criterion.
Z2Z4-linear codes: rank and kernel
Venue: arXiv cs.IT 2009
Year: 2009

A code C is Z2Z4-additive if the set of coordinates can be partitioned into two subsets X and Y such that the punctured code of C by deleting the coordinates outside X (respectively, Y) is a binary linear code (respectively, a quaternary linear code). In this paper, the rank and dimension of the kernel for Z2Z4-linear codes, which are the corresponding binary codes of Z2Z4-additive codes, are studied. The possible values of these two parameters for Z2Z4-linear codes, giving lower and upper bounds, are established. For each possible rank r between these bounds, the construction of a Z2Z4-linear code with rank r is given. Equivalently, for each possible dimension of the kernel k, the construction of a Z2Z4-linear code with dimension of the kernel k is given. Finally, the bounds on the rank, once the kernel dimension is fixed, are established and the construction of a Z2Z4-additive code for each possible pair (r,k) is given.
Authenticated Adversarial Routing
Venue: arXiv cs.CR 2009
Year: 2009

The aim of this paper is to demonstrate the feasibility of authenticated throughput-efficient routing in an unreliable and dynamically changing synchronous network in which the majority of malicious insiders try to destroy and alter messages or disrupt communication in any way. More specifically, in this paper we seek to answer the following question: Given a network in which the majority of nodes are controlled by a malicious adversary and whose topology is changing every round, is it possible to develop a protocol with polynomially-bounded memory per processor that guarantees throughput-efficient and correct end-to-end communication? We answer the question affirmatively for extremely general corruption patterns: we only request that the topology of the network and the corruption pattern of the adversary leaves at least one path each round connecting the sender and receiver through honest nodes (though this path may change at every round). Out construction works in the public-key setting and enjoys bounded memory per processor (that does not depend on the amount of traffic and is polynomial in the network size.) Our protocol achieves optimal transfer rate with negligible decoding error. We stress that our protocol assumes no knowledge of which nodes are corrupted nor which path is reliable at any round, and is also fully distributed with nodes making decisions locally, so that they need not know the topology of the network at any time.
Kovalenko's Full-Rank Limit and Overhead as Lower Bounds for Error-Performances of LDPC and LT Codes over Binary Erasure Channels
Venue: arXiv cs.IT 2009
Year: 2009

We present Kovalenko's full-rank limit as a tight lower bound for decoding error probability of LDPC codes and LT codes over BEC. From the limit, we derive a full-rank overhead as a lower bound for stable overheads for successful maximum-likelihood decoding of the codes.
Achievable rate regions for bi-directional relaying
Venue: arXiv cs.IT 2009
Year: 2009

In a bi-directional relay channel, two nodes wish to exchange independent messages over a shared wireless half-duplex channel with the help of a relay. In this paper, we derive achievable rate regions for four new half-duplex protocols and compare these to four existing half-duplex protocols and outer bounds. In time, our protocols consist of either two or three phases. In the two phase protocols, both users simultaneously transmit during the first phase and the relay alone transmits during the second phase, while in the three phase protocol the two users sequentially transmit followed by a transmission from the relay. The relay may forward information in one of four manners; we outline existing Amplify and Forward (AF), Decode and Forward (DF) and Compress and Forward (CF) relaying schemes and introduce the novel Mixed Forward scheme. The latter is a combination of CF in one direction and DF in the other. We derive achievable rate regions for the CF and Mixed relaying schemes for the two and three phase protocols. In the last part of this work we provide a comprehensive treatment of 8 possible half-duplex bi-directional relaying protocols in Gaussian noise, obtaining their respective achievable rate regions, outer bounds, and their relative performance under different SNR and relay geometries.
Studying Geometric Graph Properties of Road Networks Through an Algorithmic Lens
Venue: arXiv cs.CG 2009
Year: 2009

This paper studies real-world road networks from an algorithmic perspective, focusing on empirical studies that yield useful properties of road networks that can be exploited in the design of fast algorithms that deal with geographic data. Unlike previous approaches, our study is not based on the assumption that road networks are planar graphs. Indeed, based on the a number of experiments we have performed on the road networks of the 50 United States and District of Columbia, we provide strong empirical evidence that road networks are quite non-planar. Our approach therefore instead is directed at finding algorithmically-motivated properties of road networks as non-planar geometric graphs, focusing on alternative properties of road networks that can still lead to efficient algorithms for such problems as shortest paths and Voronoi diagrams. In particular, we study road networks as multiscale-dispersed graphs, which is a concept we formalize in terms of disk neighborhood systems. This approach allows us to develop fast algorithms for road networks without making any additional assumptions about the distribution of edge weights. In fact, our algorithms can allow for non-metric weights.
SWIM: A Simple Model to Generate Small Mobile Worlds
Venue: arXiv cs.DC 2009
Year: 2009

This paper presents small world in motion (SWIM), a new mobility model for ad-hoc networking. SWIM is relatively simple, is easily tuned by setting just a few parameters, and generates traces that look real--synthetic traces have the same statistical properties of real traces. SWIM shows experimentally and theoretically the presence of the power law and exponential decay dichotomy of inter-contact time, and, most importantly, our experiments show that it can predict very accurately the performance of forwarding protocols.
Complexity Classes as Mathematical Axioms
Venue: arXiv cs.CC 2009
Year: 2009

Treating a conjecture, P^#P != NP, on the separation of complexity classes as an axiom, an implication is found in three manifold topology with little obvious connection to complexity theory. This is reminiscent of Harvey Friedman's work on finitistic interpretations of large cardinal axioms.
Cognitive Radio with Partial Channel State Information at the Transmitter
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we present the cognitive radio system design with partial channel state information known at the transmitter (CSIT).We replace the dirty paper coding (DPC) used in the cognitive radio with full CSIT by the linear assignment Gel'fand-Pinsker coding (LA-GPC), which can utilize the limited knowledge of the channel more efficiently. Based on the achievable rate derived from the LA-GPC, two optimization problems under the fast and slow fading channels are formulated. We derive semianalytical solutions to find the relaying ratios and precoding coefficients. The critical observation is that the complex rate functions in these problems are closely related to ratios of quadratic form. Simulation results show that the proposed semi-analytical solutions perform close to the optimal solutions found by brute-force search, and outperform the systems based on naive DPC. Asymptotic analysis also shows that these solutions converge to the optimal ones solved with full CSIT when the K-factor of Rician channel approaches infinity. Moreover, a new coding scheme is proposed to implement the LA-GPC in practice. Simulation results show that the proposed practical coding scheme can efficiently reach the theoretical rate performance.
Graphical Presentations of Symmetric Monoidal Closed Theories
Venue: arXiv cs.LO 2009
Year: 2009

We define a notion of symmetric monoidal closed (SMC) theory, consisting of a SMC signature augmented with equations, and describe the classifying categories of such theories in terms of proof nets.