OpenRaiser/Intern-Atlas huggingface dataset:
Declarative Combinatorics: Isomorphisms, Hylomorphisms and Hereditarily Finite Data Types in Haskell
Venue: arXiv cs.PL 2009
Year: 2009

This paper is an exploration in a functional programming framework of {\em isomorphisms} between elementary data types (natural numbers, sets, multisets, finite functions, permutations binary decision diagrams, graphs, hypergraphs, parenthesis languages, dyadic rationals, primes, DNA sequences etc.) and their extension to hereditarily finite universes through {\em hylomorphisms} derived from {\em ranking/unranking} and {\em pairing/unpairing} operations. An embedded higher order {\em combinator language} provides any-to-any encodings automatically. Besides applications to experimental mathematics, a few examples of ``free algorithms'' obtained by transferring operations between data types are shown. Other applications range from stream iterators on combinatorial objects to self-delimiting codes, succinct data representations and generation of random instances. The paper covers 59 data types and, through the use of the embedded combinator language, provides 3540 distinct bijective transformations between them. The self-contained source code of the paper, as generated from a literate Haskell program, is available at \url{http://logic.csci.unt.edu/tarau/research/2008/fISO.zip}. {\bf Keywords}: Haskell data representations, data type isomorphisms, declarative combinatorics, computational mathematics, Ackermann encoding, Gödel numberings, arithmetization, ranking/unranking, hereditarily finite sets, functions and permutations, encodings of binary decision diagrams, dyadic rationals, DNA encodings
Constructing word similarities in Meroitic as an aid to decipherment
Venue: arXiv cs.CL 2009
Year: 2009

Meroitic is the still undeciphered language of the ancient civilization of Kush. Over the years, various techniques for decipherment such as finding a bilingual text or cognates from modern or other ancient languages in the Sudan and surrounding areas has not been successful. Using techniques borrowed from information theory and natural language statistics, similar words are paired and attempts are made to use currently defined words to extract at least partial meaning from unknown words.
A Max-Flow Min-Cut Theorem with Applications in Small Worlds and Dual Radio Networks
Venue: arXiv cs.IT 2009
Year: 2009

Intrigued by the capacity of random networks, we start by proving a max-flow min-cut theorem that is applicable to any random graph obeying a suitably defined independence-in-cut property. We then show that this property is satisfied by relevant classes, including small world topologies, which are pervasive in both man-made and natural networks, and wireless networks of dual devices, which exploit multiple radio interfaces to enhance the connectivity of the network. In both cases, we are able to apply our theorem and derive max-flow min-cut bounds for network information flow.
Fast C-K-R Partitions of Sparse Graphs
Venue: arXiv cs.DS 2009
Year: 2009

We present fast algorithms for constructing probabilistic embeddings and approximate distance oracles in sparse graphs. The main ingredient is a fast algorithm for sampling the probabilistic partitions of Calinescu, Karloff, and Rabani in sparse graphs.
Investigation on Multiuser Diversity in Spectrum Sharing Based Cognitive Radio Networks
Venue: arXiv cs.IT 2009
Year: 2009

A new form of multiuser diversity, named \emph{multiuser interference diversity}, is investigated for opportunistic communications in cognitive radio (CR) networks by exploiting the mutual interference between the CR and the existing primary radio (PR) links. The multiuser diversity gain and ergodic throughput are analyzed for different types of CR networks and compared against those in the conventional networks without the PR link.
High-Rate Space-Time Coded Large MIMO Systems: Low-Complexity Detection and Channel Estimation
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we present a low-complexity algorithm for detection in high-rate, non-orthogonal space-time block coded (STBC) large-MIMO systems that achieve high spectral efficiencies of the order of tens of bps/Hz. We also present a training-based iterative detection/channel estimation scheme for such large STBC MIMO systems. Our simulation results show that excellent bit error rate and nearness-to-capacity performance are achieved by the proposed multistage likelihood ascent search (M-LAS) detector in conjunction with the proposed iterative detection/channel estimation scheme at low complexities. The fact that we could show such good results for large STBCs like 16x16 and 32x32 STBCs from Cyclic Division Algebras (CDA) operating at spectral efficiencies in excess of 20 bps/Hz (even after accounting for the overheads meant for pilot based training for channel estimation and turbo coding) establishes the effectiveness of the proposed detector and channel estimator. We decode perfect codes of large dimensions using the proposed detector. With the feasibility of such a low-complexity detection/channel estimation scheme, large-MIMO systems with tens of antennas operating at several tens of bps/Hz spectral efficiencies can become practical, enabling interesting high data rate wireless applications.
A Distributed Algorithm for Fair and Efficient User-Network Association in Multi-Technology Wireless Networks
Venue: arXiv cs.GT 2009
Year: 2009

Recent mobile equipment (as well as the norm IEEE 802.21) now offers the possibility for users to switch from one technology to another (vertical handover). This allows flexibility in resource assignments and, consequently, increases the potential throughput allocated to each user. In this paper, we design a fully distributed algorithm based on trial and error mechanisms that exploits the benefits of vertical handover by finding fair and efficient assignment schemes. On the one hand, mobiles gradually update the fraction of data packets they send to each network based on the rewards they receive from the stations. On the other hand, network stations send rewards to each mobile that represent the impact each mobile has on the cell throughput. This reward function is closely related to the concept of marginal cost in the pricing literature. Both the station and the mobile algorithms are simple enough to be implemented in current standard equipment. Based on tools from evolutionary games, potential games and replicator dynamics, we analytically show the convergence of the algorithm to solutions that are efficient and fair in terms of throughput. Moreover, we show that after convergence, each user is connected to a single network cell which avoids costly repeated vertical handovers. Several simple heuristics based on this algorithm are proposed to achieve fast convergence. Indeed, for implementation purposes, the number of iterations should remain in the order of a few tens. We also compare, for different loads, the quality of their solutions.
Characterizing graphs with convex and connected configuration spaces
Venue: arXiv cs.CG 2009
Year: 2009

We define and study exact, efficient representations of realization spaces Euclidean Distance Constraint Systems (EDCS), which includes Linkages and Frameworks. Each representation corresponds to a choice of Cayley parameters and yields a different parametrized configuration space. Significantly, we give purely graph-theoretic, forbidden minor characterizations that capture (i) the class of graphs that always admit efficient configuration spaces and (ii) the possible choices of representation parameters that yield efficient configuration spaces for a given graph. In addition, our results are tight: we show counterexamples to obvious extensions. This is the first step in a systematic and graded program of combinatorial characterizations of efficient configuration spaces. We discuss several future theoretical and applied research directions. Some of our proofs employ an unusual interplay of (a) classical analytic results related to positive semi-definiteness of Euclidean distance matrices, with (b) recent forbidden minor characterizations and algorithms related to the notion of d-realizability of EDCS. We further introduce a novel type of restricted edge contraction or reduction to a graph minor, a "trick" that we anticipate will be useful in other situations.
Mining Meaning from Wikipedia
Venue: arXiv cs.AI 2009
Year: 2009

Wikipedia is a goldmine of information; not just for its many readers, but also for the growing community of researchers who recognize it as a resource of exceptional scale and utility. It represents a vast investment of manual effort and judgment: a huge, constantly evolving tapestry of concepts and relations that is being applied to a host of tasks. This article provides a comprehensive description of this work. It focuses on research that extracts and makes use of the concepts, relations, facts and descriptions found in Wikipedia, and organizes the work into four broad categories: applying Wikipedia to natural language processing; using it to facilitate information retrieval and information extraction; and as a resource for ontology building. The article addresses how Wikipedia is being used as is, how it is being improved and adapted, and how it is being combined with other structures to create entirely new resources. We identify the research groups and individuals involved, and how their work has developed in the last few years. We provide a comprehensive list of the open-source software they have produced.
On Pure and (approximate) Strong Equilibria of Facility Location Games
Venue: arXiv cs.GT 2009
Year: 2009

We study social cost losses in Facility Location games, where $n$ selfish agents install facilities over a network and connect to them, so as to forward their local demand (expressed by a non-negative weight per agent). Agents using the same facility share fairly its installation cost, but every agent pays individually a (weighted) connection cost to the chosen location. We study the Price of Stability (PoS) of pure Nash equilibria and the Price of Anarchy of strong equilibria (SPoA), that generalize pure equilibria by being resilient to coalitional deviations. A special case of recently studied network design games, Facility Location merits separate study as a classic model with numerous applications and individual characteristics: our analysis for unweighted agents on metric networks reveals constant upper and lower bounds for the PoS, while an $O(\ln n)$ upper bound implied by previous work is tight for non-metric networks. Strong equilibria do not always exist, even for the unweighted metric case. We show that $e$-approximate strong equilibria exist ($e=2.718...$). The SPoA is generally upper bounded by $O(\ln W)$ ($W$ is the sum of agents' weights), which becomes tight $Θ(\ln n)$ for unweighted agents. For the unweighted metric case we prove a constant upper bound. We point out several challenging open questions that arise.
A Distributed MAC Protocol for Cooperation in Random Access Networks
Venue: arXiv cs.IT 2009
Year: 2009

WLAN is one of the most successful applications of wireless communications in daily life because of low cost and ease of deployment. The enabling technique for this success is the use of random access schemes for the wireless channel. Random access requires minimal coordination between the nodes, which considerably reduces the cost of the infrastructure. Recently, cooperative communication in wireless networks has been of increasing interest because it promises higher rates and reliability. An additional MAC overhead is necessary to coordinate the nodes to allow cooperation and this overhead can possibly cancel out the cooperative benefits. In this work, a completely distributed protocol is proposed that allows nodes in the network to cooperate via Two-Hop and Decode-and-Forward for transmitting their data to a common gateway node. It is shown that high throughput gains are obtained in terms of the individual throughput that can be guaranteed to any node in the network. These results are validated by Monte Carlo simulations.
Stackelberg Contention Games in Multiuser Networks
Venue: arXiv cs.GT 2009
Year: 2009

Interactions among selfish users sharing a common transmission channel can be modeled as a non-cooperative game using the game theory framework. When selfish users choose their transmission probabilities independently without any coordination mechanism, Nash equilibria usually result in a network collapse. We propose a methodology that transforms the non-cooperative game into a Stackelberg game. Stackelberg equilibria of the Stackelberg game can overcome the deficiency of the Nash equilibria of the original game. A particular type of Stackelberg intervention is constructed to show that any positive payoff profile feasible with independent transmission probabilities can be achieved as a Stackelberg equilibrium payoff profile. We discuss criteria to select an operating point of the network and informational requirements for the Stackelberg game. We relax the requirements and examine the effects of relaxation on performance.
Two Remarkable Computational Competencies of the Simple Genetic Algorithm
Venue: arXiv cs.NE 2009
Year: 2009

Since the inception of genetic algorithmics the identification of computational efficiencies of the simple genetic algorithm (SGA) has been an important goal. In this paper we distinguish between a computational competency of the SGA--an efficient, but narrow computational ability--and a computational proficiency of the SGA--a computational ability that is both efficient and broad. Till date, attempts to deduce a computational proficiency of the SGA have been unsuccessful. It may, however, be possible to inductively infer a computational proficiency of the SGA from a set of related computational competencies that have been deduced. With this in mind we deduce two computational competencies of the SGA. These competencies, when considered together, point toward a remarkable computational proficiency of the SGA. This proficiency is pertinent to a general problem that is closely related to a well-known statistical problem at the cutting edge of computational genetics.
Learning Isometric Separation Maps
Venue: arXiv cs.LG 2009
Year: 2009

Maximum Variance Unfolding (MVU) and its variants have been very successful in embedding data-manifolds in lower dimensional spaces, often revealing the true intrinsic dimension. In this paper we show how to also incorporate supervised class information into an MVU-like method without breaking its convexity. We call this method the Isometric Separation Map and we show that the resulting kernel matrix can be used as a binary/multiclass Support Vector Machine-like method in a semi-supervised (transductive) framework. We also show that the method always finds a kernel matrix that linearly separates the training data exactly without projecting them in infinite dimensional spaces. In traditional SVMs we choose a kernel and hope that the data become linearly separable in the kernel space. In this paper we show how the hyperplane can be chosen ad-hoc and the kernel is trained so that data are always linearly separable. Comparisons with Large Margin SVMs show comparable performance.
Resource Allocation for Downlink Cellular OFDMA Systems: Part I - Optimal Allocation
Venue: arXiv cs.IT 2009
Year: 2009

In this pair of papers (Part I and Part II in this issue), we investigate the issue of power control and subcarrier assignment in a sectorized two-cell downlink OFDMA system impaired by multicell interference. As recommended for WiMAX, we assume that the first part of the available bandwidth is likely to be reused by different base stations (and is thus subject to multicell interference) and that the second part of the bandwidth is shared in an orthogonal way between the different base stations (and is thus protected from multicell interference). Although the problem of multicell resource allocation is nonconvex in this scenario, we provide in Part I the general form of the global solution. In particular, the optimal resource allocation turns out to be "binary" in the sense that, except for at most one pivot-user in each cell, any user receives data either in the reused bandwidth or in the protected bandwidth, but not in both. The determination of the optimal resource allocation essentially reduces to the determination of the latter pivot-position.
Cross-Layer Link Adaptation Design for Relay Channels with Cooperative ARQ Protocol
Venue: arXiv cs.IT 2009
Year: 2009

The cooperative automatic repeat request (C-ARQ) is a link layer relaying protocol which exploits the spatial diversity and allows the relay node to retransmit the source data packet to the destination, when the latter is unable to decode the source data correctly. This paper presents a cross-layer link adaptation design for C-ARQ based relay channels in which both source and relay nodes employ adaptive modulation coding and power adaptation at the physical layer. For this scenario, we first derive closed-form expressions for the system spectral efficiency and average power consumption. We then present a low complexity iterative algorithm to find the optimized adaptation solution by maximizing the spectral efficiency subject to a packet loss rate (PLR) and an average power consumption constraint. The results indicate that the proposed adaptation scheme enhances the spectral efficiency noticeably when compared to other adaptive schemes, while guaranteeing the required PLR performance.
Approximation Algorithms for Bregman Co-clustering and Tensor Clustering
Venue: arXiv cs.DS 2009
Year: 2009

In the past few years powerful generalizations to the Euclidean k-means problem have been made, such as Bregman clustering [7], co-clustering (i.e., simultaneous clustering of rows and columns of an input matrix) [9,18], and tensor clustering [8,34]. Like k-means, these more general problems also suffer from the NP-hardness of the associated optimization. Researchers have developed approximation algorithms of varying degrees of sophistication for k-means, k-medians, and more recently also for Bregman clustering [2]. However, there seem to be no approximation algorithms for Bregman co- and tensor clustering. In this paper we derive the first (to our knowledge) guaranteed methods for these increasingly important clustering settings. Going beyond Bregman divergences, we also prove an approximation factor for tensor clustering with arbitrary separable metrics. Through extensive experiments we evaluate the characteristics of our method, and show that it also has practical impact.
A Novel Clustering Algorithm Based on Quantum Games
Venue: arXiv cs.LG 2009
Year: 2009

Enormous successes have been made by quantum algorithms during the last decade. In this paper, we combine the quantum game with the problem of data clustering, and then develop a quantum-game-based clustering algorithm, in which data points in a dataset are considered as players who can make decisions and implement quantum strategies in quantum games. After each round of a quantum game, each player's expected payoff is calculated. Later, he uses a link-removing-and-rewiring (LRR) function to change his neighbors and adjust the strength of links connecting to them in order to maximize his payoff. Further, algorithms are discussed and analyzed in two cases of strategies, two payoff matrixes and two LRR functions. Consequently, the simulation results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the clustering algorithms have fast rates of convergence. Moreover, the comparison with other algorithms also provides an indication of the effectiveness of the proposed approach.
Secrecy capacity of a class of orthogonal relay eavesdropper channels
Venue: arXiv cs.IT 2009
Year: 2009

The secrecy capacity of relay channels with orthogonal components is studied in the presence of an additional passive eavesdropper node. The relay and destination receive signals from the source on two orthogonal channels such that the destination also receives transmissions from the relay on its channel. The eavesdropper can overhear either one or both of the orthogonal channels. Inner and outer bounds on the secrecy capacity are developed for both the discrete memoryless and the Gaussian channel models. For the discrete memoryless case, the secrecy capacity is shown to be achieved by a partial decode-and-forward (PDF) scheme when the eavesdropper can overhear only one of the two orthogonal channels. Two new outer bounds are presented for the Gaussian model using recent capacity results for a Gaussian multi-antenna point-to-point channel with a multi-antenna eavesdropper. The outer bounds are shown to be tight for two sub-classes of channels. The first sub-class is one in which the source and relay are clustered and the and the eavesdropper receives signals only on the channel from the source and the relay to the destination, for which the PDF strategy is optimal. The second is a sub-class in which the source does not transmit to the relay, for which a noise-forwarding strategy is optimal.
An identification problem in an urn and ball model with heavy tailed distributions
Venue: arXiv cs.NI 2009
Year: 2009

We consider in this paper an urn and ball problem with replacement, where balls are with different colors and are drawn uniformly from a unique urn. The numbers of balls with a given color are i.i.d. random variables with a heavy tailed probability distribution, for instance a Pareto or a Weibull distribution. We draw a small fraction $p\ll 1$ of the total number of balls. The basic problem addressed in this paper is to know to which extent we can infer the total number of colors and the distribution of the number of balls with a given color. By means of Le Cam's inequality and Chen-Stein method, bounds for the total variation norm between the distribution of the number of balls drawn with a given color and the Poisson distribution with the same mean are obtained. We then show that the distribution of the number of balls drawn with a given color has the same tail as that of the original number of balls. We finally establish explicit bounds between the two distributions when each ball is drawn with fixed probability $p$.
Succinct Greedy Geometric Routing in the Euclidean Plane
Venue: arXiv cs.CG 2009
Year: 2009

In greedy geometric routing, messages are passed in a network embedded in a metric space according to the greedy strategy of always forwarding messages to nodes that are closer to the destination. We show that greedy geometric routing schemes exist for the Euclidean metric in R^2, for 3-connected planar graphs, with coordinates that can be represented succinctly, that is, with O(log n) bits, where n is the number of vertices in the graph. Moreover, our embedding strategy introduces a coordinate system for R^2 that supports distance comparisons using our succinct coordinates. Thus, our scheme can be used to significantly reduce bandwidth, space, and header size over other recently discovered greedy geometric routing implementations for R^2.
Information Inequalities for Joint Distributions, with Interpretations and Applications
Venue: arXiv cs.IT 2009
Year: 2009

Upper and lower bounds are obtained for the joint entropy of a collection of random variables in terms of an arbitrary collection of subset joint entropies. These inequalities generalize Shannon's chain rule for entropy as well as inequalities of Han, Fujishige and Shearer. A duality between the upper and lower bounds for joint entropy is developed. All of these results are shown to be special cases of general, new results for submodular functions-- thus, the inequalities presented constitute a richly structured class of Shannon-type inequalities. The new inequalities are applied to obtain new results in combinatorics, such as bounds on the number of independent sets in an arbitrary graph and the number of zero-error source-channel codes, as well as new determinantal inequalities in matrix theory. A new inequality for relative entropies is also developed, along with interpretations in terms of hypothesis testing. Finally, revealing connections of the results to literature in economics, computer science, and physics are explored.