OpenRaiser/Intern-Atlas huggingface dataset:
Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners
Venue: arXiv cs.CG 2008
Year: 2008

We show that for every $n$-point metric space $M$ there exists a spanning tree $T$ with unweighted diameter $O(\log n)$ and weight $ω(T) = O(\log n) \cdot ω(MST(M))$. Moreover, there is a designated point $rt$ such that for every point $v$, $dist_T(rt,v) \le (1+ε) \cdot dist_M(rt,v)$, for an arbitrarily small constant $ε> 0$. We extend this result, and provide a tradeoff between unweighted diameter and weight, and prove that this tradeoff is \emph{tight up to constant factors} in the entire range of parameters. These results enable us to settle a long-standing open question in Computational Geometry. In STOC'95 Arya et al. devised a construction of Euclidean Spanners with unweighted diameter $O(\log n)$ and weight $O(\log n) \cdot ω(MST(M))$. Ten years later in SODA'05 Agarwal et al. showed that this result is tight up to a factor of $O(\log \log n)$. We close this gap and show that the result of Arya et al. is tight up to constant factors.
Information Rates of Minimal Non-Matroid-Related Access Structures
Venue: arXiv cs.CR 2008
Year: 2008

In a secret sharing scheme, shares of a secret are distributed to participants in such a way that only certain predetermined sets of participants are qualified to reconstruct the secret. An access structure on a set of participants specifies which sets are to be qualified. The information rate of an access structure is a bound on how efficient a secret sharing scheme for that access structure can be. Marti-Farre and Padro showed that all access structures with information rate greater than two-thirds are matroid-related, and Stinson showed that four of the minor-minimal, non-matroid-related access structures have information rate exactly two-thirds. By a result of Seymour, there are infinitely many remaining minor-minimal, non-matroid-related access structures. In this paper we find the exact information rates for all such structures.
Regulation and the Integrity of Spreadsheets in the Information Supply Chain
Venue: arXiv cs.CY 2008
Year: 2008

Spreadsheets provide many of the key links between information systems, closing the gap between business needs and the capability of central systems. Recent regulations have brought these vulnerable parts of information supply chains into focus. The risk they present to the organisation depends on the role that they fulfil, with generic differences between their use as modeling tools and as operational applications. Four sections of the Sarbanes-Oxley Act (SOX) are particularly relevant to the use of spreadsheets. Compliance with each of these sections is dependent on maintaining the integrity of those spreadsheets acting as operational applications. This can be achieved manually but at high cost. There are a range of commercially available off-the-shelf solutions that can reduce this cost. These may be divided into those that assist in the debugging of logic and more recently the arrival of solutions that monitor the change and user activity taking place in business-critical spreadsheets. ClusterSeven provides one of these monitoring solutions, highlighting areas of operational risk whilst also establishing a database of information to deliver new business intelligence.
Joint source and channel coding for MIMO systems: Is it better to be robust or quick?
Venue: arXiv cs.IT 2008
Year: 2008

We develop a framework to optimize the tradeoff between diversity, multiplexing, and delay in MIMO systems to minimize end-to-end distortion. We first focus on the diversity-multiplexing tradeoff in MIMO systems, and develop analytical results to minimize distortion of a vector quantizer concatenated with a space-time MIMO channel code. In the high SNR regime we obtain a closed-form expression for the end-to-end distortion as a function of the optimal point on the diversity-multiplexing tradeoff curve. For large but finite SNR we find this optimal point via convex optimization. We then consider MIMO systems using ARQ retransmission to provide additional diversity at the expense of delay. For sources without a delay constraint, distortion is minimized by maximizing the ARQ window size. This results in an ARQ-enhanced multiplexing-diversity tradeoff region, with distortion minimized over this region in the same manner as without ARQ. Under a source delay constraint the problem formulation changes to account for delay distortion associated with random message arrival and random ARQ completion times. We use a dynamic programming formulation to capture the channel diversity-multiplexing tradeoff at finite SNR as well as the random arrival and retransmission dynamics; we solve for the optimal multiplexing-diversity-delay tradeoff to minimize end-to-end distortion associated with the source encoder, channel, and ARQ retransmissions. Our results show that a delay-sensitive system should adapt its operating point on the diversity-multiplexing-delay tradeoff region to the system dynamics. We provide numerical results that demonstrate significant performance gains of this adaptive policy over a static allocation of diversity/multiplexing in the channel code and a static ARQ window size.
On the Weight Distribution of the Extended Quadratic Residue Code of Prime 137
Venue: arXiv cs.IT 2008
Year: 2008

