OpenRaiser/Intern-Atlas huggingface dataset:
Things that can be made into themselves
Venue: arXiv cs.LO 2014
Year: 2014

One says that a property $P$ of sets of natural numbers can be made into itself iff there is a numbering $α_0,α_1,\ldots$ of all left-r.e. sets such that the index set $\{e: α_e$ satisfies $P\}$ has the property $P$ as well. For example, the property of being Martin-Löf random can be made into itself. Herein we characterize those singleton properties which can be made into themselves. A second direction of the present work is the investigation of the structure of left-r.e. sets under inclusion modulo a finite set. In contrast to the corresponding structure for r.e. sets, which has only maximal but no minimal members, both minimal and maximal left-r.e. sets exist. Moreover, our construction of minimal and maximal left-r.e. sets greatly differs from Friedberg's classical construction of maximal r.e. sets. Finally, we investigate whether the properties of minimal and maximal left-r.e. sets can be made into themselves.
A Dynamic I/O-Efficient Structure for One-Dimensional Top-k Range Reporting
Venue: arXiv cs.DS 2014
Year: 2014

We present a structure in external memory for "top-k range reporting", which uses linear space, answers a query in O(lg_B n + k/B) I/Os, and supports an update in O(lg_B n) amortized I/Os, where n is the input size, and B is the block size. This improves the state of the art which incurs O(lg^2_B n) amortized I/Os per update.
Exact Byzantine Consensus in Directed Graphs
Venue: arXiv cs.DC 2014
Year: 2014

Consider a synchronous point-to-point network of n nodes connected by directed links, wherein each node has a binary input. This paper proves a tight necessary and sufficient condition on the underlying communication topology for achieving Byzantine consensus among these nodes in the presence of up to f Byzantine faults. We derive a necessary condition, and then we provide a constructive proof of sufficiency by presenting a Byzantine consensus algorithm for directed graphs that satisfy the necessary condition. Prior work has developed analogous necessary and sufficient conditions for undirected graphs. It is known that, for undirected graphs, the following two conditions are together necessary and sufficient [8, 2, 6]: (i) n ? 3f + 1, and (ii) network connectivity greater than 2f. However, these conditions are not adequate to completely characterize Byzantine consensus in directed graphs.
Robustness and Generalization for Metric Learning
Venue: arXiv cs.LG 2014
Year: 2014

Metric learning has attracted a lot of interest over the last decade, but the generalization ability of such methods has not been thoroughly studied. In this paper, we introduce an adaptation of the notion of algorithmic robustness (previously introduced by Xu and Mannor) that can be used to derive generalization bounds for metric learning. We further show that a weak notion of robustness is in fact a necessary and sufficient condition for a metric learning algorithm to generalize. To illustrate the applicability of the proposed framework, we derive generalization results for a large family of existing metric learning algorithms, including some sparse formulations that are not covered by previous results.
A new class of metrics for spike trains
Venue: arXiv cs.IT 2014
Year: 2014

The distance between a pair of spike trains, quantifying the differences between them, can be measured using various metrics. Here we introduce a new class of spike train metrics, inspired by the Pompeiu-Hausdorff distance, and compare them with existing metrics. Some of our new metrics (the modulus-metric and the max-metric) have characteristics that are qualitatively different than those of classical metrics like the van Rossum distance or the Victor & Purpura distance. The modulus-metric and the max-metric are particularly suitable for measuring distances between spike trains where information is encoded in bursts, but the number and the timing of spikes inside a burst does not carry information. The modulus-metric does not depend on any parameters and can be computed using a fast algorithm, in a time that depends linearly on the number of spikes in the two spike trains. We also introduce localized versions of the new metrics, which could have the biologically-relevant interpretation of measuring the differences between spike trains as they are perceived at a particular moment in time by a neuron receiving these spike trains.
Multiple-Input Multiple-Output Two-Way Relaying: A Space-Division Approach
Venue: arXiv cs.IT 2014
Year: 2014

