OpenRaiser/Intern-Atlas huggingface dataset:
Expurgated Random-Coding Ensembles: Exponents, Refinements and Connections
Venue: arXiv cs.IT 2014
Year: 2014

This paper studies expurgated random-coding bounds and exponents for channel coding with a given (possibly suboptimal) decoding rule. Variations of Gallager's analysis are presented, yielding several asymptotic and non-asymptotic bounds on the error probability for an arbitrary codeword distribution. A simple non-asymptotic bound is shown to attain an exponent of Csiszár and Körner under constant-composition coding. Using Lagrange duality, this exponent is expressed in several forms, one of which is shown to permit a direct derivation via cost-constrained coding which extends to infinite and continuous alphabets. The method of type class enumeration is studied, and it is shown that this approach can yield improved exponents and better tightness guarantees for some codeword distributions. A generalization of this approach is shown to provide a multi-letter exponent which extends immediately to channels with memory. Finally, a refined analysis expurgated i.i.d. random coding is shown to yield a O\big(\frac{1}{\sqrt{n}}\big) prefactor, thus improving on the standard O(1) prefactor. Moreover, the implied constant is explicitly characterized.
Asymptotic Proportion of Hard Instances of the Halting Problem
Venue: arXiv cs.LO 2014
Year: 2014

Although the halting problem is undecidable, imperfect testers that fail on some instances are possible. Such instances are called hard for the tester. One variant of imperfect testers replies "I don't know" on hard instances, another variant fails to halt, and yet another replies incorrectly "yes" or "no". Also the halting problem has three variants: does a given program halt on the empty input, does a given program halt when given itself as its input, or does a given program halt on a given input. The failure rate of a tester for some size is the proportion of hard instances among all instances of that size. This publication investigates the behaviour of the failure rate as the size grows without limit. Earlier results are surveyed and new results are proven. Some of them use C++ on Linux as the computational model. It turns out that the behaviour is sensitive to the details of the programming language or computational model, but in many cases it is possible to prove that the proportion of hard instances does not vanish.
Morpion Solitaire 5D: a new upper bound of 121 on the maximum score
Venue: arXiv cs.DM 2014
Year: 2014

Morpion Solitaire is a pencil-and-paper game for a single player. A move in this game consists of putting a cross at a lattice point and then drawing a line segment that passes through exactly five consecutive crosses. The objective is to make as many moves as possible, starting from a standard initial configuration of crosses. For one of the variants of this game, called 5D, we prove an upper bound of 121 on the number of moves. This is done by introducing line-based analysis, and improves the known upper bound of 138 obtained by potential-based analysis.
OMP Based Joint Sparsity Pattern Recovery Under Communication Constraints
Venue: arXiv cs.IT 2014
Year: 2014

We address the problem of joint sparsity pattern recovery based on low dimensional multiple measurement vectors (MMVs) in resource constrained distributed networks. We assume that distributed nodes observe sparse signals which share the same sparsity pattern and each node obtains measurements via a low dimensional linear operator. When the measurements are collected at distributed nodes in a communication network, it is often required that joint sparse recovery be performed under inherent resource constraints such as communication bandwidth and transmit/processing power. We present two approaches to take the communication constraints into account while performing common sparsity pattern recovery. First, we explore the use of a shared multiple access channel (MAC) in forwarding observations residing at each node to a fusion center. With MAC, while the bandwidth requirement does not depend on the number of nodes, the fusion center has access to only a linear combination of the observations. We discuss the conditions under which the common sparsity pattern can be estimated reliably. Second, we develop two collaborative algorithms based on Orthogonal Matching Pursuit (OMP), to jointly estimate the common sparsity pattern in a decentralized manner with a low communication overhead. In the proposed algorithms, each node exploits collaboration among neighboring nodes by sharing a small amount of information for fusion at different stages in estimating the indices of the true support in a greedy manner. Efficiency and effectiveness of the proposed algorithms are demonstrated via simulations along with a comparison with the most related existing algorithms considering the trade-off between the performance gain and the communication overhead.
Optimal Receiver Design for Diffusive Molecular Communication With Flow and Additive Noise
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we perform receiver design for a diffusive molecular communication environment. Our model includes flow in any direction, sources of information molecules in addition to the transmitter, and enzymes in the propagation environment to mitigate intersymbol interference. We characterize the mutual information between receiver observations to show how often independent observations can be made. We derive the maximum likelihood sequence detector to provide a lower bound on the bit error probability. We propose the family of weighted sum detectors for more practical implementation and derive their expected bit error probability. Under certain conditions, the performance of the optimal weighted sum detector is shown to be equivalent to a matched filter. Receiver simulation results show the tradeoff in detector complexity versus achievable bit error probability, and that a slow flow in any direction can improve the performance of a weighted sum detector.
Inverse Procedural Modeling of Facade Layouts
Venue: arXiv cs.GR 2014
Year: 2014

