OpenRaiser/Intern-Atlas huggingface dataset:
Capacity of SIMO and MISO Phase-Noise Channels with Common/Separate Oscillators
Venue: arXiv cs.IT 2015
Year: 2015

In multiple antenna systems, phase noise due to instabilities of the radio-frequency (RF) oscillators, acts differently depending on whether the RF circuitries connected to each antenna are driven by separate (independent) local oscillators (SLO) or by a common local oscillator (CLO). In this paper, we investigate the high-SNR capacity of single-input multiple-output (SIMO) and multiple-output single-input (MISO) phase-noise channels for both the CLO and the SLO configurations. Our results show that the first-order term in the high-SNR capacity expansion is the same for all scenarios (SIMO/MISO and SLO/CLO), and equal to $0.5\ln (ρ)$, where $ρ$ stands for the SNR. On the contrary, the second-order term, which we refer to as phase-noise number, turns out to be scenario-dependent. For the SIMO case, the SLO configuration provides a diversity gain, resulting in a larger phase-noise number than for the CLO configuration. For the case of Wiener phase noise, a diversity gain of at least $0.5 \ln(M)$ can be achieved, where $M$ is the number of receive antennas. For the MISO, the CLO configuration yields a higher phase-noise number than the SLO configuration. This is because with the CLO configuration one can obtain a coherent-combining gain through maximum ratio transmission (a.k.a. conjugate beamforming). This gain is unattainable with the SLO configuration.
Probabilistic Rely-guarantee Calculus
Venue: arXiv cs.LO 2015
Year: 2015

Jones' rely-guarantee calculus for shared variable concurrency is extended to include probabilistic behaviours. We use an algebraic approach which combines and adapts probabilistic Kleene algebras with concurrent Kleene algebra. Soundness of the algebra is shown relative to a general probabilistic event structure semantics. The main contribution of this paper is a collection of rely-guarantee rules built on top of that semantics. In particular, we show how to obtain bounds on probabilities by deriving rely-guarantee rules within the true-concurrent denotational semantics. The use of these rules is illustrated by a detailed verification of a simple probabilistic concurrent program: a faulty Eratosthenes sieve.
Longest common substrings with k mismatches
Venue: arXiv cs.DS 2015
Year: 2015

The longest common substring with $k$-mismatches problem is to find, given two strings $S_1$ and $S_2$, a longest substring $A_1$ of $S_1$ and $A_2$ of $S_2$ such that the Hamming distance between $A_1$ and $A_2$ is $\le k$. We introduce a practical $O(nm)$ time and $O(1)$ space solution for this problem, where $n$ and $m$ are the lengths of $S_1$ and $S_2$, respectively. This algorithm can also be used to compute the matching statistics with $k$-mismatches of $S_1$ and $S_2$ in $O(nm)$ time and $O(m)$ space. Moreover, we also present a theoretical solution for the $k = 1$ case which runs in $O(n \log m)$ time, assuming $m\le n$, and uses $O(m)$ space, improving over the existing $O(nm)$ time and $O(m)$ space bound of Babenko and Starikovskaya.
Text mixing shapes the anatomy of rank-frequency distributions: A modern Zipfian mechanics for natural language
Venue: arXiv cs.CL 2015
Year: 2015

Natural languages are full of rules and exceptions. One of the most famous quantitative rules is Zipf's law which states that the frequency of occurrence of a word is approximately inversely proportional to its rank. Though this `law' of ranks has been found to hold across disparate texts and forms of data, analyses of increasingly large corpora over the last 15 years have revealed the existence of two scaling regimes. These regimes have thus far been explained by a hypothesis suggesting a separability of languages into core and non-core lexica. Here, we present and defend an alternative hypothesis, that the two scaling regimes result from the act of aggregating texts. We observe that text mixing leads to an effective decay of word introduction, which we show provides accurate predictions of the location and severity of breaks in scaling. Upon examining large corpora from 10 languages in the Project Gutenberg eBooks collection (eBooks), we find emphatic empirical support for the universality of our claim.
Unsupervised learning of clutter-resistant visual representations from natural videos
Venue: arXiv cs.CV 2015
Year: 2015