The Hamming weight enumerator function of the formally self-dual even, binary extended quadratic residue code of prime p = 8m + 1 is given by Gleason's theorem for singly-even code. Using this theorem, the Hamming weight distribution of the extended quadratic residue is completely determined once the number of codewords of Hamming weight j A_j, for 0 <= j <= 2m, are known. The smallest prime for which the Hamming weight distribution of the corresponding extended quadratic residue code is unknown is 137. It is shown in this paper that, for p=137 A_2m = A_34 may be obtained with out the need of exhaustive codeword enumeration. After the remainder of A_j required by Gleason's theorem are computed and independently verified using their congruences, the Hamming weight distributions of the binary augmented and extended quadratic residue codes of prime 137 are derived.
New Lower Bounds on Sizes of Permutation Arrays
Venue: arXiv cs.IT 2008
Year: 2008

A permutation array(or code) of length $n$ and distance $d$, denoted by $(n,d)$ PA, is a set of permutations $C$ from some fixed set of $n$ elements such that the Hamming distance between distinct members $\mathbf{x},\mathbf{y}\in C$ is at least $d$. Let $P(n,d)$ denote the maximum size of an $(n,d)$ PA. This correspondence focuses on the lower bound on $P(n,d)$. First we give three improvements over the Gilbert-Varshamov lower bounds on $P(n,d)$ by applying the graph theorem framework presented by Jiang and Vardy. Next we show another two new improved bounds by considering the covered balls intersections. Finally some new lower bounds for certain values of $n$ and $d$ are given.
A Class of Convex Polyhedra with Few Edge Unfoldings
Venue: arXiv cs.CG 2008
Year: 2008

We construct a sequence of convex polyhedra on n vertices with the property that, as n -> infinity, the fraction of its edge unfoldings that avoid overlap approaches 0, and so the fraction that overlap approaches 1. Nevertheless, each does have (several) nonoverlapping edge unfoldings.
An equivalence preserving transformation from the Fibonacci to the Galois NLFSRs
Venue: arXiv cs.CR 2008
Year: 2008

Conventional Non-Linear Feedback Shift Registers (NLFSRs) use the Fibonacci configuration in which the value of the first bit is updated according to some non-linear feedback function of previous values of other bits, and each remaining bit repeats the value of its previous bit. We show how to transform the feedback function of a Fibonacci NLFSR into several smaller feedback functions of individual bits. Such a transformation reduces the propagation time, thus increasing the speed of pseudo-random sequence generation. The practical significance of the presented technique is that is makes possible increasing the keystream generation speed of any Fibonacci NLFSR-based stream cipher with no penalty in area.
Exact Feasibility Tests for Real-Time Scheduling of Periodic Tasks upon Multiprocessor Platforms
Venue: arXiv cs.OS 2008
Year: 2008

In this paper we study the global scheduling of periodic task systems upon multiprocessor platforms. We first show two very general properties which are well-known for uniprocessor platforms and which remain for multiprocessor platforms: (i) under few and not so restrictive assumptions, we show that feasible schedules of periodic task systems are periodic from some point with a period equal to the least common multiple of task periods and (ii) for the specific case of synchronous periodic task systems, we show that feasible schedules repeat from the origin. We then present our main result: we characterize, for task-level fixed-priority schedulers and for asynchronous constrained or arbitrary deadline periodic task models, upper bounds of the first time instant where the schedule repeats. We show that job-level fixed-priority schedulers are predictable upon unrelated multiprocessor platforms. For task-level fixed-priority schedulers, based on the upper bounds and the predictability property, we provide for asynchronous constrained or arbitrary deadline periodic task sets, exact feasibility tests. Finally, for the job-level fixed-priority EDF scheduler, for which such an upper bound remains unknown, we provide an exact feasibility test as well.
A Class of Errorless Codes for Over-loaded Synchronous Wireless and Optical CDMA Systems
Venue: arXiv cs.IT 2008
Year: 2008

In this paper we introduce a new class of codes for over-loaded synchronous wireless and optical CDMA systems which increases the number of users for fixed number of chips without introducing any errors. Equivalently, the chip rate can be reduced for a given number of users, which implies bandwidth reduction for downlink wireless systems. An upper bound for the maximum number of users for a given number of chips is derived. Also, lower and upper bounds for the sum channel capacity of a binary over-loaded CDMA are derived that can predict the existence of such over-loaded codes. We also propose a simplified maximum likelihood method for decoding these types of over-loaded codes. Although a high percentage of the over-loading factor degrades the system performance in noisy channels, simulation results show that this degradation is not significant. More importantly, for moderate values of Eb/N0 (in the range of 6-10 dB) or higher, the proposed codes perform much better than the binary Welch bound equality sequences.
Improved Deterministic Length Reduction
Venue: arXiv cs.DS 2008
Year: 2008

