OpenRaiser/Intern-Atlas huggingface dataset:
Approximating the Statistics of various Properties in Randomly Weighted Graphs
Venue: arXiv cs.DS 2010
Year: 2010

Consider the setting of \emph{randomly weighted graphs}, namely, graphs whose edge weights are chosen independently according to probability distributions with finite support over the non-negative reals. Under this setting, properties of weighted graphs typically become random variables and we are interested in computing their statistical features. Unfortunately, this turns out to be computationally hard for some properties albeit the problem of computing them in the traditional setting of algorithmic graph theory is tractable. For example, there are well known efficient algorithms that compute the \emph{diameter} of a given weighted graph, yet, computing the \emph{expected} diameter of a given randomly weighted graph is \SharpP{}-hard even if the edge weights are identically distributed. In this paper, we define a family of properties of weighted graphs and show that for each property in this family, the problem of computing the \emph{$k^{\text{th}}$ moment} (and in particular, the expected value) of the corresponding random variable in a given randomly weighted graph $G$ admits a \emph{fully polynomial time randomized approximation scheme (FPRAS)} for every fixed $k$. This family includes fundamental properties of weighted graphs such as the diameter of $G$, the \emph{radius} of $G$ (with respect to any designated vertex) and the weight of a \emph{minimum spanning tree} of $G$.
In-packet Bloom filters: Design and networking applications
Venue: arXiv cs.DS 2010
Year: 2010

The Bloom filter (BF) is a well-known space-efficient data structure that answers set membership queries with some probability of false positives. In an attempt to solve many of the limitations of current inter-networking architectures, some recent proposals rely on including small BFs in packet headers for routing, security, accountability or other purposes that move application states into the packets themselves. In this paper, we consider the design of such in-packet Bloom filters (iBF). Our main contributions are exploring the design space and the evaluation of a series of extensions (1) to increase the practicality and performance of iBFs, (2) to enable false-negative-free element deletion, and (3) to provide security enhancements. In addition to the theoretical estimates, extensive simulations of the multiple design parameters and implementation alternatives validate the usefulness of the extensions, providing for enhanced and novel iBF networking applications.
Concentric Permutation Source Codes
Venue: arXiv cs.IT 2010
Year: 2010

Permutation codes are a class of structured vector quantizers with a computationally-simple encoding procedure based on sorting the scalar components. Using a codebook comprising several permutation codes as subcodes preserves the simplicity of encoding while increasing the number of rate-distortion operating points, improving the convex hull of operating points, and increasing design complexity. We show that when the subcodes are designed with the same composition, optimization of the codebook reduces to a lower-dimensional vector quantizer design within a single cone. Heuristics for reducing design complexity are presented, including an optimization of the rate allocation in a shape-gain vector quantizer with gain-dependent wrapped spherical shape codebook.
Universal and Composite Hypothesis Testing via Mismatched Divergence
Venue: arXiv cs.IT 2010
Year: 2010

For the universal hypothesis testing problem, where the goal is to decide between the known null hypothesis distribution and some other unknown distribution, Hoeffding proposed a universal test in the nineteen sixties. Hoeffding's universal test statistic can be written in terms of Kullback-Leibler (K-L) divergence between the empirical distribution of the observations and the null hypothesis distribution. In this paper a modification of Hoeffding's test is considered based on a relaxation of the K-L divergence test statistic, referred to as the mismatched divergence. The resulting mismatched test is shown to be a generalized likelihood-ratio test (GLRT) for the case where the alternate distribution lies in a parametric family of the distributions characterized by a finite dimensional parameter, i.e., it is a solution to the corresponding composite hypothesis testing problem. For certain choices of the alternate distribution, it is shown that both the Hoeffding test and the mismatched test have the same asymptotic performance in terms of error exponents. A consequence of this result is that the GLRT is optimal in differentiating a particular distribution from others in an exponential family. It is also shown that the mismatched test has a significant advantage over the Hoeffding test in terms of finite sample size performance. This advantage is due to the difference in the asymptotic variances of the two test statistics under the null hypothesis. In particular, the variance of the K-L divergence grows linearly with the alphabet size, making the test impractical for applications involving large alphabet distributions. The variance of the mismatched divergence on the other hand grows linearly with the dimension of the parameter space, and can hence be controlled through a prudent choice of the function class defining the mismatched divergence.
Capacity of Large-scale CSMA Wireless Networks
Venue: arXiv cs.NI 2010
Year: 2010

