OpenRaiser/Intern-Atlas huggingface dataset:
Constructing Runge-Kutta Methods with the Use of Artificial Neural Networks
Venue: arXiv cs.NE 2013
Year: 2013

A methodology that can generate the optimal coefficients of a numerical method with the use of an artificial neural network is presented in this work. The network can be designed to produce a finite difference algorithm that solves a specific system of ordinary differential equations numerically. The case we are examining here concerns an explicit two-stage Runge-Kutta method for the numerical solution of the two-body problem. Following the implementation of the network, the latter is trained to obtain the optimal values for the coefficients of the Runge-Kutta method. The comparison of the new method to others that are well known in the literature proves its efficiency and demonstrates the capability of the network to provide efficient algorithms for specific problems.
Coarse abstractions make Zeno behaviours difficult to detect
Venue: arXiv cs.LO 2013
Year: 2013

An infinite run of a timed automaton is Zeno if it spans only a finite amount of time. Such runs are considered unfeasible and hence it is important to detect them, or dually, find runs that are non-Zeno. Over the years important improvements have been obtained in checking reachability properties for timed automata. We show that some of these very efficient optimizations make testing for Zeno runs costly. In particular we show NP-completeness for the LU-extrapolation of Behrmann et al. We analyze the source of this complexity in detail and give general conditions on extrapolation operators that guarantee a (low) polynomial complexity of Zenoness checking. We propose a slight weakening of the LU-extrapolation that satisfies these conditions.
Algorithmic Complexity for Short Binary Strings Applied to Psychology: A Primer
Venue: arXiv cs.CC 2013
Year: 2013

Since human randomness production has been studied and widely used to assess executive functions (especially inhibition), many measures have been suggested to assess the degree to which a sequence is random-like. However, each of them focuses on one feature of randomness, leading authors to have to use multiple measures. Here we describe and advocate for the use of the accepted universal measure for randomness based on algorithmic complexity, by means of a novel previously presented technique using the the definition of algorithmic probability. A re-analysis of the classical Radio Zenith data in the light of the proposed measure and methodology is provided as a study case of an application.
On the origin of ambiguity in efficient communication
Venue: arXiv cs.CL 2013
Year: 2013

This article studies the emergence of ambiguity in communication through the concept of logical irreversibility and within the framework of Shannon's information theory. This leads us to a precise and general expression of the intuition behind Zipf's vocabulary balance in terms of a symmetry equation between the complexities of the coding and the decoding processes that imposes an unavoidable amount of logical uncertainty in natural communication. Accordingly, the emergence of irreversible computations is required if the complexities of the coding and the decoding processes are balanced in a symmetric scenario, which means that the emergence of ambiguous codes is a necessary condition for natural communication to succeed.
Distributed Matrix Completion and Robust Factorization
Venue: arXiv cs.LG 2013
Year: 2013

If learning methods are to scale to the massive sizes of modern datasets, it is essential for the field of machine learning to embrace parallel and distributed computing. Inspired by the recent development of matrix factorization methods with rich theory but poor computational complexity and by the relative ease of mapping matrices onto distributed architectures, we introduce a scalable divide-and-conquer framework for noisy matrix factorization. We present a thorough theoretical analysis of this framework in which we characterize the statistical errors introduced by the "divide" step and control their magnitude in the "conquer" step, so that the overall algorithm enjoys high-probability estimation guarantees comparable to those of its base algorithm. We also present experiments in collaborative filtering and video background modeling that demonstrate the near-linear to superlinear speed-ups attainable with this approach.
Jaywalking your Dog - Computing the Fréchet Distance with Shortcuts
Venue: arXiv cs.CG 2013
Year: 2013

The similarity of two polygonal curves can be measured using the Fréchet distance. We introduce the notion of a more robust Fréchet distance, where one is allowed to shortcut between vertices of one of the curves. This is a natural approach for handling noise, in particular batched outliers. We compute a (3+\eps)-approximation to the minimum Fréchet distance over all possible such shortcuts, in near linear time, if the curve is c-packed and the number of shortcuts is either small or unbounded. To facilitate the new algorithm we develop several new tools: (A) A data structure for preprocessing a curve (not necessarily c-packed) that supports (1+\eps)-approximate Fréchet distance queries between a subcurve (of the original curve) and a line segment. (B) A near linear time algorithm that computes a permutation of the vertices of a curve, such that any prefix of 2k-1 vertices of this permutation, form an optimal approximation (up to a constant factor) to the original curve compared to any polygonal curve with k vertices, for any k > 0. (C) A data structure for preprocessing a curve that supports approximate Fréchet distance queries between a subcurve and query polygonal curve. The query time depends quadratically on the complexity of the query curve, and only (roughly) logarithmically on the complexity of the original curve. To our knowledge, these are the first data structures to support these kind of queries efficiently.
Propositional equality, identity types, and direct computational paths
Venue: arXiv cs.LO 2013
Year: 2013

