OpenRaiser/Intern-Atlas huggingface dataset:
Perfect Output Feedback in the Two-User Decentralized Interference Channel
Venue: arXiv cs.IT 2015
Year: 2015

In this paper, the $η$-Nash equilibrium ($η$-NE) region of the two-user Gaussian interference channel (IC) with perfect output feedback is approximated to within $1$ bit/s/Hz and $η$ arbitrarily close to $1$ bit/s/Hz. The relevance of the $η$-NE region is that it provides the set of rate-pairs that are achievable and stable in the IC when both transmitter-receiver pairs autonomously tune their own transmit-receive configurations seeking an $η$-optimal individual transmission rate. Therefore, any rate tuple outside the $η$-NE region is not stable as there always exists one link able to increase by at least $η$ bits/s/Hz its own transmission rate by updating its own transmit-receive configuration. The main insights that arise from this work are: $(i)$ The $η$-NE region achieved with feedback is larger than or equal to the $η$-NE region without feedback. More importantly, for each rate pair achievable at an $η$-NE without feedback, there exists at least one rate pair achievable at an $η$-NE with feedback that is weakly Pareto superior. $(ii)$ There always exists an $η$-NE transmit-receive configuration that achieves a rate pair that is at most $1$ bit/s/Hz per user away from the outer bound of the capacity region.
The SP theory of intelligence: an overview
Venue: arXiv cs.AI 2015
Year: 2015

This article is an overview of the "SP theory of intelligence". The theory aims to simplify and integrate concepts across artificial intelligence, mainstream computing and human perception and cognition, with information compression as a unifying theme. It is conceived as a brain-like system that receives 'New' information and stores some or all of it in compressed form as 'Old' information. It is realised in the form of a computer model -- a first version of the SP machine. The concept of "multiple alignment" is a powerful central idea. Using heuristic techniques, the system builds multiple alignments that are 'good' in terms of information compression. For each multiple alignment, probabilities may be calculated. These provide the basis for calculating the probabilities of inferences. The system learns new structures from partial matches between patterns. Using heuristic techniques, the system searches for sets of structures that are 'good' in terms of information compression. These are normally ones that people judge to be 'natural', in accordance with the 'DONSVIC' principle -- the discovery of natural structures via information compression. The SP theory may be applied in several areas including 'computing', aspects of mathematics and logic, representation of knowledge, natural language processing, pattern recognition, several kinds of reasoning, information storage and retrieval, planning and problem solving, information compression, neuroscience, and human perception and cognition. Examples include the parsing and production of language including discontinuous dependencies in syntax, pattern recognition at multiple levels of abstraction and its integration with part-whole relations, nonmonotonic reasoning and reasoning with default values, reasoning in Bayesian networks including 'explaining away', causal diagnosis, and the solving of a geometric analogy problem.
Counting thin subgraphs via packings faster than meet-in-the-middle time
Venue: arXiv cs.DS 2015
Year: 2015

Vassilevska and Williams (STOC 2009) showed how to count simple paths on $k$ vertices and matchings on $k/2$ edges in an $n$-vertex graph in time $n^{k/2+O(1)}$. In the same year, two different algorithms with the same runtime were given by Koutis and Williams~(ICALP 2009), and Björklund \emph{et al.} (ESA 2009), via $n^{st/2+O(1)}$-time algorithms for counting $t$-tuples of pairwise disjoint sets drawn from a given family of $s$-sized subsets of an $n$-element universe. Shortly afterwards, Alon and Gutner (TALG 2010) showed that these problems have $Ω(n^{\lfloor st/2\rfloor})$ and $Ω(n^{\lfloor k/2\rfloor})$ lower bounds when counting by color coding. Here we show that one can do better, namely, we show that the "meet-in-the-middle" exponent $st/2$ can be beaten and give an algorithm that counts in time $n^{0.45470382 st + O(1)}$ for $t$ a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on $k$ vertices and pathwidth $p\ll k$ in an $n$-vertex graph in $n^{0.45470382k+2p+O(1)}$ time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. We also give improved bounds for counting $t$-tuples of disjoint $s$-sets for $s=2,3,4$. Our algorithms use fast matrix multiplication. We show an argument that this is necessary to go below the meet-in-the-middle barrier.
Improving A*OMP: Theoretical and Empirical Analyses With a Novel Dynamic Cost Model
Venue: arXiv cs.IT 2015
Year: 2015