We propose a novel space-division based network-coding scheme for multiple-input multiple-output (MIMO) two-way relay channels (TWRCs), in which two multi-antenna users exchange information via a multi-antenna relay. In the proposed scheme, the overall signal space at the relay is divided into two subspaces. In one subspace, the spatial streams of the two users have nearly orthogonal directions, and are completely decoded at the relay. In the other subspace, the signal directions of the two users are nearly parallel, and linear functions of the spatial streams are computed at the relay, following the principle of physical-layer network coding (PNC). Based on the recovered messages and message-functions, the relay generates and forwards network-coded messages to the two users. We show that, at high signal-to-noise ratio (SNR), the proposed scheme achieves the asymptotic sum rate capacity of MIMO TWRCs within 1/2log(5/4) = 0.161 bits per user-antenna for any antenna configuration and channel realization. We perform large-system analysis to derive the average sum-rate of the proposed scheme over Rayleigh-fading MIMO TWRCs. We show that the average asymptotic sum rate gap to the capacity upper bound is at most 0.053 bits per relay-antenna. It is demonstrated that the proposed scheme significantly outperforms the existing schemes.
Rethinking Centrality: The Role of Dynamical Processes in Social Network Analysis
Venue: arXiv cs.SI 2014
Year: 2014

Many popular measures used in social network analysis, including centrality, are based on the random walk. The random walk is a model of a stochastic process where a node interacts with one other node at a time. However, the random walk may not be appropriate for modeling social phenomena, including epidemics and information diffusion, in which one node may interact with many others at the same time, for example, by broadcasting the virus or information to its neighbors. To produce meaningful results, social network analysis algorithms have to take into account the nature of interactions between the nodes. In this paper we classify dynamical processes as conservative and non-conservative and relate them to well-known measures of centrality used in network analysis: PageRank and Alpha-Centrality. We demonstrate, by ranking users in online social networks used for broadcasting information, that non-conservative Alpha-Centrality generally leads to a better agreement with an empirical ranking scheme than the conservative PageRank.
Fundamental Limits of Caching
Venue: arXiv cs.IT 2014
Year: 2014

Caching is a technique to reduce peak traffic rates by prefetching popular content into memories at the end users. Conventionally, these memories are used to deliver requested content in part from a locally cached copy rather than through the network. The gain offered by this approach, which we term local caching gain, depends on the local cache size (i.e, the memory available at each individual user). In this paper, we introduce and exploit a second, global, caching gain not utilized by conventional caching schemes. This gain depends on the aggregate global cache size (i.e., the cumulative memory available at all users), even though there is no cooperation among the users. To evaluate and isolate these two gains, we introduce an information-theoretic formulation of the caching problem focusing on its basic structure. For this setting, we propose a novel coded caching scheme that exploits both local and global caching gains, leading to a multiplicative improvement in the peak rate compared to previously known schemes. In particular, the improvement can be on the order of the number of users in the network. Moreover, we argue that the performance of the proposed scheme is within a constant factor of the information-theoretic optimum for all values of the problem parameters.
Reduction of Blocking Artifacts In JPEG Compressed Image
Venue: arXiv cs.GR 2014
Year: 2014

In JPEG (DCT based) compresses image data by representing the original image with a small number of transform coefficients. It exploits the fact that for typical images a large amount of signal energy is concentrated in a small number of coefficients. The goal of DCT transform coding is to minimize the number of retained transform coefficients while keeping distortion at an acceptable level.In JPEG, it is done in 8X8 non overlapping blocks. It divides an image into blocks of equal size and processes each block independently. Block processing allows the coder to adapt to the local image statistics, exploit the correlation present among neighboring image pixels, and to reduce computational and storage requirements. One of the most degradation of the block transform coding is the blocking artifact. These artifacts appear as a regular pattern of visible block boundaries. This degradation is a direct result of the coarse quantization of the coefficients and the independent processing of the blocks which does not take into account the existing correlations among adjacent block pixels. In this paper attempt is being made to reduce the blocking artifact introduced by the Block DCT Transform in JPEG.
Secure Cooperative Regenerating Codes for Distributed Storage Systems
Venue: arXiv cs.IT 2014
Year: 2014

