OpenRaiser/Intern-Atlas huggingface dataset:
Reducing the Barrier to Entry of Complex Robotic Software: a MoveIt! Case Study
Venue: arXiv cs.RO 2014
Year: 2014

Developing robot agnostic software frameworks involves synthesizing the disparate fields of robotic theory and software engineering while simultaneously accounting for a large variability in hardware designs and control paradigms. As the capabilities of robotic software frameworks increase, the setup difficulty and learning curve for new users also increase. If the entry barriers for configuring and using the software on robots is too high, even the most powerful of frameworks are useless. A growing need exists in robotic software engineering to aid users in getting started with, and customizing, the software framework as necessary for particular robotic applications. In this paper a case study is presented for the best practices found for lowering the barrier of entry in the MoveIt! framework, an open-source tool for mobile manipulation in ROS, that allows users to 1) quickly get basic motion planning functionality with minimal initial setup, 2) automate its configuration and optimization, and 3) easily customize its components. A graphical interface that assists the user in configuring MoveIt! is the cornerstone of our approach, coupled with the use of an existing standardized robot model for input, automatically generated robot-specific configuration files, and a plugin-based architecture for extensibility. These best practices are summarized into a set of barrier to entry design principles applicable to other robotic software. The approaches for lowering the entry barrier are evaluated by usage statistics, a user survey, and compared against our design objectives for their effectiveness to users.
Circuit complexity, proof complexity, and polynomial identity testing
Venue: arXiv cs.CC 2014
Year: 2014

We introduce a new algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits (VNP is not equal to VP). As a corollary to the proof, we also show that super-polynomial lower bounds on the number of lines in Polynomial Calculus proofs (as opposed to the usual measure of number of monomials) imply the Permanent versus Determinant Conjecture. Note that, prior to our work, there was no proof system for which lower bounds on an arbitrary tautology implied any computational lower bound. Our proof system helps clarify the relationships between previous algebraic proof systems, and begins to shed light on why proof complexity lower bounds for various proof systems have been so much harder than lower bounds on the corresponding circuit classes. In doing so, we highlight the importance of polynomial identity testing (PIT) for understanding proof complexity. More specifically, we introduce certain propositional axioms satisfied by any Boolean circuit computing PIT. We use these PIT axioms to shed light on AC^0[p]-Frege lower bounds, which have been open for nearly 30 years, with no satisfactory explanation as to their apparent difficulty. We show that either: a) Proving super-polynomial lower bounds on AC^0[p]-Frege implies VNP does not have polynomial-size circuits of depth d - a notoriously open question for d at least 4 - thus explaining the difficulty of lower bounds on AC^0[p]-Frege, or b) AC^0[p]-Frege cannot efficiently prove the depth d PIT axioms, and hence we have a lower bound on AC^0[p]-Frege. Using the algebraic structure of our proof system, we propose a novel way to extend techniques from algebraic circuit complexity to prove lower bounds in proof complexity.
Design space exploration for image processing architectures on FPGA targets
Venue: arXiv cs.AR 2014
Year: 2014

Due to the emergence of embedded applications in image and video processing, communication and cryptography, improvement of pictorial information for better human perception like deblurring, denoising in several fields such as satellite imaging, medical imaging, mobile applications etc. are gaining importance for renewed research. Behind such developments, the primary responsibility lies with the advancement of semiconductor technology leading to FPGA based programmable logic devices, which combines the advantages of both custom hardware and dedicated DSP resources. In addition, FPGA provides powerful reconfiguration feature and hence is an ideal target for rapid prototyping. We have endeavoured to exploit exceptional features of FPGA technology in respect to hardware parallelism leading to higher computational density and throughput, and have observed better performances than those one can get just merely porting the image processing software algorithms to hardware. In this paper, we intend to present an elaborate review, based on our expertise and experiences, on undertaking necessary transformation to an image processing software algorithm including the optimization techniques that makes its operation in hardware comparatively faster.
Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
Venue: arXiv cs.DS 2014
Year: 2014

In this paper we give upper bounds on the number of minimal separators and potential maximal cliques of graphs w.r.t. two graph parameters, namely vertex cover ($\operatorname{vc}$) and modular width ($\operatorname{mw}$). We prove that for any graph, the number of minimal separators is $\mathcal{O}^*(3^{\operatorname{vc}})$ and $\mathcal{O}^*(1.6181^{\operatorname{mw}})$, and the number of potential maximal cliques is $\mathcal{O}^*(4^{\operatorname{vc}})$ and $\mathcal{O}^*(1.7347^{\operatorname{mw}})$, and these objects can be listed within the same running times. (The $\mathcal{O}^*$ notation suppresses polynomial factors in the size of the input.) Combined with known results, we deduce that a large family of problems, e.g., Treewidth, Minimum Fill-in, Longest Induced Path, Feedback vertex set and many others, can be solved in time $\mathcal{O}^*(4^{\operatorname{vc}})$ or $\mathcal{O}^*(1.7347^{\operatorname{mw}})$.
Ensemble Classifiers and Their Applications: A Review
Venue: arXiv cs.LG 2014
Year: 2014