This paper presents a new technique for deterministic length reduction. This technique improves the running time of the algorithm presented in \cite{LR07} for performing fast convolution in sparse data. While the regular fast convolution of vectors $V_1,V_2$ whose sizes are $N_1,N_2$ respectively, takes $O(N_1 \log N_2)$ using FFT, using the new technique for length reduction, the algorithm proposed in \cite{LR07} performs the convolution in $O(n_1 \log^3 n_1)$, where $n_1$ is the number of non-zero values in $V_1$. The algorithm assumes that $V_1$ is given in advance, and $V_2$ is given in running time. The novel technique presented in this paper improves the convolution time to $O(n_1 \log^2 n_1)$ {\sl deterministically}, which equals the best running time given achieved by a {\sl randomized} algorithm. The preprocessing time of the new technique remains the same as the preprocessing time of \cite{LR07}, which is $O(n_1^2)$. This assumes and deals the case where $N_1$ is polynomial in $n_1$. In the case where $N_1$ is exponential in $n_1$, a reduction to a polynomial case can be used. In this paper we also improve the preprocessing time of this reduction from $O(n_1^4)$ to $O(n_1^3{\rm polylog}(n_1))$.
Shallow Models for Non-Iterative Modal Logics
Venue: arXiv cs.LO 2008
Year: 2008

The methods used to establish PSPACE-bounds for modal logics can roughly be grouped into two classes: syntax driven methods establish that exhaustive proof search can be performed in polynomial space whereas semantic approaches directly construct shallow models. In this paper, we follow the latter approach and establish generic PSPACE-bounds for a large and heterogeneous class of modal logics in a coalgebraic framework. In particular, no complete axiomatisation of the logic under scrutiny is needed. This does not only complement our earlier, syntactic, approach conceptually, but also covers a wide variety of new examples which are difficult to harness by purely syntactic means. Apart from re-proving known complexity bounds for a large variety of structurally different logics, we apply our method to obtain previously unknown PSPACE-bounds for Elgesem's logic of agency and for graded modal logic over reflexive frames.
Algorithmically independent sequences
Venue: arXiv cs.IT 2008
Year: 2008

Two objects are independent if they do not affect each other. Independence is well-understood in classical information theory, but less in algorithmic information theory. Working in the framework of algorithmic information theory, the paper proposes two types of independence for arbitrary infinite binary sequences and studies their properties. Our two proposed notions of independence have some of the intuitive properties that one naturally expects. For example, for every sequence $x$, the set of sequences that are independent (in the weaker of the two senses) with $x$ has measure one. For both notions of independence we investigate to what extent pairs of independent sequences, can be effectively constructed via Turing reductions (from one or more input sequences). In this respect, we prove several impossibility results. For example, it is shown that there is no effective way of producing from an arbitrary sequence with positive constructive Hausdorff dimension two sequences that are independent (even in the weaker type of independence) and have super-logarithmic complexity. Finally, a few conjectures and open questions are discussed.
Improving Performance of Cluster Based Routing Protocol using Cross-Layer Design
Venue: arXiv cs.NI 2008
Year: 2008

The main goal of routing protocol is to efficiency delivers data from source to destination. All routing protocols are the same in this goal, but the way they adopt to achieve it is different, so routing strategy has an egregious role on the performance of an ad hoc network. Most of routing protocols proposed for ad hoc networks have a flat structure. These protocols expand the control overhead packets to discover or maintain a route. On the other hand a number of hierarchical-based routing protocols have been developed, mostly are based on layered design. These protocols improve network performances especially when the network size grows up since details about remote portion of network can be handled in an aggregate manner. Although, there is another approach to design a protocol called cross-layer design. Using this approach information can exchange between different layer of protocol stack, result in optimizing network performances. In this paper, we intend to exert cross-layer design to optimize Cluster Based Routing Protocol (Cross-CBRP). Using NS-2 network simulator we evaluate rate of cluster head changes, throughput and packet delivery ratio. Comparisons denote that Cross-CBRP has better performances with respect to the original CBRP.
The Ephemeral Pairing Problem
Venue: arXiv cs.CR 2008
Year: 2008

In wireless ad-hoc broadcast networks the pairing problem consists of establishing a (long-term) connection between two specific physical nodes in the network that do not yet know each other. We focus on the ephemeral version of this problem. Ephemeral pairings occur, for example, when electronic business cards are exchanged between two people that meet, or when one pays at a check-out using a wireless wallet. This problem can, in more abstract terms, be phrased as an ephemeral key exchange problem: given a low bandwidth authentic (or private) communication channel between two nodes, and a high bandwidth broadcast channel, can we establish a high-entropy shared secret session key between the two nodes without relying on any a priori shared secret information. Apart from introducing this new problem, we present several ephemeral key exchange protocols, both for the case of authentic channels as well as for the case of private channels.
New Extensions of Pairing-based Signatures into Universal (Multi) Designated Verifier Signatures
Venue: arXiv cs.CR 2008
Year: 2008