In proof theory the notion of canonical proof is rather basic, and it is usually taken for granted that a canonical proof of a sentence must be unique up to certain minor syntactical details (such as, e.g., change of bound variables). When setting up a proof theory for equality one is faced with a rather unexpected situation where there may not be a unique canonical proof of an equality statement. Indeed, in a (1994--5) proposal for the formalisation of proofs of propositional equality in the Curry--Howard style, we have already uncovered such a peculiarity. Totally independently, and in a different setting, Hofmann & Streicher (1994) have shown how to build a model of Martin-Löf's Type Theory in which uniqueness of canonical proofs of identity types does not hold. The intention here is to show that, by considering as sequences of rewrites and substitution, it comes a rather natural fact that two (or more) distinct proofs may be yet canonical and are none to be preferred over one another. By looking at proofs of equality as rewriting (or computational) paths this approach will be in line with the recently proposed connections between type theory and homotopy theory via identity types, since elements of identity types will be, concretely, paths (or homotopies).
On Decoding Irregular Tanner Codes with Local-Optimality Guarantees
Venue: arXiv cs.IT 2013
Year: 2013

We consider decoding of binary Tanner codes using message-passing iterative decoding and linear programming (LP) decoding in MBIOS channels. We present new certificates that are based on a combinatorial characterization for local-optimality of a codeword in irregular Tanner codes with respect to any MBIOS channel. This characterization is based on a conical combination of normalized weighted subtrees in the computation trees of the Tanner graph. These subtrees may have any finite height h (even equal or greater than half of the girth of the Tanner graph). In addition, the degrees of local-code nodes in these subtrees are not restricted to two. We prove that local optimality in this new characterization implies maximum-likelihood (ML) optimality and LP optimality, and show that a certificate can be computed efficiently. We also present a new message-passing iterative decoding algorithm, called normalized weighted min-sum (NWMS). NWMS decoding is a BP-type algorithm that applies to any irregular binary Tanner code with single parity-check local codes. We prove that if a locally-optimal codeword with respect to height parameter h exists (whereby notably h is not limited by the girth of the Tanner graph), then NWMS decoding finds this codeword in h iterations. The decoding guarantee of the NWMS decoding algorithm applies whenever there exists a locally optimal codeword. Because local optimality of a codeword implies that it is the unique ML codeword, the decoding guarantee also provides an ML certificate for this codeword. Finally, we apply the new local optimality characterization to regular Tanner codes, and prove lower bounds on the noise thresholds of LP decoding in MBIOS channels. When the noise is below these lower bounds, the probability that LP decoding fails decays doubly exponentially in the girth of the Tanner graph.
The Sender-Excited Secret Key Agreement Model: Capacity, Reliability and Secrecy Exponents
Venue: arXiv cs.IT 2013
Year: 2013

We consider the secret key generation problem when sources are randomly excited by the sender and there is a noiseless public discussion channel. Our setting is thus similar to recent works on channels with action-dependent states where the channel state may be influenced by some of the parties involved. We derive single-letter expressions for the secret key capacity through a type of source emulation analysis. We also derive lower bounds on the achievable reliability and secrecy exponents, i.e., the exponential rates of decay of the probability of decoding error and of the information leakage. These exponents allow us to determine a set of strongly-achievable secret key rates. For degraded eavesdroppers the maximum strongly-achievable rate equals the secret key capacity; our exponents can also be specialized to previously known results. In deriving our strong achievability results we introduce a coding scheme that combines wiretap coding (to excite the channel) and key extraction (to distill keys from residual randomness). The secret key capacity is naturally seen to be a combination of both source- and channel-type randomness. Through examples we illustrate a fundamental interplay between the portion of the secret key rate due to each type of randomness. We also illustrate inherent tradeoffs between the achievable reliability and secrecy exponents. Our new scheme also naturally accommodates rate limits on the public discussion. We show that under rate constraints we are able to achieve larger rates than those that can be attained through a pure source emulation strategy.
Approximation Algorithms for Digraph Width Parameters
Venue: arXiv cs.DS 2013
Year: 2013

Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed treewidth, DAG-width and Kelly-width are some such notions which generalize treewidth, whereas directed pathwidth generalizes pathwidth. Each of these digraph width measures have an associated decomposition structure. In this paper, we present approximation algorithms for all these digraph width parameters. In particular, we give an O(sqrt{logn})-approximation algorithm for directed treewidth, and an O({\log}^{3/2}{n})-approximation algorithm for directed pathwidth, DAG-width and Kelly-width. Our algorithms construct the corresponding decompositions whose widths are within the above mentioned approximation factors.
Modules over relative monads for syntax and semantics
Venue: arXiv cs.LO 2013
Year: 2013