Ensemble classifier refers to a group of individual classifiers that are cooperatively trained on data set in a supervised classification problem. In this paper we present a review of commonly used ensemble classifiers in the literature. Some ensemble classifiers are also developed targeting specific applications. We also present some application driven ensemble classifiers in this paper.
An Approach to Assertion-based Debugging of Higher-Order (C)LP Programs
Venue: arXiv cs.PL 2014
Year: 2014

Higher-order constructs extend the expressiveness of first-order (Constraint) Logic Programming ((C)LP) both syntactically and semantically. At the same time assertions have been in use for some time in (C)LP systems helping programmers detect errors and validate programs. However, these assertion-based extensions to (C)LP have not been integrated well with higher-order to date. This paper contributes to filling this gap by extending the assertion-based approach to error detection and program validation to the higher-order context within (C)LP. We propose an extension of properties and assertions as used in (C)LP in order to be able to fully describe arguments that are predicates. The extension makes the full power of the assertion language available when describing higher-order arguments. We provide syntax and semantics for (higher-order) properties and assertions, as well as for programs which contain such assertions, including the notions of error and partial correctness and provide some formal results. We also discuss several alternatives for performing run-time checking of such programs.
List decoding group homomorphisms between supersolvable groups
Venue: arXiv cs.IT 2014
Year: 2014

We show that the set of homomorphisms between two supersolvable groups can be locally list decoded up to the minimum distance of the code, extending the results of Dinur et al who studied the case where the groups are abelian. Moreover, when specialized to the abelian case, our proof is more streamlined and gives a better constant in the exponent of the list size. The constant is improved from about 3.5 million to 105.
Cube-Cut: Vertebral Body Segmentation in MRI-Data through Cubic-Shaped Divergences
Venue: arXiv cs.CV 2014
Year: 2014

In this article, we present a graph-based method using a cubic template for volumetric segmentation of vertebrae in magnetic resonance imaging (MRI) acquisitions. The user can define the degree of deviation from a regular cube via a smoothness value Delta. The Cube-Cut algorithm generates a directed graph with two terminal nodes (s-t-network), where the nodes of the graph correspond to a cubic-shaped subset of the image's voxels. The weightings of the graph's terminal edges, which connect every node with a virtual source s or a virtual sink t, represent the affinity of a voxel to the vertebra (source) and to the background (sink). Furthermore, a set of infinite weighted and non-terminal edges implements the smoothness term. After graph construction, a minimal s-t-cut is calculated within polynomial computation time, which splits the nodes into two disjoint units. Subsequently, the segmentation result is determined out of the source-set. A quantitative evaluation of a C++ implementation of the algorithm resulted in an average Dice Similarity Coefficient (DSC) of 81.33% and a running time of less than a minute.
A Simple $O(\log\log(\mathrm{rank}))$-Competitive Algorithm for the Matroid Secretary Problem
Venue: arXiv cs.DS 2014
Year: 2014

Only recently progress has been made in obtaining $o(\log(\mathrm{rank}))$-competitive algorithms for the matroid secretary problem. More precisely, Chakraborty and Lachish (2012) presented a $O(\sqrt{\log(\mathrm{rank})})$-competitive procedure, and Lachish (2014) later presented a $O(\log\log(\mathrm{rank}))$-competitive algorithm. Both these algorithms and their analyses are very involved, which is also reflected in the extremely high constants in their competitive ratios. Using different tools, we present a considerably simpler $O(\log\log(\mathrm{rank}))$-competitive algorithm for the matroid secretary problem. Our algorithm can be interpreted as a distribution over a simple type of matroid secretary algorithms which are easy to analyze. Due to the simplicity of our procedure, we are also able to vastly improve on the hidden constant in the competitive ratio.
Analyzing Android Browser Apps for file:// Vulnerabilities
Venue: arXiv cs.CR 2014
Year: 2014

