OpenRaiser/Intern-Atlas huggingface dataset:
The Budgeted Transportation Problem
Venue: arXiv cs.DS 2013
Year: 2013

Consider a transportation problem with sets of sources and sinks. There are profits and prices on the edges. The goal is to maximize the profit while meeting the following constraints; the total flow going out of a source must not exceed its capacity and the total price of the incoming flow on a sink must not exceed its budget. This problem is closely related to the generalized flow problem. We propose an auction based primal dual approximation algorithm to solve the problem. The complexity is $O(ε^{-1}(n^2+ n\log{m})m\log U)$ where $n$ is the number of sources, $m$ is the number of sinks, $U$ is the ratio of the maximum profit/price to the minimum profit/price. We also show how to generalize the scheme to solve a more general version of the problem, where there are edge capacities and/or the profit function is concave and piece-wise linear. The complexity of the algorithm depends on the number of linear segments, termed ${\cal L}$, of the profit function.
A Stochastic Probing Problem with Applications
Venue: arXiv cs.DS 2013
Year: 2013

We study a general stochastic probing problem defined on a universe V, where each element e in V is "active" independently with probability p_e. Elements have weights {w_e} and the goal is to maximize the weight of a chosen subset S of active elements. However, we are given only the p_e values-- to determine whether or not an element e is active, our algorithm must probe e. If element e is probed and happens to be active, then e must irrevocably be added to the chosen set S; if e is not active then it is not included in S. Moreover, the following conditions must hold in every random instantiation: (1) the set Q of probed elements satisfy an "outer" packing constraint, and (2) the set S of chosen elements satisfy an "inner" packing constraint. The kinds of packing constraints we consider are intersections of matroids and knapsacks. Our results provide a simple and unified view of results in stochastic matching and Bayesian mechanism design, and can also handle more general constraints. As an application, we obtain the first polynomial-time $Ω(1/k)$-approximate "Sequential Posted Price Mechanism" under k-matroid intersection feasibility constraints.
Shape Characterization via Boundary Distortion
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, we derive new shape descriptors based on a directional characterization. The main idea is to study the behavior of the shape neighborhood under family of transformations. We obtain a description invariant with respect to rotation, reflection, translation and scaling. A well-defined metric is then proposed on the associated feature space. We show the continuity of this metric. Some results on shape retrieval are provided on two databases to show the accuracy of the proposed shape metric.
Adaptive Decision Feedback Detection with Parallel Interference Cancellation and Constellation Constraints for Multi-Antenna Systems
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a novel low-complexity adaptive decision feedback detection with parallel decision feedback and constellation constraints (P-DFCC) is proposed for multiuser MIMO systems. We propose a constrained constellation map which introduces a number of selected points served as the feedback candidates for interference cancellation. By introducing a reliability checking, a higher degree of freedom is introduced to refine the unreliable estimates. The P-DFCC is followed by an adaptive receive filter to estimate the transmitted symbol. In order to reduce the complexity of computing the filters with time-varying MIMO channels, an adaptive recursive least squares (RLS) algorithm is employed in the proposed P-DFCC scheme. An iterative detection and decoding (Turbo) scheme is considered with the proposed P-DFCC algorithm. Simulations show that the proposed technique has a complexity comparable to the conventional parallel decision feedback detector while it obtains a performance close to the maximum likelihood detector at a low to medium SNR range.
A Meta-Theory of Boundary Detection Benchmarks
Venue: arXiv cs.CV 2013
Year: 2013

Human labeled datasets, along with their corresponding evaluation algorithms, play an important role in boundary detection. We here present a psychophysical experiment that addresses the reliability of such benchmarks. To find better remedies to evaluate the performance of any boundary detection algorithm, we propose a computational framework to remove inappropriate human labels and estimate the intrinsic properties of boundaries.
A Fast Template Based Heuristic For Global Multiple Sequence Alignment
Venue: arXiv cs.CE 2013
Year: 2013

