OpenRaiser/Intern-Atlas huggingface dataset:
Capacity Regions and Sum-Rate Capacities of Vector Gaussian Interference Channels
Venue: arXiv cs.IT 2009
Year: 2009

The capacity regions of vector, or multiple-input multiple-output, Gaussian interference channels are established for very strong interference and aligned strong interference. Furthermore, the sum-rate capacities are established for Z interference, noisy interference, and mixed (aligned weak/intermediate and aligned strong) interference. These results generalize known results for scalar Gaussian interference channels.
Use of statistical outlier detection method in adaptive evolutionary algorithms
Venue: arXiv cs.NE 2009
Year: 2009

In this paper, the issue of adapting probabilities for Evolutionary Algorithm (EA) search operators is revisited. A framework is devised for distinguishing between measurements of performance and the interpretation of those measurements for purposes of adaptation. Several examples of measurements and statistical interpretations are provided. Probability value adaptation is tested using an EA with 10 search operators against 10 test problems with results indicating that both the type of measurement and its statistical interpretation play significant roles in EA performance. We also find that selecting operators based on the prevalence of outliers rather than on average performance is able to provide considerable improvements to adaptive methods and soundly outperforms the non-adaptive case.
Open Problems in Universal Induction & Intelligence
Venue: arXiv cs.AI 2009
Year: 2009

Specialized intelligent systems can be found everywhere: finger print, handwriting, speech, and face recognition, spam filtering, chess and other game programs, robots, et al. This decade the first presumably complete mathematical theory of artificial intelligence based on universal induction-prediction-decision-action has been proposed. This information-theoretic approach solidifies the foundations of inductive inference and artificial intelligence. Getting the foundations right usually marks a significant progress and maturing of a field. The theory provides a gold standard and guidance for researchers working on intelligent algorithms. The roots of universal induction have been laid exactly half-a-century ago and the roots of universal intelligence exactly one decade ago. So it is timely to take stock of what has been achieved and what remains to be done. Since there are already good recent surveys, I describe the state-of-the-art only in passing and refer the reader to the literature. This article concentrates on the open problems in universal induction and its extension to universal intelligence.
Search-based Structured Prediction
Venue: arXiv cs.LG 2009
Year: 2009

We present Searn, an algorithm for integrating search and learning to solve complex structured prediction problems such as those that occur in natural language, speech, computational biology, and vision. Searn is a meta-algorithm that transforms these complex problems into simple classification problems to which any binary classifier may be applied. Unlike current algorithms for structured learning that require decomposition of both the loss function and the feature functions over the predicted structure, Searn is able to learn prediction functions for any loss function and any class of features. Moreover, Searn comes with a strong, natural theoretical guarantee: good performance on the derived classification problems implies good performance on the structured prediction problem.
Tensors and n-d Arrays:A Mathematics of Arrays (MoA), psi-Calculus and the Composition of Tensor and Array Operations
Venue: arXiv cs.MS 2009
Year: 2009

The Kronecker product is a key algorithm and is ubiquitous across the physical, biological, and computation social sciences. Thus considerations of optimal implementation are important. The need to have high performance and computational reproducibility is paramount. Moreover, due to the need to compose multiple Kronecker products, issues related to data structures, layout and indexing algebra require a new look at an old problem. This paper discusses the outer product/tensor product and a special case of the tensor product: the Kronecker product, along with optimal implementation when composed, and mapped to complex processor/memory hierarchies. We discuss how the use of ``A Mathematics of Arrays" (MoA), and the psi-Calculus, (a calculus of indexing with shapes), provides optimal, verifiable, reproducible, scalable, and portable implementations of both hardware and software.
A Noisy-Channel Model for Document Compression
Venue: arXiv cs.CL 2009
Year: 2009

We present a document compression system that uses a hierarchical noisy-channel model of text production. Our compression system first automatically derives the syntactic structure of each sentence and the overall discourse structure of the text given as input. The system then uses a statistical hierarchical model of text production in order to drop non-important syntactic and discourse constituents so as to generate coherent, grammatical document compressions of arbitrary length. The system outperforms both a baseline and a sentence-based compression system that operates by simplifying sequentially all sentences in a text. Our results support the claim that discourse knowledge plays an important role in document summarization.
Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction
Venue: arXiv cs.LG 2009
Year: 2009

Mappings to structured output spaces (strings, trees, partitions, etc.) are typically learned using extensions of classification algorithms to simple graphical structures (eg., linear chains) in which search and parameter estimation can be performed exactly. Unfortunately, in many complex problems, it is rare that exact search or parameter estimation is tractable. Instead of learning exact models and searching via heuristic means, we embrace this difficulty and treat the structured output problem in terms of approximate search. We present a framework for learning as search optimization, and two parameter updates with convergence theorems and bounds. Empirical evidence shows that our integrated approach to learning and decoding can outperform exact models at smaller computational cost.
Representing Real Numbers in a Generalized Numeration Systems
Venue: arXiv cs.FL 2009
Year: 2009

