OpenRaiser/Intern-Atlas huggingface dataset:
A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
Venue: arXiv cs.DS 2013
Year: 2013

We present a simple adaptation of the Lempel Ziv 78' (LZ78) compression scheme ({\em IEEE Transactions on Information Theory, 1978}) that supports efficient random access to the input string. Namely, given query access to the compressed string, it is possible to efficiently recover any symbol of the input string. The compression algorithm is given as input a parameter $\eps >0$, and with very high probability increases the length of the compressed string by at most a factor of $(1+\eps)$. The access time is $O(\log n + 1/\eps^2)$ in expectation, and $O(\log n/\eps^2)$ with high probability. The scheme relies on sparse transitive-closure spanners. Any (consecutive) substring of the input string can be retrieved at an additional additive cost in the running time of the length of the substring. We also formally establish the necessity of modifying LZ78 so as to allow efficient random access. Specifically, we construct a family of strings for which $Ω(n/\log n)$ queries to the LZ78-compressed string are required in order to recover a single symbol in the input string. The main benefit of the proposed scheme is that it preserves the online nature and simplicity of LZ78, and that for {\em every} input string, the length of the compressed string is only a small factor larger than that obtained by running LZ78.
Connecting Terminals and 2-Disjoint Connected Subgraphs
Venue: arXiv cs.DS 2013
Year: 2013

Given a graph $G=(V,E)$ and a set of terminal vertices $T$ we say that a superset $S$ of $T$ is $T$-connecting if $S$ induces a connected graph, and $S$ is minimal if no strict subset of $S$ is $T$-connecting. In this paper we prove that there are at most ${|V \setminus T| \choose |T|-2} \cdot 3^{\frac{|V \setminus T|}{3}}$ minimal $T$-connecting sets when $|T| \leq n/3$ and that these can be enumerated within a polynomial factor of this bound. This generalizes the algorithm for enumerating all induced paths between a pair of vertices, corresponding to the case $|T|=2$. We apply our enumeration algorithm to solve the {\sc 2-Disjoint Connected Subgraphs} problem in time $O^*(1.7804^n)$, improving on the recent $O^*(1.933^n)$ algorithm of Cygan et al. 2012 LATIN paper.
Enhancing the retrieval performance by combing the texture and edge features
Venue: arXiv cs.CV 2013
Year: 2013

In this paper, anew algorithm which is based on geometrical moments and local binary patterns (LBP) for content based image retrieval (CBIR) is proposed. In geometrical moments, each vector is compared with the all other vectors for edge map generation. The same concept is utilized at LBP calculation which is generating nine LBP patterns from a given 3x3 pattern. Finally, nine LBP histograms are calculated which are used as a feature vector for image retrieval. Moments are important features used in recognition of different types of images. Two experiments have been carried out for proving the worth of our algorithm. The results after being investigated shows a significant improvement in terms of their evaluation measures as compared to LBP and other existing transform domain techniques.
An Analytical Framework for Heterogeneous Partial Feedback Design in Heterogeneous Multicell OFDMA Networks
Venue: arXiv cs.IT 2013
Year: 2013

The inherent heterogeneous structure resulting from user densities and large scale channel effects motivates heterogeneous partial feedback design in heterogeneous networks. In such emerging networks, a distributed scheduling policy which enjoys multiuser diversity as well as maintains fairness among users is favored for individual user rate enhancement and guarantees. For a system employing the cumulative distribution function based scheduling, which satisfies the two above mentioned desired features, we develop an analytical framework to investigate heterogeneous partial feedback in a general OFDMA-based heterogeneous multicell employing the best-M partial feedback strategy. Exact sum rate analysis is first carried out and closed form expressions are obtained by a novel decomposition of the probability density function of the selected user's signal-to-interference-plus-noise ratio. To draw further insight, we perform asymptotic analysis using extreme value theory to examine the effect of partial feedback on the randomness of multiuser diversity, show the asymptotic optimality of best-1 feedback, and derive an asymptotic approximation for the sum rate in order to determine the minimum required partial feedback.
Functional Regularized Least Squares Classi cation with Operator-valued Kernels
Venue: arXiv cs.LG 2013
Year: 2013