Advances in bio-technology have made available massive amounts of functional, structural and genomic data for many biological sequences. This increased availability of heterogeneous biological data has resulted in biological applications where a multiple sequence alignment (msa) is required for aligning similar features, where a feature is described in structural, functional or evolutionary terms. In these applications, for a given set of sequences, depending on the feature of interest the optimal msa is likely to be different, and sequence similarity can only be used as a rough initial estimate on the accuracy of an msa. This has motivated the growth in template based heuristics that supplement the sequence information with evolutionary, structural and functional data and exploit feature similarity instead of sequence similarity to construct multiple sequence alignments that are biologically more accurate. However, current frameworks for designing template based heuristics do not allow the user to explicitly specify information that can help to classify features into types and associate weights signifying the relative importance of a feature with respect to other features. In this paper, we first provide a mechanism where as a part of the template information the user can explicitly specify for each feature, its type, and weight. The type is to classify the features into different categories based on their characteristics and the weight signifies the relative importance of a feature with respect to other features in that sequence. Second, we exploit the above information to define scoring models for pair-wise sequence alignment that assume segment conservation as opposed to single character (residue) conservation. Finally, we present a fast progressive alignment based heuristic framework that helps in constructing a global msa efficiently.
Phoneme discrimination using KS algebra I
Venue: arXiv cs.SD 2013
Year: 2013

In our work we define a new algebra of operators as a substitute for fuzzy logic. Its primary purpose is for construction of binary discriminators for phonemes based on spectral content. It is optimized for design of non-parametric computational circuits, and makes uses of 4 operations: $\min$, $\max$, the difference and generalized additively homogenuous means.
Phoneme discrimination using $KS$-algebra II
Venue: arXiv cs.SD 2013
Year: 2013

$KS$-algebra consists of expressions constructed with four kinds operations, the minimum, maximum, difference and additively homogeneous generalized means. Five families of $Z$-classifiers are investigated on binary classification tasks between English phonemes. It is shown that the classifiers are able to reflect well known formant characteristics of vowels, while having very small Kolmogoroff's complexity.
A Treatise on Stability of Autonomous and Non-autonomous Systems: Theory and Illustrative Practical Applications
Venue: arXiv cs.IT 2013
Year: 2013

Stability is a very important property of any physical system. By a stable system, we broadly mean that small disturbances either in the system inputs or in the initial conditions do not lead to large changes in the overall behavior of the system. To be of practical use, a system must have to be stable. The theory of stability is a vast, rapidly growing subject with prolific and innovative contributions from numerous researchers. As such, an introductory book that covers the basic concepts and minute details about this theory is essential. The primary aim of this book is to make the readers familiar with the various terminologies and methods related to the stability analysis of time-invariant (autonomous) and time-varying (non-autonomous) systems. A special treatment is given to the celebrated Liapunov's direct method which is so far the most widely used and perhaps the best method for determining the stability nature of both autonomous as well as non-autonomous systems. After discussing autonomous systems to a considerable extent, the book concentrates on the non-autonomous systems. From stability point of view, these systems are often quite difficult to manage. Also, unlike their autonomous counterparts, the non-autonomous systems often behave in peculiar manners which can make the analysts arrive at misleading conclusions. Due to these issues, this book attempts to present a careful and systematic study about the stability properties of non-autonomous systems.
Typing Context-Dependent Behavioural Variation
Venue: arXiv cs.PL 2013
Year: 2013

Context Oriented Programming (COP) concerns the ability of programs to adapt to changes in their running environment. A number of programming languages endowed with COP constructs and features have been developed. However, some foundational issues remain unclear. This paper proposes adopting static analysis techniques to reason on and predict how programs adapt their behaviour. We introduce a core functional language, ContextML, equipped with COP primitives for manipulating contexts and for programming behavioural variations. In particular, we specify the dispatching mechanism, used to select the program fragments to be executed in the current active context. Besides the dynamic semantics we present an annotated type system. It guarantees that the well-typed programs adapt to any context, i.e. the dispatching mechanism always succeeds at run-time.
Modularizing and Specifying Protocols among Threads
Venue: arXiv cs.PL 2013
Year: 2013

