OpenRaiser/Intern-Atlas huggingface dataset:
Fully leafed induced subtrees
Venue: arXiv cs.DS 2018
Year: 2018

Let $G$ be a simple graph on $n$ vertices. We consider the problem LIS of deciding whether there exists an induced subtree with exactly $i \leq n$ vertices and $\ell$ leaves in $G$. We study the associated optimization problem, that consists in computing the maximal number of leaves, denoted by $L_G(i)$, realized by an induced subtree with $i$ vertices, for $0 \le i \le n$. We begin by proving that the LIS problem is NP-complete in general and then we compute the values of the map $L_G$ for some classical families of graphs and in particular for the $d$-dimensional hypercubic graphs $Q_d$, for $2 \leq d \leq 6$. We also describe a nontrivial branch and bound algorithm that computes the function $L_G$ for any simple graph $G$. In the special case where $G$ is a tree of maximum degree $Δ$, we provide a $\mathcal{O}(n^3Δ)$ time and $\mathcal{O}(n^2)$ space algorithm to compute the function $L_G$.
Energy Constrained Depth First Search
Venue: arXiv cs.DS 2018
Year: 2018

Depth first search is a natural algorithmic technique for constructing a closed route that visits all vertices of a graph. The length of such route equals, in an edge-weighted tree, twice the total weight of all edges of the tree and this is asymptotically optimal over all exploration strategies. This paper considers a variant of such search strategies where the length of each route is bounded by a positive integer $B$ (e.g. due to limited energy resources of the searcher). The objective is to cover all the edges of a tree $T$ using the minimum number of routes, each starting and ending at the root and each being of length at most $B$. To this end, we analyze the following natural greedy tree traversal process that is based on decomposing a depth first search traversal into a sequence of limited length routes. Given any arbitrary depth first search traversal $R$ of the tree $T$, we cover $R$ with routes $R_1,\ldots,R_l$, each of length at most $B$ such that: $R_i$ starts at the root, reaches directly the farthest point of $R$ visited by $R_{i-1}$, then $R_i$ continues along the path $R$ as far as possible, and finally $R_i$ returns to the root. We call the above algorithm \emph{piecemeal-DFS} and we prove that it achieves the asymptotically minimal number of routes $l$, regardless of the choice of $R$. Our analysis also shows that the total length of the traversal (and thus the traversal time) of piecemeal-DFS is asymptotically minimum over all energy-constrained exploration strategies. The fact that $R$ can be chosen arbitrarily means that the exploration strategy can be constructed in an online fashion when the input tree $T$ is not known in advance. Surprisingly, our results show that depth first search is efficient for energy constrained exploration of trees, even though it is known that the same does not hold for energy constrained exploration of arbitrary graphs.
Ranked Enumeration of Minimal Triangulations
Venue: arXiv cs.DS 2018
Year: 2018

A tree decomposition of a graph facilitates computations by grouping vertices into bags that are interconnected in an acyclic structure, hence their importance in a plethora of problems such as query evaluation over databases and inference over probabilistic graphical models. The relative benefit from different tree decompositions is measured by diverse (sometime complex) cost functions that vary from one application to another. For generic cost functions like width and fill-in, an optimal tree decomposition can be efficiently computed in some cases, notably when the number of minimal separators is bounded by a polynomial (due to Bouchitte and Todinca), we refer to this assumption as "poly-MS." To cover the variety of cost functions in need, it has recently been proposed to devise algorithms for enumerating many decomposition candidates for applications to choose from using specialized, or even machine-learned, cost functions. We explore the ability to produce a large collection of "high quality" tree decompositions. We present the first algorithm for ranked enumeration of the proper (non-redundant) tree decompositions, or equivalently minimal triangulations, under a wide class of cost functions that substantially generalizes the above generic ones. On the theoretical side, we establish the guarantee of polynomial delay if poly-MS is assumed, or if we are interested in tree decompositions of a width bounded by a constant. We describe an experimental evaluation on graphs of various domains (including join queries, Bayesian networks, treewidth benchmarks and random), and explore both the applicability of the poly-MS assumption and the performance of our algorithm relative to the state of the art.
Towards Inferring Mechanical Lock Combinations using Wrist-Wearables as a Side-Channel
Venue: arXiv cs.CR 2018
Year: 2018