Securing browsers in mobile devices is very challenging, because these browser apps usually provide browsing services to other apps in the same device. A malicious app installed in a device can potentially obtain sensitive information through a browser app. In this paper, we identify four types of attacks in Android, collectively known as FileCross, that exploits the vulnerable file:// to obtain users' private files, such as cookies, bookmarks, and browsing histories. We design an automated system to dynamically test 115 browser apps collected from Google Play and find that 64 of them are vulnerable to the attacks. Among them are the popular Firefox, Baidu and Maxthon browsers, and the more application-specific ones, including UC Browser HD for tablet users, Wikipedia Browser, and Kids Safe Browser. A detailed analysis of these browsers further shows that 26 browsers (23%) expose their browsing interfaces unintentionally. In response to our reports, the developers concerned promptly patched their browsers by forbidding file:// access to private file zones, disabling JavaScript execution in file:// URLs, or even blocking external file:// URLs. We employ the same system to validate the ten patches received from the developers and find one still failing to block the vulnerability.
The First Parallel Multilingual Corpus of Persian: Toward a Persian BLARK
Venue: arXiv cs.CL 2014
Year: 2014

In this article, we have introduced the first parallel corpus of Persian with more than 10 other European languages. This article describes primary steps toward preparing a Basic Language Resources Kit (BLARK) for Persian. Up to now, we have proposed morphosyntactic specification of Persian based on EAGLE/MULTEXT guidelines and specific resources of MULTEXT-East. The article introduces Persian Language, with emphasis on its orthography and morphosyntactic features, then a new Part-of-Speech categorization and orthography for Persian in digital environments is proposed. Finally, the corpus and related statistic will be analyzed.
Leveraging video annotations in video-based e-learning
Venue: arXiv cs.CY 2014
Year: 2014

The e-learning community has been producing and using video content for a long time, and in the last years, the advent of MOOCs greatly relied on video recordings of teacher courses. Video annotations are information pieces that can be anchored in the temporality of the video so as to sustain various processes ranging from active reading to rich media editing. In this position paper we study how video annotations can be used in an e-learning context - especially MOOCs - from the triple point of view of pedagogical processes, current technical platforms functionalities, and current challenges. Our analysis is that there is still plenty of room for leveraging video annotations in MOOCs beyond simple active reading, namely live annotation, performance annotation and annotation for assignment; and that new developments are needed to accompany this evolution.
An Efficient and Balanced Platform for Data-Parallel Subsampling Workloads
Venue: arXiv cs.DC 2014
Year: 2014

With the advent of internet services, data started growing faster than it can be processed. To personalize user experience, this enormous data has to be processed in real time, in interactive fashion. In order to achieve faster data processing often a statistical method called subsampling. Subsampling workloads compute statistics from a random subset of sample data (i.e., a subsample). Data-parallel platforms group these samples into tasks; each task subsamples its data in parallel. Current, state-of-the-art platforms such as Hadoop are built for large tasks that run for long periods of time, but applications with smaller average task sizes suffer large overheads on these platforms. Tasks in subsampling workloads are sized to minimize the number of overall cache misses, and these tasks can complete in seconds. This technique can reduce the overall length of a map-reduce job, but only when the savings from the cache miss rate reduction are not eclipsed by the platform overhead of task creation and data distribution. In this thesis, we propose a data-parallel platform with an efficient data distribution component that breaks data-parallel subsampling workloads into compute clusters with tiny tasks. Each tiny task completes in few hundreds of milliseconds to seconds. Tiny tasks reduce processor cache misses caused by random subsampling, which speeds up per-task running time. However, they cause significant scheduling overheads and data distribution challenges. We propose a task knee-pointing algorithm and a dynamic scheduler that schedules the tasks to worker nodes based on the availability and response times of the data nodes. We compare our framework against various configurations of BashReduce and Hadoop. A detailed discussion of tiny task approach on two workloads, EAGLET and Netflix movie rating is presented.
DRUG: An Energy-Efficient Data-Centric Routing Protocol for Wireless Sensor Networks
Venue: arXiv cs.NI 2014
Year: 2014

In general, sensor nodes are deployed in left unattended area. In such situation feeding energy to the batteries or replacing the batteries is difficult or even sometimes impossible too. Therefore, prolonging the network lifetime is an important optimization goal in this aspect. In this paper, we propose a new Energy-efficient Datacentric RoUtinG protocol called DRUG. In this paper, we propose an adaptive Data centric approach to find an optimal routing path from source to sink when the sensor nodes are deployed randomly deployed in a restricted service area with single sink. Using the NS-2 Simulator, we compare the performance of DRUG with that of the FLOODING and SPIN protocol.
Approximation for the Path Complexity of Binary Search Tree
Venue: arXiv cs.CC 2014
Year: 2014