Populations of neurons in inferotemporal cortex (IT) maintain an explicit code for object identity that also tolerates transformations of object appearance e.g., position, scale, viewing angle [1, 2, 3]. Though the learning rules are not known, recent results [4, 5, 6] suggest the operation of an unsupervised temporal-association-based method e.g., Foldiak's trace rule [7]. Such methods exploit the temporal continuity of the visual world by assuming that visual experience over short timescales will tend to have invariant identity content. Thus, by associating representations of frames from nearby times, a representation that tolerates whatever transformations occurred in the video may be achieved. Many previous studies verified that such rules can work in simple situations without background clutter, but the presence of visual clutter has remained problematic for this approach. Here we show that temporal association based on large class-specific filters (templates) avoids the problem of clutter. Our system learns in an unsupervised way from natural videos gathered from the internet, and is able to perform a difficult unconstrained face recognition task on natural images: Labeled Faces in the Wild [8].
Alternating Towers and Piecewise Testable Separators
Venue: arXiv cs.FL 2015
Year: 2015

Two languages are separable by a piecewise testable language if and only if there exists no infinite tower between them. An infinite tower is an infinite sequence of strings alternating between the two languages such that every string is a subsequence (scattered substring) of all the strings that follow. For regular languages represented by nondeterministic finite automata, the existence of an infinite tower is decidable in polynomial time. In this paper, we investigate the complexity of a particular method to compute a piecewise testable separator. We show that it is closely related to the height of maximal finite towers, and provide the upper and lower bounds with respect to the size of the given nondeterministic automata. Specifically, we show that the upper bound is polynomial with respect to the number of states with the cardinality of the alphabet in the exponent. Concerning the lower bound, we show that towers of exponential height with respect to the cardinality of the alphabet exist. Since these towers mostly turn out to be sequences of prefixes, we also provide a comparison with towers of prefixes.
Wireless networks appear Poissonian due to strong shadowing
Venue: arXiv cs.NI 2015
Year: 2015

Geographic locations of cellular base stations sometimes can be well fitted with spatial homogeneous Poisson point processes. In this paper we make a complementary observation: In the presence of the log-normal shadowing of sufficiently high variance, the statistics of the propagation loss of a single user with respect to different network stations are invariant with respect to their geographic positioning, whether regular or not, for a wide class of empirically homogeneous networks. Even in perfectly hexagonal case they appear as though they were realized in a Poisson network model, i.e., form an inhomogeneous Poisson point process on the positive half-line with a power-law density characterized by the path-loss exponent. At the same time, the conditional distances to the corresponding base stations, given their observed propagation losses, become independent and log-normally distributed, which can be seen as a decoupling between the real and model geometry. The result applies also to Suzuki (Rayleigh-log-normal) propagation model. We use Kolmogorov-Smirnov test to empirically study the quality of the Poisson approximation and use it to build a linear-regression method for the statistical estimation of the value of the path-loss exponent.
Evaluation of the Spectral Finite Element Method With the Theory of Phononic Crystals
Venue: arXiv cs.CE 2015
Year: 2015

We evaluated the performance of the classical and spectral finite element method in the simulation of elastodynamic problems. We used as a quality measure their ability to capture the actual dispersive behavior of the material. Four different materials are studied: a homogeneous non-dispersive material, a bilayer material, and composite materials consisting of an aluminum matrix and brass inclusions or voids. To obtain the dispersion properties, spatial periodicity is assumed so the analysis is conducted using Floquet-Bloch principles. The effects in the dispersion properties of the lumping process for the mass matrices resulting from the classical finite element method are also investigated, since that is a common practice when the problem is solved with explicit time marching schemes. At high frequencies the predictions with the spectral technique exactly match the analytical dispersion curves, while the classical method does not. This occurs even at the same computational demands. At low frequencies however, the results from both the classical (consistent or mass-lumped) and spectral finite element coincide with the analytically determined curves. Surprisingly, at low frequencies even the results obtained with the artificial diagonal mass matrix from the classical technique exactly match the analytic dispersion curves.
RoBuSt: A Crash-Failure-Resistant Distributed Storage System
Venue: arXiv cs.DS 2015
Year: 2015