Regenerating codes enable trading off repair bandwidth for storage in distributed storage systems (DSS). Due to their distributed nature, these systems are intrinsically susceptible to attacks, and they may also be subject to multiple simultaneous node failures. Cooperative regenerating codes allow bandwidth efficient repair of multiple simultaneous node failures. This paper analyzes storage systems that employ cooperative regenerating codes that are robust to (passive) eavesdroppers. The analysis is divided into two parts, studying both minimum bandwidth and minimum storage cooperative regenerating scenarios. First, the secrecy capacity for minimum bandwidth cooperative regenerating codes is characterized. Second, for minimum storage cooperative regenerating codes, a secure file size upper bound and achievability results are provided. These results establish the secrecy capacity for the minimum storage scenario for certain special cases. In all scenarios, the achievability results correspond to exact repair, and secure file size upper bounds are obtained using min-cut analyses over a suitable secrecy graph representation of DSS. The main achievability argument is based on an appropriate pre-coding of the data to eliminate the information leakage to the eavesdropper.
Analysis of Blocking Probability in a Relay-based Cellular OFDMA Network
Venue: arXiv cs.IT 2014
Year: 2014

Relay deployment in Orthogonal Frequency Division Multiple Access (OFDMA) based cellular networks helps in coverage extension and or capacity improvement. In OFDMA system, each user requires different number of subcarriers to meet its rate requirement. This resource requirement depends on the Signal to Interference Ratio (SIR) experienced by a user. Traditional methods to compute blocking probability cannot be used in relay based cellular OFDMA networks. In this paper, we present an approach to compute the blocking probability of such networks. We determine an expression of the probability distribution of the users resource requirement based on its experienced SIR and then classify the users into various classes depending upon their subcarrier requirement. We consider the system to be a multidimensional system with different classes and evaluate the blocking probability of system using the multi-dimensional Erlang loss formulas.
Separation of Reliability and Secrecy in Rate-Limited Secret-Key Generation
Venue: arXiv cs.IT 2014
Year: 2014

For a discrete or a continuous source model, we study the problem of secret-key generation with one round of rate-limited public communication between two legitimate users. Although we do not provide new bounds on the wiretap secret-key (WSK) capacity for the discrete source model, we use an alternative achievability scheme that may be useful for practical applications. As a side result, we conveniently extend known bounds to the case of a continuous source model. Specifically, we consider a sequential key-generation strategy, that implements a rate-limited reconciliation step to handle reliability, followed by a privacy amplification step performed with extractors to handle secrecy. We prove that such a sequential strategy achieves the best known bounds for the rate-limited WSK capacity (under the assumption of degraded sources in the case of two-way communication). However, we show that, unlike the case of rate-unlimited public communication, achieving the reconciliation capacity in a sequential strategy does not necessarily lead to achieving the best known bounds for the WSK capacity. Consequently, reliability and secrecy can be treated successively but not independently, thereby exhibiting a limitation of sequential strategies for rate-limited public communication. Nevertheless, we provide scenarios for which reliability and secrecy can be treated successively and independently, such as the two-way rate-limited SK capacity, the one-way rate-limited WSK capacity for degraded binary symmetric sources, and the one-way rate-limited WSK capacity for Gaussian degraded sources.
Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines
Venue: arXiv cs.IT 2014
Year: 2014