Best-first search has been recently utilized for compressed sensing (CS) by the A* orthogonal matching pursuit (A*OMP) algorithm. In this work, we concentrate on theoretical and empirical analyses of A*OMP. We present a restricted isometry property (RIP) based general condition for exact recovery of sparse signals via A*OMP. In addition, we develop online guarantees which promise improved recovery performance with the residue-based termination instead of the sparsity-based one. We demonstrate the recovery capabilities of A*OMP with extensive recovery simulations using the adaptive-multiplicative (AMul) cost model, which effectively compensates for the path length differences in the search tree. The presented results, involving phase transitions for different nonzero element distributions as well as recovery rates and average error, reveal not only the superior recovery accuracy of A*OMP, but also the improvements with the residue-based termination and the AMul cost model. Comparison of the run times indicate the speed up by the AMul cost model. We also demonstrate a hybrid of OMP and A?OMP to accelerate the search further. Finally, we run A*OMP on a sparse image to illustrate its recovery performance for more realistic coefcient distributions.
Orthogonal Matching Pursuit with Thresholding and its Application in Compressive Sensing
Venue: arXiv cs.IT 2015
Year: 2015

Greed is good. However, the tighter you squeeze, the less you have. In this paper, a less greedy algorithm for sparse signal reconstruction in compressive sensing, named orthogonal matching pursuit with thresholding is studied. Using the global 2-coherence , which provides a "bridge" between the well known mutual coherence and the restricted isometry constant, the performance of orthogonal matching pursuit with thresholding is analyzed and more general results for sparse signal reconstruction are obtained. It is also shown that given the same assumption on the coherence index and the restricted isometry constant as required for orthogonal matching pursuit, the thresholding variation gives exactly the same reconstruction performance with significantly less complexity.
Expander Chunked Codes
Venue: arXiv cs.IT 2015
Year: 2015

Chunked codes are efficient random linear network coding (RLNC) schemes with low computational cost, where the input packets are encoded into small chunks (i.e., subsets of the coded packets). During the network transmission, RLNC is performed within each chunk. In this paper, we first introduce a simple transfer matrix model to characterize the transmission of chunks, and derive some basic properties of the model to facilitate the performance analysis. We then focus on the design of overlapped chunked codes, a class of chunked codes whose chunks are non-disjoint subsets of input packets, which are of special interest since they can be encoded with negligible computational cost and in a causal fashion. We propose expander chunked (EC) codes, the first class of overlapped chunked codes that have an analyzable performance,where the construction of the chunks makes use of regular graphs. Numerical and simulation results show that in some practical settings, EC codes can achieve rates within 91 to 97 percent of the optimum and outperform the state-of-the-art overlapped chunked codes significantly.
On the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines
Venue: arXiv cs.DS 2015
Year: 2015

We consider a special case of the ordinary NP-hard two-machine flow shop problem with the objective of determining simultaneously a minimal common due date and the minimal number of tardy jobs. In [S. S. Panwalkar, C. Koulamas, An O(n^2) algorithm for the variable common due date, minimal tardy jobs bicriteria two-machine flow shop problem with ordered machines, European Journal of Operational Research 221 (2012), 7-13.], the authors presented quadratic algorithm for the problem when each job has its smaller processing time on the first machine. In this note, we improve the running time of the algorithm to O(n log n) by efficient implementation using recently introduced modified binary tree data structure.
Toward the Coevolution of Novel Vertical-Axis Wind Turbines
Venue: arXiv cs.NE 2015
Year: 2015