We give an algebraic characterization of the syntax and semantics of a class of languages with variable binding. We introduce a notion of 2-signature: such a signature specifies not only the terms of a language, but also reduction rules on those terms. To any 2-signature $S$ we associate a category of "models" of $S$. This category has an initial object, which integrates the terms freely generated by $S$, and which is equipped with reductions according to the inequations given in $S$. We call this initial object the language generated by $S$. Models of a 2--signature are built from relative monads and modules over such monads. Through the use of monads, the models---and in particular, the initial model---come equipped with a substitution operation that is compatible with reduction in a suitable sense. The initiality theorem is formalized in the proof assistant Coq, yielding a machinery which, when fed with a 2-signature, provides the associated programming language with reduction relation and certified substitution.
Randomized Strategyproof Mechanisms for Facility Location and the Mini-Sum-of-Squares Objective
Venue: arXiv cs.GT 2013
Year: 2013

We consider the problem of locating a public facility on a line, where a set of $n$ strategic agents report their \emph{locations} and a mechanism determines, either deterministically or randomly, the location of the facility. Game theoretic perspectives of the facility location problem advanced in two main directions. The first direction is concerned with the characterization of \emph{strategyproof} (SP) mechanisms; i.e., mechanisms that induce truthful reporting as a dominant strategy; and the second direction quantifies how well various objective functions can be approximated when restricted to SP mechanisms. The current paper provides contributions in both directions. First, we construct a parameterized randomized SP mechanism, and show that all of the previously proposed deterministic and randomized SP mechanisms for the current settings can be formalized as special cases of this mechanism. Second, we give tight results for the approximation ratio of SP mechanisms with respect to the objective of minimizing the sum of squares of distances to the agents (\emph{miniSOS}). Holzman \cite{Holzman1990} provided an axiomatic foundation for this function, showing that it is the unique function that satisfies unanimity, continuity and invariance. We devise a randomized mechanism that gives a 1.5-approximation for the miniSOS function, and show that no other randomized SP mechanism can provide a better approximation. This mechanism chooses the average location with probability 1/2 and a \emph{random dictator} with probability 1/2. For deterministic mechanisms, we show that the median mechanism provides a 2-approximation, and this is tight. Together, our study provides fundamental understanding of the miniSOS objective function and makes a step toward the characterization of randomized SP facility location mechanisms.
Energy Minimization for the Half-Duplex Relay Channel with Decode-Forward Relaying
Venue: arXiv cs.IT 2013
Year: 2013

We analyze coding for energy efficiency in relay channels at a fixed source rate. We first propose a half-duplex decode-forward coding scheme for the Gaussian relay channel. We then derive three optimal sets of power allocation, which respectively minimize the network, the relay and the source energy consumption. These optimal power allocations are given in closed-form, which have so far remained implicit for maximum-rate schemes. Moreover, analysis shows that minimizing the network energy consumption at a given rate is not equivalent to maximizing the rate given energy, since it only covers part of all rates achievable by decode-forward. We thus combine the optimized schemes for network and relay energy consumptions into a generalized one, which then covers all achievable rates. This generalized scheme is not only energy-optimal for the desired source rate but also rate-optimal for the consumed energy. The results also give a detailed understanding of the power consumption regimes and allow a comprehensive description of the optimal message coding and resource allocation for each desired source rate and channel realization. Finally, we simulate the proposed schemes in a realistic environment, considering path-loss and shadowing as modelled in the 3GPP standard. Significant energy gain can be obtained over both direct and two-hop transmissions, particularly when the source is far from relay and destination.
Optimal Coalition Structures in Cooperative Graph Games
Venue: arXiv cs.GT 2013
Year: 2013

Representation languages for coalitional games are a key research area in algorithmic game theory. There is an inherent tradeoff between how general a language is, allowing it to capture more elaborate games, and how hard it is computationally to optimize and solve such games. One prominent such language is the simple yet expressive Weighted Graph Games (WGGs) representation [14], which maintains knowledge about synergies between agents in the form of an edge weighted graph. We consider the problem of finding the optimal coalition structure in WGGs. The agents in such games are vertices in a graph, and the value of a coalition is the sum of the weights of the edges present between coalition members. The optimal coalition structure is a partition of the agents to coalitions, that maximizes the sum of utilities obtained by the coalitions. We show that finding the optimal coalition structure is not only hard for general graphs, but is also intractable for restricted families such as planar graphs which are amenable for many other combinatorial problems. We then provide algorithms with constant factor approximations for planar, minor-free and bounded degree graphs.
Alternative Awaiting and Broadcast for Two-Way Relay Fading Channels
Venue: arXiv cs.IT 2013
Year: 2013

