OpenRaiser/Intern-Atlas huggingface dataset:
A framework for the automation of generalised stability theory
Venue: arXiv cs.MS 2013
Year: 2013

The traditional approach to investigating the stability of a physical system is to linearise the equations about a steady base solution, and to examine the eigenvalues of the linearised operator. Over the past several decades, it has been recognised that this approach only determines the asymptotic stability of the system, and neglects the possibility of transient perturbation growth arising due to the nonnormality of the system. This observation motivated the development of a more powerful generalised stability theory (GST), which focusses instead on the singular value decomposition of the linearised propagator of the system. While GST has had significant successes in understanding the stability of phenomena in geophysical fluid dynamics, its more widespread applicability has been hampered by the fact that computing the SVD requires both the tangent linear operator and its adjoint: deriving the tangent linear and adjoint models is usually a considerable challenge, and manually embedding them inside an eigensolver is laborious. In this paper, we present a framework for the automation of generalised stability theory, which overcomes these difficulties. Given a compact high-level symbolic representation of a finite element discretisation implemented in the FEniCS system, efficient C++ code is automatically generated to assemble the forward, tangent linear and adjoint models; these models are then used to calculate the optimally growing perturbations to the forward model, and their growth rates. By automating the stability computations, we hope to make these powerful tools a more routine part of computational analysis. The efficiency and generality of the framework is demonstrated with applications drawn from geophysical fluid dynamics, phase separation and quantum mechanics.
Repetition Avoidance in Circular Factors
Venue: arXiv cs.FL 2013
Year: 2013

We consider the following novel variation on a classical avoidance problem from combinatorics on words: instead of avoiding repetitions in all factors of a word, we avoid repetitions in all factors where each individual factor is considered as a "circular word", i.e., the end of the word wraps around to the beginning. We determine the best possible avoidance exponent for alphabet size 2 and 3, and provide a lower bound for larger alphabets.
Building Confidential and Efficient Query Services in the Cloud with RASP Data Perturbation
Venue: arXiv cs.DB 2013
Year: 2013

With the wide deployment of public cloud computing infrastructures, using clouds to host data query services has become an appealing solution for the advantages on scalability and cost-saving. However, some data might be sensitive that the data owner does not want to move to the cloud unless the data confidentiality and query privacy are guaranteed. On the other hand, a secured query service should still provide efficient query processing and significantly reduce the in-house workload to fully realize the benefits of cloud computing. We propose the RASP data perturbation method to provide secure and efficient range query and kNN query services for protected data in the cloud. The RASP data perturbation method combines order preserving encryption, dimensionality expansion, random noise injection, and random projection, to provide strong resilience to attacks on the perturbed data and queries. It also preserves multidimensional ranges, which allows existing indexing techniques to be applied to speedup range query processing. The kNN-R algorithm is designed to work with the RASP range query algorithm to process the kNN queries. We have carefully analyzed the attacks on data and queries under a precisely defined threat model and realistic security assumptions. Extensive experiments have been conducted to show the advantages of this approach on efficiency and security.
Interdisciplinarity at the Journal and Specialty Level: The changing knowledge bases of the journal Cognitive Science
Venue: arXiv cs.DL 2013
Year: 2013

Using the referencing patterns in articles in Cognitive Science over three decades, we analyze the knowledge base of this literature in terms of its changing disciplinary composition. Three periods are distinguished: (1) construction of the interdisciplinary space in the 1980s; (2) development of an interdisciplinary orientation in the 1990s; (3) reintegration into "cognitive psychology" in the 2000s. The fluidity and fuzziness of the interdisciplinary delineations in the different visualizations can be reduced and clarified using factor analysis. We also explore newly available routines ("CorText") to analyze this development in terms of "tubes" using an alluvial map, and compare the results with an animation (using "visone"). The historical specificity of this development can be compared with the development of "artificial intelligence" into an integrated specialty during this same period. "Interdisciplinarity" should be defined differently at the level of journals and of specialties.
The Optimal Mechanism in Differential Privacy
Venue: arXiv cs.CR 2013
Year: 2013

