OpenRaiser/Intern-Atlas huggingface dataset:
AWGN Channel under Time-Varying Amplitude Constraints with Causal Information at the Transmitter
Venue: arXiv cs.IT 2012
Year: 2012

We consider the classical AWGN channel where the channel input is constrained to an amplitude constraint that stochastically varies at each channel use, independent of the message. This is an abstraction of an energy harvesting transmitter where the code symbol energy at each channel use is determined by an exogenous energy arrival process and there is no battery for energy storage. At each channel use, an independent realization of the amplitude constraint process is observed by the transmitter causally. This scenario is a state-dependent channel with perfect causal state information at the transmitter. We derive the capacity of this channel using Shannon's coding scheme with causal state information. We prove that the code symbols must be selected from a finite set in the capacity achieving scheme, as in the case of Smith. We numerically study the binary on-off energy arrivals where the amplitude constraint is either zero or a non-zero constant.
Merging Belief Propagation and the Mean Field Approximation: A Free Energy Approach
Venue: arXiv cs.IT 2012
Year: 2012

We present a joint message passing approach that combines belief propagation and the mean field approximation. Our analysis is based on the region-based free energy approximation method proposed by Yedidia et al. We show that the message passing fixed-point equations obtained with this combination correspond to stationary points of a constrained region-based free energy approximation. Moreover, we present a convergent implementation of these message passing fixedpoint equations provided that the underlying factor graph fulfills certain technical conditions. In addition, we show how to include hard constraints in the part of the factor graph corresponding to belief propagation. Finally, we demonstrate an application of our method to iterative channel estimation and decoding in an orthogonal frequency division multiplexing (OFDM) system.
Linear Nearest Neighbor Synthesis of Reversible Circuits by Graph Partitioning
Venue: arXiv cs.ET 2012
Year: 2012

Linear Nearest Neighbor (LNN) synthesis in reversible circuits has emerged as an important issue in terms of technological implementation for quantum computation. The objective is to obtain a LNN architecture with minimum gate cost. As achieving optimal synthesis is a hard problem, heuristic methods have been proposed in recent literature. In this work we present a graph partitioning based approach for LNN synthesis with reduction in circuit cost. In particular, the number of SWAP gates required to convert a given gate-level quantum circuit to its equivalent LNN configuration is minimized. Our algorithm determines the reordering of indices of the qubit line(s) for both single control and multiple controlled gates. Experimental results for placing the target qubits of Multiple Controlled Toffoli (MCT) library of benchmark circuits show a significant reduction in gate count and quantum gate cost compared to those of related research works.
Multi-timescale Nexting in a Reinforcement Learning Robot
Venue: arXiv cs.LG 2012
Year: 2012

The term "nexting" has been used by psychologists to refer to the propensity of people and many other animals to continually predict what will happen next in an immediate, local, and personal sense. The ability to "next" constitutes a basic kind of awareness and knowledge of one's environment. In this paper we present results with a robot that learns to next in real time, predicting thousands of features of the world's state, including all sensory inputs, at timescales from 0.1 to 8 seconds. This was achieved by treating each state feature as a reward-like target and applying temporal-difference methods to learn a corresponding value function with a discount rate corresponding to the timescale. We show that two thousand predictions, each dependent on six thousand state features, can be learned and updated online at better than 10Hz on a laptop computer, using the standard TD(lambda) algorithm with linear function approximation. We show that this approach is efficient enough to be practical, with most of the learning complete within 30 minutes. We also show that a single tile-coded feature representation suffices to accurately predict many different signals at a significant range of timescales. Finally, we show that the accuracy of our learned predictions compares favorably with the optimal off-line solution.
On Optimal Link Activation with Interference Cancellation in Wireless Networking
Venue: arXiv cs.IT 2012
Year: 2012