The production of renewable and sustainable energy is one of the most important challenges currently facing mankind. Wind has made an increasing contribution to the world's energy supply mix, but still remains a long way from reaching its full potential. In this paper, we investigate the use of artificial evolution to design vertical-axis wind turbine prototypes that are physically instantiated and evaluated under fan generated wind conditions. Initially a conventional evolutionary algorithm is used to explore the design space of a single wind turbine and later a cooperative coevolutionary algorithm is used to explore the design space of an array of wind turbines. Artificial neural networks are used throughout as surrogate models to assist learning and found to reduce the number of fabrications required to reach a higher aerodynamic efficiency. Unlike in other approaches, such as computational fluid dynamics simulations, no mathematical formulations are used and no model assumptions are made.
Sublinear Matching With Finite Automata Using Reverse Suffix Scanning
Venue: arXiv cs.DS 2015
Year: 2015

We give algorithms to accelerate the computation of deterministic finite automata (DFA) by calculating the state of a DFA n positions ahead utilizing a reverse scan of the next n characters. Often this requires scanning fewer than n characters resulting in a fraction of the input being skipped and a commensurate increase in processing speed. The skipped fraction is > 80% in several of our examples. We introduce offsetting finite automata (OFA) to encode the accelerated computation. OFA generalize DFA by adding an integer offset to the current input index at each state transition. We give algorithms for constructing an OFA that accepts the same language as a DFA while possibly skipping input, and for matching with an OFA. Compared to previous algorithms that attempt to skip some of the input, the new matching algorithm can skip more often and can skip farther. In the worst case the new matching algorithm scans the same number of characters as a simple forward scan, whereas previous approaches often scan more, so the new algorithm can be used as a reliable replacement for the simple forward scan. Additionally, the new algorithm adapts to available memory and time constraints.
Bandwidth Aggregation Techniques in Heterogeneous Multi-homed Devices: A Survey
Venue: arXiv cs.NI 2015
Year: 2015

The widespread deployment of various networking technologies, coupled with the exponential increase in end- user data demand, have led to the proliferation of multi-homed, or multi-interface enabled, devices. These trends drove researchers to investigate a wide spectrum of solutions, at different layers of the protocol stack, that utilize available interfaces in such devices by aggregating their bandwidth. In this survey paper, we provide an overview and examine the evolution of bandwidth aggregation solutions over time. We begin by describing the bandwidth aggregation problem. We investigate the common features of proposed bandwidth aggregation systems and break them down into two major categories: layer-dependent and layer-independent features. Afterwards, we discuss the evolution trends in the literature and discuss some open challenges requiring further research. We end the survey with a brief presentation of related work in tangential research areas.
Dispersion Analysis of Infinite Constellations in Ergodic Fading Channels
Venue: arXiv cs.IT 2015
Year: 2015

This thesis considers infinite constellations in fading channels, without power constraint and with perfect channel state information available at the receiver. Infinite constellations are the framework, proposed by Poltyrev, for analyzing coded modulation codes. The Poltyrev's capacity, is the highest achievable normalized log density (NLD) of codewords per unit volume, at possibly large block length, that guarantees a vanishing error probability. For a given finite block length and a fixed error probability, there is a gap between the highest achievable NLD and Poltyrev's capacity. The dispersion analysis quantifies asymptotically this gap. The thesis begins by the dispersion analysis of infinite constellations in scalar fading channels. Later on, we extend the analysis to the case of multiple input multiple output fading channels. As in other channels, we show that the gap between the highest achievable NLD and the Poltyrev's capacity, vanishes asymptotically as the square root of the channel dispersion over the block length, multiplied by the inverse Q-function of the allowed error probability. Moreover, exact terms for Poltyrev's capacity and channel dispersion, are derived in the thesis. The relations to the amplitude and to the power constrained fading channels are also discussed, especially in terms of capacity, channel dispersion and error exponents. These relations hint that in typical cases the unconstrained model can be interpreted as the limit of the constrained model, when the signal to noise ratio tends to infinity.
Distance Oracles for Time-Dependent Networks
Venue: arXiv cs.DS 2015
Year: 2015