We derive the optimal $ε$-differentially private mechanism for single real-valued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has {\em staircase-shaped} probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a {\em geometric mixture of uniform probability distributions}, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the optimal noise probability distributions with minimum expectation of noise amplitude and power. Comparing the optimal performances with those of the Laplacian mechanism, we show that in the high privacy regime ($ε$ is small), Laplacian mechanism is asymptotically optimal as $ε\to 0$; in the low privacy regime ($ε$ is large), the minimum expectation of noise amplitude and minimum noise power are $Θ(Δe^{-\fracε{2}})$ and $Θ(Δ^2 e^{-\frac{2ε}{3}})$ as $ε\to +\infty$, while the expectation of noise amplitude and power using the Laplacian mechanism are $\fracΔε$ and $\frac{2Δ^2}{ε^2}$, where $Δ$ is the sensitivity of the query function. We conclude that the gains are more pronounced in the low privacy regime.
Distributed Adaptive Networks: A Graphical Evolutionary Game-Theoretic View
Venue: arXiv cs.GT 2013
Year: 2013

Distributed adaptive filtering has been considered as an effective approach for data processing and estimation over distributed networks. Most existing distributed adaptive filtering algorithms focus on designing different information diffusion rules, regardless of the nature evolutionary characteristic of a distributed network. In this paper, we study the adaptive network from the game theoretic perspective and formulate the distributed adaptive filtering problem as a graphical evolutionary game. With the proposed formulation, the nodes in the network are regarded as players and the local combiner of estimation information from different neighbors is regarded as different strategies selection. We show that this graphical evolutionary game framework is very general and can unify the existing adaptive network algorithms. Based on this framework, as examples, we further propose two error-aware adaptive filtering algorithms. Moreover, we use graphical evolutionary game theory to analyze the information diffusion process over the adaptive networks and evolutionarily stable strategy of the system. Finally, simulation results are shown to verify the effectiveness of our analysis and proposed methods.
Similarity of Polygonal Curves in the Presence of Outliers
Venue: arXiv cs.CG 2013
Year: 2013

The Fréchet distance is a well studied and commonly used measure to capture the similarity of polygonal curves. Unfortunately, it exhibits a high sensitivity to the presence of outliers. Since the presence of outliers is a frequently occurring phenomenon in practice, a robust variant of Fréchet distance is required which absorbs outliers. We study such a variant here. In this modified variant, our objective is to minimize the length of subcurves of two polygonal curves that need to be ignored (MinEx problem), or alternately, maximize the length of subcurves that are preserved (MaxIn problem), to achieve a given Fréchet distance. An exact solution to one problem would imply an exact solution to the other problem. However, we show that these problems are not solvable by radicals over $\mathbb{Q}$ and that the degree of the polynomial equations involved is unbounded in general. This motivates the search for approximate solutions. We present an algorithm, which approximates, for a given input parameter $δ$, optimal solutions for the \MinEx\ and \MaxIn\ problems up to an additive approximation error $δ$ times the length of the input curves. The resulting running time is upper bounded by $\mathcal{O} \left(\frac{n^3}δ \log \left(\frac{n}δ \right)\right)$, where $n$ is the complexity of the input polygonal curves.
Deciding Monotone Duality and Identifying Frequent Itemsets in Quadratic Logspace
Venue: arXiv cs.DS 2013
Year: 2013