In this paper, we address the following research problem: How can we generate a meaningful split grammar that explains a given facade layout? To evaluate if a grammar is meaningful, we propose a cost function based on the description length and minimize this cost using an approximate dynamic programming framework. Our evaluation indicates that our framework extracts meaningful split grammars that are competitive with those of expert users, while some users and all competing automatic solutions are less successful.
Further results on the observability analysis and observer design for single range localization in 3D
Venue: arXiv cs.RO 2014
Year: 2014

The issue of single range based observability analysis and observer design for the kinematics model of a 3D vehicle subject to a constant unknown drift velocity is addressed. The proposed method departs from alternative solutions to the problem and leads to the definition of a linear time invariant state equation with a linear time varying output that can be used to globally solve the original nonlinear state estimation problem with a standard Kalman filter. Simple necessary and sufficient observability conditions are derived. Numerical simulation examples are described to illustrate the performance of the method.
Generating Sequences With Recurrent Neural Networks
Venue: arXiv cs.NE 2014
Year: 2014

This paper shows how Long Short-term Memory recurrent neural networks can be used to generate complex sequences with long-range structure, simply by predicting one data point at a time. The approach is demonstrated for text (where the data are discrete) and online handwriting (where the data are real-valued). It is then extended to handwriting synthesis by allowing the network to condition its predictions on a text sequence. The resulting system is able to generate highly realistic cursive handwriting in a wide variety of styles.
Controllability Metrics, Limitations and Algorithms for Complex Networks
Venue: arXiv cs.SY 2014
Year: 2014

This paper studies the problem of controlling complex networks, that is, the joint problem of selecting a set of control nodes and of designing a control input to steer a network to a target state. For this problem (i) we propose a metric to quantify the difficulty of the control problem as a function of the required control energy, (ii) we derive bounds based on the system dynamics (network topology and weights) to characterize the tradeoff between the control energy and the number of control nodes, and (iii) we propose an open-loop control strategy with performance guarantees. In our strategy we select control nodes by relying on network partitioning, and we design the control input by leveraging optimal and distributed control techniques. Our findings show several control limitations and properties. For instance, for Schur stable and symmetric networks: (i) if the number of control nodes is constant, then the control energy increases exponentially with the number of network nodes, (ii) if the number of control nodes is a fixed fraction of the network nodes, then certain networks can be controlled with constant energy independently of the network dimension, and (iii) clustered networks may be easier to control because, for sufficiently many control nodes, the control energy depends only on the controllability properties of the clusters and on their coupling strength. We validate our results with examples from power networks, social networks, and epidemics spreading.
The Parameterised Complexity of Counting Connected Subgraphs and Graph Motifs
Venue: arXiv cs.CC 2014
Year: 2014