We present the first approximate distance oracle for sparse directed networks with time-dependent arc-travel-times determined by continuous, piecewise linear, positive functions possessing the FIFO property. Our approach precomputes $(1+ε)-$approximate distance summaries from selected landmark vertices to all other vertices in the network. Our oracle uses subquadratic space and time preprocessing, and provides two sublinear-time query algorithms that deliver constant and $(1+σ)-$approximate shortest-travel-times, respectively, for arbitrary origin-destination pairs in the network, for any constant $σ> ε$. Our oracle is based only on the sparsity of the network, along with two quite natural assumptions about travel-time functions which allow the smooth transition towards asymmetric and time-dependent distance metrics.
A Unified Framework for Representation-based Subspace Clustering of Out-of-sample and Large-scale Data
Venue: arXiv cs.LG 2015
Year: 2015

Under the framework of spectral clustering, the key of subspace clustering is building a similarity graph which describes the neighborhood relations among data points. Some recent works build the graph using sparse, low-rank, and $\ell_2$-norm-based representation, and have achieved state-of-the-art performance. However, these methods have suffered from the following two limitations. First, the time complexities of these methods are at least proportional to the cube of the data size, which make those methods inefficient for solving large-scale problems. Second, they cannot cope with out-of-sample data that are not used to construct the similarity graph. To cluster each out-of-sample datum, the methods have to recalculate the similarity graph and the cluster membership of the whole data set. In this paper, we propose a unified framework which makes representation-based subspace clustering algorithms feasible to cluster both out-of-sample and large-scale data. Under our framework, the large-scale problem is tackled by converting it as out-of-sample problem in the manner of "sampling, clustering, coding, and classifying". Furthermore, we give an estimation for the error bounds by treating each subspace as a point in a hyperspace. Extensive experimental results on various benchmark data sets show that our methods outperform several recently-proposed scalable methods in clustering large-scale data set.
Hopping over Big Data: Accelerating Ad-hoc OLAP Queries with Grasshopper Algorithms
Venue: arXiv cs.DB 2015
Year: 2015

This paper presents a family of algorithms for fast subset filtering within ordered sets of integers representing composite keys. Applications include significant acceleration of (ad-hoc) analytic queries against a data warehouse without any additional indexing. The algorithms work for point, range and set restrictions on multiple attributes, in any combination, and are inherently multidimensional. The main idea consists in intelligent combination of sequential crawling with jumps over large portions of irrelevant keys. The way to combine them is adaptive to characteristics of the underlying data store.
Quantified Constraints and Containment Problems
Venue: arXiv cs.LO 2015
Year: 2015

