OpenRaiser/Intern-Atlas huggingface dataset:
The Diversity-Multiplexing-Delay Tradeoff in MIMO Multihop Networks with ARQ
Venue: arXiv cs.IT 2011
Year: 2011

We study the tradeoff between reliability, data rate, and delay for half-duplex MIMO multihop networks that utilize the automatic-retransmission-request (ARQ) protocol both in the asymptotic high signal-to-noise ratio (SNR) regime and in the finite SNR regime. We propose novel ARQ protocol designs that optimize these tradeoffs. We first derive the diversity-multiplexing-delay tradeoff (DMDT) in the high SNR regime, where the delay is caused only by retransmissions. This asymptotic DMDT shows that the performance of an N node network is limited by the weakest three-node sub-network, and the performance of a three-node sub-network is determined by its weakest link, and, hence, the optimal ARQ protocol needs to equalize the performance on each link by allocating ARQ window sizes optimally. This equalization is captured through a novel Variable Block-Length (VBL) ARQ protocol that we propose, which achieves the optimal DMDT. We then consider the DMDT in the finite SNR regime, where the delay is caused by both the ARQ retransmissions and queueing. We characterize the finite SNR DMDT of the fixed ARQ protocol, when an end-to-end delay constraint is imposed, by deriving the probability of message error using an approach that couples the information outage analysis with the queueing network analysis. The exponent of the probability of deadline violation demonstrates that the system performance is again limited by the weakest three-node sub-network. The queueing delay changes the consideration for optimal ARQ design: more retransmissions reduce decoding error by lowering the information outage probability, but may also increase message drop rate due to delay deadline violations. Hence, the optimal ARQ should balance link performance while avoiding significant delay.
Self-Optimized OFDMA via Multiple Stackelberg Leader Equilibrium
Venue: arXiv cs.IT 2011
Year: 2011

The challenge of self-optimization for orthogonal frequency-division multiple-access (OFDMA) interference channels is that users inherently compete harmfully and simultaneous water-filling (WF) would lead to a Pareto-inefficient equilibrium. To overcome this, we first introduce the role of environmental interference derivative in the WF optimization of the interactive OFDMA game and then study the environmental interference derivative properties of Stackelberg equilibrium (SE). Such properties provide important insights to devise free OFDMA games for achieving various SEs, realizable by simultaneous WF regulated by specifically chosen operational interference derivatives. We also present a definition of all-Stackelberg-leader equilibrium (ASE) where users are all foresighted to each other, albeit each with only local channel state information (CSI), and can thus most effectively reconcile their competition to maximize the user rates. We show that under certain environmental conditions, the free games are both unique and optimal. Simulation results reveal that our distributed ASE game achieves the performance very close to the near-optimal centralized iterative spectrum balancing (ISB) method in [5].
Differential properties of functions x -> x^{2^t-1} -- extended version
Venue: arXiv cs.CR 2011
Year: 2011

We provide an extensive study of the differential properties of the functions $x\mapsto x^{2^t-1}$ over $\F$, for $2 \leq t \leq n-1$. We notably show that the differential spectra of these functions are determined by the number of roots of the linear polynomials $x^{2^t}+bx^2+(b+1)x$ where $b$ varies in $\F$.We prove a strong relationship between the differential spectra of $x\mapsto x^{2^t-1}$ and $x\mapsto x^{2^{s}-1}$ for $s= n-t+1$. As a direct consequence, this result enlightens a connection between the differential properties of the cube function and of the inverse function. We also determine the complete differential spectra of $x \mapsto x^7$ by means of the value of some Kloosterman sums, and of $x \mapsto x^{2^t-1}$ for $t \in \{\lfloor n/2\rfloor, \lceil n/2\rceil+1, n-2\}$.
A Classification Framework for Web Browser Cross-Context Communication
Venue: arXiv cs.SE 2011
Year: 2011