We identify three problems with current techniques for implementing protocols among threads, which complicate and impair the scalability of multicore software development: implementing synchronization, implementing coordination, and modularizing protocols. To mend these deficiencies, we argue for the use of domain-specific languages (DSL) based on existing models of concurrency. To demonstrate the feasibility of this proposal, we explain how to use the model of concurrency Reo as a high-level protocol DSL, which offers appropriate abstractions and a natural separation of protocols and computations. We describe a Reo-to-Java compiler and illustrate its use through examples.
Linear Compressed Pattern Matching for Polynomial Rewriting (Extended Abstract)
Venue: arXiv cs.LO 2013
Year: 2013

This paper is an extended abstract of an analysis of term rewriting where the terms in the rewrite rules as well as the term to be rewritten are compressed by a singleton tree grammar (STG). This form of compression is more general than node sharing or representing terms as dags since also partial trees (contexts) can be shared in the compression. In the first part efficient but complex algorithms for detecting applicability of a rewrite rule under STG-compression are constructed and analyzed. The second part applies these results to term rewriting sequences. The main result for submatching is that finding a redex of a left-linear rule can be performed in polynomial time under STG-compression. The main implications for rewriting and (single-position or parallel) rewriting steps are: (i) under STG-compression, n rewriting steps can be performed in nondeterministic polynomial time. (ii) under STG-compression and for left-linear rewrite rules a sequence of n rewriting steps can be performed in polynomial time, and (iii) for compressed rewrite rules where the left hand sides are either DAG-compressed or ground and STG-compressed, and an STG-compressed target term, n rewriting steps can be performed in polynomial time.
Evaluating functions as processes
Venue: arXiv cs.PL 2013
Year: 2013

A famous result by Milner is that the lambda-calculus can be simulated inside the pi-calculus. This simulation, however, holds only modulo strong bisimilarity on processes, i.e. there is a slight mismatch between beta-reduction and how it is simulated in the pi-calculus. The idea is that evaluating a lambda-term in the pi-calculus is like running an environment-based abstract machine, rather than applying ordinary beta-reduction. In this paper we show that such an abstract-machine evaluation corresponds to linear weak head reduction, a strategy arising from the representation of lambda-terms as linear logic proof nets, and that the relation between the two is as tight as it can be. The study is also smoothly rephrased in the call-by-value case, introducing a call-by-value analogous of linear weak head reduction.
Stochastic Context-Free Grammars, Regular Languages, and Newton's Method
Venue: arXiv cs.FL 2013
Year: 2013

We study the problem of computing the probability that a given stochastic context-free grammar (SCFG), G, generates a string in a given regular language L(D) (given by a DFA, D). This basic problem has a number of applications in statistical natural language processing, and it is also a key necessary step towards quantitative ω-regular model checking of stochastic context-free processes (equivalently, 1-exit recursive Markov chains, or stateless probabilistic pushdown processes). We show that the probability that G generates a string in L(D) can be computed to within arbitrary desired precision in polynomial time (in the standard Turing model of computation), under a rather mild assumption about the SCFG, G, and with no extra assumption about D. We show that this assumption is satisfied for SCFG's whose rule probabilities are learned via the well-known inside-outside (EM) algorithm for maximum-likelihood estimation (a standard method for constructing SCFGs in statistical NLP and biological sequence analysis). Thus, for these SCFGs the algorithm always runs in P-time.
ML4PG in Computer Algebra verification
Venue: arXiv cs.LO 2013
Year: 2013

