OpenRaiser/Intern-Atlas huggingface dataset:
On the Iterated Hairpin Completion
Venue: arXiv cs.FL 2011
Year: 2011

The (bounded) hairpin completion and its iterated versions are operations on formal lan- guages which have been inspired by the hairpin formation in DNA-biochemistry. The paper answers two questions asked in the literature about the iterated hairpin completion. The first question is whether the class of regular languages is closed under iterated bounded hairpin completion. Here we show that this is true by providing a more general result which applies to all the classes of languages which are closed under finite union, intersection with regular sets, and concatenation with regular sets. In particular, all Chomsky classes and all standard complexity classes are closed under iterated bounded hairpin completion. In the second part of the paper we address the question whether the iterated hairpin completion of a singleton is always regular. In contrast to the first question, this one has a negative answer. We exhibit an example of a singleton language whose iterated hairpin completion is not regular, actually it is not context-free, but context-sensitive.
Windowed Decoding of Protograph-based LDPC Convolutional Codes over Erasure Channels
Venue: arXiv cs.IT 2011
Year: 2011

We consider a windowed decoding scheme for LDPC convolutional codes that is based on the belief-propagation (BP) algorithm. We discuss the advantages of this decoding scheme and identify certain characteristics of LDPC convolutional code ensembles that exhibit good performance with the windowed decoder. We will consider the performance of these ensembles and codes over erasure channels with and without memory. We show that the structure of LDPC convolutional code ensembles is suitable to obtain performance close to the theoretical limits over the memoryless erasure channel, both for the BP decoder and windowed decoding. However, the same structure imposes limitations on the performance over erasure channels with memory.
Towards a communication-theoretic understanding of system-level power consumption
Venue: arXiv cs.IT 2011
Year: 2011

Traditional communication theory focuses on minimizing transmit power. However, communication links are increasingly operating at shorter ranges where transmit power can be significantly smaller than the power consumed in decoding. This paper models the required decoding power and investigates the minimization of total system power from two complementary perspectives. First, an isolated point-to-point link is considered. Using new lower bounds on the complexity of message-passing decoding, lower bounds are derived on decoding power. These bounds show that 1) there is a fundamental tradeoff between transmit and decoding power; 2) unlike the implications of the traditional "waterfall" curve which focuses on transmit power, the total power must diverge to infinity as error probability goes to zero; 3) Regular LDPCs, and not their known capacity-achieving irregular counterparts, can be shown to be power order optimal in some cases; and 4) the optimizing transmit power is bounded away from the Shannon limit. Second, we consider a collection of links. When systems both generate and face interference, coding allows a system to support a higher density of transmitter-receiver pairs (assuming interference is treated as noise). However, at low densities, uncoded transmission may be more power-efficient in some cases.
Optimal Packet Scheduling on an Energy Harvesting Broadcast Link
Venue: arXiv cs.IT 2011
Year: 2011

The minimization of transmission completion time for a given number of bits per user in an energy harvesting communication system, where energy harvesting instants are known in an offline manner is considered. An achievable rate region with structural properties satisfied by the 2-user AWGN Broadcast Channel capacity region is assumed. It is shown that even though all data are available at the beginning, a non-negative amount of energy from each energy harvest is deferred for later use such that the transmit power starts at its lowest value and rises as time progresses. The optimal scheduler ends the transmission to both users at the same time. Exploiting the special structure in the problem, the iterative offline algorithm, FlowRight, from earlier literature, is adapted and proved to solve this problem. The solution has polynomial complexity in the number of harvests used, and is observed to converge quickly on numerical examples.
Stable Takens' Embeddings for Linear Dynamical Systems
Venue: arXiv cs.SY 2011
Year: 2011