The monotone duality problem is defined as follows: Given two monotone formulas f and g in iredundant DNF, decide whether f and g are dual. This problem is the same as duality testing for hypergraphs, that is, checking whether a hypergraph H consists of precisely all minimal transversals of a simple hypergraph G. By exploiting a recent problem-decomposition method by Boros and Makino (ICALP 2009), we show that duality testing for hypergraphs, and thus for monotone DNFs, is feasible in DSPACE[log^2 n], i.e., in quadratic logspace. As the monotone duality problem is equivalent to a number of problems in the areas of databases, data mining, and knowledge discovery, the results presented here yield new complexity results for those problems, too. For example, it follows from our results that whenever for a Boolean-valued relation (whose attributes represent items), a number of maximal frequent itemsets and a number of minimal infrequent itemsets are known, then it can be decided in quadratic logspace whether there exist additional frequent or infrequent itemsets.
Asymptotic Optimality of Equal Power Allocation for Linear Estimation of WSS Random Processes
Venue: arXiv cs.IT 2013
Year: 2013

This letter establishes the asymptotic optimality of equal power allocation for measurements of a continuous wide-sense stationary (WSS) random process with a square-integrable autocorrelation function when linear estimation is used on equally-spaced measurements with periodicity meeting the Nyquist criterion and with the variance of the noise on any sample inversely proportional to the power expended by the user to obtain that measurement.
Chaotic Analog-to-Information Conversion: Principle and Reconstructability with Parameter Identifiability
Venue: arXiv cs.IT 2013
Year: 2013

This paper proposes a chaos-based analog-to-information conversion system for the acquisition and reconstruction of sparse analog signals. The sparse signal acts as an excitation term of a continuous-time chaotic system and the compressive measurements are performed by sampling chaotic system outputs. The reconstruction is realized through the estimation of the sparse coefficients with principle of chaotic parameter estimation. With the deterministic formulation, the analysis on the reconstructability is conducted via the sensitivity matrix from the parameter identifiability of chaotic systems. For the sparsity-regularized nonlinear least squares estimation, it is shown that the sparse signal is locally reconstructable if the columns of the sparsity-regularized sensitivity matrix are linearly independent. A Lorenz system excited by the sparse multitone signal is taken as an example to illustrate the principle and the performance.
The Entropy of Conditional Markov Trajectories
Venue: arXiv cs.IT 2013
Year: 2013

To quantify the randomness of Markov trajectories with fixed initial and final states, Ekroot and Cover proposed a closed-form expression for the entropy of trajectories of an irreducible finite state Markov chain. Numerous applications, including the study of random walks on graphs, require the computation of the entropy of Markov trajectories conditioned on a set of intermediate states. However, the expression of Ekroot and Cover does not allow for computing this quantity. In this paper, we propose a method to compute the entropy of conditional Markov trajectories through a transformation of the original Markov chain into a Markov chain that exhibits the desired conditional distribution of trajectories. Moreover, we express the entropy of Markov trajectories - a global quantity - as a linear combination of local entropies associated with the Markov chain states.
Identifying Metaphoric Antonyms in a Corpus Analysis of Finance Articles
Venue: arXiv cs.CL 2013
Year: 2013

Using a corpus of 17,000+ financial news reports (involving over 10M words), we perform an analysis of the argument-distributions of the UP and DOWN verbs used to describe movements of indices, stocks and shares. In Study 1 participants identified antonyms of these verbs in a free-response task and a matching task from which the most commonly identified antonyms were compiled. In Study 2, we determined whether the argument-distributions for the verbs in these antonym-pairs were sufficiently similar to predict the most frequently-identified antonym. Cosine similarity correlates moderately with the proportions of antonym-pairs identified by people (r = 0.31). More impressively, 87% of the time the most frequently-identified antonym is either the first- or second-most similar pair in the set of alternatives. The implications of these results for distributional approaches to determining metaphoric knowledge are discussed.
AND and/or OR: Uniform Polynomial-Size Circuits
Venue: arXiv cs.CC 2013
Year: 2013

