OpenRaiser/Intern-Atlas huggingface dataset:
Binary Cyclic codes with two primitive nonzeros
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we make some progress towards a well-known conjecture on the minimum weights of binary cyclic codes with two primitive nonzeros. We also determine the Walsh spectrum of $\Tr(x^d)$ over $\F_{2^{m}}$ in the case where $m=2t$, $d=3+2^{t+1}$ and $\gcd(d, 2^{m}-1)=1$.
A systematic empirical comparison of different approaches for normalizing citation impact indicators
Venue: arXiv cs.DL 2013
Year: 2013

We address the question how citation-based bibliometric indicators can best be normalized to ensure fair comparisons between publications from different scientific fields and different years. In a systematic large-scale empirical analysis, we compare a traditional normalization approach based on a field classification system with three source normalization approaches. We pay special attention to the selection of the publications included in the analysis. Publications in national scientific journals, popular scientific magazines, and trade magazines are not included. Unlike earlier studies, we use algorithmically constructed classification systems to evaluate the different normalization approaches. Our analysis shows that a source normalization approach based on the recently introduced idea of fractional citation counting does not perform well. Two other source normalization approaches generally outperform the classification-system-based normalization approach that we study. Our analysis therefore offers considerable support for the use of source-normalized bibliometric indicators.
Single and multiple consecutive permutation motif search
Venue: arXiv cs.DS 2013
Year: 2013

Let $t$ be a permutation (that shall play the role of the {\em text}) on $[n]$ and a pattern $p$ be a sequence of $m$ distinct integer(s) of $[n]$, $m\leq n$. The pattern $p$ occurs in $t$ in position $i$ if and only if $p_1... p_m$ is order-isomorphic to $t_i... t_{i+m-1}$, that is, for all $1 \leq k< \ell \leq m$, $p_k>p_\ell$ if and only if $t_{i+k-1}>t_{i+\ell-1}$. Searching for a pattern $p$ in a text $t$ consists in identifying all occurrences of $p$ in $t$. We first present a forward automaton which allows us to search for $p$ in $t$ in $O(m^2\log \log m +n)$ time. We then introduce a Morris-Pratt automaton representation of the forward automaton which allows us to reduce this complexity to $O(m\log \log m +n)$ at the price of an additional amortized constant term by integer of the text. Both automata occupy $O(m)$ space. We then extend the problem to search for a set of patterns and exhibit a specific Aho-Corasick like algorithm. Next we present a sub-linear average case search algorithm running in $O(\frac{m\log m}{\log\log m}+\frac{n\log m}{m\log\log m})$ time, that we eventually prove to be optimal on average.
Disjunctive Interpolants for Horn-Clause Verification (Extended Technical Report)
Venue: arXiv cs.LO 2013
Year: 2013

One of the main challenges in software verification is efficient and precise compositional analysis of programs with procedures and loops. Interpolation methods remain one of the most promising techniques for such verification, and are closely related to solving Horn clause constraints. We introduce a new notion of interpolation, disjunctive interpolation, which solve a more general class of problems in one step compared to previous notions of interpolants, such as tree interpolants or inductive sequences of interpolants. We present algorithms and complexity for construction of disjunctive interpolants, as well as their use within an abstraction-refinement loop. We have implemented Horn clause verification algorithms that use disjunctive interpolants and evaluate them on benchmarks expressed as Horn clauses over the theory of integer linear arithmetic.
Closed form solutions of linear difference equations in terms of symmetric products
Venue: arXiv cs.SC 2013
Year: 2013

In this paper we show how to find a closed form solution for third order difference operators in terms of solutions of second order operators. This work is an extension of previous results on finding closed form solutions of recurrence equations and a counterpart to existing results on differential equations. As motivation and application for this work, we discuss the problem of proving positivity of sequences given merely in terms of their defining recurrence relation. The main advantage of the present approach to earlier methods attacking the same problem is that our algorithm provides human-readable and verifiable, i.e., certified proofs.
Knowledge Base Approach for 3D Objects Detection in Point Clouds Using 3D Processing and Specialists Knowledge
Venue: arXiv cs.AI 2013
Year: 2013