We introduce a class of parameterised counting problems on graphs, p-#Induced Subgraph With Property(Φ), which generalises a number of problems which have previously been studied. This paper focusses on the case in which Φdefines a family of graphs whose edge-minimal elements all have bounded treewidth; this includes the special case in which Φdescribes the property of being connected. We show that exactly counting the number of connected induced k-vertex subgraphs in an n-vertex graph is #W[1]-hard, but on the other hand there exists an FPTRAS for the problem; more generally, we show that there exists an FPTRAS for p-#Induced Subgraph With Property(Φ) whenever Φis monotone and all the minimal graphs satisfying Φhave bounded treewidth. We then apply these results to a counting version of the Graph Motif problem.
Frameworks for Reasoning about Syntax that Utilize Quotation and Evaluation
Venue: arXiv cs.LO 2014
Year: 2014

It is often useful, if not necessary, to reason about the syntactic structure of an expression in an interpreted language (i.e., a language with a semantics). This paper introduces a mathematical structure called a syntax framework that is intended to be an abstract model of a system for reasoning about the syntax of an interpreted language. Like many concrete systems for reasoning about syntax, a syntax framework contains a mapping of expressions in the interpreted language to syntactic values that represent the syntactic structures of the expressions; a language for reasoning about the syntactic values; a mechanism called quotation to refer to the syntactic value of an expression; and a mechanism called evaluation to refer to the value of the expression represented by a syntactic value. A syntax framework provides a basis for integrating reasoning about the syntax of the expressions with reasoning about what the expressions mean. The notion of a syntax framework is used to discuss how quotation and evaluation can be built into a language and to define what quasiquotation is. Several examples of syntax frameworks are presented.
Multipath TCP: Analysis, Design and Implementation
Venue: arXiv cs.NI 2014
Year: 2014

Multi-path TCP (MP-TCP) has the potential to greatly improve application performance by using multiple paths transparently. We propose a fluid model for a large class of MP-TCP algorithms and identify design criteria that guarantee the existence, uniqueness, and stability of system equilibrium. We clarify how algorithm parameters impact TCP-friendliness, responsiveness, and window oscillation and demonstrate an inevitable tradeoff among these properties. We discuss the implications of these properties on the behavior of existing algorithms and motivate a new design that generalizes existing algorithms and strikes a good balance among TCP-friendliness, responsiveness, and window oscillation. We have implemented our algorithm in the Linux kernel. We use our prototype to compare the new algorithm with existing MP-TCP algorithms.
To Relay or Not to Relay: Learning Device-to-Device Relaying Strategies in Cellular Networks
Venue: arXiv cs.GT 2014
Year: 2014

We consider a cellular network where mobile transceiver devices that are owned by self-interested users are incentivized to cooperate with each other using tokens, which they exchange electronically to "buy" and "sell" downlink relay services, thereby increasing the network's capacity compared to a network that only supports base station-to-device (B2D) communications. We investigate how an individual device in the network can learn its optimal cooperation policy online, which it uses to decide whether or not to provide downlink relay services for other devices in exchange for tokens. We propose a supervised learning algorithm that devices can deploy to learn their optimal cooperation strategies online given their experienced network environment. We then systematically evaluate the learning algorithm in various deployment scenarios. Our simulation results suggest that devices have the greatest incentive to cooperate when the network contains (i) many devices with high energy budgets for relaying, (ii) many highly mobile users (e.g., users in motor vehicles), and (iii) neither too few nor too many tokens. Additionally, within the token system, self-interested devices can effectively learn to cooperate online, and achieve over 20% higher throughput on average than with B2D communications alone, all while selfishly maximizing their own utilities.
Objective Information Theory: A Sextuple Model and 9 Kinds of Metrics
Venue: arXiv cs.IT 2014
Year: 2014

