OpenRaiser/Intern-Atlas huggingface dataset:
Bio-linguistic transition and Baldwin effect in an evolutionary naming-game model
Venue: arXiv cs.CL 2007
Year: 2007

We examine an evolutionary naming-game model where communicating agents are equipped with an evolutionarily selected learning ability. Such a coupling of biological and linguistic ingredients results in an abrupt transition: upon a small change of a model control parameter a poorly communicating group of linguistically unskilled agents transforms into almost perfectly communicating group with large learning abilities. When learning ability is kept fixed, the transition appears to be continuous. Genetic imprinting of the learning abilities proceeds via Baldwin effect: initially unskilled communicating agents learn a language and that creates a niche in which there is an evolutionary pressure for the increase of learning ability.Our model suggests that when linguistic (or cultural) processes became intensive enough, a transition took place where both linguistic performance and biological endowment of our species experienced an abrupt change that perhaps triggered the rapid expansion of human civilization.
A Probability Model for Lifetime of Wireless Sensor Networks
Venue: arXiv cs.NI 2007
Year: 2007

Considering a wireless sensor network whose nodes are distributed randomly over a given area, a probability model for the network lifetime is provided. Using this model and assuming that packet generation follows a Poisson distribution, an analytical expression for the complementary cumulative density function (ccdf) of the lifetime is obtained. Using this ccdf, one can accurately find the probability that the network achieves a given lifetime. It is also shown that when the number of sensors, $N$, is large, with an error exponentially decaying with $N$, one can predict whether or not a certain lifetime can be achieved. The results of this work are obtained for both multi-hop and single-hop wireless sensor networks and are verified with computer simulation. The approaches of this paper are shown to be applicable to other packet generation models and the effect of the area shape is also investigated.
Distributed MIMO receiver - Achievable rates and upper bounds
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we investigate the achievable rate of a system that includes a nomadic transmitter with several antennas, which is received by multiple agents, exhibiting independent channel gains and additive circular-symmetric complex Gaussian noise. In the nomadic regime, we assume that the agents do not have any decoding ability. These agents process their channel observations and forward them to the final destination through lossless links with a fixed capacity. We propose new achievable rates based on elementary compression and also on a Wyner-Ziv (CEO-like) processing, for both fast fading and block fading channels, as well as for general discrete channels. The simpler two agents scheme is solved, up to an implicit equation with a single variable. Limiting the nomadic transmitter to a circular-symmetric complex Gaussian signalling, new upper bounds are derived for both fast and block fading, based on the vector version of the entropy power inequality. These bounds are then compared to the achievable rates in several extreme scenarios. The asymptotic setting with numbers of agents and transmitter's antennas taken to infinity is analyzed. In addition, the upper bounds are analytically shown to be tight in several examples, while numerical calculations reveal a rather small gap in a finite $2\times2$ setting. The advantage of the Wyner-Ziv approach over elementary compression is shown where only the former can achieve the full diversity-multiplexing tradeoff. We also consider the non-nomadic setting, with agents that can decode. Here we give an achievable rate, over fast fading channel, which combines broadcast with dirty paper coding and the decentralized reception, which was introduced for the nomadic setting.
Binary quantization using Belief Propagation with decimation over factor graphs of LDGM codes
Venue: arXiv cs.IT 2007
Year: 2007

We propose a new algorithm for binary quantization based on the Belief Propagation algorithm with decimation over factor graphs of Low Density Generator Matrix (LDGM) codes. This algorithm, which we call Bias Propagation (BiP), can be considered as a special case of the Survey Propagation algorithm proposed for binary quantization by Wainwright et al. [8]. It achieves the same near-optimal rate-distortion performance with a substantially simpler framework and 10-100 times faster implementation. We thus challenge the widespread belief that binary quantization based on sparse linear codes cannot be solved by simple Belief Propagation algorithms. Finally, we give examples of suitably irregular LDGM codes that work with the BiP algorithm and show their performance.
Z4-Linear Perfect Codes
Venue: arXiv cs.IT 2007
Year: 2007