ML4PG is a machine-learning extension that provides statistical proof hints during the process of Coq/SSReflect proof development. In this paper, we use ML4PG to find proof patterns in the CoqEAL library -- a library that was devised to verify the correctness of Computer Algebra algorithms. In particular, we use ML4PG to help us in the formalisation of an efficient algorithm to compute the inverse of triangular matrices.
Imperfect and Unmatched CSIT is Still Useful for the Frequency Correlated MISO Broadcast Channel
Venue: arXiv cs.IT 2013
Year: 2013

Since Maddah-Ali and Tse showed that the completely stale transmitter-side channel state information (CSIT) still benefits the Degrees of Freedom (DoF) of the Multiple-Input-Multiple-Output (MISO) Broadcast Channel (BC), there has been much interest in the academic literature to investigate the impact of imperfect CSIT on \emph{DoF} region of time correlated broadcast channel. Even though the research focus has been on time correlated channels so far, a similar but different problem concerns the frequency correlated channels. Indeed, the imperfect CSIT also impacts the DoF region of frequency correlated channels, as exemplified by current multi-carrier wireless systems. This contribution, for the first time in the literature, investigates a general frequency correlated setting where a two-antenna transmitter has imperfect knowledge of CSI of two single-antenna users on two adjacent subbands. A new scheme is derived as an integration of Zero-Forcing Beamforming (ZFBF) and the scheme proposed by Maddah-Ali and Tse. The achievable DoF region resulted by this scheme is expressed as a function of the qualities of CSIT.
Self-Organization Promotes the Evolution of Cooperation with Cultural Propagation
Venue: arXiv cs.GT 2013
Year: 2013

In this paper three computational models for the study of the evolution of cooperation under cultural propagation are studied: Kin Selection, Direct Reciprocity and Indirect Reciprocity. Two analyzes are reported, one comparing their behavior between them and a second one identifying the impact that different parameters have in the model dynamics. The results of these analyzes illustrate how game transitions may occur depending of some parameters within the models and also explain how agents adapt to these transitions by individually choosing their attachment to a cooperative attitude. These parameters regulate how cooperation can self-organize under different circumstances. The emergence of the evolution of cooperation as a result of the agent's adapting processes is also discussed.
Arriving on time: estimating travel time distributions on large-scale road networks
Venue: arXiv cs.LG 2013
Year: 2013