In the contemporary era, the importance of information is undisputed, but there has never been a common understanding of information, nor a unanimous conclusion to the researches on information metrics. Based on the previous studies, this paper analyzes the important achievements in the researches of the properties and metrics of information as well as their main insufficiencies, and explores the essence and connotation, the mathematical expressions and other basic problems related to information. On the basis of the understanding of the objectivity of information, it proposes the definitions and a Sextuple model of information; discusses the basic properties of information, and brings forward the definitions and mathematical expressions of nine kinds of metrics of information, i.e., extensity, detailedness, sustainability, containability, delay, richness, distribution, validity and matchability. Through these, this paper establishes a basic theory frame of Objective Information Theory to support the analysis and research on information and information system systematically and comprehensively.
Connection Matrices and the Definability of Graph Parameters
Venue: arXiv cs.LO 2014
Year: 2014

In this paper we extend and prove in detail the Finite Rank Theorem for connection matrices of graph parameters definable in Monadic Second Order Logic with counting (CMSOL) from B. Godlin, T. Kotek and J.A. Makowsky (2008) and J.A. Makowsky (2009). We demonstrate its vast applicability in simplifying known and new non-definability results of graph properties and finding new non-definability results for graph parameters. We also prove a Feferman-Vaught Theorem for the logic CFOL, First Order Logic with the modular counting quantifiers.
Evolving a Behavioral Repertoire for a Walking Robot
Venue: arXiv cs.RO 2014
Year: 2014

Numerous algorithms have been proposed to allow legged robots to learn to walk. However, the vast majority of these algorithms is devised to learn to walk in a straight line, which is not sufficient to accomplish any real-world mission. Here we introduce the Transferability-based Behavioral Repertoire Evolution algorithm (TBR-Evolution), a novel evolutionary algorithm that simultaneously discovers several hundreds of simple walking controllers, one for each possible direction. By taking advantage of solutions that are usually discarded by evolutionary processes, TBR-Evolution is substantially faster than independently evolving each controller. Our technique relies on two methods: (1) novelty search with local competition, which searches for both high-performing and diverse solutions, and (2) the transferability approach, which com-bines simulations and real tests to evolve controllers for a physical robot. We evaluate this new technique on a hexapod robot. Results show that with only a few dozen short experiments performed on the robot, the algorithm learns a repertoire of con-trollers that allows the robot to reach every point in its reachable space. Overall, TBR-Evolution opens a new kind of learning algorithm that simultaneously optimizes all the achievable behaviors of a robot.
Wiretap Channel With Causal State Information and Secure Rate-Limited Feedback
Venue: arXiv cs.IT 2014
Year: 2014

In this paper, we consider the secrecy capacity of a wiretap channel in the presence of causal state information and secure rate-limited feedback. In this scenario, the causal state information from the channel is available to both the legitimate transmitter and legitimate receiver. In addition, the legitimate receiver can send secure feedback to the transmitter at a limited rate Rf . We shown that the secrecy capacity is bounded. Moreover, when the channel to the legitimate receiver is less noisy than the channel to the eavesdropper, the bound is shown to be tight. The capacity achieving scheme is based on both the Wyner wiretap coding and two steps of shared-key generation: one from the state information and one via the noiseless feedback. Finally, we consider several special cases. When state information is available only at the legitimate receiver, the analysis suggests that unlike previous results involving feedback, it is better to use the feedback to send the state information to the transmitter (when possible), rather than send a random key.
Herding Cats - Modelling, simulation, testing, and data-mining for weak memory
Venue: arXiv cs.LO 2014
Year: 2014

We propose an axiomatic generic framework for modelling weak memory. We show how to instantiate this framework for SC, TSO, C++ restricted to release-acquire atomics, and Power. For Power, we compare our model to a preceding operational model in which we found a flaw. To do so, we define an operational model that we show equivalent to our axiomatic model. We also propose a model for ARM. Our testing on this architecture revealed a behaviour later acknowledged as a bug by ARM, and more recently 33 additional anomalies. We offer a new simulation tool, called herd, which allows the user to specify the model of his choice in a concise way. Given a specification of a model, the tool becomes a simulator for that model. The tool relies on an axiomatic description; this choice allows us to outperform all previous simulation tools. Additionally, we confirm that verification time is vastly improved, in the case of bounded model-checking. Finally, we put our models in perspective, in the light of empirical data obtained by analysing the C and C++ code of a Debian Linux distribution. We present our new analysis tool, called mole, which explores a piece of code to find the weak memory idioms that it uses.
Cooperative Access in Cognitive Radio Networks: Stable Throughput and Delay Tradeoffs
Venue: arXiv cs.NI 2014
Year: 2014