In the literature, asymptotic studies of multi-hop wireless network capacity often consider only centralized and deterministic TDMA (time-division multi-access) coordination schemes. There have been fewer studies of the asymptotic capacity of large-scale wireless networks based on CSMA (carrier-sensing multi-access), which schedules transmissions in a distributed and random manner. With the rapid and widespread adoption of CSMA technology, a critical question is that whether CSMA networks can be as scalable as TDMA networks. To answer this question and explore the capacity of CSMA networks, we first formulate the models of CSMA protocols to take into account the unique CSMA characteristics not captured by existing interference models in the literature. These CSMA models determine the feasible states, and consequently the capacity of CSMA networks. We then study the throughput efficiency of CSMA scheduling as compared to TDMA. Finally, we tune the CSMA parameters so as to maximize the throughput to the optimal order. As a result, we show that CSMA can achieve throughput as $Ω(\frac{1}{\sqrt{n}})$, the same order as optimal centralized TDMA, on uniform random networks. Our CSMA scheme makes use of an efficient backbone-peripheral routing scheme and a careful design of dual carrier-sensing and dual channel scheme. We also address the implementation issues of our CSMA scheme.
Packet Scheduling in a Size-Bounded Buffer
Venue: arXiv cs.DS 2010
Year: 2010

We consider algorithms to schedule packets with values and deadlines in a size-bounded buffer. At any time, the buffer can store at most B packets. Packets arrive over time. Each packet has a non-negative value and an integer deadline. In each time step, at most one packet can be sent. Packets can be dropped at any time before they are sent. The objective is to maximize the total value gained by delivering packets no later than their respective deadlines. This model generalizes the well-studied bounded-delay model (Hajek. CISS 2001. Kesselman et al. STOC 2001). We first provide an optimal offline algorithm for this model. Then we present an alternative proof of the 2-competitive deterministic online algorithm (Fung. arXiv July 2009). We also prove that the lower bound of competitive ratio of a family of (deterministic and randomized) algorithms is 2 - 1 / B.
Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation
Venue: arXiv cs.DS 2010
Year: 2010

We construct efficient data structures that are resilient against a constant fraction of adversarial noise. Our model requires that the decoder answers most queries correctly with high probability and for the remaining queries, the decoder with high probability either answers correctly or declares "don't know." Furthermore, if there is no noise on the data structure, it answers all queries correctly with high probability. Our model is the common generalization of a model proposed recently by de Wolf and the notion of "relaxed locally decodable codes" developed in the PCP literature. We measure the efficiency of a data structure in terms of its length, measured by the number of bits in its representation, and query-answering time, measured by the number of bit-probes to the (possibly corrupted) representation. In this work, we study two data structure problems: membership and polynomial evaluation. We show that these two problems have constructions that are simultaneously efficient and error-correcting.
Long non-crossing configurations in the plane
Venue: arXiv cs.CG 2010
Year: 2010