We investigate the complexity of uniform OR circuits and AND circuits of polynomial-size and depth. As their name suggests, OR circuits have OR gates as their computation gates, as well as the usual input, output and constant (0/1) gates. As is the norm for Boolean circuits, our circuits have multiple sink gates, which implies that an OR circuit computes an OR function on some subset of its input variables. Determining that subset amounts to solving a number of reachability questions on a polynomial-size directed graph (which input gates are connected to the output gate?), taken from a very sparse set of graphs. However, it is not obvious whether or not this (restricted) reachability problem can be solved, by say, uniform AC^0 circuits (constant depth, polynomial-size, AND, OR, NOT gates). This is one reason why characterizing the power of these simple-looking circuits in terms of uniform classes turns out to be intriguing. Another is that the model itself seems particularly natural and worthy of study. Our goal is the systematic characterization of uniform polynomial-size OR circuits, and AND circuits, in terms of known uniform machine-based complexity classes. In particular, we consider the languages reducible to such uniform families of OR circuits, and AND circuits, under a variety of reduction types. We give upper and lower bounds on the computational power of these language classes. We find that these complexity classes are closely related to tallyNL, the set of unary languages within NL, and to sets reducible to tallyNL. Specifically, for a variety of types of reductions (many-one, conjunctive truth table, disjunctive truth table, truth table, Turing) we give characterizations of languages reducible to OR circuit classes in terms of languages reducible to tallyNL classes. Then, some of these OR classes are shown to coincide, and some are proven to be distinct. We give analogous results for AND circuits. Finally, for many of our OR circuit classes, and analogous AND circuit classes, we prove whether or not the two classes coincide, although we leave one such inclusion open.
From compression to compressed sensing
Venue: arXiv cs.IT 2013
Year: 2013

Can compression algorithms be employed for recovering signals from their underdetermined set of linear measurements? Addressing this question is the first step towards applying compression algorithms for compressed sensing (CS). In this paper, we consider a family of compression algorithms $\mathcal{C}_r$, parametrized by rate $r$, for a compact class of signals $\mathcal{Q} \subset \mathds{R}^n$. The set of natural images and JPEG at different rates are examples of $\mathcal{Q}$ and $\mathcal{C}_r$, respectively. We establish a connection between the rate-distortion performance of $\mathcal{C}_r$, and the number of linear measurements required for successful recovery in CS. We then propose compressible signal pursuit (CSP) algorithm and prove that, with high probability, it accurately and robustly recovers signals from an underdetermined set of linear measurements. We also explore the performance of CSP in the recovery of infinite dimensional signals.
Improved Multiuser Detection in Asynchronous Flat-Fading Non-Gaussian Channels
Venue: arXiv cs.SY 2013
Year: 2013

In this paper, a new M-estimator based multiuser detection in asynchronous flat-fading non-Gaussian CDMA channels is considered. A new closed-form expression is derived for the characteristic function of the multiple-access interference signals. Simulation results are provided to prove the effectiveness of the derived bit-error probabilities obtained with this expression in asynchronous flat-fading non-Gaussian CDMA channels.
Convolutional Codes Derived From Group Character Codes
Venue: arXiv cs.IT 2013
Year: 2013

New families of unit memory as well as multi-memory convolutional codes are constructed algebraically in this paper. These convolutional codes are derived from the class of group character codes. The proposed codes have basic generator matrices, consequently, they are non catastrophic. Additionally, the new code parameters are better than the ones available in the literature.
Towards common-sense reasoning via conditional simulation: legacies of Turing in Artificial Intelligence
Venue: arXiv cs.AI 2013
Year: 2013