Drawing on various notions from theoretical computer science, we present a novel numerical approach, motivated by the notion of algorithmic probability, to the problem of approximating the Kolmogorov-Chaitin complexity of short strings. The method is an alternative to the traditional lossless compression algorithms, which it may complement, the two being serviceable for different string lengths. We provide a thorough analysis for all $\sum_{n=1}^{11} 2^n$ binary strings of length $n<12$ and for most strings of length $12\leq n \leq16$ by running all $\sim 2.5 \times 10^{13}$ Turing machines with 5 states and 2 symbols ($8\times 22^9$ with reduction techniques) using the most standard formalism of Turing machines, used in for example the Busy Beaver problem. We address the question of stability and error estimation, the sensitivity of the continued application of the method for wider coverage and better accuracy, and provide statistical evidence suggesting robustness. As with compression algorithms, this work promises to deliver a range of applications, and to provide insight into the question of complexity calculation of finite (and short) strings.
Paths to stable allocations
Venue: arXiv cs.DM 2014
Year: 2014

The stable allocation problem is one of the broadest extensions of the well-known stable marriage problem. In an allocation problem, edges of a bipartite graph have capacities and vertices have quotas to fill. Here we investigate the case of uncoordinated processes in stable allocation instances. In this setting, a feasible allocation is given and the aim is to reach a stable allocation by raising the value of the allocation along blocking edges and reducing it on worse edges if needed. Do such myopic changes lead to a stable solution? In our present work, we analyze both better and best response dynamics from an algorithmic point of view. With the help of two deterministic algorithms we show that random procedures reach a stable solution with probability one for all rational input data in both cases. Surprisingly, while there is a polynomial path to stability when better response strategies are played (even for irrational input data), the more intuitive best response steps may require exponential time. We also study the special case of correlated markets. There, random best response strategies lead to a stable allocation in expected polynomial time.
Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension
Venue: arXiv cs.CG 2014
Year: 2014

For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed k>1, there is a polynomial-time algorithm that, for a 1-connected topological space X given as a finite simplicial complex, or more generally, as a simplicial set with polynomial-time homology, computes the k-th homotopy group π_k(X), as well as the first k stages of a Postnikov system of X. Combined with results of an earlier paper, this yields a polynomial-time computation of [X,Y], i.e., all homotopy classes of continuous mappings X -> Y, under the assumption that Y is (k-1)-connected and dim X < 2k-1. We also obtain a polynomial-time solution of the extension problem, where the input consists of finite simplicial complexes X,Y, where Y is (k-1)-connected and dim X < 2k, plus a subspace A\subseteq X and a (simplicial) map f:A -> Y, and the question is the extendability of f to all of X. The algorithms are based on the notion of a simplicial set with polynomial-time homology, which is an enhancement of the notion of a simplicial set with effective homology developed earlier by Sergeraert and his co-workers. Our polynomial-time algorithms are obtained by showing that simplicial sets with polynomial-time homology are closed under various operations, most notably, Cartesian products, twisted Cartesian products, and classifying space. One of the key components is also polynomial-time homology for the Eilenberg--MacLane space K(Z,1), provided in another recent paper by Krcal, Matousek, and Sergeraert.
Lasso Screening Rules via Dual Polytope Projection
Venue: arXiv cs.LG 2014
Year: 2014

Lasso is a widely used regression technique to find sparse representations. When the dimension of the feature space and the number of samples are extremely large, solving the Lasso problem remains challenging. To improve the efficiency of solving large-scale Lasso problems, El Ghaoui and his colleagues have proposed the SAFE rules which are able to quickly identify the inactive predictors, i.e., predictors that have $0$ components in the solution vector. Then, the inactive predictors or features can be removed from the optimization problem to reduce its scale. By transforming the standard Lasso to its dual form, it can be shown that the inactive predictors include the set of inactive constraints on the optimal dual solution. In this paper, we propose an efficient and effective screening rule via Dual Polytope Projections (DPP), which is mainly based on the uniqueness and nonexpansiveness of the optimal dual solution due to the fact that the feasible set in the dual space is a convex and closed polytope. Moreover, we show that our screening rule can be extended to identify inactive groups in group Lasso. To the best of our knowledge, there is currently no "exact" screening rule for group Lasso. We have evaluated our screening rule using synthetic and real data sets. Results show that our rule is more effective in identifying inactive predictors than existing state-of-the-art screening rules for Lasso.
Loop invariants: analysis, classification, and examples
Venue: arXiv cs.SE 2014
Year: 2014