This paper presents a knowledge-based detection of objects approach using the OWL ontology language, the Semantic Web Rule Language, and 3D processing built-ins aiming at combining geometrical analysis of 3D point clouds and specialist's knowledge. Here, we share our experience regarding the creation of 3D semantic facility model out of unorganized 3D point clouds. Thus, a knowledge-based detection approach of objects using the OWL ontology language is presented. This knowledge is used to define SWRL detection rules. In addition, the combination of 3D processing built-ins and topological Built-Ins in SWRL rules allows a more flexible and intelligent detection, and the annotation of objects contained in 3D point clouds. The created WiDOP prototype takes a set of 3D point clouds as input, and produces as output a populated ontology corresponding to an indexed scene visualized within VRML language. The context of the study is the detection of railway objects materialized within the Deutsche Bahn scene such as signals, technical cupboards, electric poles, etc. Thus, the resulting enriched and populated ontology, that contains the annotations of objects in the point clouds, is used to feed a GIS system or an IFC file for architecture purposes.
Adaptive Interference Suppression for CDMA Systems using Interpolated FIR Filters with Adaptive Interpolators in Multipath Channels
Venue: arXiv cs.IT 2013
Year: 2013

In this work we propose an adaptive linear receiver structure based on interpolated finite impulse response (FIR) filters with adaptive interpolators for direct sequence code division multiple access (DS-CDMA) systems in multipath channels. The interpolated minimum mean-squared error (MMSE) and the interpolated constrained minimum variance (CMV) solutions are described for a novel scheme where the interpolator is rendered time-varying in order to mitigate multiple access interference (MAI) and multiple-path propagation effects. Based upon the interpolated MMSE and CMV solutions we present computationally efficient stochastic gradient (SG) and exponentially weighted recursive least squares type (RLS) algorithms for both receiver and interpolator filters in the supervised and blind modes of operation. A convergence analysis of the algorithms and a discussion of the convergence properties of the method are carried out for both modes of operation. Simulation experiments for a downlink scenario show that the proposed structures achieve a superior BER convergence and steady-state performance to previously reported reduced-rank receivers at lower complexity.
Adaptive Space-Time Decision Feedback Neural Detectors with Data Selection for High-Data Rate Users in DS-CDMA Systems
Venue: arXiv cs.IT 2013
Year: 2013

A space-time adaptive decision feedback (DF) receiver using recurrent neural networks (RNN) is proposed for joint equalization and interference suppression in direct-sequence code-division-multiple-access (DS-CDMA) systems equipped with antenna arrays. The proposed receiver structure employs dynamically driven RNNs in the feedforward section for equalization and multi-access interference suppression and a finite impulse response (FIR) linear filter in the feedback section for performing interference cancellation. A data selective gradient algorithm, based upon the set-membership design framework, is proposed for the estimation of the coefficients of RNN structures and is applied to the estimation of the parameters of the proposed neural receiver structure. Simulation results show that the proposed techniques achieve significant performance gains over existing schemes.
How Computers Work: Computational Thinking for Everyone
Venue: arXiv cs.CY 2013
Year: 2013

What would you teach if you had only one course to help students grasp the essence of computation and perhaps inspire a few of them to make computing a subject of further study? Assume they have the standard college prep background. This would include basic algebra, but not necessarily more advanced mathematics. They would have written a few term papers, but would not have written computer programs. They could surf and twitter, but could not exclusive-or and nand. What about computers would interest them or help them place their experience in context? This paper provides one possible answer to this question by discussing a course that has completed its second iteration. Grounded in classical logic, elucidated in digital circuits and computer software, it expands into areas such as CPU components and massive databases. The course has succeeded in garnering the enthusiastic attention of students with a broad range of interests, exercising their problem solving skills, and introducing them to computational thinking.
Mathematics Is Imprecise
Venue: arXiv cs.PL 2013
Year: 2013