The complexity of an algorithm is an important parameter to determine its effi-ciency. They are of different types viz. Time complexity, Space complexity, etc. However, none of them consider the execution path as a complexity measure. Ashok et al, firstly proposed the notion of the Path Complexity of a pro-gram/algorithm, which defined based on the number of execution paths as a function of the input size. However, the notion of path complexity of the pro-gram, cannot apply to the object-oriented environment. Therefore, Anupam et al, has extended the notion of path complexity to the class as follows. The notion of the state of the class is defined based on structural representation (aka state) of the class. The class contains data members and data operations. It considers only those data operations that change the state of the class. The path complexity of the class is defined to be the number of valid input sequences, each of them con-taining valid data operations. Anupam et al, had applied this notion to the class Stack. However, the stack is basic and simple data structures. Therefore, in this research we have used a more complex class to understand the path complexity behavior in the object oriented environment. Binary Search Tree (BST) is one of the well known (and more complex too) data structure, which is useful in sorting, searching, Traffic Engineering and many more applications. We have analyzed the path complexity of the class BST based on the algorithms for insert and delete operations. Additionally, we have modified the delete operation to minimize the path complexity for the class BST.
Decoding binary node labels from censored edge measurements: Phase transition and efficient recovery
Venue: arXiv cs.IT 2014
Year: 2014

We consider the problem of clustering a graph $G$ into two communities by observing a subset of the vertex correlations. Specifically, we consider the inverse problem with observed variables $Y=B_G x \oplus Z$, where $B_G$ is the incidence matrix of a graph $G$, $x$ is the vector of unknown vertex variables (with a uniform prior) and $Z$ is a noise vector with Bernoulli$(\varepsilon)$ i.i.d. entries. All variables and operations are Boolean. This model is motivated by coding, synchronization, and community detection problems. In particular, it corresponds to a stochastic block model or a correlation clustering problem with two communities and censored edges. Without noise, exact recovery (up to global flip) of $x$ is possible if and only the graph $G$ is connected, with a sharp threshold at the edge probability $\log(n)/n$ for Erdős-Rényi random graphs. The first goal of this paper is to determine how the edge probability $p$ needs to scale to allow exact recovery in the presence of noise. Defining the degree (oversampling) rate of the graph by $α=np/\log(n)$, it is shown that exact recovery is possible if and only if $α>2/(1-2\varepsilon)^2+ o(1/(1-2\varepsilon)^2)$. In other words, $2/(1-2\varepsilon)^2$ is the information theoretic threshold for exact recovery at low-SNR. In addition, an efficient recovery algorithm based on semidefinite programming is proposed and shown to succeed in the threshold regime up to twice the optimal rate. For a deterministic graph $G$, defining the degree rate as $α=d/\log(n)$, where $d$ is the minimum degree of the graph, it is shown that the proposed method achieves the rate $α> 4((1+λ)/(1-λ)^2)/(1-2\varepsilon)^2+ o(1/(1-2\varepsilon)^2)$, where $1-λ$ is the spectral gap of the graph $G$.
Efficient Proactive Caching for Supporting Seamless Mobility
Venue: arXiv cs.NI 2014
Year: 2014

We present a distributed proactive caching approach that exploits user mobility information to decide where to proactively cache data to support seamless mobility, while efficiently utilizing cache storage using a congestion pricing scheme. The proposed approach is applicable to the case where objects have different sizes and to a two-level cache hierarchy, for both of which the proactive caching problem is hard. Additionally, our modeling framework considers the case where the delay is independent of the requested data object size and the case where the delay is a function of the object size. Our evaluation results show how various system parameters influence the delay gains of the proposed approach, which achieves robust and good performance relative to an oracle and an optimal scheme for a flat cache structure.
Scheduling over Scenarios on Two Machines
Venue: arXiv cs.DS 2014
Year: 2014

We consider scheduling problems over scenarios where the goal is to find a single assignment of the jobs to the machines which performs well over all possible scenarios. Each scenario is a subset of jobs that must be executed in that scenario and all scenarios are given explicitly. The two objectives that we consider are minimizing the maximum makespan over all scenarios and minimizing the sum of the makespans of all scenarios. For both versions, we give several approximation algorithms and lower bounds on their approximability. With this research into optimization problems over scenarios, we have opened a new and rich field of interesting problems.
iPiano: Inertial Proximal Algorithm for Non-Convex Optimization
Venue: arXiv cs.CV 2014
Year: 2014

In this paper we study an algorithm for solving a minimization problem composed of a differentiable (possibly non-convex) and a convex (possibly non-differentiable) function. The algorithm iPiano combines forward-backward splitting with an inertial force. It can be seen as a non-smooth split version of the Heavy-ball method from Polyak. A rigorous analysis of the algorithm for the proposed class of problems yields global convergence of the function values and the arguments. This makes the algorithm robust for usage on non-convex problems. The convergence result is obtained based on the \KL inequality. This is a very weak restriction, which was used to prove convergence for several other gradient methods. First, an abstract convergence theorem for a generic algorithm is proved, and, then iPiano is shown to satisfy the requirements of this theorem. Furthermore, a convergence rate is established for the general problem class. We demonstrate iPiano on computer vision problems: image denoising with learned priors and diffusion based image compression.