In this work we present the first distributed storage system that is provably robust against crash failures issued by an adaptive adversary, i.e., for each batch of requests the adversary can decide based on the entire system state which servers will be unavailable for that batch of requests. Despite up to $γn^{1/\log\log n}$ crashed servers, with $γ>0$ constant and $n$ denoting the number of servers, our system can correctly process any batch of lookup and write requests (with at most a polylogarithmic number of requests issued at each non-crashed server) in at most a polylogarithmic number of communication rounds, with at most polylogarithmic time and work at each server and only a logarithmic storage overhead. Our system is based on previous work by Eikel and Scheideler (SPAA 2013), who presented IRIS, a distributed information system that is provably robust against the same kind of crash failures. However, IRIS is only able to serve lookup requests. Handling both lookup and write requests has turned out to require major changes in the design of IRIS.
Planning Security Services for IT Systems
Venue: arXiv cs.CR 2015
Year: 2015

Often the hardest job is to get business representatives to look at security as something that makes managing their risks and achieving their objectives easier, with security compliance as just part of that journey. This paper addresses that by making planning for security services a 'business tool'.
A Global Approach for Solving Edge-Matching Puzzles
Venue: arXiv cs.CV 2015
Year: 2015

We consider apictorial edge-matching puzzles, in which the goal is to arrange a collection of puzzle pieces with colored edges so that the colors match along the edges of adjacent pieces. We devise an algebraic representation for this problem and provide conditions under which it exactly characterizes a puzzle. Using the new representation, we recast the combinatorial, discrete problem of solving puzzles as a global, polynomial system of equations with continuous variables. We further propose new algorithms for generating approximate solutions to the continuous problem by solving a sequence of convex relaxations.
Reliability of Erasure Coded Storage Systems: A Geometric Approach
Venue: arXiv cs.DC 2015
Year: 2015

We consider the probability of data loss, or equivalently, the reliability function for an erasure coded distributed data storage system under worst case conditions. Data loss in an erasure coded system depends on probability distributions for the disk repair duration and the disk failure duration. In previous works, the data loss probability of such systems has been studied under the assumption of exponentially distributed disk failure and disk repair durations, using well-known analytic methods from the theory of Markov processes. These methods lead to an estimate of the integral of the reliability function. Here, we address the problem of directly calculating the data loss probability for general repair and failure duration distributions. A closed limiting form is developed for the probability of data loss and it is shown that the probability of the event that a repair duration exceeds a failure duration is sufficient for characterizing the data loss probability. For the case of constant repair duration, we develop an expression for the conditional data loss probability given the number of failures experienced by a each node in a given time window. We do so by developing a geometric approach that relies on the computation of volumes of a family of polytopes that are related to the code. An exact calculation is provided and an upper bound on the data loss probability is obtained by posing the problem as a set avoidance problem. Theoretical calculations are compared to simulation results.
More is less: Connectivity in fractal regions
Venue: arXiv cs.NI 2015
Year: 2015

Ad-hoc networks are often deployed in regions with complicated boundaries. We show that if the boundary is modeled as a fractal, a network requiring line of sight connections has the counterintuitive property that increasing the number of nodes decreases the full connection probability. We characterise this decay as a stretched exponential involving the fractal dimension of the boundary, and discuss mitigation strategies. Applications of this study include the analysis and design of sensor networks operating in rugged terrain (e.g. railway cuttings), mm-wave networks in industrial settings and vehicle-to-vehicle/vehicle-to-infrastructure networks in urban environments.
On The Power of Joint Wavelet-DCT Features for Multispectral Palmprint Recognition
Venue: arXiv cs.CV 2015
Year: 2015