We investigate a two-way relay (TWR) fading channel where two source nodes wish to exchange information with the help of a relay node. Given traditional TWR protocols, transmission rates in both directions are known to be limited by the hop with lower capacity, i.e., the min operations between uplink and downlink. In this paper, we propose a new transmission protocol, named as alternative awaiting and broadcast (AAB), to cancel the min operations in the TWR fading channels. The operational principles, new upper bound on ergodic sum-capacity (ESC) and convergence behavior of average delay of signal transmission (ST) (in relay buffer) for the proposed AAB protocol are analyzed. Moreover, we propose a suboptimal encoding/decoding solution for the AAB protocol and derive an achievable ergodic sum-rate (ESR) with corresponding average delay of ST. Numerical results show that 1) the proposed AAB protocol significantly improves the achievable ESR compared to the traditional TWR protocols, 2) considering the average delay of system service (SS) (in source buffer), the average delay of ST induced by the proposed AAB protocol is very small and negligible.
Learning Sequence Neighbourhood Metrics
Venue: arXiv cs.NE 2013
Year: 2013

Recurrent neural networks (RNNs) in combination with a pooling operator and the neighbourhood components analysis (NCA) objective function are able to detect the characterizing dynamics of sequences and embed them into a fixed-length vector space of arbitrary dimensionality. Subsequently, the resulting features are meaningful and can be used for visualization or nearest neighbour classification in linear time. This kind of metric learning for sequential data enables the use of algorithms tailored towards fixed length vector spaces such as R^n.
Downlink Capacity and Base Station Density in Cellular Networks
Venue: arXiv cs.NI 2013
Year: 2013

There have been a bulk of analytic results about the performance of cellular networks where base stations are regularly located on a hexagonal or square lattice. This regular model cannot reflect the reality, and tends to overestimate the network performance. Moreover, tractable analysis can be performed only for a fixed location user (e.g., cell center or edge user). In this paper, we use the stochastic geometry approach, where base stations can be modeled as a homogeneous Poisson point process. We also consider the user density, and derive the user outage probability that an arbitrary user is under outage owing to low signal-to-interference-plus-noise ratio or high congestion by multiple users. Using the result, we calculate the density of success transmissions in the downlink cellular network. An interesting observation is that the success transmission density increases with the base station density, but the increasing rate diminishes. This means that the number of base stations installed should be more than $n$-times to increase the network capacity by a factor of $n$. Our results will provide a framework for performance analysis of the wireless infrastructure with a high density of access points, which will significantly reduce the burden of network-level simulations.
On the Degrees of Freedom of $K$-User SISO Interference and X Channels with Delayed CSIT
Venue: arXiv cs.IT 2013
Year: 2013

The $K$-user single-input single-output (SISO) AWGN interference channel and $2\times K$ SISO AWGN X channel are considered where the transmitters have the delayed channel state information (CSI) through noiseless feedback links. Multi-phase transmission schemes are proposed for both channels which possess novel ingredients, namely, multi-phase partial interference nulling, distributed interference management via user scheduling, and distributed higher-order symbol generation. The achieved degrees of freedom (DoF) values are greater than the best previously known DoFs for both channels with delayed CSI at transmitters.
Dependence logic with a majority quantifier
Venue: arXiv cs.LO 2013
Year: 2013

We study the extension of dependence logic D by a majority quantifier M over finite structures. We show that the resulting logic is equi-expressive with the extension of second-order logic by second-order majority quantifiers of all arities. Our results imply that, from the point of view of descriptive complexity theory, D(M) captures the complexity class counting hierarchy.
Natural hand gestures for human identification in a Human-Computer Interface
Venue: arXiv cs.HC 2013
Year: 2013

The goal of this work is the identification of humans based on motion data in the form of natural hand gestures. In this paper, the identification problem is formulated as classification with classes corresponding to persons' identities, based on recorded signals of performed gestures. The identification performance is examined with a database of twenty-two natural hand gestures recorded with two types of hardware and three state-of-art classifiers: Linear Discrimination Analysis (LDA), Support Vector machines (SVM) and k-Nearest Neighbour (k-NN). Results show that natural hand gestures allow for an effective human classification.
Deterministic Feature Selection for $k$-means Clustering
Venue: arXiv cs.LG 2013
Year: 2013

We study feature selection for $k$-means clustering. Although the literature contains many methods with good empirical performance, algorithms with provable theoretical behavior have only recently been developed. Unfortunately, these algorithms are randomized and fail with, say, a constant probability. We address this issue by presenting a deterministic feature selection algorithm for k-means with theoretical guarantees. At the heart of our algorithm lies a deterministic method for decompositions of the identity.