We revisit several maximization problems for geometric networks design under the non-crossing constraint, first studied by Alon, Rajagopalan and Suri (ACM Symposium on Computational Geometry, 1993). Given a set of $n$ points in the plane in general position (no three points collinear), compute a longest non-crossing configuration composed of straight line segments that is: (a) a matching (b) a Hamiltonian path (c) a spanning tree. Here we obtain new results for (b) and (c), as well as for the Hamiltonian cycle problem: (i) For the longest non-crossing Hamiltonian path problem, we give an approximation algorithm with ratio $\frac{2}{π+1} \approx 0.4829$. The previous best ratio, due to Alon et al., was $1/π\approx 0.3183$. Moreover, the ratio of our algorithm is close to $2/π$ on a relatively broad class of instances: for point sets whose perimeter (or diameter) is much shorter than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. (ii) For the longest non-crossing spanning tree problem, we give an approximation algorithm with ratio 0.502 which runs in $O(n \log{n})$ time. The previous ratio, 1/2, due to Alon et al., was achieved by a quadratic time algorithm. Along the way, we first re-derive the result of Alon et al. with a faster $O(n \log{n})$-time algorithm and a very simple analysis. (iii) For the longest non-crossing Hamiltonian cycle problem, we give an approximation algorithm whose ratio is close to $2/π$ on a relatively broad class of instances: for point sets with the product $\bf{<}$diameter$\times$ convex hull size $\bf{>}$ much smaller than the maximum length matching. The algorithm runs in $O(n^{7/3}\log{n})$ time. No previous approximation results were known for this problem.
Transform-based Distributed Data Gathering
Venue: arXiv cs.DC 2010
Year: 2010

A general class of unidirectional transforms is presented that can be computed in a distributed manner along an arbitrary routing tree. Additionally, we provide a set of conditions under which these transforms are invertible. These transforms can be computed as data is routed towards the collection (or sink) node in the tree and exploit data correlation between nodes in the tree. Moreover, when used in wireless sensor networks, these transforms can also leverage data received at nodes via broadcast wireless communications. Various constructions of unidirectional transforms are also provided for use in data gathering in wireless sensor networks. New wavelet transforms are also proposed which provide significant improvements over existing unidirectional transforms.
The Remote Point Problem, Small Bias Space, and Expanding Generator Sets
Venue: arXiv cs.CC 2010
Year: 2010

Using $ε$-bias spaces over $F_2$, we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace $F^n$ by $G^n$ for an arbitrary fixed group $G$. When $G$ is Abelian, we give an $NC^2$ algorithm for RPP, again using $ε$-bias spaces. For nonabelian $G$, we give a deterministic polynomial-time algorithm for RPP. We also show the connection to construction of expanding generator sets for the group $G^n$. All our algorithms for the RPP achieve essentially the same parameters as [APY09].
The averaging trick and the Cerny conjecture
Venue: arXiv cs.FL 2010
Year: 2010

The results of several papers concerning the Černý conjecture are deduced as consequences of a simple idea that I call the averaging trick. This idea is implicitly used in the literature, but no attempt was made to formalize the proof scheme axiomatically. Instead, authors axiomatized classes of automata to which it applies.
Use of L-system mathematics for making new subfamily members of olfactory receptor full length genes, OR1D2, OR1D4 and OR1D5
Venue: arXiv cs.OH 2010
Year: 2010

Ligands for only two human olfactory receptors are known. One of them, OR1D2, binds to Bourgeonal [Malnic B, Godfrey P-A, Buck L-B (2004) The human olfactory receptor gene family. Proc. Natl. Acad. Sci U. S. A. 101: 2584-2589 and Erratum in: Proc Natl Acad Sci U. S. A. (2004) 101: 7205]. OR1D2, OR1D4 and OR1D5 are three full length olfactory receptors present in an olfactory locus in human genome. These receptors are more than 80% identical in DNA sequences and have 108 base pair mismatches among them. We have used L-system mathematics and have been able to show a closely related subfamily of OR1D2, OR1D4 and OR1D5.
Engineering a Scalable High Quality Graph Partitioner
Venue: arXiv cs.DC 2010
Year: 2010