Demand for more advanced Web applications is the driving force behind Web browser evolution. Recent requirements for Rich Internet Applications, such as mashing-up data and background processing, are emphasizing the need for building and executing Web applications as a coordination of browser execution contexts. Since development of such Web applications depends on cross-context communication, many browser primitives and client-side frameworks have been developed to support this communication. In this paper we present a systematization of cross-context communication systems for Web browsers. Based on an analysis of previous research, requirements for modern Web applications and existing systems, we extract a framework for classifying cross-context communica-tion systems. Using the framework, we evaluate the current ecosystem of cross-context communication and outline directions for future Web research and engineering.
Constraint Satisfaction Problems Parameterized Above or Below Tight Bounds: A Survey
Venue: arXiv cs.DS 2011
Year: 2011

We consider constraint satisfaction problems parameterized above or below tight bounds. One example is MaxSat parameterized above $m/2$: given a CNF formula $F$ with $m$ clauses, decide whether there is a truth assignment that satisfies at least $m/2+k$ clauses, where $k$ is the parameter. Among other problems we deal with are MaxLin2-AA (given a system of linear equations over $\mathbb{F}_2$ in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least $W/2+k$, where $W$ is the total weight of all equations), Max-$r$-Lin2-AA (the same as MaxLin2-AA, but each equation has at most $r$ variables, where $r$ is a constant) and Max-$r$-Sat-AA (given a CNF formula $F$ with $m$ clauses in which each clause has at most $r$ literals, decide whether there is a truth assignment satisfying at least $\sum_{i=1}^m(1-2^{r_i})+k$ clauses, where $k$ is the parameter, $r_i$ is the number of literals in Clause $i$, and $r$ is a constant). We also consider Max-$r$-CSP-AA, a natural generalization of both Max-$r$-Lin2-AA and Max-$r$-Sat-AA, order (or, permutation) constraint satisfaction problems of arities 2 and 3 parameterized above the average value and some other problems related to MaxSat. We discuss results, both polynomial kernels and parameterized algorithms, obtained for the problems mainly in the last few years as well as some open questions.
Some Measurements of Nullable and Non-Nullable Parameter Declarations in Relation to Software Malleability
Venue: arXiv cs.PL 2011
Year: 2011

The usual advantages put forward for including nullability declarations in the type systems of programming languages are that they improve program reliability or performance. But there is another, entirely different, reason for doing so. In the right context, this information enables the software artifacts we produce, the objects and methods, to exhibit much greater malleability. For declaratively typed languages, we can obtain greater software malleability by extending the model of method call so that assurance of a method's availability can be provided by any non-nullable parameter, not simply the target parameter, and by allowing the method's implementation to reside in classes or objects other than the target.. This paper examines the question of whether this hypothetical improvement in software malleability is consistent with existing programming practice by examining the question of the extent to which methods in existing software have multiplicities of non-nullable parameters. The circumstance occurs frequently enough to provide an important reason to introduce declarations of nullability into programming languages.
Non-trivial two-armed partial-monitoring games are bandits
Venue: arXiv cs.LG 2011
Year: 2011

We consider online learning in partial-monitoring games against an oblivious adversary. We show that when the number of actions available to the learner is two and the game is nontrivial then it is reducible to a bandit-like game and thus the minimax regret is $Θ(\sqrt{T})$.
Robust Stackelberg game in communication systems
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies multi-user communication systems with two groups of users: leaders which possess system information, and followers which have no system information using the formulation of Stackelberg games. In such games, the leaders play and choose their actions based on their information about the system and the followers choose their actions myopically according to their observations of the aggregate impact of other users. However, obtaining the exact value of these parameters is not practical in communication systems. To study the effect of uncertainty and preserve the players' utilities in these conditions, we introduce a robust equilibrium for Stackelberg games. In this framework, the leaders' information and the followers' observations are uncertain parameters, and the leaders and the followers choose their actions by solving the worst-case robust optimizations. We show that the followers' uncertain parameters always increase the leaders' utilities and decrease the followers' utilities. Conversely, the leaders' uncertain information reduces the leaders' utilities and increases the followers' utilities. We illustrate our theoretical results with the numerical results obtained based on the power control games in the interference channels.
RBO Protocol: Broadcasting Huge Databases for Tiny Receivers
Venue: arXiv cs.DS 2011
Year: 2011