Biometric-based identification has drawn a lot of attention in the recent years. Among all biometrics, palmprint is known to possess a rich set of features. In this paper we have proposed to use DCT-based features in parallel with wavelet-based ones for palmprint identification. PCA is applied to the features to reduce their dimensionality and the majority voting algorithm is used to perform classification. The features introduced here result in a near-perfectly accurate identification. This method is tested on a well-known multispectral palmprint database and an accuracy rate of 99.97-100\% is achieved, outperforming all previous methods in similar conditions.
Autonomous robots and the SP theory of intelligence
Venue: arXiv cs.AI 2015
Year: 2015

This article is about how the "SP theory of intelligence" and its realisation in the "SP machine" (both outlined in the article) may help to solve computer-related problems in the design of autonomous robots, meaning robots that do not depend on external intelligence or power supplies, are mobile, and are designed to exhibit as much human-like intelligence as possible. The article is about: how to increase the computational and energy efficiency of computers and reduce their bulk; how to achieve human-like versatility in intelligence; and likewise for human-like adaptability in intelligence. The SP system has potential for substantial gains in computational and energy efficiency and reductions in the bulkiness of computers: by reducing the size of data to be processed; by exploiting statistical information that the system gathers; and via an updated version of Donald Hebb's concept of a "cell assembly". Towards human-like versatility in intelligence, the SP system has strengths in unsupervised learning, natural language processing, pattern recognition, information retrieval, several kinds of reasoning, planning, problem solving, and more, with seamless integration amongst structures and functions. The SP system's strengths in unsupervised learning and other aspects of intelligence may help to achieve human-like adaptability in intelligence via: the learning of natural language; learning to see; building 3D models of objects and of a robot's surroundings; learning regularities in the workings of a robot and in the robot's environment; exploration and play; learning major skills; and secondary forms of learning. Also discussed are: how the SP system may process parallel streams of information; generalisation of knowledge, correction of over-generalisations, and learning from dirty data; how to cut the cost of learning; and reinforcements, motivations, goals, and demonstration.
Capacity Region of MISO Broadcast Channel for Simultaneous Wireless Information and Power Transfer
Venue: arXiv cs.IT 2015
Year: 2015

This paper studies a multiple-input single-output (MISO) broadcast channel (BC) featuring simultaneous wireless information and power transfer (SWIPT), where a multi-antenna access point (AP) delivers both information and energy via radio signals to multiple single-antenna receivers simultaneously, and each receiver implements either information decoding (ID) or energy harvesting (EH). In particular, pseudo-random sequences that are {\it a priori} known and therefore can be cancelled at each ID receiver is used as the energy signals, and the information-theoretically optimal dirty paper coding (DPC) is employed for the information transmission. We characterize the capacity region for ID receivers under given energy requirements for EH receivers, by solving a sequence of weighted sum-rate (WSR) maximization (WSRMax) problems subject to a maximum sum-power constraint for the AP, and a set of minimum harvested power constraints for individual EH receivers. The problem corresponds to a new form of WSRMax problem in MISO-BC with combined maximum and minimum linear transmit covariance constraints (MaxLTCCs and MinLTCCs), which differs from the celebrated capacity region characterization problem for MISO-BC under a set of MaxLTCCs only and is challenging to solve. By extending the general BC-multiple access channel (MAC) duality, which is only applicable to WSRMax problems with MaxLTCCs, and applying the ellipsoid method, we propose an efficient algorithm to solve this problem globally optimally. Furthermore, we also propose two suboptimal algorithms with lower complexity by assuming that the information and energy signals are designed separately. Finally, numerical results are provided to validate our proposed algorithms.
The Odds of Staying on Budget
Venue: arXiv cs.CC 2015
Year: 2015