Wrist-wearables such as smartwatches and fitness bands are equipped with a variety of high-precision sensors that support novel contextual and activity-based applications. The presence of a diverse set of on-board sensors, however, also expose an additional attack surface which, if not adequately protected, could be potentially exploited to leak private user information. In this paper, we investigate the feasibility of a new attack that takes advantage of a wrist-wearable's motion sensors to infer input on mechanical devices typically used to secure physical access, for example, combination locks. We outline an inference framework that attempts to infer a lock's unlock combination from the wrist motion captured by a smartwatch's gyroscope sensor, and uses a probabilistic model to produce a ranked list of likely unlock combinations. We conduct a thorough empirical evaluation of the proposed framework by employing unlocking-related motion data collected from human subject participants in a variety of controlled and realistic settings. Evaluation results from these experiments demonstrate that motion data from wrist-wearables can be effectively employed as a side-channel to significantly reduce the unlock combination search-space of commonly found combination locks, thus compromising the physical security provided by these locks.
DeepWheat: Estimating Phenotypic Traits from Crop Images with Deep Learning
Venue: arXiv cs.CV 2018
Year: 2018

In this paper, we investigate estimating emergence and biomass traits from color images and elevation maps of wheat field plots. We employ a state-of-the-art deconvolutional network for segmentation and convolutional architectures, with residual and Inception-like layers, to estimate traits via high dimensional nonlinear regression. Evaluation was performed on two different species of wheat, grown in field plots for an experimental plant breeding study. Our framework achieves satisfactory performance with mean and standard deviation of absolute difference of 1.05 and 1.40 counts for emergence and 1.45 and 2.05 for biomass estimation. Our results for counting wheat plants from field images are better than the accuracy reported for the similar, but arguably less difficult, task of counting leaves from indoor images of rosette plants. Our results for biomass estimation, even with a very small dataset, improve upon all previously proposed approaches in the literature.
Orthogonal Terrain Guarding is NP-complete
Venue: arXiv cs.CG 2018
Year: 2018