We propose a protocol (called RBO) for broadcasting long streams of single-packet messages over radio channel for tiny, battery powered, receivers. The messages are labeled by the keys from some linearly ordered set. The sender repeatedly broadcasts a sequence of many (possibly millions) of messages, while each receiver is interested in reception of a message with a specified key within this sequence. The transmission is arranged so that the receiver can wake up in arbitrary moment and find the nearest transmission of its searched message. Even if it does not know the position of the message in the sequence, it needs only to receive a small number of (the headers of) other messages to locate it properly. Thus it can save energy by keeping the radio switched off most of the time. We show that bit-reversal permutation has "recursive bisection properties" and, as a consequence, RBO can be implemented very efficiently with only constant number of $\log_2 n$-bit variables, where $n$ is the total number of messages in the sequence. The total number of the required receptions is at most $2\log_2 n +2$ in the model with perfect synchronization. The basic procedure of RBO (computation of the time slot for the next required reception) requires only $O(\log^3 n)$ bit-wise operations. We propose implementation mechanisms for realistic model (with imperfect synchronization), for operating systems (such as e.g. TinyOS).
CD-PHY: Physical Layer Security in Wireless Networks through Constellation Diversity
Venue: arXiv cs.CR 2011
Year: 2011

A common approach for introducing security at the physical layer is to rely on the channel variations of the wireless environment. This type of approach is not always suitable for wireless networks where the channel remains static for most of the network lifetime. For these scenarios, a channel independent physical layer security measure is more appropriate which will rely on a secret known to the sender and the receiver but not to the eavesdropper. In this paper, we propose CD-PHY, a physical layer security technique that exploits the constellation diversity of wireless networks which is independent of the channel variations. The sender and the receiver use a custom bit sequence to constellation symbol mapping to secure the physical layer communication which is not known a priori to the eavesdropper. Through theoretical modeling and experimental simulation, we show that this information theoretic construct can achieve Shannon secrecy and any brute force attack from the eavesdropper incurs high overhead and minuscule probability of success. Our results also show that the high bit error rate also makes decoding practically infeasible for the eavesdropper, thus securing the communication between the sender and receiver.
Transfer of semantics from argumentation frameworks to logic programming A preliminary report
Venue: arXiv cs.LO 2011
Year: 2011

There are various interesting semantics' (extensions) designed for argumentation frameworks. They enable to assign a meaning, e.g., to odd-length cycles. Our main motivation is to transfer semantics' proposed by Baroni, Giacomin and Guida for argumetation frameworks with odd-length cycles to logic programs with odd-length cycles through default negation. The developed construction is even stronger. For a given logic program an argumentation framework is defined. The construction enables to transfer each semantics of the resulting argumentation framework to a semantics of the given logic program. Weak points of the construction are discussed and some future continuations of this approach are outlined.
Un metodo estable para la evaluacion de la complejidad algoritmica de cadenas cortas
Venue: arXiv cs.CC 2011
Year: 2011

It is discussed and surveyed a numerical method proposed before, that alternative to the usual compression method, provides an approximation to the algorithmic (Kolmogorov) complexity, particularly useful for short strings for which compression methods simply fail. The method shows to be stable enough and useful to conceive and compare patterns in an algorithmic models. (article in Spanish)
Green Cellular Networks: A Survey, Some Research Issues and Challenges
Venue: arXiv cs.NI 2011
Year: 2011