Most optimal routing problems focus on minimizing travel time or distance traveled. Oftentimes, a more useful objective is to maximize the probability of on-time arrival, which requires statistical distributions of travel times, rather than just mean values. We propose a method to estimate travel time distributions on large-scale road networks, using probe vehicle data collected from GPS. We present a framework that works with large input of data, and scales linearly with the size of the network. Leveraging the planar topology of the graph, the method computes efficiently the time correlations between neighboring streets. First, raw probe vehicle traces are compressed into pairs of travel times and number of stops for each traversed road segment using a `stop-and-go' algorithm developed for this work. The compressed data is then used as input for training a path travel time model, which couples a Markov model along with a Gaussian Markov random field. Finally, scalable inference algorithms are developed for obtaining path travel time distributions from the composite MM-GMRF model. We illustrate the accuracy and scalability of our model on a 505,000 road link network spanning the San Francisco Bay Area.
A Matrix-Field Weighted Mean-Square-Error Model for MIMO Transceiver Designs
Venue: arXiv cs.IT 2013
Year: 2013

In this letter, we investigate an important and famous issue, namely weighted mean-square-error (MSE) minimization transceiver designs. In our work, for transceiver designs a novel weighted MSE model is proposed, which is defined as a linear matrix function with respect to the traditional data detection MSE matrix. The new model can be interpreted an extension of weighting operation from vector field to matrix field. Based on the proposed weighting operation a general transceiver design is proposed, which aims at minimizing an increasing matrix-monotone function of the output of the previous linear matrix function. The structure of the optimal solutions is also derived. Furthermore, two important special cases of the matrix-monotone functions are discussed in detail. It is also revealed that these two problems are exactly equivalent to the transceiver designs of sum MSE minimization and capacity maximization for dual-hop amplify-and-forward (AF) MIMO relaying systems, respectively. Finally, it is concluded that the AF relaying is undoubtedly this kind of weighting operation.
Why some heaps support constant-amortized-time decrease-key operations, and others do not
Venue: arXiv cs.DS 2013
Year: 2013

A lower bound is presented which shows that a class of heap algorithms in the pointer model with only heap pointers must spend Omega(log log n / log log log n) amortized time on the decrease-key operation (given O(log n) amortized-time extract-min). Intuitively, this bound shows the key to having O(1)-time decrease-key is the ability to sort O(log n) items in O(log n) time; Fibonacci heaps [M.L. Fredman and R. E. Tarjan. J. ACM 34(3):596-615 (1987)] do this through the use of bucket sort. Our lower bound also holds no matter how much data is augmented; this is in contrast to the lower bound of Fredman [J. ACM 46(4):473-501 (1999)] who showed a tradeoff between the number of augmented bits and the amortized cost of decrease-key. A new heap data structure, the sort heap, is presented. This heap is a simplification of the heap of Elmasry [SODA 2009: 471-476] and shares with it a O(log log n) amortized-time decrease-key, but with a straightforward implementation such that our lower bound holds. Thus a natural model is presented for a pointer-based heap such that the amortized runtime of a self-adjusting structure and amortized lower asymptotic bounds for decrease-key differ by but a O(log log log n) factor.
Complexity vs Energy: Theory of Computation and Theoretical Physics
Venue: arXiv cs.CC 2013
Year: 2013

This paper is a survey dedicated to the analogy between the notions of {\it complexity} in theoretical computer science and {\it energy} in physics. This analogy is not metaphorical: I describe three precise mathematical contexts, suggested recently, in which mathematics related to (un)computability is inspired by and to a degree reproduces formalisms of statistical physics and quantum field theory.
Compressive Sensing for Spread Spectrum Receivers
Venue: arXiv cs.IT 2013
Year: 2013

With the advent of ubiquitous computing there are two design parameters of wireless communication devices that become very important power: efficiency and production cost. Compressive sensing enables the receiver in such devices to sample below the Shannon-Nyquist sampling rate, which may lead to a decrease in the two design parameters. This paper investigates the use of Compressive Sensing (CS) in a general Code Division Multiple Access (CDMA) receiver. We show that when using spread spectrum codes in the signal domain, the CS measurement matrix may be simplified. This measurement scheme, named Compressive Spread Spectrum (CSS), allows for a simple, effective receiver design. Furthermore, we numerically evaluate the proposed receiver in terms of bit error rate under different signal to noise ratio conditions and compare it with other receiver structures. These numerical experiments show that though the bit error rate performance is degraded by the subsampling in the CS-enabled receivers, this may be remedied by including quantization in the receiver model. We also study the computational complexity of the proposed receiver design under different sparsity and measurement ratios. Our work shows that it is possible to subsample a CDMA signal using CSS and that in one example the CSS receiver outperforms the classical receiver.
Probabilistic Constraint Satisfaction with Non-Gaussian Noise
Venue: arXiv cs.AI 2013
Year: 2013

We have previously reported a Bayesian algorithm for determining the coordinates of points in three-dimensional space from uncertain constraints. This method is useful in the determination of biological molecular structure. It is limited, however, by the requirement that the uncertainty in the constraints be normally distributed. In this paper, we present an extension of the original algorithm that allows constraint uncertainty to be represented as a mixture of Gaussians, and thereby allows arbitrary constraint distributions. We illustrate the performance of this algorithm on a problem drawn from the domain of molecular structure determination, in which a multicomponent constraint representation produces a much more accurate solution than the old single component mechanism. The new mechanism uses mixture distributions to decompose the problem into a set of independent problems with unimodal constraint uncertainty. The results of the unimodal subproblems are periodically recombined using Bayes' law, to avoid combinatorial explosion. The new algorithm is particularly suited for parallel implementation.