A terrain is an x-monotone polygonal curve, i.e., successive vertices have increasing x-coordinates. Terrain Guarding can be seen as a special case of the famous art gallery problem where one has to place at most $k$ guards on a terrain made of $n$ vertices in order to fully see it. In 2010, King and Krohn showed that Terrain Guarding is NP-complete [SODA '10, SIAM J. Comput. '11] thereby solving a long-standing open question. They observe that their proof does not settle the complexity of Orthogonal Terrain Guarding where the terrain only consists of horizontal or vertical segments; those terrains are called rectilinear or orthogonal. Recently, Ashok et al. [SoCG'17] presented an FPT algorithm running in time $k^{O(k)}n^{O(1)}$ for Dominating Set in the visibility graphs of rectilinear terrains without 180-degree vertices. They ask if Orthogonal Terrain Guarding is in P or NP-hard. In the same paper, they give a subexponential-time algorithm running in $n^{O(\sqrt n)}$ (actually even $n^{O(\sqrt k)}$) for the general Terrain Guarding and notice that the hardness proof of King and Krohn only disproves a running time $2^{o(n^{1/4})}$ under the ETH. Hence, there is a significant gap between their $2^{O(n^{1/2} \log n)}$-algorithm and the no $2^{o(n^{1/4})}$ ETH-hardness implied by King and Krohn's result. In this paper, we adapt the gadgets of King and Krohn to rectilinear terrains in order to prove that even Orthogonal Terrain Guarding is NP-complete. Then, we show how to obtain an improved ETH lower bound of $2^{Ω(n^{1/3})}$ by refining the quadratic reduction from Planar 3-SAT into a cubic reduction from 3-SAT. This works for both Orthogonal Terrain Guarding and Terrain Guarding.
A Crowd-Annotated Spanish Corpus for Humor Analysis
Venue: arXiv cs.CL 2018
Year: 2018

Computational Humor involves several tasks, such as humor recognition, humor generation, and humor scoring, for which it is useful to have human-curated data. In this work we present a corpus of 27,000 tweets written in Spanish and crowd-annotated by their humor value and funniness score, with about four annotations per tweet, tagged by 1,300 people over the Internet. It is equally divided between tweets coming from humorous and non-humorous accounts. The inter-annotator agreement Krippendorff's alpha value is 0.5710. The dataset is available for general use and can serve as a basis for humor detection and as a first step to tackle subjectivity.
Sparse Doppler Sensing Based on Nested Arrays
Venue: arXiv cs.IT 2018
Year: 2018

Spectral Doppler ultrasound imaging allows visualizing blood flow by estimating its velocity distribution over time. Duplex ultrasound is a modality in which an ultrasound system is used for displaying simultaneously both B-mode images and spectral Doppler data. In B-mode imaging short wide-band pulses are used to achieve sufficient spatial resolution in the images. In contrast, for Doppler imaging, narrow-band pulses are preferred in order to attain increased spectral resolution. Thus, the acquisition time must be shared between the two sequences. In this work, we propose a non-uniform slow-time transmission scheme for spectral Doppler, based on nested arrays, which reduces the number of pulses needed for accurate spectrum recovery. We derive the minimal number of Doppler emissions needed, using this approach, for perfect reconstruction of the blood spectrum in a noise-free environment. Next, we provide two spectrum recovery techniques which achieve this minimal number. The first method performs efficient recovery based on the fast Fourier transform. The second allows for continuous recovery of the Doppler frequencies, thus avoiding off-grid error leakage, at the expense of increased complexity. The performance of the techniques is evaluated using realistic Field II simulations as well as in vivo measurements, producing accurate spectrograms of the blood velocities using a significant reduced number of transmissions. The time gained, where no Doppler pulses are sent, can be used to enable the display of both blood velocities and high quality B-mode images at a high frame rate.
Selfish Attacks in Two-hop IEEE 802.11 Relay Networks: Impact and Countermeasures
Venue: arXiv cs.NI 2018
Year: 2018

In IEEE 802.11 networks, selfish stations can pursue a better quality of service (QoS) through selfish MAC-layer attacks. Such attacks are easy to perform, secure routing protocols do not prevent them, and their detection may be complex. Two-hop relay topologies allow a new angle of attack: a selfish relay can tamper with either source traffic, transit traffic, or both. We consider the applicability of selfish attacks and their variants in the two-hop relay topology, quantify their impact, and study defense measures.
Group Affect Prediction Using Multimodal Distributions
Venue: arXiv cs.CV 2018
Year: 2018

We describe our approach towards building an efficient predictive model to detect emotions for a group of people in an image. We have proposed that training a Convolutional Neural Network (CNN) model on the emotion heatmaps extracted from the image, outperforms a CNN model trained entirely on the raw images. The comparison of the models have been done on a recently published dataset of Emotion Recognition in the Wild (EmotiW) challenge, 2017. The proposed method achieved validation accuracy of 55.23% which is 2.44% above the baseline accuracy, provided by the EmotiW organizers.
A D2D-based Protocol for Ultra-Reliable Wireless Communications for Industrial Automation
Venue: arXiv cs.IT 2018
Year: 2018

As one indispensable use case for the 5G wireless systems on the roadmap, ultra-reliable and low latency communications (URLLC) is a crucial requirement for the coming era of wireless industrial automation. This paper aims to develop communication techniques for making such a paradigm shift from the conventional human-type broadband communications to the emerging machine-type URLLC. One fundamental task for URLLC is to deliver a short command from the controller to each actuator within the stringent delay requirement and also with high-reliability in the downlink. Motivated by the geographic feature in industrial automation that in the factories many tasks are assigned to different groups of devices who work in close proximity to each other and thus can form clusters of reliable device-to-device (D2D) networks, this paper proposes a novel two-phase transmission protocol for achieving the above goal. Specifically, in the first phase within the latency requirement, the multi-antenna base station (BS) combines the messages of each group together and multicasts them to the corresponding groups; while in the second phase, the devices that have decoded the messages successfully, who are defined as the leaders, help relay the messages to the other devices in their groups. Under this protocol, we further design an innovative leader selection based beamforming strategy at the BS by utilizing the sparse optimization technique, which leads to the desired sparsity pattern in user activity, i.e., at least one leader exists in each group, in the first phase, thus making full utilization of the reliable D2D networks in the second phase. Simulation results are provided to show that the proposed two-phase transmission protocol considerably improves the reliability of the whole system within the stringent latency requirement as compared to other existing schemes for URLLC such as Occupy CoW.
Massively Parallel Algorithms and Hardness for Single-Linkage Clustering Under $\ell_p$-Distances
Venue: arXiv cs.DS 2018
Year: 2018

We present massively parallel (MPC) algorithms and hardness of approximation results for computing Single-Linkage Clustering of $n$ input $d$-dimensional vectors under Hamming, $\ell_1, \ell_2$ and $\ell_\infty$ distances. All our algorithms run in $O(\log n)$ rounds of MPC for any fixed $d$ and achieve $(1+ε)$-approximation for all distances (except Hamming for which we show an exact algorithm). We also show constant-factor inapproximability results for $o(\log n)$-round algorithms under standard MPC hardness assumptions (for sufficiently large dimension depending on the distance used). Efficiency of implementation of our algorithms in Apache Spark is demonstrated through experiments on a variety of datasets exhibiting speedups of several orders of magnitude.
Unusual Events in GitHub Repositories
Venue: arXiv cs.SE 2018
Year: 2018

In large and active software projects, it becomes impractical for a developer to stay aware of all project activity. While it might not be necessary to know about each commit or issue, it is arguably important to know about the ones that are unusual. To investigate this hypothesis, we identified unusual events in 200 GitHub projects using a comprehensive list of ways in which an artifact can be unusual and asked 140 developers responsible for or affected by these events to comment on the usefulness of the corresponding information. Based on 2,096 answers, we identify the subset of unusual events that developers consider particularly useful, including large code modifications and unusual amounts of reviewing activity, along with qualitative evidence on the reasons behind these answers. Our findings provide a means for reducing the amount of information that developers need to parse in order to stay up to date with development activity in their projects.
Fast and Accurate Image Super-Resolution with Deep Laplacian Pyramid Networks
Venue: arXiv cs.CV 2018
Year: 2018

Convolutional neural networks have recently demonstrated high-quality reconstruction for single image super-resolution. However, existing methods often require a large number of network parameters and entail heavy computational loads at runtime for generating high-accuracy super-resolution results. In this paper, we propose the deep Laplacian Pyramid Super-Resolution Network for fast and accurate image super-resolution. The proposed network progressively reconstructs the sub-band residuals of high-resolution images at multiple pyramid levels. In contrast to existing methods that involve the bicubic interpolation for pre-processing (which results in large feature maps), the proposed method directly extracts features from the low-resolution input space and thereby entails low computational loads. We train the proposed network with deep supervision using the robust Charbonnier loss functions and achieve high-quality image reconstruction. Furthermore, we utilize the recursive layers to share parameters across as well as within pyramid levels, and thus drastically reduce the number of parameters. Extensive quantitative and qualitative evaluations on benchmark datasets show that the proposed algorithm performs favorably against the state-of-the-art methods in terms of run-time and image quality.
Simpler proof for nonlinearity of majority function
Venue: arXiv cs.IT 2018
Year: 2018

Given a Boolean function f, the (Hamming) weight wt(f) and the nonlinearity N(f) are well known to be important in designing functions that are useful in cryptography. The nonlinearity is expensive to compute, in general, so any shortcuts for doing that for particular functions f are significant. The well known majority function has been extensively studied in a cryptographic context for the last dozen years or so, and there is a formula for its nonlinearity. The known proofs for this formula rely on many detailed results for the Krawtchouk polynomials. This paper gives a much simpler proof.
Heterogeneous multireference alignment: a single pass approach
Venue: arXiv cs.IT 2018
Year: 2018

Multireference alignment (MRA) is the problem of estimating a signal from many noisy and cyclically shifted copies of itself. In this paper, we consider an extension called heterogeneous MRA, where $K$ signals must be estimated, and each observation comes from one of those signals, unknown to us. This is a simplified model for the heterogeneity problem notably arising in cryo-electron microscopy. We propose an algorithm which estimates the $K$ signals without estimating either the shifts or the classes of the observations. It requires only one pass over the data and is based on low-order moments that are invariant under cyclic shifts. Given sufficiently many measurements, one can estimate these invariant features averaged over the $K$ signals. We then design a smooth, non-convex optimization problem to compute a set of signals which are consistent with the estimated averaged features. We find that, in many cases, the proposed approach estimates the set of signals accurately despite non-convexity, and conjecture the number of signals $K$ that can be resolved as a function of the signal length $L$ is on the order of $\sqrt{L}$.
Modelling and Path Planning of Snake Robot in cluttered environment
Venue: arXiv cs.RO 2018
Year: 2018

Studying snake robot locomotion in a cluttered environment has been a complicated task because the motion model is discontinuous due to the physical contact with obstacles, and the contact force cannot be determined solely by contact positions. We present a unique mathematical model of the robot interacting with obstacles in which the contact forces are mapped on the basis of a viscous friction model. Also a motion planning strategy has been introduced which helps deriving the simplest path that ensures sufficient number of contacts of the robot with the obstacles required to reach a goal position. Numerical simulations and experimental results are presented to validate the theoretical approach.
Joint Energy Efficient and QoS-aware Path Allocation and VNF Placement for Service Function Chaining
Venue: arXiv cs.NI 2018
Year: 2018

Service Function Chaining (SFC) allows the forwarding of a traffic flow along a chain of Virtual Network Functions (VNFs, e.g., IDS, firewall, and NAT). Software Defined Networking (SDN) solutions can be used to support SFC reducing the management complexity and the operational costs. One of the most critical issues for the service and network providers is the reduction of energy consumption, which should be achieved without impact to the quality of services. In this paper, we propose a novel resource (re)allocation architecture which enables energy-aware SFC for SDN-based networks. To this end, we model the problems of VNF placement, allocation of VNFs to flows, and flow routing as optimization problems. Thereafter, heuristic algorithms are proposed for the different optimization problems, in order find near-optimal solutions in acceptable times. The performance of the proposed algorithms are numerically evaluated over a real-world topology and various network traffic patterns. The results confirm that the proposed heuristic algorithms provide near optimal solutions while their execution time is applicable for real-life networks.
Image Identification Using SIFT Algorithm: Performance Analysis against Different Image Deformations
Venue: arXiv cs.CV 2018
Year: 2018

Image identification is one of the most challenging tasks in different areas of computer vision. Scale-invariant feature transform is an algorithm to detect and describe local features in images to further use them as an image matching criteria. In this paper, the performance of the SIFT matching algorithm against various image distortions such as rotation, scaling, fisheye and motion distortion are evaluated and false and true positive rates for a large number of image pairs are calculated and presented. We also evaluate the distribution of the matched keypoint orientation difference for each image deformation.