For every $n = 2^k > 8$ there exist exactly $[(k+1)/2]$ mutually nonequivalent $Z_4$-linear extended perfect codes with distance 4. All these codes have different ranks.
An Analytical Study of a Structured Overlay in the presence of Dynamic Membership
Venue: arXiv cs.NI 2007
Year: 2007

In this paper we present an analytical study of dynamic membership (aka churn) in structured peer-to-peer networks. We use a fluid model approach to describe steady-state or transient phenomena, and apply it to the Chord system. For any rate of churn and stabilization rates, and any system size, we accurately account for the functional form of the probability of network disconnection as well as the fraction of failed or incorrect successor and finger pointers. We show how we can use these quantities to predict both the performance and consistency of lookups under churn. All theoretical predictions match simulation results. The analysis includes both features that are generic to structured overlays deploying a ring as well as Chord-specific details, and opens the door to a systematic comparative analysis of, at least, ring-based structured overlay systems under churn.
A Novel Solution to the ATT48 Benchmark Problem
Venue: arXiv cs.DS 2007
Year: 2007

A solution to the benchmark ATT48 Traveling Salesman Problem (from the TSPLIB95 library) results from isolating the set of vertices into ten open-ended zones with nine lengthwise boundaries. In each zone, a minimum-length Hamiltonian Path (HP) is found for each combination of boundary vertices, leading to an approximation for the minimum-length Hamiltonian Cycle (HC). Determination of the optimal HPs for subsequent zones has the effect of automatically filtering out non-optimal HPs from earlier zones. Although the optimal HC for ATT48 involves only two crossing edges between all zones (with one exception), adding inter-zone edges can accommodate more complex problems.
A Fast Heuristic Algorithm Based on Verification and Elimination Methods for Maximum Clique Problem
Venue: arXiv cs.DM 2007
Year: 2007

A clique in an undirected graph G= (V, E) is a subset V' V of vertices, each pair of which is connected by an edge in E. The clique problem is an optimization problem of finding a clique of maximum size in graph. The clique problem is NP-Complete. We have succeeded in developing a fast algorithm for maximum clique problem by employing the method of verification and elimination. For a graph of size N there are 2N sub graphs, which may be cliques and hence verifying all of them, will take a long time. Idea is to eliminate a major number of sub graphs, which cannot be cliques and verifying only the remaining sub graphs. This heuristic algorithm runs in polynomial time and executes successfully for several examples when applied to random graphs and DIMACS benchmark graphs.
Multichannel algorithm based on generalized positional numeration system
Venue: arXiv cs.IT 2007
Year: 2007

This report is devoted to introduction in multichannel algorithm based on generalized numeration notations (GPN). The internal, external and mixed account are entered. The concept of the GPN and its classification as decomposition of an integer on composed of integers is discussed. Realization of multichannel algorithm on the basis of GPN is introduced. In particular, some properties of Fibonacci multichannel algorithm are discussed.
A Group Theoretic Model for Information
Venue: arXiv cs.IT 2007
Year: 2007

In this paper we formalize the notions of information elements and information lattices, first proposed by Shannon. Exploiting this formalization, we identify a comprehensive parallelism between information lattices and subgroup lattices. Qualitatively, we demonstrate isomorphisms between information lattices and subgroup lattices. Quantitatively, we establish a decisive approximation relation between the entropy structures of information lattices and the log-index structures of the corresponding subgroup lattices. This approximation extends the approximation for joint entropies carried out previously by Chan and Yeung. As a consequence of our approximation result, we show that any continuous law holds in general for the entropies of information elements if and only if the same law holds in general for the log-indices of subgroups. As an application, by constructing subgroup counterexamples we find surprisingly that common information, unlike joint information, obeys neither the submodularity nor the supermodularity law. We emphasize that the notion of information elements is conceptually significant--formalizing it helps to reveal the deep connection between information theory and group theory. The parallelism established in this paper admits an appealing group-action explanation and provides useful insights into the intrinsic structure among information elements from a group-theoretic perspective.
The MIMOME Channel
Venue: arXiv cs.IT 2007
Year: 2007