We commonly think of mathematics as bringing precision to application domains, but its relationship with computer science is more complex. This experience report on the use of Racket and Haskell to teach a required first university CS course to students with very good mathematical skills focusses on the ways that programming forces one to get the details right, with consequent benefits in the mathematical domain. Conversely, imprecision in mathematical abstractions and notation can work to the benefit of beginning programmers, if handled carefully.
Cryptanalysis and improvement of two certificateless three-party authenticated key agreement protocols
Venue: arXiv cs.CR 2013
Year: 2013

Recently, two certificateless three-party authenticated key agreement protocols were proposed, and both protocols were claimed they can meet the desirable security properties including forward security, key compromise impersonation resistance and so on. Through cryptanalysis, we show that one neither meets forward security and key compromise impersonation resistance nor resists an attack by an adversary who knows all users' secret values, and the other cannot resist key compromise impersonation attack. Finally, we propose improved protocols to make up two original protocols' security weaknesses, respectively. Further security analysis shows that our improved protocols can remove such security weaknesses.
Partitioning Graph Databases - A Quantitative Evaluation
Venue: arXiv cs.DB 2013
Year: 2013

Electronic data is growing at increasing rates, in both size and connectivity: the increasing presence of, and interest in, relationships between data. An example is the Twitter social network graph. Due to this growth demand is increasing for technologies that can process such data. Currently relational databases are the predominant technology, but they are poorly suited to processing connected data as they are optimized for index-intensive operations. Conversely, graph databases are optimized for graph computation. They link records by direct references, avoiding index lookups, and enabling retrieval of adjacent elements in constant time, regardless of graph size. However, as data volume increases these databases outgrow the resources of one computer and data partitioning becomes necessary. We evaluate the viability of using graph partitioning algorithms to partition graph databases. A prototype partitioned database was developed. Three partitioning algorithms explored and one implemented. Three graph datasets were used: two real and one synthetically generated. These were partitioned in various ways and the impact on database performance measured. We defined one synthetic access pattern per dataset and executed each on the partitioned datasets. Evaluation took place in a simulation environment, ensuring repeatability and allowing measurement of metrics like network traffic and load balance. Results show that compared to random partitioning the partitioning algorithm reduced traffic by 40-90%. Executing the algorithm intermittently during usage maintained partition quality, while requiring only 1% the computation of initial partitioning. Strong correlations were found between theoretic quality metrics and generated network traffic under non-uniform access patterns.
See the Tree Through the Lines: The Shazoo Algorithm -- Full Version --
Venue: arXiv cs.LG 2013
Year: 2013

Predicting the nodes of a given graph is a fascinating theoretical problem with applications in several domains. Since graph sparsification via spanning trees retains enough information while making the task much easier, trees are an important special case of this problem. Although it is known how to predict the nodes of an unweighted tree in a nearly optimal way, in the weighted case a fully satisfactory algorithm is not available yet. We fill this hole and introduce an efficient node predictor, Shazoo, which is nearly optimal on any weighted tree. Moreover, we show that Shazoo can be viewed as a common nontrivial generalization of both previous approaches for unweighted trees and weighted lines. Experiments on real-world datasets confirm that Shazoo performs well in that it fully exploits the structure of the input tree, and gets very close to (and sometimes better than) less scalable energy minimization methods.
Extremality Properties for the Basic Polarization Transformations
Venue: arXiv cs.IT 2013
Year: 2013

We study the extremality of the BEC and the BSC for Gallager's reliability function $E_0$ evaluated under the uniform input distribution for binary input DMCs from the aspect of channel polarization. In particular, we show that amongst all B-DMCs of a given $E_0(ρ)$ value, for a fixed $ρ\geq 0$, the BEC and BSC are extremal in the evolution of $E_0$ under the one-step polarization transformations.
Internationalization of Malaysian Mathematical and Computer Science Journal
Venue: arXiv cs.DL 2013
Year: 2013