Given Markov chains and Markov decision processes (MDPs) whose transitions are labelled with non-negative integer costs, we study the computational complexity of deciding whether the probability of paths whose accumulated cost satisfies a Boolean combination of inequalities exceeds a given threshold. For acyclic Markov chains, we show that this problem is PP-complete, whereas it is hard for the PosSLP problem and in PSPACE for general Markov chains. Moreover, for acyclic and general MDPs, we prove PSPACE- and EXP-completeness, respectively. Our results have direct implications on the complexity of computing reward quantiles in succinctly represented stochastic systems.
Stochastic Subgradient Algorithms for Strongly Convex Optimization over Distributed Networks
Venue: arXiv cs.NA 2015
Year: 2015

We study diffusion and consensus based optimization of a sum of unknown convex objective functions over distributed networks. The only access to these functions is through stochastic gradient oracles, each of which is only available at a different node, and a limited number of gradient oracle calls is allowed at each node. In this framework, we introduce a convex optimization algorithm based on the stochastic gradient descent (SGD) updates. Particularly, we use a carefully designed time-dependent weighted averaging of the SGD iterates, which yields a convergence rate of $O\left(\frac{N\sqrt{N}}{T}\right)$ after $T$ gradient updates for each node on a network of $N$ nodes. We then show that after $T$ gradient oracle calls, the average SGD iterate achieves a mean square deviation (MSD) of $O\left(\frac{\sqrt{N}}{T}\right)$. This rate of convergence is optimal as it matches the performance lower bound up to constant terms. Similar to the SGD algorithm, the computational complexity of the proposed algorithm also scales linearly with the dimensionality of the data. Furthermore, the communication load of the proposed method is the same as the communication load of the SGD algorithm. Thus, the proposed algorithm is highly efficient in terms of complexity and communication load. We illustrate the merits of the algorithm with respect to the state-of-art methods over benchmark real life data sets and widely studied network topologies.
A Multi-World Approach to Question Answering about Real-World Scenes based on Uncertain Input
Venue: arXiv cs.AI 2015
Year: 2015

We propose a method for automatically answering questions about images by bringing together recent advances from natural language processing and computer vision. We combine discrete reasoning with uncertain predictions by a multi-world approach that represents uncertainty about the perceived world in a bayesian framework. Our approach can handle human questions of high complexity about realistic scenes and replies with range of answer like counts, object classes, instances and lists of them. The system is directly trained from question-answer pairs. We establish a first benchmark for this task that can be seen as a modern attempt at a visual turing test.
On the Computational Complexity of MapReduce
Venue: arXiv cs.CC 2015
Year: 2015

In this paper we study MapReduce computations from a complexity-theoretic perspective. First, we formulate a uniform version of the MRC model of Karloff et al. (2010). We then show that the class of regular languages, and moreover all of sublogarithmic space, lies in constant round MRC. This result also applies to the MPC model of Andoni et al. (2014). In addition, we prove that, conditioned on a variant of the Exponential Time Hypothesis, there are strict hierarchies within MRC so that increasing the number of rounds or the amount of time per processor increases the power of MRC. To the best of our knowledge we are the first to approach the MapReduce model with complexity-theoretic techniques, and our work lays the foundation for further analysis relating MapReduce to established complexity classes.
Terminated and Tailbiting Spatially-Coupled Codes with Optimized Bit Mappings for Spectrally Efficient Fiber-Optical Systems
Venue: arXiv cs.IT 2015
Year: 2015

We study the design of spectrally efficient fiber-optical communication systems based on different spatially coupled (SC) forward error correction (FEC) schemes. In particular, we optimize the allocation of the coded bits from the FEC encoder to the modulation bits of the signal constellation. Two SC code classes are considered. The codes in the first class are protograph-based low-density parity-check (LDPC) codes which are decoded using iterative soft-decision decoding. The codes in the second class are generalized LDPC codes which are decoded using iterative hard-decision decoding. For both code classes, the bit allocation is optimized for the terminated and tailbiting SC cases based on a density evolution analysis. An optimized bit allocation can significantly improve the performance of tailbiting SC codes codes over the baseline sequential allocation, up to the point where they have a comparable gap to capacity as their terminated counterparts, at a lower FEC overhead. For the considered terminated SC codes, the optimization only results in marginal performance improvements, suggesting that in this case a sequential allocation is close to optimal.