Takens' Embedding Theorem remarkably established that concatenating M previous outputs of a dynamical system into a vector (called a delay coordinate map) can be a one-to-one mapping of a low-dimensional attractor from the system state space. However, Takens' theorem is fragile in the sense that even small imperfections can induce arbitrarily large errors in this attractor representation. We extend Takens' result to establish deterministic, explicit and non-asymptotic sufficient conditions for a delay coordinate map to form a stable embedding in the restricted case of linear dynamical systems and observation functions. Our work is inspired by the field of Compressive Sensing (CS), where results guarantee that low-dimensional signal families can be robustly reconstructed if they are stably embedded by a measurement operator. However, in contrast to typical CS results, i) our sufficient conditions are independent of the size of the ambient state space, and ii) some system and measurement pairs have fundamental limits on the conditioning of the embedding (i.e., how close it is to an isometry), meaning that further measurements beyond some point add no further significant value. We use several simple simulations to explore the conditions of the main results, including the tightness of the bounds and the convergence speed of the stable embedding. We also present an example task of estimating the attractor dimension from time-series data to highlight the value of stable embeddings over traditional Takens' embeddings.
A parametric approach to list decoding of Reed-Solomon codes using interpolation
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we present a minimal list decoding algorithm for Reed-Solomon (RS) codes. Minimal list decoding for a code $C$ refers to list decoding with radius $L$, where $L$ is the minimum of the distances between the received word $\mathbf{r}$ and any codeword in $C$. We consider the problem of determining the value of $L$ as well as determining all the codewords at distance $L$. Our approach involves a parametrization of interpolating polynomials of a minimal Gröbner basis $G$. We present two efficient ways to compute $G$. We also show that so-called re-encoding can be used to further reduce the complexity. We then demonstrate how our parametric approach can be solved by a computationally feasible rational curve fitting solution from a recent paper by Wu. Besides, we present an algorithm to compute the minimum multiplicity as well as the optimal values of the parameters associated with this multiplicity which results in overall savings in both memory and computation.
Equivalence of the Random Oracle Model and the Ideal Cipher Model, Revisited
Venue: arXiv cs.CR 2011
Year: 2011

We consider the cryptographic problem of constructing an invertible random permutation from a public random function (i.e., which can be accessed by the adversary). This goal is formalized by the notion of indifferentiability of Maurer et al. (TCC 2004). This is the natural extension to the public setting of the well-studied problem of building random permutations from random functions, which was first solved by Luby and Rackoff (Siam J. Comput., '88) using the so-called Feistel construction. The most important implication of such a construction is the equivalence of the random oracle model (Bellare and Rogaway, CCS '93) and the ideal cipher model, which is typically used in the analysis of several constructions in symmetric cryptography. Coron et al. (CRYPTO 2008) gave a rather involved proof that the six-round Feistel construction with independent random round functions is indifferentiable from an invertible random permutation. Also, it is known that fewer than six rounds do not suffice for indifferentiability. The first contribution (and starting point) of our paper is a concrete distinguishing attack which shows that the indifferentiability proof of Coron et al. is not correct. In addition, we provide supporting evidence that an indifferentiability proof for the six-round Feistel construction may be very hard to find. To overcome this gap, our main contribution is a proof that the Feistel construction with eigthteen rounds is indifferentiable from an invertible random permutation. The approach of our proof relies on assigning to each of the rounds in the construction a unique and specific role needed in the proof. This avoids many of the problems that appear in the six-round case.
Online Importance Weight Aware Updates
Venue: arXiv cs.LG 2011
Year: 2011