The MIMOME channel is a Gaussian wiretap channel in which the sender, receiver, and eavesdropper all have multiple antennas. We characterize the secrecy capacity as the saddle-value of a minimax problem. Among other implications, our result establishes that a Gaussian distribution maximizes the secrecy capacity characterization of Csisz{á}r and K{ö}rner when applied to the MIMOME channel. We also determine a necessary and sufficient condition for the secrecy capacity to be zero. Large antenna array analysis of this condition reveals several useful insights into the conditions under which secure communication is possible.
Fast Reliability-based Algorithm of Finding Minimum-weight Codewords for LDPC Codes
Venue: arXiv cs.IT 2007
Year: 2007

Despite the NP hardness of acquiring minimum distance $d_m$ for linear codes theoretically, in this paper we propose one experimental method of finding minimum-weight codewords, the weight of which is equal to $d_m$ for LDPC codes. One existing syndrome decoding method, called serial belief propagation (BP) with ordered statistic decoding (OSD), is adapted to serve our purpose. We hold the conjecture that among many candidate error patterns in OSD reprocessing, modulo 2 addition of the lightest error pattern with one of the left error patterns may generate a light codeword. When the decoding syndrome changes to all-zero state, the lightest error pattern reduces to all-zero, the lightest non-zero error pattern is a valid codeword to update lightest codeword list. Given sufficient codewords sending, the survived lightest codewords are likely to be the target. Compared with existing techniques, our method demonstrates its efficiency in the simulation of several interested LDPC codes.
Throughput Scaling in Random Wireless Networks: A Non-Hierarchical Multipath Routing Strategy
Venue: arXiv cs.IT 2007
Year: 2007

Franceschetti et al. have recently shown that per-node throughput in an extended, ad hoc wireless network with $Θ(n)$ randomly distributed nodes and multihop routing can be increased from the $Ω({1 \over \sqrt{n} \log n})$ scaling demonstrated in the seminal paper of Gupta and Kumar to $Ω({1 \over \sqrt{n}})$. The goal of the present paper is to understand the dependence of this interesting result on the principal new features it introduced relative to Gupta-Kumar: (1) a capacity-based formula for link transmission bit-rates in terms of received signal-to-interference-and-noise ratio (SINR); (2) hierarchical routing from sources to destinations through a system of communal highways; and (3) cell-based routes constructed by percolation. The conclusion of the present paper is that the improved throughput scaling is principally due to the percolation-based routing, which enables shorter hops and, consequently, less interference. This is established by showing that throughput $Ω({1 \over \sqrt{n}})$ can be attained by a system that does not employ highways, but instead uses percolation to establish, for each source-destination pair, a set of $Θ(\log n)$ routes within a narrow routing corridor running from source to destination. As a result, highways are not essential. In addition, it is shown that throughput $Ω({1 \over \sqrt{n}})$ can be attained with the original threshold transmission bit-rate model, provided that node transmission powers are permitted to grow with $n$. Thus, the benefit of the capacity bit-rate model is simply to permit the power to remain bounded, even as the network expands.
A polynomial bound for untangling geometric planar graphs
Venue: arXiv cs.CG 2007
Year: 2007