The quantified constraint satisfaction problem $\mathrm{QCSP}(\mathcal{A})$ is the problem to decide whether a positive Horn sentence, involving nothing more than the two quantifiers and conjunction, is true on some fixed structure $\mathcal{A}$. We study two containment problems related to the QCSP. Firstly, we give a combinatorial condition on finite structures $\mathcal{A}$ and $\mathcal{B}$ that is necessary and sufficient to render $\mathrm{QCSP}(\mathcal{A}) \subseteq \mathrm{QCSP}(\mathcal{B})$. We prove that $\mathrm{QCSP}(\mathcal{A}) \subseteq \mathrm{QCSP}(\mathcal{B})$, that is all sentences of positive Horn logic true on $\mathcal{A}$ are true on $\mathcal{B}$, iff there is a surjective homomorphism from $\mathcal{A}^{|A|^{|B|}}$ to $\mathcal{B}$. This can be seen as improving an old result of Keisler that shows the former equivalent to there being a surjective homomorphism from $\mathcal{A}^ω$ to $\mathcal{B}$. We note that this condition is already necessary to guarantee containment of the $Π_2$ restriction of the QCSP, that is $Π_2$-$\mathrm{CSP}(\mathcal{A}) \subseteq Π_2$-$\mathrm{CSP}(\mathcal{B})$. The exponent's bound of ${|A|^{|B|}}$ places the decision procedure for the model containment problem in non-deterministic double-exponential time complexity. We further show the exponent's bound $|A|^{|B|}$ to be close to tight by giving a sequence of structures $\mathcal{A}$ together with a fixed $\mathcal{B}$, $|B|=2$, such that there is a surjective homomorphism from $\mathcal{A}^r$ to $\mathcal{B}$ only when $r \geq |A|$. Secondly, we prove that the entailment problem for positive Horn fragment of first-order logic is decidable. That is, given two sentences $φ$ and $ψ$ of positive Horn, we give an algorithm that determines whether $φ\rightarrow ψ$ is true in all structures (models). Our result is in some sense tight, since we show that the entailment problem for positive first-order logic (i.e. positive Horn plus disjunction) is undecidable. In the final part of the paper we ponder a notion of Q-core that is some canonical representative among the class of templates that engender the same QCSP. Although the Q-core is not as well-behaved as its better known cousin the core, we demonstrate that it is still a useful notion in the realm of QCSP complexity classifications.
Simple Dynamics for Plurality Consensus
Venue: arXiv cs.DM 2015
Year: 2015

We study a \emph{Plurality-Consensus} process in which each of $n$ anonymous agents of a communication network initially supports an opinion (a color chosen from a finite set $[k]$). Then, in every (synchronous) round, each agent can revise his color according to the opinions currently held by a random sample of his neighbors. It is assumed that the initial color configuration exhibits a sufficiently large \emph{bias} $s$ towards a fixed plurality color, that is, the number of nodes supporting the plurality color exceeds the number of nodes supporting any other color by $s$ additional nodes. The goal is having the process to converge to the \emph{stable} configuration in which all nodes support the initial plurality. We consider a basic model in which the network is a clique and the update rule (called here the \emph{3-majority dynamics}) of the process is the following: each agent looks at the colors of three random neighbors and then applies the majority rule (breaking ties uniformly). We prove that the process converges in time $\mathcal{O}( \min\{ k, (n/\log n)^{1/3} \} \, \log n )$ with high probability, provided that $s \geqslant c \sqrt{ \min\{ 2k, (n/\log n)^{1/3} \}\, n \log n}$. We then prove that our upper bound above is tight as long as $k \leqslant (n/\log n)^{1/4}$. This fact implies an exponential time-gap between the plurality-consensus process and the \emph{median} process studied by Doerr et al. in [ACM SPAA'11]. A natural question is whether looking at more (than three) random neighbors can significantly speed up the process. We provide a negative answer to this question: In particular, we show that samples of polylogarithmic size can speed up the process by a polylogarithmic factor only.
Sublinear Column-wise Actions of the Matrix Exponential on Social Networks
Venue: arXiv cs.SI 2015
Year: 2015

We consider stochastic transition matrices from large social and information networks. For these matrices, we describe and evaluate three fast methods to estimate one column of the matrix exponential. The methods are designed to exploit the properties inherent in social networks, such as a power-law degree distribution. Using only this property, we prove that one of our algorithms has a sublinear runtime. We present further experimental evidence showing that all of them run quickly on social networks with billions of edges and accurately identify the largest elements of the column.
Weak bisimulation for coalgebras over order enriched monads
Venue: arXiv cs.LO 2015
Year: 2015

The paper introduces the notion of a weak bisimulation for coalgebras whose type is a monad satisfying some extra properties. In the first part of the paper we argue that systems with silent moves should be modelled coalgebraically as coalgebras whose type is a monad. We show that the visible and invisible part of the functor can be handled internally inside a monadic structure. In the second part we introduce the notion of an ordered saturation monad, study its properties, and show that it allows us to present two approaches towards defining weak bisimulation for coalgebras and compare them. We support the framework presented in this paper by two main examples of models: labelled transition systems and simple Segala systems.