OpenRaiser/Intern-Atlas huggingface dataset:
Equational axioms associated with finite automata for fixed point operations in cartesian categories
Venue: arXiv cs.LO 2015
Year: 2015

The axioms of iteration theories, or iteration categories, capture the equational properties of fixed point operations in several computationally significant categories. Iteration categories may be axiomatized by the Conway identities and identities associated with finite automata. We show that in conjunction with the Conway identities, each identity associated with a finite automaton implies the identity associated with any input extension of the automaton. We conclude that the Conway identities and the identities associated with the members of a subclass $\cQ$ of finite automata is complete for iteration categories iff for every finite simple group $G$ there is an automaton $\bQ \in \cQ$ such that $G$ is a quotient of a group in the monoid $M(\bQ)$ of the automaton $\bQ$. We also prove a stronger result that concerns identities associated with finite automata with a distinguished initial state.
Survey of Security and Privacy Issues of Internet of Things
Venue: arXiv cs.CR 2015
Year: 2015

This paper is a general survey of all the security issues existing in the Internet of Things (IoT) along with an analysis of the privacy issues that an end-user may face as a consequence of the spread of IoT. The majority of the survey is focused on the security loopholes arising out of the information exchange technologies used in Internet of Things. No countermeasure to the security drawbacks has been analyzed in the paper.
Task-Cloning Algorithms in a MapReduce Cluster with Competitive Performance Bounds
Venue: arXiv cs.DC 2015
Year: 2015

Job scheduling for a MapReduce cluster has been an active research topic in recent years. However, measurement traces from real-world production environment show that the duration of tasks within a job vary widely. The overall elapsed time of a job, i.e. the so-called flowtime, is often dictated by one or few slowly-running tasks within a job, generally referred as the "stragglers". The cause of stragglers include tasks running on partially/intermittently failing machines or the existence of some localized resource bottleneck(s) within a MapReduce cluster. To tackle this online job scheduling challenge, we adopt the task cloning approach and design the corresponding scheduling algorithms which aim at minimizing the weighted sum of job flowtimes in a MapReduce cluster based on the Shortest Remaining Processing Time scheduler (SRPT). To be more specific, we first design a 2-competitive offline algorithm when the variance of task-duration is negligible. We then extend this offline algorithm to yield the so-called SRPTMS+C algorithm for the online case and show that SRPTMS+C is $(1+ε)-speed$ $o(\frac{1}{ε^2})-competitive$ in reducing the weighted sum of job flowtimes within a cluster. Both of the algorithms explicitly consider the precedence constraints between the two phases within the MapReduce framework. We also demonstrate via trace-driven simulations that SRPTMS+C can significantly reduce the weighted/unweighted sum of job flowtimes by cutting down the elapsed time of small jobs substantially. In particular, SRPTMS+C beats the Microsoft Mantri scheme by nearly 25% according to this metric.
Simplified vision based automatic navigation for wheat harvesting in low income economies
Venue: arXiv cs.RO 2015
Year: 2015

Recent developments in the domain of agricultural robotics have resulted in development of complex and efficient systems. Most of the land owners in the South Asian region are low income farmers. The agricultural experience for them is still a completely manual process. However, the extreme weather conditions, heat and flooding, often combine to put a lot of stress on these small land owners and the associated labor. In this paper, we propose a prototype for an automated power reaper for the wheat crop. This automated vehicle is navigated using a simple vision based approach employing the low-cost camera and assisted GPS. The mechanical platform is driven by three motors controlled through an interface between the proposed vision algorithm and the electrical drive. The proposed methodology is applied on some real field scenarios to demonstrate the efficiency of the vision based algorithm.
Learning a Fuzzy Hyperplane Fat Margin Classifier with Minimum VC dimension
Venue: arXiv cs.LG 2015
Year: 2015

The Vapnik-Chervonenkis (VC) dimension measures the complexity of a learning machine, and a low VC dimension leads to good generalization. The recently proposed Minimal Complexity Machine (MCM) learns a hyperplane classifier by minimizing an exact bound on the VC dimension. This paper extends the MCM classifier to the fuzzy domain. The use of a fuzzy membership is known to reduce the effect of outliers, and to reduce the effect of noise on learning. Experimental results show, that on a number of benchmark datasets, the the fuzzy MCM classifier outperforms SVMs and the conventional MCM in terms of generalization, and that the fuzzy MCM uses fewer support vectors. On several benchmark datasets, the fuzzy MCM classifier yields excellent test set accuracies while using one-tenth the number of support vectors used by SVMs.
Design of LDPC Codes Robust to Noisy Message-Passing Decoding
Venue: arXiv cs.IT 2015
Year: 2015