Software verification has emerged as a key concern for ensuring the continued progress of information technology. Full verification generally requires, as a crucial step, equipping each loop with a "loop invariant". Beyond their role in verification, loop invariants help program understanding by providing fundamental insights into the nature of algorithms. In practice, finding sound and useful invariants remains a challenge. Fortunately, many invariants seem intuitively to exhibit a common flavor. Understanding these fundamental invariant patterns could therefore provide help for understanding and verifying a large variety of programs. We performed a systematic identification, validation, and classification of loop invariants over a range of fundamental algorithms from diverse areas of computer science. This article analyzes the patterns, as uncovered in this study, governing how invariants are derived from postconditions; it proposes a taxonomy of invariants according to these patterns, and presents its application to the algorithms reviewed. The discussion also shows the need for high-level specifications based on "domain theory". It describes how the invariants and the corresponding algorithms have been mechanically verified using an automated program prover; the proof source files are available. The contributions also include suggestions for invariant inference and for model-based specification.
Forest Sparsity for Multi-channel Compressive Sensing
Venue: arXiv cs.LG 2014
Year: 2014

In this paper, we investigate a new compressive sensing model for multi-channel sparse data where each channel can be represented as a hierarchical tree and different channels are highly correlated. Therefore, the full data could follow the forest structure and we call this property as \emph{forest sparsity}. It exploits both intra- and inter- channel correlations and enriches the family of existing model-based compressive sensing theories. The proposed theory indicates that only $\mathcal{O}(Tk+\log(N/k))$ measurements are required for multi-channel data with forest sparsity, where $T$ is the number of channels, $N$ and $k$ are the length and sparsity number of each channel respectively. This result is much better than $\mathcal{O}(Tk+T\log(N/k))$ of tree sparsity, $\mathcal{O}(Tk+k\log(N/k))$ of joint sparsity, and far better than $\mathcal{O}(Tk+Tk\log(N/k))$ of standard sparsity. In addition, we extend the forest sparsity theory to the multiple measurement vectors problem, where the measurement matrix is a block-diagonal matrix. The result shows that the required measurement bound can be the same as that for dense random measurement matrix, when the data shares equal energy in each channel. A new algorithm is developed and applied on four example applications to validate the benefit of the proposed model. Extensive experiments demonstrate the effectiveness and efficiency of the proposed theory and algorithm.
Computing coset leaders and leader codewords of binary codes
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we use the Gröbner representation of a binary linear code $\mathcal C$ to give efficient algorithms for computing the whole set of coset leaders, denoted by $\mathrm{CL}(\mathcal C)$ and the set of leader codewords, denoted by $\mathrm L(\mathcal C)$. The first algorithm could be adapted to provide not only the Newton and the covering radius of $\mathcal C$ but also to determine the coset leader weight distribution. Moreover, providing the set of leader codewords we have a test-set for decoding by a gradient-like decoding algorithm. Another contribution of this article is the relation stablished between zero neighbours and leader codewords.
An Empirical Evaluation of Portfolios Approaches for solving CSPs
Venue: arXiv cs.AI 2014
Year: 2014

Recent research in areas such as SAT solving and Integer Linear Programming has shown that the performances of a single arbitrarily efficient solver can be significantly outperformed by a portfolio of possibly slower on-average solvers. We report an empirical evaluation and comparison of portfolio approaches applied to Constraint Satisfaction Problems (CSPs). We compared models developed on top of off-the-shelf machine learning algorithms with respect to approaches used in the SAT field and adapted for CSPs, considering different portfolio sizes and using as evaluation metrics the number of solved problems and the time taken to solve them. Results indicate that the best SAT approaches have top performances also in the CSP field and are slightly more competitive than simple models built on top of classification algorithms.