In this paper, we study and analyze fundamental throughput-delay tradeoffs in cooperative multiple access for cognitive radio systems. We focus on the class of randomized cooperative policies, whereby the secondary user (SU) serves either the queue of its own data or the queue of the primary user (PU) relayed data with certain service probabilities. The proposed policy opens room for trading the PU delay for enhanced SU delay. Towards this objective, stability conditions for the queues involved in the system are derived. Furthermore, a moment generating function approach is employed to derive closed-form expressions for the average delay encountered by the packets of both users. Results reveal that cooperation expands the stable throughput region of the system and significantly reduces the delay at both users. Moreover, we quantify the gain obtained in terms of the SU delay under the proposed policy, over conventional relaying that gives strict priority to the relay queue.
A "Piano Movers" Problem Reformulated
Venue: arXiv cs.CG 2014
Year: 2014

It has long been known that cylindrical algebraic decompositions (CADs) can in theory be used for robot motion planning. However, in practice even the simplest examples can be too complicated to tackle. We consider in detail a "Piano Mover's Problem" which considers moving an infinitesimally thin piano (or ladder) through a right-angled corridor. Producing a CAD for the original formulation of this problem is still infeasible after 25 years of improvements in both CAD theory and computer hardware. We review some alternative formulations in the literature which use differing levels of geometric analysis before input to a CAD algorithm. Simpler formulations allow CAD to easily address the question of the existence of a path. We provide a new formulation for which both a CAD can be constructed and from which an actual path could be determined if one exists, and analyse the CADs produced using this approach for variations of the problem. This emphasises the importance of the precise formulation of such problems for CAD. We analyse the formulations and their CADs considering a variety of heuristics and general criteria, leading to conclusions about tackling other problems of this form.
Security analysis of epsilon-almost dual universal2 hash functions: smoothing of min entropy vs. smoothing of Rényi entropy of order 2
Venue: arXiv cs.IT 2014
Year: 2014

Recently, $\varepsilon$-almost dual universal$_2$ hash functions has been proposed as a new and wider class of hash functions. Using this class of hash functions, several efficient hash functions were proposed. This paper evaluates the security performance when we apply this kind of hash functions. We evaluate the security in several kinds of setting based on the $L_1$ distinguishability criterion and the modified mutual information criterion. The obtained evaluation is based on smoothing of Rényi entropy of order 2 and/or min entropy. We clarify the difference between these two methods.
Multiway Cut, Pairwise Realizable Distributions, and Descending Thresholds
Venue: arXiv cs.DS 2014
Year: 2014

We design new approximation algorithms for the Multiway Cut problem, improving the previously known factor of 1.32388 [Buchbinder et al., 2013]. We proceed in three steps. First, we analyze the rounding scheme of Buchbinder et al., 2013 and design a modification that improves the approximation to (3+sqrt(5))/4 (approximately 1.309017). We also present a tight example showing that this is the best approximation one can achieve with the type of cuts considered by Buchbinder et al., 2013: (1) partitioning by exponential clocks, and (2) single-coordinate cuts with equal thresholds. Then, we prove that this factor can be improved by introducing a new rounding scheme: (3) single-coordinate cuts with descending thresholds. By combining these three schemes, we design an algorithm that achieves a factor of (10 + 4 sqrt(3))/13 (approximately 1.30217). This is the best approximation factor that we are able to verify by hand. Finally, we show that by combining these three rounding schemes with the scheme of independent thresholds from Karger et al., 2004, the approximation factor can be further improved to 1.2965. This approximation factor has been verified only by computer.