OpenRaiser/Intern-Atlas huggingface dataset:
Negative Beta Encoder
Venue: arXiv cs.IT 2009
Year: 2009

A new class of analog-to-digital (A/D) and digital-to-analog (D/A) converters using a flaky quantiser, called the $β$-encoder, has been shown to have exponential bit rate accuracy while possessing a self-correction property for fluctuations of the amplifier factor $β$ and the quantiser threshold $ν$. The probabilistic behavior of such a flaky quantiser is explained as the deterministic dynamics of the multi-valued Rényi map. That is, a sample $x$ is always confined to a contracted subinterval while successive approximations of $x$ are performed using $β$-expansion even if $ν$ may vary at each iteration. This viewpoint enables us to get the decoded sample, which is equal to the midpoint of the subinterval, and its associated characteristic equation for recovering $β$ which improves the quantisation error by more than $3{dB}$ when $β>1.5$. The invariant subinterval under the Rényi map shows that $ν$ should be set to around the midpoint of its associated greedy and lazy values. %in terms of its quantisation MSE (mean square error). Furthermore, a new A/D converter is introduced called the negative $β$-encoder, which further improves the quantisation error of the $β$-encoder. A two-state Markov chain describing the $β$-encoder suggests that a negative eigenvalue of its associated transition probability matrix reduces the quantisation error.
Approaching Blokh-Zyablov Error Exponent with Linear-Time Encodable/Decodable Codes
Venue: arXiv cs.IT 2009
Year: 2009

Guruswami and Indyk showed in [1] that Forney's error exponent can be achieved with linear coding complexity over binary symmetric channels. This paper extends this conclusion to general discrete-time memoryless channels and shows that Forney's and Blokh-Zyablov error exponents can be arbitrarily approached by one-level and multi-level concatenated codes with linear encoding/decoding complexity. The key result is a revision to Forney's general minimum distance decoding algorithm, which enables a low complexity integration of Guruswami-Indyk's outer codes into the concatenated coding schemes.
Swapping Lemmas for Regular and Context-Free Languages
Venue: arXiv cs.CC 2009
Year: 2009

In formal language theory, one of the most fundamental tools, known as pumping lemmas, is extremely useful for regular and context-free languages. However, there are natural properties for which the pumping lemmas are of little use. One of such examples concerns a notion of advice, which depends only on the size of an underlying input. A standard pumping lemma encounters difficulty in proving that a given language is not regular in the presence of advice. We develop its substitution, called a swapping lemma for regular languages, to demonstrate the non-regularity of a target language with advice. For context-free languages, we also present a similar form of swapping lemma, which serves as a technical tool to show that certain languages are not context-free with advice.
Efficient Implementation of the Generalized Tunstall Code Generation Algorithm
Venue: arXiv cs.IT 2009
Year: 2009

A method is presented for constructing a Tunstall code that is linear time in the number of output items. This is an improvement on the state of the art for non-Bernoulli sources, including Markov sources, which require a (suboptimal) generalization of Tunstall's algorithm proposed by Savari and analytically examined by Tabus and Rissanen. In general, if n is the total number of output leaves across all Tunstall trees, s is the number of trees (states), and D is the number of leaves of each internal node, then this method takes O((1+(log s)/D) n) time and O(n) space.
Sector and Sphere: Towards Simplified Storage and Processing of Large Scale Distributed Data
Venue: arXiv cs.DC 2009
Year: 2009

Cloud computing has demonstrated that processing very large datasets over commodity clusters can be done simply given the right programming model and infrastructure. In this paper, we describe the design and implementation of the Sector storage cloud and the Sphere compute cloud. In contrast to existing storage and compute clouds, Sector can manage data not only within a data center, but also across geographically distributed data centers. Similarly, the Sphere compute cloud supports User Defined Functions (UDF) over data both within a data center and across data centers. As a special case, MapReduce style programming can be implemented in Sphere by using a Map UDF followed by a Reduce UDF. We describe some experimental studies comparing Sector/Sphere and Hadoop using the Terasort Benchmark. In these studies, Sector is about twice as fast as Hadoop. Sector/Sphere is open source.
On Information-Theoretic Scaling Laws for Wireless Networks
Venue: arXiv cs.IT 2009
Year: 2009