Although operator-valued kernels have recently received increasing interest in various machine learning and functional data analysis problems such as multi-task learning or functional regression, little attention has been paid to the understanding of their associated feature spaces. In this paper, we explore the potential of adopting an operator-valued kernel feature space perspective for the analysis of functional data. We then extend the Regularized Least Squares Classification (RLSC) algorithm to cover situations where there are multiple functions per observation. Experiments on a sound recognition problem show that the proposed method outperforms the classical RLSC algorithm.
A Triclustering Approach for Time Evolving Graphs
Venue: arXiv cs.LG 2013
Year: 2013

This paper introduces a novel technique to track structures in time evolving graphs. The method is based on a parameter free approach for three-dimensional co-clustering of the source vertices, the target vertices and the time. All these features are simultaneously segmented in order to build time segments and clusters of vertices whose edge distributions are similar and evolve in the same way over the time segments. The main novelty of this approach lies in that the time segments are directly inferred from the evolution of the edge distribution between the vertices, thus not requiring the user to make an a priori discretization. Experiments conducted on a synthetic dataset illustrate the good behaviour of the technique, and a study of a real-life dataset shows the potential of the proposed approach for exploratory data analysis.
Database-assisted Distributed Spectrum Sharing
Venue: arXiv cs.NI 2013
Year: 2013

According to FCC's ruling for white-space spectrum access, white-space devices are required to query a database to determine the spectrum availability. In this paper, we study the database-assisted distributed white-space access point (AP) network design. We first model the cooperative and non-cooperative channel selection problems among the APs as the system-wide throughput optimization and non-cooperative AP channel selection games, respectively, and design distributed AP channel selection algorithms that achieve system optimal point and Nash equilibrium, respectively. We then propose a state-based game formulation for the distributed AP association problem of the secondary users by taking the cost of mobility into account. We show that the state-based distributed AP association game has the finite improvement property, and design a distributed AP association algorithm that can converge to a state-based Nash equilibrium. Numerical results show that the algorithm is robust to the perturbation by secondary users' dynamical leaving and entering the system.
On Byzantine Broadcast in Planar Graphs
Venue: arXiv cs.DS 2013
Year: 2013

We consider the problem of reliably broadcasting information in a multihop asynchronous network in the presence of Byzantine failures: some nodes may exhibit unpredictable malicious behavior. We focus on completely decentralized solutions. Few Byzantine-robust algorithms exist for loosely connected networks. A recent solution guarantees reliable broadcast on a torus when D > 4, D being the minimal distance between two Byzantine nodes. In this paper, we generalize this result to 4-connected planar graphs. We show that reliable broadcast can be guaranteed when D > Z, Z being the maximal number of edges per polygon. We also show that this bound on D is a lower bound for this class of graphs. Our solution has the same time complexity as a simple broadcast. This is also the first solution where the memory required increases linearly (instead of exponentially) with the size of transmitted information. Important disclaimer: these results have NOT yet been published in an international conference or journal. This is just a technical report presenting intermediary and incomplete results. A generalized version of these results may be under submission.
Wavelet-based Scale Saliency
Venue: arXiv cs.CV 2013
Year: 2013