Energy efficiency in cellular networks is a growing concern for cellular operators to not only maintain profitability, but also to reduce the overall environment effects. This emerging trend of achieving energy efficiency in cellular networks is motivating the standardization authorities and network operators to continuously explore future technologies in order to bring improvements in the entire network infrastructure. In this article, we present a brief survey of methods to improve the power efficiency of cellular networks, explore some research issues and challenges and suggest some techniques to enable an energy efficient or "green" cellular network. Since base stations consume a maximum portion of the total energy used in a cellular system, we will first provide a comprehensive survey on techniques to obtain energy savings in base stations. Next, we discuss how heterogeneous network deployment based on micro, pico and femto-cells can be used to achieve this goal. Since cognitive radio and cooperative relaying are undisputed future technologies in this regard, we propose a research vision to make these technologies more energy efficient. Lastly, we explore some broader perspectives in realizing a "green" cellular network technology
Hierarchical N-body simulations with auto-tuning for heterogeneous systems
Venue: arXiv cs.NA 2011
Year: 2011

With the current hybridization of treecodes and FMMs, combined with auto-tuning capabilities on heterogeneous architectures, the flexibility of fast N-body methods has been greatly enhanced. These features are a requirement to developing a black-box software library for fast N-body algorithms on heterogeneous systems, which is our immediate goal.
A Rejoinder on Energy versus Impact Indicators
Venue: arXiv cs.DL 2011
Year: 2011

Citation distributions are so skewed that using the mean or any other central tendency measure is ill-advised. Unlike G. Prathap's scalar measures (Energy, Exergy, and Entropy or EEE), the Integrated Impact Indicator (I3) is based on non-parametric statistics using the (100) percentiles of the distribution. Observed values can be tested against expected ones; impact can be qualified at the article level and then aggregated.
Edge-preserving self-healing: keeping network backbones densely connected
Venue: arXiv cs.DC 2011
Year: 2011