A fundamental aspect in performance engineering of wireless networks is optimizing the set of links that can be concurrently activated to meet given signal-to-interference-and-noise ratio (SINR) thresholds. The solution of this combinatorial problem is the key element in scheduling and cross-layer resource management. Previous works on link activation assume single-user decoding receivers, that treat interference in the same way as noise. In this paper, we assume multiuser decoding receivers, which can cancel strongly interfering signals. As a result, in contrast to classical spatial reuse, links being close to each other are more likely to be active simultaneously. Our goal here is to deliver a comprehensive theoretical and numerical study on optimal link activation under this novel setup, in order to provide insight into the gains from adopting interference cancellation. We therefore consider the optimal problem setting of successive interference cancellation (SIC), as well as the simpler, yet instructive, case of parallel interference cancellation (PIC). We prove that both problems are NP-hard and develop compact integer linear programming formulations that enable us to approach the global optimum solutions. We provide an extensive numerical performance evaluation, indicating that for low to medium SINR thresholds the improvement is quite substantial, especially with SIC, whereas for high SINR thresholds the improvement diminishes and both schemes perform equally well.
Optimal Merging Algorithms for Lossless Codes with Generalized Criteria
Venue: arXiv cs.IT 2012
Year: 2012

This paper presents lossless prefix codes optimized with respect to a pay-off criterion consisting of a convex combination of maximum codeword length and average codeword length. The optimal codeword lengths obtained are based on a new coding algorithm which transforms the initial source probability vector into a new probability vector according to a merging rule. The coding algorithm is equivalent to a partition of the source alphabet into disjoint sets on which a new transformed probability vector is defined as a function of the initial source probability vector and a scalar parameter. The pay-off criterion considered encompasses a trade-off between maximum and average codeword length; it is related to a pay-off criterion consisting of a convex combination of average codeword length and average of an exponential function of the codeword length, and to an average codeword length pay-off criterion subject to a limited length constraint. A special case of the first related pay-off is connected to coding problems involving source probability uncertainty and codeword overflow probability, while the second related pay-off compliments limited length Huffman coding algorithms.
Extended Combinatorial Constructions for Peer-to-peer User-Private Information Retrieval
Venue: arXiv cs.CR 2012
Year: 2012

We consider user-private information retrieval (UPIR), an interesting alternative to private information retrieval (PIR) introduced by Domingo-Ferrer et al. In UPIR, the database knows which records have been retrieved, but does not know the identity of the query issuer. The goal of UPIR is to disguise user profiles from the database. Domingo-Ferrer et al.\ focus on using a peer-to-peer community to construct a UPIR scheme, which we term P2P UPIR. In this paper, we establish a strengthened model for P2P UPIR and clarify the privacy goals of such schemes using standard terminology from the field of privacy research. In particular, we argue that any solution providing privacy against the database should attempt to minimize any corresponding loss of privacy against other users. We give an analysis of existing schemes, including a new attack by the database. Finally, we introduce and analyze two new protocols. Whereas previous work focuses on a special type of combinatorial design known as a configuration, our protocols make use of more general designs. This allows for flexibility in protocol set-up, allowing for a choice between having a dynamic scheme (in which users are permitted to enter and leave the system), or providing increased privacy against other users.
Energy and Spectral Efficiency of Very Large Multiuser MIMO Systems
Venue: arXiv cs.IT 2012
Year: 2012

A multiplicity of autonomous terminals simultaneously transmits data streams to a compact array of antennas. The array uses imperfect channel-state information derived from transmitted pilots to extract the individual data streams. The power radiated by the terminals can be made inversely proportional to the square-root of the number of base station antennas with no reduction in performance. In contrast if perfect channel-state information were available the power could be made inversely proportional to the number of antennas. Lower capacity bounds for maximum-ratio combining (MRC), zero-forcing (ZF) and minimum mean-square error (MMSE) detection are derived. A MRC receiver normally performs worse than ZF and MMSE. However as power levels are reduced, the cross-talk introduced by the inferior maximum-ratio receiver eventually falls below the noise level and this simple receiver becomes a viable option. The tradeoff between the energy efficiency (as measured in bits/J) and spectral efficiency (as measured in bits/channel use/terminal) is quantified. It is shown that the use of moderately large antenna arrays can improve the spectral and energy efficiency with orders of magnitude compared to a single-antenna system.
The Price of Matching Selfish Vertices
Venue: arXiv cs.CG 2012
Year: 2012