We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers using the Dyck language. We also show that our framework can be applied to the rational base numeration systems.
Approximating Spanning Trees with Low Crossing Number
Venue: arXiv cs.CG 2009
Year: 2009

We present a linear programming based algorithm for computing a spanning tree $T$ of a set $P$ of $n$ points in $\Re^d$, such that its crossing number is $O(\min(t \log n, n^{1-1/d}))$, where $t$ the minimum crossing number of any spanning tree of $P$. This is the first guaranteed approximation algorithm for this problem. We provide a similar approximation algorithm for the more general settings of building a spanning tree for a set system with bounded \VC dimension. Our approach is an alternative to the reweighting technique previously used in computing such spanning trees. Our approach is an alternative to the reweighting technique previously used in computing such spanning trees.
Using HB Family of Protocols for Privacy-Preserving Authentication of RFID Tags in a Population
Venue: arXiv cs.CR 2009
Year: 2009

In this paper, we propose an HB-like protocol for privacy-preserving authentication of RFID tags, whereby a tag can remain anonymous and untraceable to an adversary during the authentication process. Previous proposals of such protocols were based on PRF computations. Our protocol can instead be used on low-cost tags that may be incapable of computing standard PRFs. Moreover, since the underlying computations in HB protocols are very efficient, our protocol also reduces reader load compared to PRF-based protocols. We suggest a tree-based approach that replaces the PRF-based authentication from prior work with a procedure such as HB+ or HB#. We optimize the tree- traversal stage through usage of a "light version" of the underlying protocol and shared random challenges across all levels of the tree. This provides significant reduction of the communication resources, resulting in a privacy-preserving protocol almost as efficient as the underlying HB+ or HB#
The Complexity of Guarding Terrains
Venue: arXiv cs.CG 2009
Year: 2009

A set $G$ of points on a 1.5-dimensional terrain, also known as an $x$-monotone polygonal chain, is said to guard the terrain if any point on the terrain is 'seen' by a point in $G$. Two points on the terrain see each other if and only if the line segment between them is never strictly below the terrain. The minimum terrain guarding problem asks for a minimum guarding set for the given input terrain. We prove that the decision version of this problem is NP-hard. This solves a significant open problem and complements recent positive approximability results for the optimization problem. Our proof uses a reduction from PLANAR 3-SAT. We build gadgets capable of 'mirroring' a consistent variable assignment back and forth across a main valley. The structural simplicity of 1.5-dimensional terrains makes it difficult to build general clause gadgets that do not destroy this assignment when they are evaluated. However, we exploit the structure in instances of PLANAR 3-SAT to find very specific operations involving only 'adjacent' variables. For these restricted operations we can construct gadgets that allow a full reduction to work.
Towards an $O(\sqrt[3]{\log n})$-Approximation Algorithm for {\sc Balanced Separator}
Venue: arXiv cs.DS 2009
Year: 2009

The {\sc $c$-Balanced Separator} problem is a graph-partitioning problem in which given a graph $G$, one aims to find a cut of minimum size such that both the sides of the cut have at least $cn$ vertices. In this paper, we present new directions of progress in the {\sc $c$-Balanced Separator} problem. More specifically, we propose a new family of mathematical programs, which depends upon a parameter $ε> 0$, and extend the seminal work of Arora-Rao-Vazirani ({\sf ARV}) \cite{ARV} to show that the polynomial time solvability of the proposed family of programs implies an improvement in the approximation factor to $O(\log^{{1/3} + ε} n)$ from the best-known factor of $O(\sqrt{\log n})$ due to {\sf ARV}. In fact, for $ε= 1/3$, the program we get is the SDP proposed by {\sf ARV}. For $ε< 1/3$, this family of programs is not convex but one can transform them into so called \emph{\textbf{concave programs}} in which one optimizes a concave function over a convex feasible set. The properties of concave programs allows one to apply techniques due to Hoffman \cite{H81} or Tuy \emph{et al} \cite{TTT85} to solve such problems with arbitrary accuracy. But the problem of finding of a method to solve these programs that converges in polynomial time still remains open. Our result, although conditional, introduces a new family of programs which is more powerful than semi-definite programming in the context of approximation algorithms and hence it will of interest to investigate this family both in the direction of designing efficient algorithms and proving hardness results.
Reciprocity in Linear Deterministic Networks under Linear Coding
Venue: arXiv cs.IT 2009
Year: 2009