We describe an approach to parallel graph partitioning that scales to hundreds of processors and produces a high solution quality. For example, for many instances from Walshaw's benchmark collection we improve the best known partitioning. We use the well known framework of multi-level graph partitioning. All components are implemented by scalable parallel algorithms. Quality improvements compared to previous systems are due to better prioritization of edges to be contracted, better approximation algorithms for identifying matchings, better local search heuristics, and perhaps most notably, a parallelization of the FM local search algorithm that works more locally than previous approaches.
Self-optimized Coverage Coordination in Femtocell Networks
Venue: arXiv cs.NI 2010
Year: 2010

This paper proposes a self-optimized coverage coordination scheme for two-tier femtocell networks, in which a femtocell base station adjusts the transmit power based on the statistics of the signal and the interference power that is measured at a femtocell downlink. Furthermore, an analytic expression is derived for the coverage leakage probability that a femtocell coverage area leaks into an outdoor macrocell. The coverage analysis is verified by simulation, which shows that the proposed scheme provides sufficient indoor femtocell coverage and that the femtocell coverage does not leak into an outdoor macrocell.
Cooperative Interference Management with MISO Beamforming
Venue: arXiv cs.IT 2010
Year: 2010

This correspondence studies the downlink transmission in a multi-cell system, where multiple base stations (BSs) each with multiple antennas cooperatively design their respective transmit beamforming vectors to optimize the overall system performance. For simplicity, it is assumed that all mobile stations (MSs) are equipped with a single antenna each, and there is one active MS in each cell at one time. Accordingly, the system of interests can be modeled by a multiple-input single-output (MISO) interference channel (IC), termed as MISO-IC, with interference treated as noise. We propose a new method to characterize different rate-tuples for active MSs on the Pareto boundary of the achievable rate region for the MISO-IC, by exploring the relationship between the MISO-IC and the cognitive radio (CR) MISO channel. We show that each Pareto-boundary rate-tuple of the MISO-IC can be achieved in a decentralized manner when each of the BSs attains its own channel capacity subject to a certain set of interference-power constraints (also known as interference-temperature constraints in the CR system) at the other MS receivers. Furthermore, we show that this result leads to a new decentralized algorithm for implementing the multi-cell cooperative downlink beamforming.
A Game Theoretic Analysis of Incentives in Content Production and Sharing over Peer-to-Peer Networks
Venue: arXiv cs.NI 2010
Year: 2010

User-generated content can be distributed at a low cost using peer-to-peer (P2P) networks, but the free-rider problem hinders the utilization of P2P networks. In order to achieve an efficient use of P2P networks, we investigate fundamental issues on incentives in content production and sharing using game theory. We build a basic model to analyze non-cooperative outcomes without an incentive scheme and then use different game formulations derived from the basic model to examine five incentive schemes: cooperative, payment, repeated interaction, intervention, and enforced full sharing. The results of this paper show that 1) cooperative peers share all produced content while non-cooperative peers do not share at all without an incentive scheme; 2) a cooperative scheme allows peers to consume more content than non-cooperative outcomes do; 3) a cooperative outcome can be achieved among non-cooperative peers by introducing an incentive scheme based on payment, repeated interaction, or intervention; and 4) enforced full sharing has ambiguous welfare effects on peers. In addition to describing the solutions of different formulations, we discuss enforcement and informational requirements to implement each solution, aiming to offer a guideline for protocol designers when designing incentive schemes for P2P networks.
High Dimensional Error-Correcting Codes
Venue: arXiv cs.IT 2010
Year: 2010

In this paper we construct multidimensional codes with high dimension. The codes can correct high dimensional errors which have the form of either small clusters, or confined to an area with a small radius. We also consider small number of errors in a small area. The clusters which are discussed are mainly spheres such as semi-crosses and crosses. Also considered are clusters with small number of errors such as 2-bursts, two errors in various clusters, and three errors on a line. Our main focus is on the redundancy of the codes when the most dominant parameter is the dimension of the code.
Topological De-Noising: Strengthening the Topological Signal
Venue: arXiv cs.CG 2010
Year: 2010