We analyze the setting of minimum-cost perfect matchings with selfish vertices through the price of anarchy (PoA) and price of stability (PoS) lens. The underlying solution concept used for this analysis is the Gale-Shapley stable matching notion, where the preferences are determined so that each player (vertex) wishes to minimize the cost of her own matching edge.
Ranking and clustering of nodes in networks with smart teleportation
Venue: arXiv cs.SI 2012
Year: 2012

Random teleportation is a necessary evil for ranking and clustering directed networks based on random walks. Teleportation enables ergodic solutions, but the solutions must necessarily depend on the exact implementation and parametrization of the teleportation. For example, in the commonly used PageRank algorithm, the teleportation rate must trade off a heavily biased solution with a uniform solution. Here we show that teleportation to links rather than nodes enables a much smoother trade-off and effectively more robust results. We also show that, by not recording the teleportation steps of the random walker, we can further reduce the effect of teleportation with dramatic effects on clustering.
Search space analysis with Wang-Landau sampling and slow adaptive walks
Venue: arXiv cs.NE 2012
Year: 2012

Two complementary techniques for analyzing search spaces are proposed: (i) an algorithm to detect search points with potential to be local optima; and (ii) a slightly adjusted Wang-Landau sampling algorithm to explore larger search spaces. The detection algorithm assumes that local optima are points which are easier to reach and harder to leave by a slow adaptive walker. A slow adaptive walker moves to a nearest fitter point. Thus, points with larger outgoing step sizes relative to incoming step sizes are marked using the local optima score formulae as potential local optima points (PLOPs). Defining local optima in these more general terms allows their detection within the closure of a subset of a search space, and the sampling of a search space unshackled by a particular move set. Tests are done with NK and HIFF problems to confirm that PLOPs detected in the manner proposed retain characteristics of local optima, and that the adjusted Wang-Landau samples are more representative of the search space than samples produced by choosing points uniformly at random. While our approach shows promise, more needs to be done to reduce its computation cost that it may pave a way toward analyzing larger search spaces of practical meaning.
Testing Low Complexity Affine-Invariant Properties
Venue: arXiv cs.CC 2012
Year: 2012

Invariance with respect to linear or affine transformations of the domain is arguably the most common symmetry exhibited by natural algebraic properties. In this work, we show that any low complexity affine-invariant property of multivariate functions over finite fields is testable with a constant number of queries. This immediately reproves, for instance, that the Reed-Muller code over F_p of degree d < p is testable, with an argument that uses no detailed algebraic information about polynomials except that low degree is preserved by composition with affine maps. The complexity of an affine-invariant property P refers to the maximum complexity, as defined by Green and Tao (Ann. Math. 2008), of the sets of linear forms used to characterize P. A more precise statement of our main result is that for any fixed prime p >=2 and fixed integer R >= 2, any affine-invariant property P of functions f: F_p^n -> [R] is testable, assuming the complexity of the property is less than p. Our proof involves developing analogs of graph-theoretic techniques in an algebraic setting, using tools from higher-order Fourier analysis.
Lower bounding edit distances between permutations
Venue: arXiv cs.DM 2012
Year: 2012