Both pixel-based scale saliency (PSS) and basis project methods focus on multiscale analysis of data content and structure. Their theoretical relations and practical combination are previously discussed. However, no models have ever been proposed for calculating scale saliency on basis-projected descriptors since then. This paper extend those ideas into mathematical models and implement them in the wavelet-based scale saliency (WSS). While PSS uses pixel-value descriptors, WSS treats wavelet sub-bands as basis descriptors. The paper discusses different wavelet descriptors: discrete wavelet transform (DWT), wavelet packet transform (DWPT), quaternion wavelet transform (QWT) and best basis quaternion wavelet packet transform (QWPTBB). WSS saliency maps of different descriptors are generated and compared against other saliency methods by both quantitative and quanlitative methods. Quantitative results, ROC curves, AUC values and NSS values are collected from simulations on Bruce and Kootstra image databases with human eye-tracking data as ground-truth. Furthermore, qualitative visual results of saliency maps are analyzed and compared against each other as well as eye-tracking data inclusive in the databases.
GADTs meet subtyping
Venue: arXiv cs.PL 2013
Year: 2013

While generalized algebraic datatypes (\GADTs) are now considered well-understood, adding them to a language with a notion of subtyping comes with a few surprises. What does it mean for a \GADT parameter to be covariant? The answer turns out to be quite subtle. It involves fine-grained properties of the subtyping relation that raise interesting design questions. We allow variance annotations in \GADT definitions, study their soundness, and present a sound and complete algorithm to check them. Our work may be applied to real-world ML-like languages with explicit subtyping such as OCaml, or to languages with general subtyping constraints.
Recurrence relations versus succession rules
Venue: arXiv cs.DM 2013
Year: 2013

In this paper we present a method to pass from a recurrence relation having constant coefficients (in short, a C-recurrence) to a finite succession rule defining the same number sequence. We recall that succession rules are a recently studied tool for the enumeration of combinatorial objects related to the ECO method. We also discuss the applicability of our method as a test for the positivity of a number sequence.
On the Vector Linear Solvability of Networks and Discrete Polymatroids
Venue: arXiv cs.IT 2013
Year: 2013

We consider the vector linear solvability of networks over a field $\mathbb{F}_q.$ It is well known that a scalar linear solution over $\mathbb{F}_q$ exists for a network if and only if the network is \textit{matroidal} with respect to a \textit{matroid} representable over $\mathbb{F}_q.$ A \textit{discrete polymatroid} is the multi-set analogue of a matroid. In this paper, a \textit{discrete polymatroidal} network is defined and it is shown that a vector linear solution over a field $\mathbb{F}_q$ exists for a network if and only if the network is discrete polymatroidal with respect to a discrete polymatroid representable over $\mathbb{F}_q.$ An algorithm to construct networks starting from a discrete polymatroid is provided. Every representation over $\mathbb{F}_q$ for the discrete polymatroid, results in a vector linear solution over $\mathbb{F}_q$ for the constructed network. Examples which illustrate the construction algorithm are provided, in which the resulting networks admit vector linear solution but no scalar linear solution over $\mathbb{F}_q.$
A DP Approach to Hamiltonian Path Problem
Venue: arXiv cs.DS 2013
Year: 2013

A Dynamic Programming based polynomial worst case time and space algorithm is described for computing Hamiltonian Path of a directed graph. Complexity constructive proofs along with a tested C++ implementation are provided as well. The result is obtained via the use of original colored hypergraph structures in order to maintain and update the necessary DP states.
Distributed Admission Control without Knowledge of the Capacity Region
Venue: arXiv cs.NI 2013
Year: 2013

We consider the problem of distributed admission control without knowledge of the capacity region in single-hop wireless networks, for flows that require a pre-specified bandwidth from the network. We present an optimization framework that allows us to design a scheduler and resource allocator, and by properly choosing a suitable utility function in the resource allocator, we prove that existing flows can be served with a pre-specified bandwidth, while the link requesting admission can determine the largest rate that it can get such that it does not interfere with the allocation to the existing flows.
The Expressive Power of Word Embeddings
Venue: arXiv cs.LG 2013
Year: 2013