The concept of universal designated verifier signatures was introduced by Steinfeld, Bull, Wang and Pieprzyk at Asiacrypt 2003. These signatures can be used as standard publicly verifiable digital signatures but have an additional functionality which allows any holder of a signature to designate the signature to any desired verifier. This designated verifier can check that the message was indeed signed, but is unable to convince anyone else of this fact. We propose new efficient constructions for pairing-based short signatures. Our first scheme is based on Boneh-Boyen signatures and its security can be analyzed in the standard security model. We prove its resistance to forgery assuming the hardness of the so-called strong Diffie-Hellman problem, under the knowledge-of-exponent assumption. The second scheme is compatible with the Boneh-Lynn-Shacham signatures and is proven unforgeable, in the random oracle model, under the assumption that the computational bilinear Diffie-Hellman problem is untractable. Both schemes are designed for devices with constrained computation capabilities since the signing and the designation procedure are pairing-free. Finally, we present extensions of these schemes in the multi-user setting proposed by Desmedt in 2003.
Learning Balanced Mixtures of Discrete Distributions with Small Sample
Venue: arXiv cs.LG 2008
Year: 2008

We study the problem of partitioning a small sample of $n$ individuals from a mixture of $k$ product distributions over a Boolean cube $\{0, 1\}^K$ according to their distributions. Each distribution is described by a vector of allele frequencies in $\R^K$. Given two distributions, we use $γ$ to denote the average $\ell_2^2$ distance in frequencies across $K$ dimensions, which measures the statistical divergence between them. We study the case assuming that bits are independently distributed across $K$ dimensions. This work demonstrates that, for a balanced input instance for $k = 2$, a certain graph-based optimization function returns the correct partition with high probability, where a weighted graph $G$ is formed over $n$ individuals, whose pairwise hamming distances between their corresponding bit vectors define the edge weights, so long as $K = Ω(\ln n/γ)$ and $Kn = \tildeΩ(\ln n/γ^2)$. The function computes a maximum-weight balanced cut of $G$, where the weight of a cut is the sum of the weights across all edges in the cut. This result demonstrates a nice property in the high-dimensional feature space: one can trade off the number of features that are required with the size of the sample to accomplish certain tasks like clustering.
On quantum statistics in data analysis
Venue: arXiv cs.IR 2008
Year: 2008

Originally, quantum probability theory was developed to analyze statistical phenomena in quantum systems, where classical probability theory does not apply, because the lattice of measurable sets is not necessarily distributive. On the other hand, it is well known that the lattices of concepts, that arise in data analysis, are in general also non-distributive, albeit for completely different reasons. In his recent book, van Rijsbergen argues that many of the logical tools developed for quantum systems are also suitable for applications in information retrieval. I explore the mathematical support for this idea on an abstract vector space model, covering several forms of data analysis (information retrieval, data mining, collaborative filtering, formal concept analysis...), and roughly based on an idea from categorical quantum mechanics. It turns out that quantum (i.e., noncommutative) probability distributions arise already in this rudimentary mathematical framework. We show that a Bell-type inequality must be satisfied by the standard similarity measures, if they are used for preference predictions. The fact that already a very general, abstract version of the vector space model yields simple counterexamples for such inequalities seems to be an indicator of a genuine need for quantum statistics in data analysis.
Untangling polygons and graphs
Venue: arXiv cs.CG 2008
Year: 2008

Untangling is a process in which some vertices of a planar graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph C_n while keeping at least Ω(n^{2/3}) vertices fixed. For any graph G, we also present an upper bound on the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree and diameter of G. One of its consequences is the upper bound O((n log n)^{2/3}) for all 3-vertex-connected planar graphs.
Interior-Point Algorithms for Linear-Programming Decoding
Venue: arXiv cs.IT 2008
Year: 2008

Interior-point algorithms constitute a very interesting class of algorithms for solving linear-programming problems. In this paper we study efficient implementations of such algorithms for solving the linear program that appears in the linear-programming decoder formulation.
An integral formula for large random rectangular matrices and its application to analysis of linear vector channels
Venue: arXiv cs.IT 2008
Year: 2008

A statistical mechanical framework for analyzing random linear vector channels is presented in a large system limit. The framework is based on the assumptions that the left and right singular value bases of the rectangular channel matrix $\bH$ are generated independently from uniform distributions over Haar measures and the eigenvalues of $\bH^{\rm T}\bH$ asymptotically follow a certain specific distribution. These assumptions make it possible to characterize the communication performance of the channel utilizing an integral formula with respect to $\bH$, which is analogous to the one introduced by Marinari {\em et. al.} in {\em J. Phys. A} {\bf 27}, 7647 (1994) for large random square (symmetric) matrices. A computationally feasible algorithm for approximately decoding received signals based on the integral formula is also provided.