An importance weight quantifies the relative importance of one example over another, coming up in applications of boosting, asymmetric classification costs, reductions, and active learning. The standard approach for dealing with importance weights in gradient descent is via multiplication of the gradient. We first demonstrate the problems of this approach when importance weights are large, and argue in favor of more sophisticated ways for dealing with them. We then develop an approach which enjoys an invariance property: that updating twice with importance weight $h$ is equivalent to updating once with importance weight $2h$. For many important losses this has a closed form update which satisfies standard regret guarantees when all examples have $h=1$. We also briefly discuss two other reasonable approaches for handling large importance weights. Empirically, these approaches yield substantially superior prediction with similar computational performance while reducing the sensitivity of the algorithm to the exact setting of the learning rate. We apply these to online active learning yielding an extraordinarily fast active learning algorithm that works even in the presence of adversarial noise.
Linear lambda Calculus with Explicit Substitutions as Proof-Search in Deep Inference
Venue: arXiv cs.LO 2011
Year: 2011

SBV is a deep inference system that extends the set of logical operators of multiplicative linear logic with the non commutative operator Seq. We introduce the logical system SBVr which extends SBV by adding a self-dual atom-renaming operator to it. We prove that the cut elimination holds on SBVr. SBVr and its cut free subsystem BVr are complete and sound with respect to linear lambda calculus with explicit substitutions. Under any strategy, a sequence of evaluation steps of any linear lambda-term M becomes a process of proof-search in SBVr (BVr) once M is mapped into a formula of SBVr. Completeness and soundness follow from simulating linear beta-reduction with explicit substitutions as processes. The role of the new renaming operator of SBVr is to rename channel-names on-demand. This simulates the substitution that occurs in a beta-reduction. Despite SBVr is a minimal extension of SBV its proof-search can compute all boolean functions, as linear lambda-calculus with explicit substitutions can compute all boolean functions as well. So, proof search of SBVr and BVr is at least ptime-complete.
Bayesian Sequential Detection with Phase-Distributed Change Time and Nonlinear Penalty -- A POMDP Approach
Venue: arXiv cs.IT 2011
Year: 2011

We show that the optimal decision policy for several types of Bayesian sequential detection problems has a threshold switching curve structure on the space of posterior distributions. This is established by using lattice programming and stochastic orders in a partially observed Markov decision process (POMDP) framework. A stochastic gradient algorithm is presented to estimate the optimal linear approximation to this threshold curve. We illustrate these results by first considering quickest time detection with phase-type distributed change time and a variance stopping penalty. Then it is proved that the threshold switching curve also arises in several other Bayesian decision problems such as quickest transient detection, exponential delay (risk-sensitive) penalties, stopping time problems in social learning, and multi-agent scheduling in a changing world. Using Blackwell dominance, it is shown that for dynamic decision making problems, the optimal decision policy is lower bounded by a myopic policy. Finally, it is shown how the achievable cost of the optimal decision policy varies with change time distribution by imposing a partial order on transition matrices.
Layered Label Propagation: A MultiResolution Coordinate-Free Ordering for Compressing Social Networks
Venue: arXiv cs.DS 2011
Year: 2011

We continue the line of research on graph compression started with WebGraph, but we move our focus to the compression of social networks in a proper sense (e.g., LiveJournal): the approaches that have been used for a long time to compress web graphs rely on a specific ordering of the nodes (lexicographical URL ordering) whose extension to general social networks is not trivial. In this paper, we propose a solution that mixes clusterings and orders, and devise a new algorithm, called Layered Label Propagation, that builds on previous work on scalable clustering and can be used to reorder very large graphs (billions of nodes). Our implementation uses overdecomposition to perform aggressively on multi-core architecture, making it possible to reorder graphs of more than 600 millions nodes in a few hours. Experiments performed on a wide array of web graphs and social networks show that combining the order produced by the proposed algorithm with the WebGraph compression framework provides a major increase in compression with respect to all currently known techniques, both on web graphs and on social networks. These improvements make it possible to analyse in main memory significantly larger graphs.
Application of the EWL protocol to decision problems with imperfect recall
Venue: arXiv cs.GT 2011
Year: 2011