We seek to better understand the difference in quality of the several publicly released embeddings. We propose several tasks that help to distinguish the characteristics of different embeddings. Our evaluation of sentiment polarity and synonym/antonym relations shows that embeddings are able to capture surprisingly nuanced semantics even in the absence of sentence structure. Moreover, benchmarking the embeddings shows great variance in quality and characteristics of the semantics captured by the tested embeddings. Finally, we show the impact of varying the number of dimensions and the resolution of each dimension on the effective useful features captured by the embedding space. Our contributions highlight the importance of embeddings for NLP tasks and the effect of their quality on the final results.
Sparse Recovery with Coherent Tight Frames via Analysis Dantzig Selector and Analysis LASSO
Venue: arXiv cs.IT 2013
Year: 2013

This article considers recovery of signals that are sparse or approximately sparse in terms of a (possibly) highly overcomplete and coherent tight frame from undersampled data corrupted with additive noise. We show that the properly constrained $l_1$-analysis, called analysis Dantzig selector, stably recovers a signal which is nearly sparse in terms of a tight frame provided that the measurement matrix satisfies a restricted isometry property adapted to the tight frame. As a special case, we consider the Gaussian noise. Further, under a sparsity scenario, with high probability, the recovery error from noisy data is within a log-like factor of the minimax risk over the class of vectors which are at most $s$ sparse in terms of the tight frame. Similar results for the analysis LASSO are showed. The above two algorithms provide guarantees only for noise that is bounded or bounded with high probability (for example, Gaussian noise). However, when the underlying measurements are corrupted by sparse noise, these algorithms perform suboptimally. We demonstrate robust methods for reconstructing signals that are nearly sparse in terms of a tight frame in the presence of bounded noise combined with sparse noise. The analysis in this paper is based on the restricted isometry property adapted to a tight frame, which is a natural extension to the standard restricted isometry property.
New variant of ElGamal signature scheme
Venue: arXiv cs.CR 2013
Year: 2013

In this paper, a new variant of ElGamal signature scheme is presented and its security analyzed. We also give, for its theoretical interest, a general form of the signature equation.
Counterexample-Preserving Reduction for Symbolic Model Checking
Venue: arXiv cs.LO 2013
Year: 2013

The cost of LTL model checking is highly sensitive to the length of the formula under verification. We observe that, under some specific conditions, the input LTL formula can be reduced to an easier-to-handle one before model checking. In our reduction, these two formulae need not to be logically equivalent, but they share the same counterexample set w.r.t the model. In the case that the model is symbolically represented, the condition enabling such reduction can be detected with a lightweight effort (e.g., with SAT-solving). In this paper, we tentatively name such technique "Counterexample-Preserving Reduction" (CePRe for short), and finally the proposed technquie is experimentally evaluated by adapting NuSMV.
Measurement Based Impromptu Deployment of a Multi-Hop Wireless Relay Network
Venue: arXiv cs.NI 2013
Year: 2013

We study the problem of optimal sequential ("as-you-go") deployment of wireless relay nodes as a person walks along a line of random length (with a known distribution). The objective is to create an impromptu multihop wireless network for connecting a packet source to be placed at the end of the line with a sink node located at the starting point, to operate in the light traffic regime. As the deployment person walks along the line from the sink towards the source, at every step, he measures the channel quality to one (or more) previously placed relays, and places the relay nodes based on these measurements, so as to minimize either the sum power or the maximum power from the source to the sink node in the resultant network, subject to a constraint on the expected number of relays placed. For each of these two objectives, two different relay selection strategies are considered: (i) each relay communicates with the sink via its immediate previous relay, (ii) the communication path can skip some of the deployed relays. With appropriate modeling assumptions, we formulate each of these problems as a Markov decision process (MDP). We provide the optimal policy structures for all these cases, and provide illustrations, via numerical results, for some typical parameters.
On Recursive Operations Over Logic LTS
Venue: arXiv cs.LO 2013
Year: 2013