To untangle a geometric graph means to move some of the vertices so that the resulting geometric graph has no crossings. Pach and Tardos [Discrete Comput. Geom., 2002] asked if every n-vertex geometric planar graph can be untangled while keeping at least n^εvertices fixed. We answer this question in the affirmative with ε=1/4. The previous best known bound was Ω((\log n / \log\log n)^{1/2}). We also consider untangling geometric trees. It is known that every n-vertex geometric tree can be untangled while keeping at least (n/3)^{1/2} vertices fixed, while the best upper bound was O(n\log n)^{2/3}. We answer a question of Spillner and Wolff [arXiv:0709.0170 2007] by closing this gap for untangling trees. In particular, we show that for infinitely many values of n, there is an n-vertex geometric tree that cannot be untangled while keeping more than 3(n^{1/2}-1) vertices fixed. Moreover, we improve the lower bound to (n/2)^{1/2}.
Cross-Participants : fostering design-use mediation in an Open Source Software community
Venue: arXiv cs.CY 2007
Year: 2007

Motivation - This research aims at investigating emerging roles and forms of participation fostering design-use mediation during the Open Source Software design process Research approach - We compare online interactions for a successful "pushed-by-users" design process with unsuccessful previous proposals. The methodology developed, articulate structural analyses of the discussions (organization of discussions, participation) to actions to the code and documentation made by participants to the project. We focus on the useroriented and the developer-oriented mailing-lists of the Python project. Findings/Design - We find that key-participants, the cross-participants, foster the design process and act as boundary spanners between the users and the developers' communities. Research limitations/Implications - These findings can be reinforced developing software to automate the structural analysis of discussions and actions to the code and documentation. Further analyses, supported by these tools, will be necessary to generalise our results. Originality/Value - The analysis of participation among the three interaction spaces of OSS design (discussion, documentation and implementation) is the main originality of this work compared to other OSS research that mainly analyse one or two spaces. Take away message - Beside the idealistic picture that users may intervene freely in the process, OSS design is boost and framed by some key-participants and specific rules and there can be barriers to users' participation
Distributed Source Coding Using Continuous-Valued Syndromes
Venue: arXiv cs.IT 2007
Year: 2007

This paper addresses the problem of coding a continuous random source correlated with another source which is only available at the decoder. The proposed approach is based on the extension of the channel coding concept of syndrome from the discrete into the continuous domain. If the correlation between the sources can be described by an additive Gaussian backward channel and capacity-achieving linear codes are employed, it is shown that the performance of the system is asymptotically close to the Wyner-Ziv bound. Even if such an additive channel is not Gaussian, the design procedure can fit the desired correlation and transmission rate. Experiments based on trellis-coded quantization show that the proposed system achieves a performance within 3-4 dB of the theoretical bound in the 0.5-3 bit/sample rate range for any Gaussian correlation, with a reasonable computational complexity.
An Affinity Propagation Based method for Vector Quantization Codebook Design
Venue: arXiv cs.CV 2007
Year: 2007

In this paper, we firstly modify a parameter in affinity propagation (AP) to improve its convergence ability, and then, we apply it to vector quantization (VQ) codebook design problem. In order to improve the quality of the resulted codebook, we combine the improved AP (IAP) with the conventional LBG algorithm to generate an effective algorithm call IAP-LBG. According to the experimental results, the proposed method not only enhances the convergence abilities but also is capable of providing higher-quality codebooks than conventional LBG method.
Generic Trace Semantics via Coinduction
Venue: arXiv cs.LO 2007
Year: 2007

Trace semantics has been defined for various kinds of state-based systems, notably with different forms of branching such as non-determinism vs. probability. In this paper we claim to identify one underlying mathematical structure behind these "trace semantics," namely coinduction in a Kleisli category. This claim is based on our technical result that, under a suitably order-enriched setting, a final coalgebra in a Kleisli category is given by an initial algebra in the category Sets. Formerly the theory of coalgebras has been employed mostly in Sets where coinduction yields a finer process semantics of bisimilarity. Therefore this paper extends the application field of coalgebras, providing a new instance of the principle "process semantics via coinduction."
Efficient Skyline Querying with Variable User Preferences on Nominal Attributes
Venue: arXiv cs.DB 2007
Year: 2007