A number of fields, including the study of genome rearrangements and the design of interconnection networks, deal with the connected problems of sorting permutations in "as few moves as possible", using a given set of allowed operations, or computing the number of moves the sorting process requires, often referred to as the \emph{distance} of the permutation. These operations often act on just one or two segments of the permutation, e.g. by reversing one segment or exchanging two segments. The \emph{cycle graph} of the permutation to sort is a fundamental tool in the theory of genome rearrangements, and has proved useful in settling the complexity of many variants of the above problems. In this paper, we present an algebraic reinterpretation of the cycle graph of a permutation $π$ as an even permutation $\barπ$, and show how to reformulate our sorting problems in terms of particular factorisations of the latter permutation. Using our framework, we recover known results in a simple and unified way, and obtain a new lower bound on the \emph{prefix transposition distance} (where a \emph{prefix transposition} displaces the initial segment of a permutation), which is shown to outperform previous results. Moreover, we use our approach to improve the best known lower bound on the \emph{prefix transposition diameter} from $2n/3$ to $\lfloor3n/4\rfloor$, and investigate a few relations between some statistics on $π$ and $\barπ$.
Continuity in Information Algebras
Venue: arXiv cs.AI 2012
Year: 2012

In this paper, the continuity and strong continuity in domain-free information algebras and labeled information algebras are introduced respectively. A more general concept of continuous function which is defined between two domain-free continuous information algebras is presented. It is shown that, with the operations combination and focusing, the set of all continuous functions between two domain-free s-continuous information algebras forms a new s-continuous information algebra. By studying the relationship between domain-free information algebras and labeled information algebras, it is demonstrated that they do correspond to each other on s-compactness.
Open Bisimulation for Quantum Processes
Venue: arXiv cs.LO 2012
Year: 2012

Quantum processes describe concurrent communicating systems that may involve quantum information. We propose a notion of open bisimulation for quantum processes and show that it provides both a sound and complete proof methodology for a natural extensional behavioural equivalence between quantum processes. We also give a modal characterisation of open bisimulation, by extending the Hennessy-Milner logic to a quantum setting.
The RegularGcc Matrix Constraint
Venue: arXiv cs.AI 2012
Year: 2012

We study propagation of the RegularGcc global constraint. This ensures that each row of a matrix of decision variables satisfies a Regular constraint, and each column satisfies a Gcc constraint. On the negative side, we prove that propagation is NP-hard even under some strong restrictions (e.g. just 3 values, just 4 states in the automaton, or just 5 columns to the matrix). On the positive side, we identify two cases where propagation is fixed parameter tractable. In addition, we show how to improve propagation over a simple decomposition into separate Regular and Gcc constraints by identifying some necessary but insufficient conditions for a solution. We enforce these conditions with some additional weighted row automata. Experimental results demonstrate the potential of these methods on some standard benchmark problems.
LTL to Büchi Automata Translation: Fast and More Deterministic
Venue: arXiv cs.FL 2012
Year: 2012

We introduce improvements in the algorithm by Gastin and Oddoux translating LTL formulae into Büchi automata via very weak alternating co-Büchi automata and generalized Büchi automata. Several improvements are based on specific properties of any formula where each branch of its syntax tree contains at least one eventually operator and at least one always operator. These changes usually result in faster translations and smaller automata. Other improvements reduce non-determinism in the produced automata. In fact, we modified all the steps of the original algorithm and its implementation known as LTL2BA. Experimental results show that our modifications are real improvements. Their implementations within an LTL2BA translation made LTL2BA very competitive with the current version of SPOT, sometimes outperforming it substantially.
Performance of Modeling wireless networks in realistic environment
Venue: arXiv cs.NI 2012
Year: 2012

A wireless network is realized by mobile devices which communicate over radio channels. Since, experiments of real life problem with real devices are very difficult, simulation is used very often. Among many other important properties that have to be defined for simulative experiments, the mobility model and the radio propagation model have to be selected carefully. Both have strong impact on the performance of mobile wireless networks, e.g., the performance of routing protocols varies with these models. There are many mobility and radio propagation models proposed in literature. Each of them was developed with different objectives and is not suited for every physical scenario. The radio propagation models used in common wireless network simulators, in general researcher consider simple radio propagation models and neglect obstacles in the propagation environment. In this paper, we study the performance of wireless networks simulation by consider different Radio propagation models with considering obstacles in the propagation environment. In this paper we analyzed the performance of wireless networks by OPNET Modeler .In this paper we quantify the parameters such as throughput, packet received attenuation.
Applicative Bisimulations for Delimited-Control Operators
Venue: arXiv cs.PL 2012
Year: 2012