The problem of replicating the flexibility of human common-sense reasoning has captured the imagination of computer scientists since the early days of Alan Turing's foundational work on computation and the philosophy of artificial intelligence. In the intervening years, the idea of cognition as computation has emerged as a fundamental tenet of Artificial Intelligence (AI) and cognitive science. But what kind of computation is cognition? We describe a computational formalism centered around a probabilistic Turing machine called QUERY, which captures the operation of probabilistic conditioning via conditional simulation. Through several examples and analyses, we demonstrate how the QUERY abstraction can be used to cast common-sense reasoning as probabilistic inference in a statistical model of our observations and the uncertain structure of the world that generated that experience. This formulation is a recent synthesis of several research programs in AI and cognitive science, but it also represents a surprising convergence of several of Turing's pioneering insights in AI, the foundations of computation, and statistics.
On the Capacity Region and the Generalized Degrees of Freedom Region for the MIMO Interference Channel with Feedback
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study the effect of feedback on two-user MIMO interference channels. The capacity region of MIMO interference channels with feedback is characterized within a constant number of bits, where this constant is independent of the channel matrices. Further, it is shown that the capacity region of a MIMO interference channel with feedback and its reciprocal interference channel are within a constant number of bits. Finally, the generalized degrees of freedom region for the MIMO interference channel with feedback is characterized.
Efficient Incremental Relaying
Venue: arXiv cs.IT 2013
Year: 2013

We propose a novel relaying scheme which improves the spectral efficiency of cooperative diversity systems by utilizing limited feedback from destination. Our scheme capitalizes on the fact that relaying is only required when direct transmission suffers deep fading. We calculate the packet error rate for the proposed efficient incremental relaying scheme with both amplify and forward and decode and forward relaying. Numerical results are also presented to verify their analytical counterparts.
On Max-SINR Receiver for Hexagonal Multicarrier Transmission Over Doubly Dispersive Channel
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, a novel receiver for Hexagonal Multicarrier Transmission (HMT) system based on the maximizing Signal-to-Interference-plus-Noise Ratio (Max-SINR) criterion is proposed. Theoretical analysis shows that the prototype pulse of the proposed Max-SINR receiver should adapt to the root mean square (RMS) delay spread of the doubly dispersive (DD) channel with exponential power delay profile and U-shape Doppler spectrum. Simulation results show that the proposed Max-SINR receiver outperforms traditional projection scheme and obtains an approximation to the theoretical upper bound SINR performance within the full range of channel spread factor. Meanwhile, the SINR performance of the proposed prototype pulse is robust to the estimation error between the estimated value and the real value of time delay spread.
Modeling page-view dynamics on Wikipedia
Venue: arXiv cs.CY 2013
Year: 2013

We introduce a model for predicting page-view dynamics of promoted content. The regularity of the content promotion process on Wikipedia provides excellent experimental conditions which favour detailed modelling. We show that the popularity of an article featured on Wikipedia's main page decays exponentially in time if the circadian cycles of the users are taken into account. Our model can be explained as the result of individual Poisson processes and is validated through empirical measurements. It provides a simpler explanation for the evolution of content popularity than previous studies.
On parallel implementation of a discrete optimization random search algorithm
Venue: arXiv cs.DC 2013
Year: 2013

A random search algorithm intended to solve discrete optimization problems is considered. We outline the main components of the algorithm, and then describe it in more detail. We show how the algorithm can be implemented on parallel computer systems. A performance analysis of both serial and parallel versions of the algorithm is given, and related results of solving test problems are discussed.
How Much of the Web Is Archived?
Venue: arXiv cs.DL 2013
Year: 2013

Although the Internet Archive's Wayback Machine is the largest and most well-known web archive, there have been a number of public web archives that have emerged in the last several years. With varying resources, audiences and collection development policies, these archives have varying levels of overlap with each other. While individual archives can be measured in terms of number of URIs, number of copies per URI, and intersection with other archives, to date there has been no answer to the question "How much of the Web is archived?" We study the question by approximating the Web using sample URIs from DMOZ, Delicious, Bitly, and search engine indexes; and, counting the number of copies of the sample URIs exist in various public web archives. Each sample set provides its own bias. The results from our sample sets indicate that range from 35%-90% of the Web has at least one archived copy, 17%-49% has between 2-5 copies, 1%-8% has 6-10 copies, and 8%-63% has more than 10 copies in public web archives. The number of URI copies varies as a function of time, but no more than 31.3% of URIs are archived more than once per month.