The internationalization characteristics of two Malaysian journals, Bulletin of the Malaysian Mathematical Sciences Society (indexed by ISI) and the Malaysian Journal of Computer Science (indexed by Inspec and Scopus) is observed. All issues for the years 2000 to 2007 were looked at to obtain the following information, (i) total articles published between 2000 and 2007; (ii) the distribution of foreign and Malaysian authors publishing in the journals; (iii) the distribution of articles by country and (iv) the geographical distribution of authors citing articles published in the journals. Citation to articles is derived from information given by Google scholar. The results indicate that both journals exhibit average internationalization characteristics as they are current in their publications but with between 19% -30% international composition of reviewers or editorials, publish between 36%-79% of foreign articles and receive between 60%-70% of citations from foreign authors.
Spread spectrum compressed sensing MRI using chirp radio frequency pulses
Venue: arXiv cs.CV 2013
Year: 2013

Compressed sensing has shown great potential in reducing data acquisition time in magnetic resonance imaging (MRI). Recently, a spread spectrum compressed sensing MRI method modulates an image with a quadratic phase. It performs better than the conventional compressed sensing MRI with variable density sampling, since the coherence between the sensing and sparsity bases are reduced. However, spread spectrum in that method is implemented via a shim coil which limits its modulation intensity and is not convenient to operate. In this letter, we propose to apply chirp (linear frequency-swept) radio frequency pulses to easily control the spread spectrum. To accelerate the image reconstruction, an alternating direction algorithm is modified by exploiting the complex orthogonality of the quadratic phase encoding. Reconstruction on the acquired data demonstrates that more image features are preserved using the proposed approach than those of conventional CS-MRI.
Multi-class Generalized Binary Search for Active Inverse Reinforcement Learning
Venue: arXiv cs.LG 2013
Year: 2013

This paper addresses the problem of learning a task from demonstration. We adopt the framework of inverse reinforcement learning, where tasks are represented in the form of a reward function. Our contribution is a novel active learning algorithm that enables the learning agent to query the expert for more informative demonstrations, thus leading to more sample-efficient learning. For this novel algorithm (Generalized Binary Search for Inverse Reinforcement Learning, or GBS-IRL), we provide a theoretical bound on sample complexity and illustrate its applicability on several different tasks. To our knowledge, GBS-IRL is the first active IRL algorithm with provable sample complexity bounds. We also discuss our method in light of other existing methods in the literature and its general applicability in multi-class classification problems. Finally, motivated by recent work on learning from demonstration in robots, we also discuss how different forms of human feedback can be integrated in a transparent manner in our learning framework.
ChESS - Quick and Robust Detection of Chess-board Features
Venue: arXiv cs.CV 2013
Year: 2013