We address noisy message-passing decoding of lowdensity parity-check (LDPC) codes over additive white Gaussian noise channels. Message-passing decoders in which certain processing units iteratively exchange messages are common for decoding LDPC codes. The exchanged messages are in general subject to internal noise in hardware implementation of these decoders. We model the internal decoder noise as additive white Gaussian noise (AWGN) degrading exchanged messages. Using Gaussian approximation of the exchanged messages, we perform a two-dimensional density evolution analysis for the noisy LDPC decoder. This makes it possible to track both the mean, and the variance of the exchanged message densities, and hence, to quantify the threshold of the LDPC code in the presence of internal decoder noise. The numerical and simulation results are presented that quantify the performance loss due to the internal decoder noise. To partially compensate this performance loss, we propose a simple method, based on EXIT chart analysis, to design robust irregular LDPC codes. The simulation results indicate that the designed codes can indeed compensate part of the performance loss due to the internal decoder noise.
Autodetection and Classification of Hidden Cultural City Districts from Yelp Reviews
Venue: arXiv cs.CL 2015
Year: 2015

Topic models are a way to discover underlying themes in an otherwise unstructured collection of documents. In this study, we specifically used the Latent Dirichlet Allocation (LDA) topic model on a dataset of Yelp reviews to classify restaurants based off of their reviews. Furthermore, we hypothesize that within a city, restaurants can be grouped into similar "clusters" based on both location and similarity. We used several different clustering methods, including K-means Clustering and a Probabilistic Mixture Model, in order to uncover and classify districts, both well-known and hidden (i.e. cultural areas like Chinatown or hearsay like "the best street for Italian restaurants") within a city. We use these models to display and label different clusters on a map. We also introduce a topic similarity heatmap that displays the similarity distribution in a city to a new restaurant.
Tri-Subject Kinship Verification: Understanding the Core of A Family
Venue: arXiv cs.CV 2015
Year: 2015

One major challenge in computer vision is to go beyond the modeling of individual objects and to investigate the bi- (one-versus-one) or tri- (one-versus-two) relationship among multiple visual entities, answering such questions as whether a child in a photo belongs to given parents. The child-parents relationship plays a core role in a family and understanding such kin relationship would have fundamental impact on the behavior of an artificial intelligent agent working in the human world. In this work, we tackle the problem of one-versus-two (tri-subject) kinship verification and our contributions are three folds: 1) a novel relative symmetric bilinear model (RSBM) introduced to model the similarity between the child and the parents, by incorporating the prior knowledge that a child may resemble a particular parent more than the other; 2) a spatially voted method for feature selection, which jointly selects the most discriminative features for the child-parents pair, while taking local spatial information into account; 3) a large scale tri-subject kinship database characterized by over 1,000 child-parents families. Extensive experiments on KinFaceW, Family101 and our newly released kinship database show that the proposed method outperforms several previous state of the art methods, while could also be used to significantly boost the performance of one-versus-one kinship verification when the information about both parents are available.
Lazy TSO Reachability
Venue: arXiv cs.PL 2015
Year: 2015

We address the problem of checking state reachability for programs running under Total Store Order (TSO). The problem has been shown to be decidable but the cost is prohibitive, namely non-primitive recursive. We propose here to give up completeness. Our contribution is a new algorithm for TSO reachability: it uses the standard SC semantics and introduces the TSO semantics lazily and only where needed. At the heart of our algorithm is an iterative refinement of the program of interest. If the program's goal state is SC-reachable, we are done. If the goal state is not SC-reachable, this may be due to the fact that SC under-approximates TSO. We employ a second algorithm that determines TSO computations which are infeasible under SC, and hence likely to lead to new states. We enrich the program to emulate, under SC, these TSO computations. Altogether, this yields an iterative under-approximation that we prove sound and complete for bug hunting, i.e., a semi-decision procedure halting for positive cases of reachability. We have implemented the procedure as an extension to the tool Trencher and compared it to the Memorax and CBMC model checkers.
Lossless Secret Image Sharing Schemes
Venue: arXiv cs.CR 2015
Year: 2015

Secret image sharing deals with splitting confidential images into several shares and the original image can be reconstructed from the qualified subset of the shares. Secret sharing schemes are used in transmission and storage of private medical images and military secrets. Increased confidentiality and availability are the major achievements. We propose an efficient (2, 2) scheme and (2, 3) scheme for secret image sharing. The scheme is lossless and also the share size is same as the secret size. The sharing and revealing phase uses simple modular arithmetic which can be very easily implemented. Experimental results on Binary and Gray scale images show that the proposed scheme is secure and efficient.
Sorting and Selection with Imprecise Comparisons
Venue: arXiv cs.DS 2015
Year: 2015