We demonstrate implementations of the Eisert-Wilkens-Lewenstein scheme be- yond normal-form games. The scope of our research includes decision problems, i.e., one-player extensive games. The research is based on the examination of their features when the decision problems are carried out via the EWL protocol. We prove that unitary operators can be adapted to play the role of strategies in deci- sion problems with imperfect recall. Furthermore, we prove that unitary operators provide the decision maker possibilities that are inaccessible for classical strategies.
Plug-in privacy for Smart Metering billing
Venue: arXiv cs.CR 2011
Year: 2011

Traditional electricity meters are replaced by Smart Meters in customers' households. Smart Meters collects fine-grained utility consumption profiles from customers, which in turn enables the introduction of dynamic, time-of-use tariffs. However, the fine-grained usage data that is compiled in this process also allows to infer the inhabitant's personal schedules and habits. We propose a privacy-preserving protocol that enables billing with time-of-use tariffs without disclosing the actual consumption profile to the supplier. Our approach relies on a zero-knowledge proof based on Pedersen Commitments performed by a plug-in privacy component that is put into the communication link between Smart Meter and supplier's back-end system. We require no changes to the Smart Meter hardware and only small changes to the software of Smart Meter and back-end system. In this paper we describe the functional and privacy requirements, the specification and security proof of our solution and give a performance evaluation of a prototypical implementation.
A Focused Sequent Calculus Framework for Proof Search in Pure Type Systems
Venue: arXiv cs.LO 2011
Year: 2011

Basic proof-search tactics in logic and type theory can be seen as the root-first applications of rules in an appropriate sequent calculus, preferably without the redundancies generated by permutation of rules. This paper addresses the issues of defining such sequent calculi for Pure Type Systems (PTS, which were originally presented in natural deduction style) and then organizing their rules for effective proof-search. We introduce the idea of Pure Type Sequent Calculus with meta-variables (PTSCalpha), by enriching the syntax of a permutation-free sequent calculus for propositional logic due to Herbelin, which is strongly related to natural deduction and already well adapted to proof-search. The operational semantics is adapted from Herbelin's and is defined by a system of local rewrite rules as in cut-elimination, using explicit substitutions. We prove confluence for this system. Restricting our attention to PTSC, a type system for the ground terms of this system, we obtain the Subject Reduction property and show that each PTSC is logically equivalent to its corresponding PTS, and the former is strongly normalising iff the latter is. We show how to make the logical rules of PTSC into a syntax-directed system PS for proof-search, by incorporating the conversion rules as in syntax-directed presentations of the PTS rules for type-checking. Finally, we consider how to use the explicitly scoped meta-variables of PTSCalpha to represent partial proof-terms, and use them to analyse interactive proof construction. This sets up a framework PE in which we are able to study proof-search strategies, type inhabitant enumeration and (higher-order) unification.
Belief-propagation-based joint channel estimation and decoding for spectrally efficient communication over unknown sparse channels
Venue: arXiv cs.IT 2011
Year: 2011

We consider spectrally-efficient communication over a Rayleigh N-block-fading channel with a K- sparse L-length discrete-time impulse response (for 0<K<L<N), where neither the transmitter nor receiver know the channel's coefficients nor its support. Since the high-SNR ergodic capacity of this channel has been shown to obey C(SNR) = (1-K/N)log2(SNR)+O(1), any pilot-aided scheme that sacrifices more than K dimensions per fading block to pilots will be spectrally inefficient. This causes concern about the conventional "compressed channel sensing" approach, which uses O(K polylog L) pilots. In this paper, we demonstrate that practical spectrally-efficient communication is indeed possible. For this, we propose a novel belief-propagation-based reception scheme to use with a standard bit- interleaved coded orthogonal frequency division multiplexing (OFDM) transmitter. In particular, we leverage the "relaxed belief propagation" methodology, which allows us to perform joint sparse-channel estimation and data decoding with only O(LN) complexity. Empirical results show that our receiver achieves the desired capacity pre-log factor of 1 - K/N and performs near genie-aided bounds at both low and high SNR.
Algebraic Notions of Termination
Venue: arXiv cs.LO 2011
Year: 2011