Localization of chess-board vertices is a common task in computer vision, underpinning many applications, but relatively little work focusses on designing a specific feature detector that is fast, accurate and robust. In this paper the `Chess-board Extraction by Subtraction and Summation' (ChESS) feature detector, designed to exclusively respond to chess-board vertices, is presented. The method proposed is robust against noise, poor lighting and poor contrast, requires no prior knowledge of the extent of the chess-board pattern, is computationally very efficient, and provides a strength measure of detected features. Such a detector has significant application both in the key field of camera calibration, as well as in Structured Light 3D reconstruction. Evidence is presented showing its robustness, accuracy, and efficiency in comparison to other commonly used detectors both under simulation and in experimental 3D reconstruction of flat plate and cylindrical objects
On the Achievable Rate-Regions for State-Dependent Gaussian Interference Channel
Venue: arXiv cs.IT 2013
Year: 2013

In this paper, we study a general additive state-dependent Gaussian interference channel (ASD-GIC) where we consider two-user interference channel with two independent states known non-causally at both transmitters, but unknown to either of the receivers. An special case, where the additive states over the two links are the same is studied in [1], [2], in which it is shown that the gap between the achievable symmetric rate and the upper bound is less than 1/4 bit for the strong interference case. Here, we also consider the case where each channel state has unbounded variance [3], which is referred to as the strong interferences. We first obtain an outer bound on the capacity region. By utilizing lattice-based coding schemes, we obtain four achievable rate regions. Depend on noise variance and channel power constraint, achievable rate regions can coincide with the channel capacity region. For the symmetric model, the achievable sum-rate reaches to within 0.661 bit of the channel capacity for signal to noise ratio (SNR) greater than one.
On the Complexity of Computing Gröbner Bases for Quasi-homogeneous Systems
Venue: arXiv cs.SC 2013
Year: 2013

Let $\K$ be a field and $(f_1, \ldots, f_n)\subset \K[X_1, \ldots, X_n]$ be a sequence of quasi-homogeneous polynomials of respective weighted degrees $(d_1, \ldots, d_n)$ w.r.t a system of weights $(w_{1},\dots,w_{n})$. Such systems are likely to arise from a lot of applications, including physics or cryptography. We design strategies for computing Gröbner bases for quasi-homogeneous systems by adapting existing algorithms for homogeneous systems to the quasi-homogeneous case. Overall, under genericity assumptions, we show that for a generic zero-dimensional quasi-homogeneous system, the complexity of the full strategy is polynomial in the weighted Bézout bound $\prod_{i=1}^{n}d_{i} / \prod_{i=1}^{n}w_{i}$. We provide some experimental results based on generic systems as well as systems arising from a cryptography problem. They show that taking advantage of the quasi-homogeneous structure of the systems allow us to solve systems that were out of reach otherwise.
Achievable rate region based on coset codes for multiple access channel with states
Venue: arXiv cs.IT 2013
Year: 2013

We prove that the ensemble the nested coset codes built on finite fields achieves the capacity of arbitrary discrete memoryless point-to-point channels. Exploiting it's algebraic structure, we develop a coding technique for communication over general discrete multiple access channel with channel state information distributed at the transmitters. We build an algebraic coding framework for this problem using the ensemble of Abelian group codes and thereby derive a new achievable rate region. We identify non-additive and non-symmteric examples for which the proposed achievable rate region is strictly larger than the one achievable using random unstructured codes.
Towards a faster symbolic aggregate approximation method
Venue: arXiv cs.DB 2013
Year: 2013

The similarity search problem is one of the main problems in time series data mining. Traditionally, this problem was tackled by sequentially comparing the given query against all the time series in the database, and returning all the time series that are within a predetermined threshold of that query. But the large size and the high dimensionality of time series databases that are in use nowadays make that scenario inefficient. There are many representation techniques that aim at reducing the dimensionality of time series so that the search can be handled faster at a lower-dimensional space level. The symbolic aggregate approximation (SAX) is one of the most competitive methods in the literature. In this paper we present a new method that improves the performance of SAX by adding to it another exclusion condition that increases the exclusion power. This method is based on using two representations of the time series: one of SAX and the other is based on an optimal approximation of the time series. Pre-computed distances are calculated and stored offline to be used online to exclude a wide range of the search space using two exclusion conditions. We conduct experiments which show that the new method is faster than SAX.
Phase Diagram and Approximate Message Passing for Blind Calibration and Dictionary Learning
Venue: arXiv cs.IT 2013
Year: 2013

We consider dictionary learning and blind calibration for signals and matrices created from a random ensemble. We study the mean-squared error in the limit of large signal dimension using the replica method and unveil the appearance of phase transitions delimiting impossible, possible-but-hard and possible inference regions. We also introduce an approximate message passing algorithm that asymptotically matches the theoretical performance, and show through numerical tests that it performs very well, for the calibration problem, for tractable system sizes.