We consider a simple model of imprecise comparisons: there exists some $δ>0$ such that when a subject is given two elements to compare, if the values of those elements (as perceived by the subject) differ by at least $δ$, then the comparison will be made correctly; when the two elements have values that are within $δ$, the outcome of the comparison is unpredictable. This model is inspired by both imprecision in human judgment of values and also by bounded but potentially adversarial errors in the outcomes of sporting tournaments. Our model is closely related to a number of models commonly considered in the psychophysics literature where $δ$ corresponds to the {\em just noticeable difference unit (JND)} or {\em difference threshold}. In experimental psychology, the method of paired comparisons was proposed as a means for ranking preferences amongst $n$ elements of a human subject. The method requires performing all $\binom{n}{2}$ comparisons, then sorting elements according to the number of wins. The large number of comparisons is performed to counter the potentially faulty decision-making of the human subject, who acts as an imprecise comparator. We show that in our model the method of paired comparisons has optimal accuracy, minimizing the errors introduced by the imprecise comparisons. However, it is also wasteful, as it requires all $\binom{n}{2}$. We show that the same optimal guarantees can be achieved using $4 n^{3/2}$ comparisons, and we prove the optimality of our method. We then explore the general tradeoff between the guarantees on the error that can be made and number of comparisons for the problems of sorting, max-finding, and selection. Our results provide strong lower bounds and close-to-optimal solutions for each of these problems.
$G^{k,l}$-constrained multi-degree reduction of Bézier curves
Venue: arXiv cs.GR 2015
Year: 2015

We present a new approach to the problem of $G^{k,l}$-constrained ($k,l \leq 3$) multi-degree reduction of Bézier curves with respect to the least squares norm. First, to minimize the least squares error, we consider two methods of determining the values of geometric continuity parameters. One of them is based on quadratic and nonlinear programming, while the other uses some simplifying assumptions and solves a system of linear equations. Next, for prescribed values of these parameters, we obtain control points of the multi-degree reduced curve, using the properties of constrained dual Bernstein basis polynomials. Assuming that the input and output curves are of degree $n$ and $m$, respectively, we determine these points with the complexity $O(mn)$, which is significantly less than the cost of other known methods. Finally, we give several examples to demonstrate the effectiveness of our algorithms.
AutoProof: Auto-active Functional Verification of Object-oriented Programs
Venue: arXiv cs.LO 2015
Year: 2015

Auto-active verifiers provide a level of automation intermediate between fully automatic and interactive: users supply code with annotations as input while benefiting from a high level of automation in the back-end. This paper presents AutoProof, a state-of-the-art auto-active verifier for object-oriented sequential programs with complex functional specifications. AutoProof fully supports advanced object-oriented features and a powerful methodology for framing and class invariants, which make it applicable in practice to idiomatic object-oriented patterns. The paper focuses on describing AutoProof's interface, design, and implementation features, and demonstrates AutoProof's performance on a rich collection of benchmark problems. The results attest AutoProof's competitiveness among tools in its league on cutting-edge functional verification of object-oriented programs.
Variance Analysis of Linear SIMO Models with Spatially Correlated Noise
Venue: arXiv cs.SY 2015
Year: 2015

Substantial improvement in accuracy of identified linear time-invariant single-input multi-output (SIMO) dynamical models is possible when the disturbances affecting the output measurements are spatially correlated. Using an orthogonal representation for the modules composing the SIMO structure, in this paper we show that the variance of a parameter estimate of a module is dependent on the model structure of the other modules, and the correlation structure of the disturbances. In addition, we quantify the variance-error for the parameter estimates for finite model orders, where the effect of noise correlation structure, model structure and signal spectra are visible. From these results, we derive the noise correlation structure under which the mentioned model parameterization gives the lowest variance, when one module is identified using less parameters than the other modules.
A Parallel Min-Cut Algorithm using Iteratively Reweighted Least Squares
Venue: arXiv cs.DC 2015
Year: 2015

We present a parallel algorithm for the undirected $s,t$-mincut problem with floating-point valued weights. Our overarching algorithm uses an iteratively reweighted least squares framework. This generates a sequence of Laplacian linear systems, which we solve using parallel matrix algorithms. Our overall implementation is up to 30-times faster than a serial solver when using 128 cores.
Higher dimensional homodyne filtering for suppression of incidental phase artifacts in multichannel MRI
Venue: arXiv cs.CV 2015
Year: 2015

The aim of this paper is to introduce procedural steps for extension of the 1D homodyne phase correction for k-space truncation in all gradient encoding directions. Compared to the existing method applied to 2D partial k-space, signal losses introduced by the phase correction filter is observed to be minimal for the extended approach. In addition, the modified form of phase correction mitigates Incidental Phase Artifacts (IPA) due to truncation. For parallel imaging with undersampling along phase encode direction, the extended homodyne filtering is shown to be effective for minimizing these artifacts when each of the channel k-spaces are truncated along both phase and frequency encode directions. This is illustrated with 2D partial k-space for flow compensated multichannel Susceptibility Weighted Imaging (SWI). Extension of our method to 3D partial k-space shows improved reconstruction of flow information in phase contrast angiography.
Binary Systematic Network Coding for Progressive Packet Decoding
Venue: arXiv cs.IT 2015
Year: 2015