Topological methods, including persistent homology, are powerful tools for analysis of high-dimensional data sets but these methods rely almost exclusively on thresholding techniques. In noisy data sets, thresholding does not always allow for the recovery of topological information. We present an easy to implement, computationally efficient pre-processing algorithm to prepare noisy point cloud data sets for topological data analysis. The topological de-noising algorithm allows for the recovery of topological information that is inaccessible by thresholding methods. We apply the algorithm to synthetically-generated noisy data sets and show the recovery of topological information which is impossible to obtain by thresholding. We also apply the algorithm to natural image data in R^8 and show a very clean recovery of topological information previously only available with large amounts of thresholding. Finally, we discuss future directions for improving this algorithm using zig-zag persistence methods.
Entropy sensitivity of languages defined by infinite automata, via Markov chains with forbidden transitions
Venue: arXiv cs.FL 2010
Year: 2010

A language L over a finite alphabet is growth-sensitive (or entropy sensitive) if forbidding any set of subwords F yields a sub-language L^F whose exponential growth rate (entropy) is smaller than that of L. Let (X, E, l) be an infinite, oriented, labelled graph. Considering the graph as an (infinite) automaton, we associate with any pair of vertices x,y in X the language consisting of all words that can be read as the labels along some path from x to y. Under suitable, general assumptions we prove that these languages are growth-sensitive. This is based on using Markov chains with forbidden transitions.
Research report : Collaborative Peer 2 Peer Edition: Avoiding Conflicts is Better than Solving Conflicts
Venue: arXiv cs.HC 2010
Year: 2010

Collaborative edition is achieved by distinct sites that work independently on (a copy of) a shared document. Conflicts may arise during this process and must be solved by the collaborative editor. In pure Peer to Peer collaborative editing, no centralization nor locks nor time-stamps are used which make conflict resolution difficult. We propose an algorithm which relies on the notion or semantics dependence and avoids the need of any integration transformation to solve conflicts. Furthermore, it doesn't use any history file recording operations performed since starting the edition process. We show how to define editing operations for semi-structured documents i.e. XML-like trees, that are enriched with informations derived for free from the editing process. Then we define the semantics dependence relation required by the algorithm and we present preliminary results obtained by a prototype implementation.
Vertical partitioning of relational OLTP databases using integer programming
Venue: arXiv cs.DB 2010
Year: 2010

A way to optimize performance of relational row store databases is to reduce the row widths by vertically partitioning tables into table fractions in order to minimize the number of irrelevant columns/attributes read by each transaction. This paper considers vertical partitioning algorithms for relational row-store OLTP databases with an H-store-like architecture, meaning that we would like to maximize the number of single-sited transactions. We present a model for the vertical partitioning problem that, given a schema together with a vertical partitioning and a workload, estimates the costs (bytes read/written by storage layer access methods and bytes transferred between sites) of evaluating the workload on the given partitioning. The cost model allows for arbitrarily prioritizing load balancing of sites vs. total cost minimization. We show that finding a minimum-cost vertical partitioning in this model is NP-hard and present two algorithms returning solutions in which single-sitedness of read queries is preserved while allowing column replication (which may allow a drastically reduced cost compared to disjoint partitioning). The first algorithm is a quadratic integer program that finds optimal minimum-cost solutions with respect to the model, and the second algorithm is a more scalable heuristic based on simulated annealing. Experiments show that the algorithms can reduce the cost of the model objective by 37% when applied to the TPC-C benchmark and the heuristic is shown to obtain solutions with cost close to the ones found using the quadratic program.
Functional units for natural numbers
Venue: arXiv cs.PL 2010
Year: 2010

Interaction with services provided by an execution environment forms part of the behaviours exhibited by instruction sequences under execution. Mechanisms related to the kind of interaction in question have been proposed in the setting of thread algebra. Like thread, service is an abstract behavioural concept. The concept of a functional unit is similar to the concept of a service, but more concrete. A state space is inherent in the concept of a functional unit, whereas it is not inherent in the concept of a service. In this paper, we establish the existence of a universal computable functional unit for natural numbers and related results.