Healing algorithms play a crucial part in distributed P2P networks where failures occur continuously and frequently. Several self-healing algorithms have been suggested recently [IPDPS'08, PODC'08, PODC'09, PODC'11] in a line of work that has yielded gradual improvements in the properties ensured on the graph. This work motivates a strong general phenomenon of edge-preserving healing that aims at obtaining self-healing algorithms with the constraint that all original edges in the graph (not deleted by the adversary), be retained in every intermediate graph. The previous algorithms, in their nascent form, are not explicitly edge preserving. In this paper, we show they can be suitably modified (We introduce Xheal+, an edge-preserving version of Xheal[PODC'11]). Towards this end, we present a general self-healing model that unifies the previous models. The main contribution of this paper is not in the technical complexity, rather in the simplicity with which the edge-preserving property can be ensured and the message that this is a crucial property with several benefits. In particular, we highlight this by showing that, almost as an immediate corollary, subgraph densities are preserved or increased. Maintaining density is a notion motivated by the fact that in certain distributed networks, certain nodes may require and initially have a larger number of inter-connections. It is vital that a healing algorithm, even amidst failures, respect these requirements. Our suggested modifications yield such subgraph density preservation as a by product. In addition, edge preservation helps maintain any subgraph induced property that is monotonic. Also, algorithms that are edge-preserving require minimal alteration of edges which can be an expensive cost in healing - something that has not been modeled in any of the past work.
Proof System for Plan Verification under 0-Approximation Semantics
Venue: arXiv cs.AI 2011
Year: 2011

In this paper a proof system is developed for plan verification problems $\{X\}c\{Y\}$ and $\{X\}c\{KW p\}$ under 0-approximation semantics for ${\mathcal A}_K$. Here, for a plan $c$, two sets $X,Y$ of fluent literals, and a literal $p$, $\{X\}c\{Y\}$ (resp. $\{X\}c\{KW p\}$) means that all literals of $Y$ become true (resp. $p$ becomes known) after executing $c$ in any initial state in which all literals in $X$ are true.Then, soundness and completeness are proved. The proof system allows verifying plans and generating plans as well.
Optimal Deterministic Polynomial-Time Data Exchange for Omniscience
Venue: arXiv cs.IT 2011
Year: 2011

We study the problem of constructing a deterministic polynomial time algorithm that achieves omniscience, in a rate-optimal manner, among a set of users that are interested in a common file but each has only partial knowledge about it as side-information. Assuming that the collective information among all the users is sufficient to allow the reconstruction of the entire file, the goal is to minimize the (possibly weighted) amount of bits that these users need to exchange over a noiseless public channel in order for all of them to learn the entire file. Using established connections to the multi-terminal secrecy problem, our algorithm also implies a polynomial-time method for constructing a maximum size secret shared key in the presence of an eavesdropper. We consider the following types of side-information settings: (i) side information in the form of uncoded fragments/packets of the file, where the users' side-information consists of subsets of the file; (ii) side information in the form of linearly correlated packets, where the users have access to linear combinations of the file packets; and (iii) the general setting where the the users' side-information has an arbitrary (i.i.d.) correlation structure. Building on results from combinatorial optimization, we provide a polynomial-time algorithm (in the number of users) that, first finds the optimal rate allocations among these users, then determines an explicit transmission scheme (i.e., a description of which user should transmit what information) for cases (i) and (ii).
Optimizing Network Topology to Reduce Aggregate Traffic in Systems of Mobile Robots
Venue: arXiv cs.NI 2011
Year: 2011

Systems of networked mobile robots, such as unmanned aerial or ground vehicles, will play important roles in future military and commercial applications. The communications for such systems will typically be over wireless links and may require that the robots form an ad hoc network and communicate on a peer-to-peer basis. In this paper, we consider the problem of optimizing the network topology to minimize the total traffic in a network required to support a given set of data flows under constraints on the amount of movement possible at each mobile robot. In this paper, we consider a subclass of this problem in which the initial and final topologies are trees, and the movement restrictions are given in terms of the number of edges in the graph that must be traversed. We develop algorithms to optimize the network topology while maintaining network connectivity during the topology reconfiguration process. Our topology reconfiguration algorithm uses the concept of prefix labelling and routing to move nodes through the network while maintaining network connectivity. We develop two algorithms to determine the final network topology: an optimal, but computationally complex algorithm, and a greedy suboptimal algorithm that has much lower complexity. We present simulation results to compare the performance of these algorithm.
Projective Parameterized Linear Codes Arising from some Matrices and their Main Parameters
Venue: arXiv cs.IT 2011
Year: 2011

In this paper we will estimate the main parameters of some evaluation codes which are known as projective parameterized codes. We will find the length of these codes and we will give a formula for the dimension in terms of the Hilbert function associated to two ideals, one of them being the vanishing ideal of the projective torus. Also we will find an upper bound for the minimum distance and, in some cases, we will give some lower bounds for the regularity index and the minimum distance. These lower bounds work in several cases, particularly for any projective parameterized code associated to the incidence matrix of uniform clutters and then they work in the case of graphs.
Every Formula-Based Logic Program Has a Least Infinite-Valued Model
Venue: arXiv cs.LO 2011
Year: 2011

Every definite logic program has as its meaning a least Herbrand model with respect to the program-independent ordering "set-inclusion". In the case of normal logic programs there do not exist least models in general. However, according to a recent approach by Rondogiannis and Wadge, who consider infinite-valued models, every normal logic program does have a least model with respect to a program-independent ordering. We show that this approach can be extended to formula-based logic programs (i.e., finite sets of rules of the form A\leftarrowF where A is an atom and F an arbitrary first-order formula). We construct for a given program P an interpretation M_P and show that it is the least of all models of P. Keywords: Logic programming, semantics of programs, negation-as-failure, infinite-valued logics, set theory