We consider binary systematic network codes and investigate their capability of decoding a source message either in full or in part. We carry out a probability analysis, derive closed-form expressions for the decoding probability and show that systematic network coding outperforms conventional network coding. We also develop an algorithm based on Gaussian elimination that allows progressive decoding of source packets. Simulation results show that the proposed decoding algorithm can achieve the theoretical optimal performance. Furthermore, we demonstrate that systematic network codes equipped with the proposed algorithm are good candidates for progressive packet recovery owing to their overall decoding delay characteristics.
Optimized Network-coded Scalable Video Multicasting over eMBMS Networks
Venue: arXiv cs.IT 2015
Year: 2015

Delivery of multicast video services over fourth generation (4G) networks such as 3GPP Long Term Evolution-Advanced (LTE-A) is gaining momentum. In this paper, we address the issue of efficiently multicasting layered video services by defining a novel resource allocation framework that aims to maximize the service coverage whilst keeping the radio resource footprint low. A key point in the proposed system mode is that the reliability of multicast video services is ensured by means of an Unequal Error Protection implementation of the Network Coding (UEP-NC) scheme. In addition, both the communication parameters and the UEP-NC scheme are jointly optimized by the proposed resource allocation framework. Numerical results show that the proposed allocation framework can significantly increase the service coverage when compared to a conventional Multi-rate Transmission (MrT) strategy.
Research Data Explored: Citations versus Altmetrics
Venue: arXiv cs.DL 2015
Year: 2015

The study explores the citedness of research data, its distribution over time and how it is related to the availability of a DOI (Digital Object Identifier) in Thomson Reuters' DCI (Data Citation Index). We investigate if cited research data "impact" the (social) web, reflected by altmetrics scores, and if there is any relationship between the number of citations and the sum of altmetrics scores from various social media-platforms. Three tools are used to collect and compare altmetrics scores, i.e. PlumX, ImpactStory, and Altmetric.com. In terms of coverage, PlumX is the most helpful altmetrics tool. While research data remain mostly uncited (about 85%), there has been a growing trend in citing data sets published since 2007. Surprisingly, the percentage of the number of cited research data with a DOI in DCI has decreased in the last years. Only nine repositories account for research data with DOIs and two or more citations. The number of cited research data with altmetrics scores is even lower (4 to 9%) but shows a higher coverage of research data from the last decade. However, no correlation between the number of citations and the total number of altmetrics scores is observable. Certain data types (i.e. survey, aggregate data, and sequence data) are more often cited and receive higher altmetrics scores.
OnionBots: Subverting Privacy Infrastructure for Cyber Attacks
Venue: arXiv cs.CR 2015
Year: 2015

Over the last decade botnets survived by adopting a sequence of increasingly sophisticated strategies to evade detection and take overs, and to monetize their infrastructure. At the same time, the success of privacy infrastructures such as Tor opened the door to illegal activities, including botnets, ransomware, and a marketplace for drugs and contraband. We contend that the next waves of botnets will extensively subvert privacy infrastructure and cryptographic mechanisms. In this work we propose to preemptively investigate the design and mitigation of such botnets. We first, introduce OnionBots, what we believe will be the next generation of resilient, stealthy botnets. OnionBots use privacy infrastructures for cyber attacks by completely decoupling their operation from the infected host IP address and by carrying traffic that does not leak information about its source, destination, and nature. Such bots live symbiotically within the privacy infrastructures to evade detection, measurement, scale estimation, observation, and in general all IP-based current mitigation techniques. Furthermore, we show that with an adequate self-healing network maintenance scheme, that is simple to implement, OnionBots achieve a low diameter and a low degree and are robust to partitioning under node deletions. We developed a mitigation technique, called SOAP, that neutralizes the nodes of the basic OnionBots. We also outline and discuss a set of techniques that can enable subsequent waves of Super OnionBots. In light of the potential of such botnets, we believe that the research community should proactively develop detection and mitigation methods to thwart OnionBots, potentially making adjustments to privacy infrastructure.
Stability of Markov regenerative switched linear systems
Venue: arXiv cs.SY 2015
Year: 2015

In this paper, we give a necessary and sufficient condition for mean stability of switched linear systems having a Markov regenerative process as its switching signal. This class of switched linear systems, which we call Markov regenerative switched linear systems, contains Markov jump linear systems and semi-Markov jump linear systems as special cases. We show that a Markov regenerative switched linear system is $m$th mean stable if and only if a particular matrix is Schur stable, under the assumption that either $m$ is even or the system is positive.