With the analysis of the hierarchical scheme, the potential influence of the pre-constant in deriving scaling laws is exposed. It is found that a modified hierarchical scheme can achieve a throughput arbitrarily times higher than the original one, although it is still diminishingly small compared to the linear scaling. The study demonstrates the essential importance of the throughput formula itself, rather than the scaling laws consequently derived.
Cognitive Beamforming Made Practical: Effective Interference Channel and Learning-Throughput Tradeoff
Venue: arXiv cs.IT 2009
Year: 2009

This paper studies the transmit strategy for a secondary link or the so-called cognitive radio (CR) link under opportunistic spectrum sharing with an existing primary radio (PR) link. It is assumed that the CR transmitter is equipped with multi-antennas, whereby transmit precoding and power control can be jointly deployed to balance between avoiding interference at the PR terminals and optimizing performance of the CR link. This operation is named as cognitive beamforming (CB). Unlike prior study on CB that assumes perfect knowledge of the channels over which the CR transmitter interferes with the PR terminals, this paper proposes a practical CB scheme utilizing a new idea of effective interference channel (EIC), which can be efficiently estimated at the CR transmitter from its observed PR signals. Somehow surprisingly, this paper shows that the learning-based CB scheme with the EIC improves the CR channel capacity against the conventional scheme even with the exact CR-to-PR channel knowledge, when the PR link is equipped with multi-antennas but only communicates over a subspace of the total available spatial dimensions. Moreover, this paper presents algorithms for the CR to estimate the EIC over a finite learning time. Due to channel estimation errors, the proposed CB scheme causes leakage interference at the PR terminals, which leads to an interesting learning-throughput tradeoff phenomenon for the CR, pertinent to its time allocation between channel learning and data transmission. This paper derives the optimal channel learning time to maximize the effective throughput of the CR link, subject to the CR transmit power constraint and the interference power constraints for the PR terminals.
A Log-space Algorithm for Canonization of Planar Graphs
Venue: arXiv cs.CC 2009
Year: 2009

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. We bridge this gap for a natural and important special case, planar graph isomorphism, by presenting an upper bound that matches the known logspace hardness [Lindell'92]. In fact, we show the formally stronger result that planar graph canonization is in logspace. This improves the previously known upper bound of AC1 [MillerReif'91]. Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to logspace reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in logspace by [DattaLimayeNimbhorkar'08]. This is achieved by using the above decomposition, and by making significant modifications to Lindell's algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas, including a non-trivial case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph. This lemma is crucial for the reduction to work in logspace.
Bounds on Covering Codes with the Rank Metric
Venue: arXiv cs.IT 2009
Year: 2009

In this paper, we investigate geometrical properties of the rank metric space and covering properties of rank metric codes. We first establish an analytical expression for the intersection of two balls with rank radii, and then derive an upper bound on the volume of the union of multiple balls with rank radii. Using these geometrical properties, we derive both upper and lower bounds on the minimum cardinality of a code with a given rank covering radius. The geometrical properties and bounds proposed in this paper are significant to the design, decoding, and performance analysis of rank metric codes.
Mácajová and Škoviera Conjecture on Cubic Graphs
Venue: arXiv cs.DM 2009
Year: 2009

A conjecture of Máucajová and uSkoviera asserts that every bridgeless cubic graph has two perfect matchings whose intersection does not contain any odd edge cut. We prove this conjecture for graphs with few vertices and we give a stronger result for traceable graphs.
An algebraic approach to the set of intervals (a new approach of arithmetic of intervals)
Venue: arXiv cs.NA 2009
Year: 2009

In this paper we present the set of intervals as a normed vector space. We define also a four-dimensional associative algebra whose product gives the product of intervals in any cases. This approach allows to give a notion of divisibility and in some cases an euclidian division. We introduce differential calculus and give some applications.
Asymptotic Performance of Linear Receivers in MIMO Fading Channels
Venue: arXiv cs.IT 2009
Year: 2009

Linear receivers are an attractive low-complexity alternative to optimal processing for multi-antenna MIMO communications. In this paper we characterize the information-theoretic performance of MIMO linear receivers in two different asymptotic regimes. For fixed number of antennas, we investigate the limit of error probability in the high-SNR regime in terms of the Diversity-Multiplexing Tradeoff (DMT). Following this, we characterize the error probability for fixed SNR in the regime of large (but finite) number of antennas. As far as the DMT is concerned, we report a negative result: we show that both linear Zero-Forcing (ZF) and linear Minimum Mean-Square Error (MMSE) receivers achieve the same DMT, which is largely suboptimal even in the case where outer coding and decoding is performed across the antennas. We also provide an approximate quantitative analysis of the markedly different behavior of the MMSE and ZF receivers at finite rate and non-asymptotic SNR, and show that while the ZF receiver achieves poor diversity at any finite rate, the MMSE receiver error curve slope flattens out progressively, as the coding rate increases. When SNR is fixed and the number of antennas becomes large, we show that the mutual information at the output of a MMSE or ZF linear receiver has fluctuations that converge in distribution to a Gaussian random variable, whose mean and variance can be characterized in closed form. This analysis extends to the linear receiver case a well-known result previously obtained for the optimal receiver. Simulations reveal that the asymptotic analysis captures accurately the outage behavior of systems even with a moderate number of antennas.
On the expressiveness of single-pass instruction sequences
Venue: arXiv cs.PL 2009
Year: 2009

We perceive programs as single-pass instruction sequences. A single-pass instruction sequence under execution is considered to produce a behaviour to be controlled by some execution environment. Threads as considered in basic thread algebra model such behaviours. We show that all regular threads, i.e. threads that can only be in a finite number of states, can be produced by single-pass instruction sequences without jump instructions if use can be made of Boolean registers. We also show that, in the case where goto instructions are used instead of jump instructions, a bound to the number of labels restricts the expressiveness.
DSTC Layering Protocols in Wireless Cooperative Networks
Venue: arXiv cs.NI 2009
Year: 2009

In a radio network with single source-destination pair and some relays, a link between any two nodes is considered to have same or zero path loss. However in practice some links may have considerably high path loss than others but still being useful. In this report, we take into account signals received from these links also. \indent Our system model consists of a source-destination pair with two layers of relays in which weaker links between source and second layer and between the first layer and destination are also considered. We propose some protocols in this system model, run simulations under optimum power allocation, and compare these protocols. We show that under reasonable channel strength of these weaker links, the proposed protocols perform ($ \approx 2$ dB) better than the existing basic protocol. As expected, the degree of improvement increases with the strength of the weaker links. We also show that with the receive channel knowledge in relays, the reliability and data rate are improved.
Power Control in Two-Tier Femtocell Networks
Venue: arXiv cs.NI 2009
Year: 2009

In a two tier cellular network -- comprised of a central macrocell underlaid with shorter range femtocell hotspots -- cross-tier interference limits overall capacity with universal frequency reuse. To quantify near-far effects with universal frequency reuse, this paper derives a fundamental relation providing the largest feasible cellular Signal-to-Interference-Plus-Noise Ratio (SINR), given any set of feasible femtocell SINRs. We provide a link budget analysis which enables simple and accurate performance insights in a two-tier network. A distributed utility-based SINR adaptation at femtocells is proposed in order to alleviate cross-tier interference at the macrocell from cochannel femtocells. The Foschini-Miljanic (FM) algorithm is a special case of the adaptation. Each femtocell maximizes their individual utility consisting of a SINR based reward less an incurred cost (interference to the macrocell). Numerical results show greater than 30% improvement in mean femtocell SINRs relative to FM. In the event that cross-tier interference prevents a cellular user from obtaining its SINR target, an algorithm is proposed that reduces transmission powers of the strongest femtocell interferers. The algorithm ensures that a cellular user achieves its SINR target even with 100 femtocells/cell-site, and requires a worst case SINR reduction of only 16% at femtocells. These results motivate design of power control schemes requiring minimal network overhead in two-tier networks with shared spectrum.
On the Equation $x^{2^l+1}+x+a=0$ over $\mathrm{GF}(2^k)$ (Extended Version)
Venue: arXiv cs.DM 2009
Year: 2009

In this paper, the polynomials $P_a(x)=x^{2^l+1}+x+a$ with $a\in\mathrm{GF}(2^k)$ are studied. New criteria for the number of zeros of $P_a(x)$ in $\mathrm{GF}(2^k)$ are proved. In particular, a criterion for $P_a(x)$ to have exactly one zero in $\mathrm{GF}(2^k)$ when $\gcd(l,k)=1$ is formulated in terms of the values of permutation polynomials introduced by Dobbertin. We also study the affine polynomial $a^{2^l}x^{2^{2l}}+x^{2^l}+ax+1$ which is closely related to $P_a(x)$. In many cases, explicit expressions for calculating zeros of these polynomials are provided.
Binding bigraphs as symmetric monoidal closed theories
Venue: arXiv cs.LO 2009
Year: 2009

Milner's bigraphs are a general framework for reasoning about distributed and concurrent programming languages. Notably, it has been designed to encompass both the pi-calculus and the Ambient calculus. This paper is only concerned with bigraphical syntax: given what we here call a bigraphical signature K, Milner constructs a (pre-) category of bigraphs BBig(K), whose main features are (1) the presence of relative pushouts (RPOs), which makes them well-behaved w.r.t. bisimulations, and that (2) the so-called structural equations become equalities. Examples of the latter include, e.g., in pi and Ambient, renaming of bound variables, associativity and commutativity of parallel composition, or scope extrusion for restricted names. Also, bigraphs follow a scoping discipline ensuring that, roughly, bound variables never escape their scope. Here, we reconstruct bigraphs using a standard categorical tool: symmetric monoidal closed (SMC) theories. Our theory enforces the same scoping discipline as bigraphs, as a direct property of SMC structure. Furthermore, it elucidates the slightly mysterious status of so-called links in bigraphs. Finally, our category is also considerably larger than the category of bigraphs, notably encompassing in the same framework terms and a flexible form of higher-order contexts.
Sequential adaptive compressed sampling via Huffman codes
Venue: arXiv cs.IT 2009
Year: 2009

There are two main approaches in compressed sensing: the geometric approach and the combinatorial approach. In this paper we introduce an information theoretic approach and use results from the theory of Huffman codes to construct a sequence of binary sampling vectors to determine a sparse signal. Unlike other approaches, our approach is adaptive in the sense that each sampling vector depends on the previous sample. The number of measurements we need for a k-sparse vector in n-dimensional space is no more than O(k log n) and the reconstruction is O(k).
Reconstructing Extended Perfect Binary One-Error-Correcting Codes from Their Minimum Distance Graphs
Venue: arXiv cs.IT 2009
Year: 2009

The minimum distance graph of a code has the codewords as vertices and edges exactly when the Hamming distance between two codewords equals the minimum distance of the code. A constructive proof for reconstructibility of an extended perfect binary one-error-correcting code from its minimum distance graph is presented. Consequently, inequivalent such codes have nonisomorphic minimum distance graphs. Moreover, it is shown that the automorphism group of a minimum distance graph is isomorphic to that of the corresponding code.
Semantics and Evaluation of Top-k Queries in Probabilistic Databases
Venue: arXiv cs.DB 2009
Year: 2009

We study here fundamental issues involved in top-k query evaluation in probabilistic databases. We consider simple probabilistic databases in which probabilities are associated with individual tuples, and general probabilistic databases in which, additionally, exclusivity relationships between tuples can be represented. In contrast to other recent research in this area, we do not limit ourselves to injective scoring functions. We formulate three intuitive postulates that the semantics of top-k queries in probabilistic databases should satisfy, and introduce a new semantics, Global-Topk, that satisfies those postulates to a large degree. We also show how to evaluate queries under the Global-Topk semantics. For simple databases we design dynamic-programming based algorithms, and for general databases we show polynomial-time reductions to the simple cases. For example, we demonstrate that for a fixed k the time complexity of top-k query evaluation is as low as linear, under the assumption that probabilistic databases are simple and scoring functions are injective.
Characterizing the Robustness of Complex Networks
Venue: arXiv cs.NI 2009
Year: 2009

With increasingly ambitious initiatives such as GENI and FIND that seek to design the future Internet, it becomes imperative to define the characteristics of robust topologies, and build future networks optimized for robustness. This paper investigates the characteristics of network topologies that maintain a high level of throughput in spite of multiple attacks. To this end, we select network topologies belonging to the main network models and some real world networks. We consider three types of attacks: removal of random nodes, high degree nodes, and high betweenness nodes. We use elasticity as our robustness measure and, through our analysis, illustrate that different topologies can have different degrees of robustness. In particular, elasticity can fall as low as 0.8% of the upper bound based on the attack employed. This result substantiates the need for optimized network topology design. Furthermore, we implement a tradeoff function that combines elasticity under the three attack strategies and considers the cost of the network. Our extensive simulations show that, for a given network density, regular and semi-regular topologies can have higher degrees of robustness than heterogeneous topologies, and that link redundancy is a sufficient but not necessary condition for robustness.
Learning Class-Level Bayes Nets for Relational Data
Venue: arXiv cs.LG 2009
Year: 2009

Many databases store data in relational format, with different types of entities and information about links between the entities. The field of statistical-relational learning (SRL) has developed a number of new statistical models for such data. In this paper we focus on learning class-level or first-order dependencies, which model the general database statistics over attributes of linked objects and links (e.g., the percentage of A grades given in computer science classes). Class-level statistical relationships are important in themselves, and they support applications like policy making, strategic planning, and query optimization. Most current SRL methods find class-level dependencies, but their main task is to support instance-level predictions about the attributes or links of specific entities. We focus only on class-level prediction, and describe algorithms for learning class-level models that are orders of magnitude faster for this task. Our algorithms learn Bayes nets with relational structure, leveraging the efficiency of single-table nonrelational Bayes net learners. An evaluation of our methods on three data sets shows that they are computationally feasible for realistic table sizes, and that the learned structures represent the statistical information in the databases well. After learning compiles the database statistics into a Bayes net, querying these statistics via Bayes net inference is faster than with SQL queries, and does not depend on the size of the database.
A Matlab Implementation of a Flat Norm Motivated Polygonal Edge Matching Method using a Decomposition of Boundary into Four 1-Dimensional Currents
Venue: arXiv cs.CV 2009
Year: 2009

We describe and provide code and examples for a polygonal edge matching method.
Driven by Compression Progress: A Simple Principle Explains Essential Aspects of Subjective Beauty, Novelty, Surprise, Interestingness, Attention, Curiosity, Creativity, Art, Science, Music, Jokes
Venue: arXiv cs.AI 2009
Year: 2009

I argue that data becomes temporarily interesting by itself to some self-improving, but computationally limited, subjective observer once he learns to predict or compress the data in a better way, thus making it subjectively simpler and more beautiful. Curiosity is the desire to create or discover more non-random, non-arbitrary, regular data that is novel and surprising not in the traditional sense of Boltzmann and Shannon but in the sense that it allows for compression progress because its regularity was not yet known. This drive maximizes interestingness, the first derivative of subjective beauty or compressibility, that is, the steepness of the learning curve. It motivates exploring infants, pure mathematicians, composers, artists, dancers, comedians, yourself, and (since 1990) artificial systems.