Current skyline evaluation techniques assume a fixed ordering on the attributes. However, dynamic preferences on nominal attributes are more realistic in known applications. In order to generate online response for any such preference issued by a user, we propose two methods of different characteristics. The first one is a semi-materialization method and the second is an adaptive SFS method. Finally, we conduct experiments to show the efficiency of our proposed algorithms.
Fingerprinting with Minimum Distance Decoding
Venue: arXiv cs.IT 2007
Year: 2007

This work adopts an information theoretic framework for the design of collusion-resistant coding/decoding schemes for digital fingerprinting. More specifically, the minimum distance decision rule is used to identify 1 out of t pirates. Achievable rates, under this detection rule, are characterized in two distinct scenarios. First, we consider the averaging attack where a random coding argument is used to show that the rate 1/2 is achievable with t=2 pirates. Our study is then extended to the general case of arbitrary $t$ highlighting the underlying complexity-performance tradeoff. Overall, these results establish the significant performance gains offered by minimum distance decoding as compared to other approaches based on orthogonal codes and correlation detectors. In the second scenario, we characterize the achievable rates, with minimum distance decoding, under any collusion attack that satisfies the marking assumption. For t=2 pirates, we show that the rate $1-H(0.25)\approx 0.188$ is achievable using an ensemble of random linear codes. For $t\geq 3$, the existence of a non-resolvable collusion attack, with minimum distance decoding, for any non-zero rate is established. Inspired by our theoretical analysis, we then construct coding/decoding schemes for fingerprinting based on the celebrated Belief-Propagation framework. Using an explicit repeat-accumulate code, we obtain a vanishingly small probability of misidentification at rate 1/3 under averaging attack with t=2. For collusion attacks which satisfy the marking assumption, we use a more sophisticated accumulate repeat accumulate code to obtain a vanishingly small misidentification probability at rate 1/9 with t=2. These results represent a marked improvement over the best available designs in the literature.
Effective linkage learning using low-order statistics and clustering
Venue: arXiv cs.NE 2007
Year: 2007

The adoption of probabilistic models for the best individuals found so far is a powerful approach for evolutionary computation. Increasingly more complex models have been used by estimation of distribution algorithms (EDAs), which often result better effectiveness on finding the global optima for hard optimization problems. Supervised and unsupervised learning of Bayesian networks are very effective options, since those models are able to capture interactions of high order among the variables of a problem. Diversity preservation, through niching techniques, has also shown to be very important to allow the identification of the problem structure as much as for keeping several global optima. Recently, clustering was evaluated as an effective niching technique for EDAs, but the performance of simpler low-order EDAs was not shown to be much improved by clustering, except for some simple multimodal problems. This work proposes and evaluates a combination operator guided by a measure from information theory which allows a clustered low-order EDA to effectively solve a comprehensive range of benchmark optimization problems.
Nontraditional Scoring of C-tests
Venue: arXiv cs.CY 2007
Year: 2007

In C-tests the hypothesis of items local independence is violated, which doesn't permit to consider them as real tests. It is suggested to determine the distances between separate C-test items (blanks) and to combine items into clusters. Weights, inversely proportional to the number of items in corresponding clusters, are assigned to items. As a result, the C-test structure becomes similar to the structure of classical tests, without violation of local independence hypothesis.
Utility-Based Wireless Resource Allocation for Variable Rate Transmission
Venue: arXiv cs.NI 2007
Year: 2007

For most wireless services with variable rate transmission, both average rate and rate oscillation are important performance metrics. The traditional performance criterion, utility of average transmission rate, boosts the average rate but also results in high rate oscillations. We introduce a utility function of instantaneous transmission rates. It is capable of facilitating the resource allocation with flexible combinations of average rate and rate oscillation. Based on the new utility, we consider the time and power allocation in a time-shared wireless network. Two adaptation policies are developed, namely, time sharing (TS) and joint time sharing and power control (JTPC). An extension to quantized time sharing with limited channel feedback (QTSL) for practical systems is also discussed. Simulation results show that by controlling the concavity of the utility function, a tradeoff between the average rate and rate oscillation can be easily made.