Recently, in order to mix algebraic and logic styles of specification in a uniform framework, the notion of a logic labelled transition system (Logic LTS or LLTS for short) has been introduced and explored. A variety of constructors over LLTS, including usual process-algebraic operators, logic connectives (conjunction and disjunction) and standard temporal operators (always and unless), have been given. However, no attempt has made so far to develop general theory concerning (nested) recursive operations over LLTSs and a few fundamental problems are still open. This paper intends to study this issue in pure process-algebraic style. A few fundamental properties, including precongruence and the uniqueness of consistent solutions for equations, will be established.
Factorized Topic Models
Venue: arXiv cs.LG 2013
Year: 2013

In this paper we present a modification to a latent topic model, which makes the model exploit supervision to produce a factorized representation of the observed data. The structured parameterization separately encodes variance that is shared between classes from variance that is private to each class by the introduction of a new prior over the topic space. The approach allows for a more eff{}icient inference and provides an intuitive interpretation of the data in terms of an informative signal together with structured noise. The factorized representation is shown to enhance inference performance for image, text, and video classification.
Kidney Exchange in Dynamic Sparse Heterogenous Pools
Venue: arXiv cs.DS 2013
Year: 2013

Current kidney exchange pools are of moderate size and thin, as they consist of many highly sensitized patients. Creating a thicker pool can be done by waiting for many pairs to arrive. We analyze a simple class of matching algorithms that search periodically for allocations. We find that if only 2-way cycles are conducted, in order to gain a significant amount of matches over the online scenario (matching each time a new incompatible pair joins the pool) the waiting period should be "very long". If 3-way cycles are also allowed we find regimes in which waiting for a short period also increases the number of matches considerably. Finally, a significant increase of matches can be obtained by using even one non-simultaneous chain while still matching in an online fashion. Our theoretical findings and data-driven computational experiments lead to policy recommendations.
Training Sequence Design for MIMO Channels: An Application-Oriented Approach
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, the problem of training optimization for estimating a multiple-input multiple-output (MIMO) flat fading channel in the presence of spatially and temporally correlated Gaussian noise is studied in an application-oriented setup. So far, the problem of MIMO channel estimation has mostly been treated within the context of minimizing the mean square error (MSE) of the channel estimate subject to various constraints, such as an upper bound on the available training energy. We introduce a more general framework for the task of training sequence design in MIMO systems, which can treat not only the minimization of channel estimator's MSE, but also the optimization of a final performance metric of interest related to the use of the channel estimate in the communication system. First, we show that the proposed framework can be used to minimize the training energy budget subject to a quality constraint on the MSE of the channel estimator. A deterministic version of the "dual" problem is also provided. We then focus on four specific applications, where the training sequence can be optimized with respect to the classical channel estimation MSE, a weighted channel estimation MSE and the MSE of the equalization error due to the use of an equalizer at the receiver or an appropriate linear precoder at the transmitter. In this way, the intended use of the channel estimate is explicitly accounted for. The superiority of the proposed designs over existing methods is demonstrated via numerical simulations.
Deep Impact: Unintended consequences of journal rank
Venue: arXiv cs.DL 2013
Year: 2013

Most researchers acknowledge an intrinsic hierarchy in the scholarly journals ('journal rank') that they submit their work to, and adjust not only their submission but also their reading strategies accordingly. On the other hand, much has been written about the negative effects of institutionalizing journal rank as an impact measure. So far, contributions to the debate concerning the limitations of journal rank as a scientific impact assessment tool have either lacked data, or relied on only a few studies. In this review, we present the most recent and pertinent data on the consequences of our current scholarly communication system with respect to various measures of scientific quality (such as utility/citations, methodological soundness, expert ratings or retractions). These data corroborate previous hypotheses: using journal rank as an assessment tool is bad scientific practice. Moreover, the data lead us to argue that any journal rank (not only the currently-favored Impact Factor) would have this negative impact. Therefore, we suggest that abandoning journals altogether, in favor of a library-based scholarly communication system, will ultimately be necessary. This new system will use modern information technology to vastly improve the filter, sort and discovery functions of the current journal system.