The linear deterministic model has been used recently to get a first order understanding of many wireless communication network problems. In many of these cases, it has been pointed out that the capacity regions of the network and its reciprocal (where the communication links are reversed and the roles of the sources and the destinations are swapped) are the same. In this paper, we consider a linear deterministic communication network with multiple unicast information flows. For this model and under the restriction to the class of linear coding, we show that the rate regions for a network and its reciprocal are the same. This can be viewed as a generalization of the linear reversibility of wireline networks, already known in the network coding literature.
A PTAS for the Minimum Consensus Clustering Problem with a Fixed Number of Clusters
Venue: arXiv cs.DS 2009
Year: 2009

The Consensus Clustering problem has been introduced as an effective way to analyze the results of different microarray experiments. The problem consists of looking for a partition that best summarizes a set of input partitions (each corresponding to a different microarray experiment) under a simple and intuitive cost function. The problem admits polynomial time algorithms on two input partitions, but is APX-hard on three input partitions. We investigate the restriction of Consensus Clustering when the output partition is required to contain at most k sets, giving a polynomial time approximation scheme (PTAS) while proving the NP-hardness of this restriction.
Amplified Hardness of Approximation for VCG-Based Mechanisms
Venue: arXiv cs.GT 2009
Year: 2009

If a two-player social welfare maximization problem does not admit a PTAS, we prove that any maximal-in-range truthful mechanism that runs in polynomial time cannot achieve an approximation factor better than 1/2. Moreover, for the k-player version of the same problem, the hardness of approximation improves to 1/k under the same two-player hardness assumption. (We note that 1/k is achievable by a trivial deterministic maximal-in-range mechanism.) This hardness result encompasses not only deterministic maximal-in-range mechanisms, but also all universally-truthful randomized maximal in range algorithms, as well as a class of strictly more powerful truthful-in-expectation randomized mechanisms recently introduced by Dobzinski and Dughmi. Our result applies to any class of valuation functions that satisfies some minimal closure properties. These properties are satisfied by the valuation functions in all well-studied APX-hard social welfare maximization problems, such as coverage, submodular, and subadditive valuations. We also prove a stronger result for universally-truthful maximal-in-range mechanisms. Namely, even for the class of budgeted additive valuations, which admits an FPTAS, no such mechanism can achieve an approximation factor better than 1/k in polynomial time.
On the Chances of Completing the Game of "Perpetual Motion"
Venue: arXiv cs.GT 2009
Year: 2009

This brief paper describes the single-player card game called "Perpetual Motion" and reports on a computational analysis of the game's outcome. The analysis follows a Monte Carlo methodology based on a sample of 10,000 randomly generated games. The key result is that 54.55% +/- 0.89% of games can be completed (by a patient player!) but that the remaining 45.45% result in non-terminating cycles. The lengths of these non-terminating cycles leave some outstanding questions.
Spectrum sensing by cognitive radios at very low SNR
Venue: arXiv cs.IT 2009
Year: 2009

Spectrum sensing is one of the enabling functionalities for cognitive radio (CR) systems to operate in the spectrum white space. To protect the primary incumbent users from interference, the CR is required to detect incumbent signals at very low signal-to-noise ratio (SNR). In this paper, we present a spectrum sensing technique based on correlating spectra for detection of television (TV) broadcasting signals. The basic strategy is to correlate the periodogram of the received signal with the a priori known spectral features of the primary signal. We show that according to the Neyman-Pearson criterion, this spectral correlation-based sensing technique is asymptotically optimal at very low SNR and with a large sensing time. From the system design perspective, we analyze the effect of the spectral features on the spectrum sensing performance. Through the optimization analysis, we obtain useful insights on how to choose effective spectral features to achieve reliable sensing. Simulation results show that the proposed sensing technique can reliably detect analog and digital TV signals at SNR as low as -20 dB.
Algebraic properties of structured context-free languages: old approaches and novel developments
Venue: arXiv cs.FL 2009
Year: 2009

The historical research line on the algebraic properties of structured CF languages initiated by McNaughton's Parenthesis Languages has recently attracted much renewed interest with the Balanced Languages, the Visibly Pushdown Automata languages (VPDA), the Synchronized Languages, and the Height-deterministic ones. Such families preserve to a varying degree the basic algebraic properties of Regular languages: boolean closure, closure under reversal, under concatenation, and Kleene star. We prove that the VPDA family is strictly contained within the Floyd Grammars (FG) family historically known as operator precedence. Languages over the same precedence matrix are known to be closed under boolean operations, and are recognized by a machine whose pop or push operations on the stack are purely determined by terminal letters. We characterize VPDA's as the subclass of FG having a peculiarly structured set of precedence relations, and balanced grammars as a further restricted case. The non-counting invariance property of FG has a direct implication for VPDA too.
Adaptive Point-to-Multipoint Transmission for Multimedia Broadcast Multicast Services in LTE
Venue: arXiv cs.NI 2009
Year: 2009