Five algebraic notions of termination are formalised, analysed and compared: wellfoundedness or Noetherity, Löb's formula, absence of infinite iteration, absence of divergence and normalisation. The study is based on modal semirings, which are additively idempotent semirings with forward and backward modal operators. To model infinite behaviours, idempotent semirings are extended to divergence semirings, divergence Kleene algebras and omega algebras. The resulting notions and techniques are used in calculational proofs of classical theorems of rewriting theory. These applications show that modal semirings are powerful tools for reasoning algebraically about the finite and infinite dynamics of programs and transition systems.
On Elementary Loops of Logic Programs
Venue: arXiv cs.AI 2011
Year: 2011

Using the notion of an elementary loop, Gebser and Schaub refined the theorem on loop formulas due to Lin and Zhao by considering loop formulas of elementary loops only. In this article, we reformulate their definition of an elementary loop, extend it to disjunctive programs, and study several properties of elementary loops, including how maximal elementary loops are related to minimal unfounded sets. The results provide useful insights into the stable model semantics in terms of elementary loops. For a nondisjunctive program, using a graph-theoretic characterization of an elementary loop, we show that the problem of recognizing an elementary loop is tractable. On the other hand, we show that the corresponding problem is {\sf coNP}-complete for a disjunctive program. Based on the notion of an elementary loop, we present the class of Head-Elementary-loop-Free (HEF) programs, which strictly generalizes the class of Head-Cycle-Free (HCF) programs due to Ben-Eliyahu and Dechter. Like an HCF program, an HEF program can be turned into an equivalent nondisjunctive program in polynomial time by shifting head atoms into the body.
Linear Codes, Target Function Classes, and Network Computing Capacity
Venue: arXiv cs.IT 2011
Year: 2011

We study the use of linear codes for network computing in single-receiver networks with various classes of target functions of the source messages. Such classes include reducible, injective, semi-injective, and linear target functions over finite fields. Computing capacity bounds and achievability are given with respect to these target function classes for network codes that use routing, linear coding, or nonlinear coding.
Asynchronous Interference Alignment
Venue: arXiv cs.IT 2011
Year: 2011

A constant K-user interference channel in which the users are not symbol-synchronous is considered. It is shown that the asynchronism among the users facilitates aligning interfering signals at each receiver node while it does not affect the total number of degrees of freedom (DoF) of the channel. To achieve the total K/2 DoF of the channel when single antenna nodes are used, a novel practical interference alignment scheme is proposed wherein the alignment task is performed with the help of asynchronous delays which inherently exist among the received signals at each receiver node. When each node is equipped with M > 1 antennas, it is argued that the same alignment scheme is sufficient to achieve the total MK/2 DoF of the medium when all links between collocated antennas experience the same asynchronous delay.
A Round-Robin Tournament of the Iterated Prisoner's Dilemma with Complete Memory-Size-Three Strategies
Venue: arXiv cs.GT 2011
Year: 2011

In this paper the results of a simulation of a prisoner's dilemma robin-round tournament are presented. In the tournament each participating strategy plays an iterated prisoner's dilemma against each other strategy (round-robin) and as a variant also against itself. The participants of a tournament are all strategies that are deterministic and have the same size of memory with regard to their own and their opponent's past actions: up to three most recent actions of their opponent and up to two most recent actions of their own. A focus is set on the investigation of the influence of the number of iterations, details of the payoff matrix, and the influence of memory size. The main result is that for the tournament as carried out here, different strategies emerge as winners for different payoff matrices, even for different payoff matrices being similar judged on if they fulfill relations T + S = P + R or 2R > T + S. As a consequence of this result it is suggested that whenever the iterated prisoner's dilemma is used to model a real system that does not explicitly fix the payoff matrix, one should check if conclusions remain valid, when a different payoff matrix is used.