We develop a behavioral theory for the untyped call-by-value lambda calculus extended with the delimited-control operators shift and reset. For this calculus, we discuss the possible observable behaviors and we define an applicative bisimilarity that characterizes contextual equivalence. We then compare the applicative bisimilarity and the CPS equivalence, a relation on terms often used in studies of control operators. In the process, we illustrate how bisimilarity can be used to prove equivalence of terms with delimited-control effects.
Cops and Invisible Robbers: the Cost of Drunkenness
Venue: arXiv cs.DM 2012
Year: 2012

We examine a version of the Cops and Robber (CR) game in which the robber is invisible, i.e., the cops do not know his location until they capture him. Apparently this game (CiR) has received little attention in the CR literature. We examine two variants: in the first the robber is adversarial (he actively tries to avoid capture); in the second he is drunk (he performs a random walk). Our goal in this paper is to study the invisible Cost of Drunkenness (iCOD), which is defined as the ratio ct_i(G)/dct_i(G), with ct_i(G) and dct_i(G) being the expected capture times in the adversarial and drunk CiR variants, respectively. We show that these capture times are well defined, using game theory for the adversarial case and partially observable Markov decision processes (POMDP) for the drunk case. We give exact asymptotic values of iCOD for several special graph families such as $d$-regular trees, give some bounds for grids, and provide general upper and lower bounds for general classes of graphs. We also give an infinite family of graphs showing that iCOD can be arbitrarily close to any value in [2,infinty). Finally, we briefly examine one more CiR variant, in which the robber is invisible and "infinitely fast"; we argue that this variant is significantly different from the Graph Search game, despite several similarities between the two games.
A Novel Error Correcting System Based on Product Codes for Future Magnetic Recording Channels
Venue: arXiv cs.IT 2012
Year: 2012

We propose a novel construction of product codes for high-density magnetic recording based on binary low-density parity check (LDPC) codes and binary image of Reed Solomon (RS) codes. Moreover, two novel algorithms are proposed to decode the codes in the presence of both AWGN errors and scattered hard errors (SHEs). Simulation results show that at a bit error rate (bER) of approximately 10^-8, our method allows improving the error performance by approximately 1.9dB compared with that of a hard decision decoder of RS codes of the same length and code rate. For the mixed error channel including random noises and SHEs, the signal-to-noise ratio (SNR) is set at 5dB and 150 to 400 SHEs are randomly generated. The bit error performance of the proposed product code shows a significant improvement over that of equivalent random LDPC codes or serial concatenation of LDPC and RS codes.
Abstracting Runtime Heaps for Program Understanding
Venue: arXiv cs.PL 2012
Year: 2012

Modern programming environments provide extensive support for inspecting, analyzing, and testing programs based on the algorithmic structure of a program. Unfortunately, support for inspecting and understanding runtime data structures during execution is typically much more limited. This paper provides a general purpose technique for abstracting and summarizing entire runtime heaps. We describe the abstract heap model and the associated algorithms for transforming a concrete heap dump into the corresponding abstract model as well as algorithms for merging, comparing, and computing changes between abstract models. The abstract model is designed to emphasize high-level concepts about heap-based data structures, such as shape and size, as well as relationships between heap structures, such as sharing and connectivity. We demonstrate the utility and computational tractability of the abstract heap model by building a memory profiler. We then use this tool to check for, pinpoint, and correct sources of memory bloat from a suite of programs from DaCapo.