This paper investigates point-to-multipoint (PTM) transmission supporting adaptive modulation and coding (AMC) as well as retransmissions based on incremental redundancy. In contrast to the classical PTM transmission which was introduced by the Multimedia Broadcast Multicast Service (MBMS), the adaptiveness requires user individual feedback channels that allow the receivers to report their radio conditions and send positive or negative acknowledgments (ACK/NACK) for a Layer 1 transport block to the eNodeB. In this work, an adaptive PTM scheme based on feedback from multiple users is presented and evaluated. Furthermore, a simple NACK-oriented feedback mechanism is introduced to relieve the feedback channel that is used in the uplink. Finally, the performance of different single-cell MBMS transmission modes is evaluated by dynamic radio network simulations. It is shown that adaptive PTM transmission outperforms the conventional MBMS configurations in terms of radio resource consumption and user satisfaction rate.
Separations of non-monotonic randomness notions
Venue: arXiv cs.CC 2009
Year: 2009

In the theory of algorithmic randomness, several notions of random sequence are defined via a game-theoretic approach, and the notions that received most attention are perhaps Martin-Loef randomness and computable randomness. The latter notion was introduced by Schnorr and is rather natural: an infinite binary sequence is computably random if no total computable strategy succeeds on it by betting on bits in order. However, computably random sequences can have properties that one may consider to be incompatible with being random, in particular, there are computably random sequences that are highly compressible. The concept of Martin-Loef randomness is much better behaved in this and other respects, on the other hand its definition in terms of martingales is considerably less natural. Muchnik, elaborating on ideas of Kolmogorov and Loveland, refined Schnorr's model by also allowing non-monotonic strategies, i.e. strategies that do not bet on bits in order. The subsequent ``non-monotonic'' notion of randomness, now called Kolmogorov-Loveland randomness, has been shown to be quite close to Martin-Loef randomness, but whether these two classes coincide remains a fundamental open question. As suggested by Miller and Nies, we study in this paper weak versions of Kolmogorov-Loveland randomness, where the betting strategies are non-adaptive (i.e., the positions of the bits to bet on should be decided before the game). We obtain a full classification of the different notions we consider.
Optimal Diversity-Multiplexing Tradeoff in Selective-Fading MIMO Channels
Venue: arXiv cs.IT 2009
Year: 2009

We establish the optimal diversity-multiplexing (DM) tradeoff of coherent time, frequency, and time-frequency selective-fading multiple-input multiple-output (MIMO) channels and provide a code design criterion for DM tradeoff optimality. Our results are based on the new concept of the "Jensen channel" associated to a given selective-fading MIMO channel. While the original problem seems analytically intractable due to the mutual information between channel input and output being a sum of correlated random variables, the Jensen channel is equivalent to the original channel in the sense of the DM tradeoff and lends itself nicely to analytical treatment. We formulate a systematic procedure for designing DM tradeoff optimal codes for general selective-fading MIMO channels by demonstrating that the design problem can be separated into two simpler and independent problems: the design of an inner code, or precoder, adapted to the channel statistics (i.e., the selectivity characteristics) and an outer code independent of the channel statistics. Our results are supported by appealing geometric intuition, first pointed out for the flat-fading case by Zheng and Tse, IEEE Trans. Inf. Theory, 2003.
Untangling the Braid: Finding Outliers in a Set of Streams
Venue: arXiv cs.DB 2009
Year: 2009

Monitoring the performance of large shared computing systems such as the cloud computing infrastructure raises many challenging algorithmic problems. One common problem is to track users with the largest deviation from the norm (outliers), for some measure of performance. Taking a stream-computing perspective, we can think of each user's performance profile as a stream of numbers (such as response times), and the aggregate performance profile of the shared infrastructure as a "braid" of these intermixed streams. The monitoring system's goal then is to untangle this braid sufficiently to track the top k outliers. This paper investigates the space complexity of one-pass algorithms for approximating outliers of this kind, proves lower bounds using multi-party communication complexity, and proposes small-memory heuristic algorithms. On one hand, stream outliers are easily tracked for simple measures, such as max or min, but our theoretical results rule out even good approximations for most of the natural measures such as average, median, or the quantiles. On the other hand, we show through simulation that our proposed heuristics perform quite well for a variety of synthetic data.