OpenRaiser/Intern-Atlas huggingface dataset:
Shape Neutral Analysis of Graph-based Data-structures
Venue: arXiv cs.PL 2018
Year: 2018

Malformed data-structures can lead to runtime errors such as arbitrary memory access or corruption. Despite this, reasoning over data-structure properties for low-level heap manipulating programs remains challenging. In this paper we present a constraint-based program analysis that checks data-structure integrity, w.r.t. given target data-structure properties, as the heap is manipulated by the program. Our approach is to automatically generate a solver for properties using the type definitions from the target program. The generated solver is implemented using a Constraint Handling Rules (CHR) extension of built-in heap, integer and equality solvers. A key property of our program analysis is that the target data-structure properties are shape neutral, i.e., the analysis does not check for properties relating to a given data-structure graph shape, such as doubly-linked-lists versus trees. Nevertheless, the analysis can detect errors in a wide range of data-structure manipulating programs, including those that use lists, trees, DAGs, graphs, etc. We present an implementation that uses the Satisfiability Modulo Constraint Handling Rules (SMCHR) system. Experimental results show that our approach works well for real-world C programs.
A quasi linear-time b-Matching algorithm on distance-hereditary graphs and bounded split-width graphs
Venue: arXiv cs.DS 2018
Year: 2018

We present a quasi linear-time algorithm for Maximum Matching on distance-hereditary graphs and some of their generalizations. This improves on [Dragan, WG'97], who proposed such an algorithm for the subclass of (tent,hexahedron)-free distance-hereditary graphs. Furthermore, our result is derived from a more general one that is obtained for b-Matching. In the (unit cost) b-Matching problem, we are given a graph G = (V, E) together with a nonnegative integer capacity b v for every vertex v $\in$ V. The objective is to assign nonnegative integer weights (x e) e$\in$E so that: for every v $\in$ V the sum of the weights of its incident edges does not exceed b v , and e$\in$E x e is maximized. We present the first algorithm for solving b-Matching on cographs, distance-hereditary graphs and some of their generalizations in quasi linear time. For that, we use a decomposition algorithm that outputs for any graph G a collection of subgraphs of G with no edge-cutsets inducing a complete bipartite subgraph (a.k.a., splits). The latter collection is sometimes called a split decomposition of G. Furthermore, there exists a generic method in order to design graph algorithms based on split decomposition [Rao, DAM'08]. However, this technique only applies to "localized" problems: for which a "best" partial solution for any given subgraph in a split decomposition can be computed almost independently from the remaining of the graph. Such framework does not apply to matching problems since an augmenting path may cross the subgraphs arbitrarily. We introduce a new technique that somehow captures all the partial solutions for a given union of subgraphs in a split decomposition, in a compact and amenable way for algorithms - assuming some piecewise linear assumption holds on the value of such solutions. The latter assumption is shown to hold for b-Matching. Doing so, we prove that solving b-Matching on any pair G, b can be reduced in quasi linear-time to solving this problem on a collection of smaller graphs: that are obtained from the subgraphs in any split decomposition of G by replacing every vertex with a constant-size module. In particular, if G has a split decomposition where all subgraphs have order at most a fixed k, then we can solve b-Matching for G, b in O((k log 2 k)$\times$(m+n)$\times$log ||b|| 1)-time. This answers an open question of [Coudert et al., SODA'18].
Design-Oriented Transient Stability Analysis of Grid-Connected Converters with Power Synchronization Control
Venue: arXiv cs.SY 2018
Year: 2018

The power synchronization control (PSC) has been increasingly used with voltage-source converters (VSCs) connected to the weak ac grid. This paper presents an in-depth analysis on the transient stability of the PSC-VSC by means of the phase portrait. It is revealed that the PSC-VSC will maintain synchronization with the grid as long as there are equilibrium points after the transient disturbance. In contrast, during grid faults without any equilibrium points, the critical clearing angle (CCA) for the PSC-VSC is identified, which is found equal to the power angle at the unstable equilibrium point of the post-fault operation. This fixed CCA facilitates the design of power system protection. Moreover, it is also found that the PSC-VSC can still re-synchronize with the grid after around one cycle of oscillation, even if the fault-clearing angle is beyond the CCA. This feature reduces the risk of system collapse caused by the delayed fault clearance. These findings are corroborated by simulations and experimental tests.
Weakly-Supervised Learning-Based Feature Localization in Confocal Laser Endomicroscopy Glioma Images
Venue: arXiv cs.CV 2018
Year: 2018

Confocal Laser Endomicroscope (CLE) is a novel handheld fluorescence imaging device that has shown promise for rapid intraoperative diagnosis of brain tumor tissue. Currently CLE is capable of image display only and lacks an automatic system to aid the surgeon in analyzing the images. The goal of this project was to develop a computer-aided diagnostic approach for CLE imaging of human glioma with feature localization function. Despite the tremendous progress in object detection and image segmentation methods in recent years, most of such methods require large annotated datasets for training. However, manual annotation of thousands of histopathological images by physicians is costly and time consuming. To overcome this problem, we propose a Weakly-Supervised Learning (WSL)-based model for feature localization that trains on image-level annotations, and then localizes incidences of a class-of-interest in the test image. We developed a novel convolutional neural network for diagnostic features localization from CLE images by employing a novel multiscale activation map that is laterally inhibited and collaterally integrated. To validate our method, we compared proposed model's output to the manual annotation performed by four neurosurgeons on test images. Proposed model achieved 88% mean accuracy and 86% mean intersection over union on intermediate features and 87% mean accuracy and 88% mean intersection over union on restrictive fine features, while outperforming other state of the art methods tested. This system can improve accuracy and efficiency in characterization of CLE images of glioma tissue during surgery, augment intraoperative decision-making process regarding tumor margin and affect resection rates.
Der Trusted Connector im Industrial Data Space
Venue: arXiv cs.CR 2018
Year: 2018

Digitalization affects all industrial domains and causes disruption of various business models. Especially in domains such as logistics and manufacturing, inter-connected devices and near-realtime exchange of sensor data across enterprises allows to speed up processes, reduce costs and respond to customer's needs. However, the advent of the Industrial Internet of Things (IIoT) also raises challenges with respect to security and privacy of sensitive and personal data that is created by sensors and processed by services hosted in different administrative domains. The Industrial Data Space initiative addresses these challenges and proposes a secure edge gateway platform named "Trusted Connector". In this report, we introduce the main security building blocks of the Trusted Connector and point out how they help protecting business-critical data and preserving the user's privacy.
Extensor-Coding
Venue: arXiv cs.DS 2018
Year: 2018

We devise an algorithm that approximately computes the number of paths of length $k$ in a given directed graph with $n$ vertices up to a multiplicative error of $1 \pm \varepsilon$. Our algorithm runs in time $\varepsilon^{-2} 4^k(n+m) \operatorname{poly}(k)$. The algorithm is based on associating with each vertex an element in the exterior (or, Grassmann) algebra, called an extensor, and then performing computations in this algebra. This connection to exterior algebra generalizes a number of previous approaches for the longest path problem and is of independent conceptual interest. Using this approach, we also obtain a deterministic $2^{k}\cdot\operatorname{poly}(n)$ time algorithm to find a $k$-path in a given directed graph that is promised to have few of them. Our results and techniques generalize to the subgraph isomorphism problem when the subgraphs we are looking for have bounded pathwidth. Finally, we also obtain a randomized algorithm to detect $k$-multilinear terms in a multivariate polynomial given as a general algebraic circuit. To the best of our knowledge, this was previously only known for algebraic circuits not involving negative constants.
Coverage of highly-cited documents in Google Scholar, Web of Science, and Scopus: a multidisciplinary comparison
Venue: arXiv cs.DL 2018
Year: 2018

This study explores the extent to which bibliometric indicators based on counts of highly-cited documents could be affected by the choice of data source. The initial hypothesis is that databases that rely on journal selection criteria for their document coverage may not necessarily provide an accurate representation of highly-cited documents across all subject areas, while inclusive databases, which give each document the chance to stand on its own merits, might be better suited to identify highly-cited documents. To test this hypothesis, an analysis of 2,515 highly-cited documents published in 2006 that Google Scholar displays in its Classic Papers product is carried out at the level of broad subject categories, checking whether these documents are also covered in Web of Science and Scopus, and whether the citation counts offered by the different sources are similar. The results show that a large fraction of highly-cited documents in the Social Sciences and Humanities (8.6%-28.2%) are invisible to Web of Science and Scopus. In the Natural, Life, and Health Sciences the proportion of missing highly-cited documents in Web of Science and Scopus is much lower. Furthermore, in all areas, Spearman correlation coefficients of citation counts in Google Scholar, as compared to Web of Science and Scopus citation counts, are remarkably strong (.83-.99). The main conclusion is that the data about highly-cited documents available in the inclusive database Google Scholar does indeed reveal significant coverage deficiencies in Web of Science and Scopus in several areas of research. Therefore, using these selective databases to compute bibliometric indicators based on counts of highly-cited documents might produce biased assessments in poorly covered areas.
Fast parallel multidimensional FFT using advanced MPI
Venue: arXiv cs.DC 2018
Year: 2018

We present a new method for performing global redistributions of multidimensional arrays essential to parallel fast Fourier (or similar) transforms. Traditional methods use standard all-to-all collective communication of contiguous memory buffers, thus necessary requiring local data realignment steps intermixed in-between redistribution and transform steps. Instead, our method takes advantage of subarray datatypes and generalized all-to-all scatter/gather from the MPI-2 standard to communicate discontiguous memory buffers, effectively eliminating the need for local data realignments. Despite generalized all-to-all communication of discontiguous data being generally slower, our proposal economizes in local work. For a range of strong and weak scaling tests, we found the overall performance of our method to be on par and often better than well-established libraries like MPI-FFTW, P3DFFT, and 2DECOMP&FFT. We provide compact routines implemented at the highest possible level using the MPI bindings for the C programming language. These routines apply to any global redistribution, over any two directions of a multidimensional array, decomposed on arbitrary Cartesian processor grids (1D slabs, 2D pencils, or even higher-dimensional decompositions). The high level implementation makes the code easy to read, maintain, and eventually extend. Our approach enables for future speedups from optimizations in the internal datatype handling engines within MPI implementations.
Automatic speech recognition for launch control center communication using recurrent neural networks with data augmentation and custom language model
Venue: arXiv cs.CL 2018
Year: 2018

Transcribing voice communications in NASA's launch control center is important for information utilization. However, automatic speech recognition in this environment is particularly challenging due to the lack of training data, unfamiliar words in acronyms, multiple different speakers and accents, and conversational characteristics of speaking. We used bidirectional deep recurrent neural networks to train and test speech recognition performance. We showed that data augmentation and custom language models can improve speech recognition accuracy. Transcribing communications from the launch control center will help the machine analyze information and accelerate knowledge generation.
Robust Video Content Alignment and Compensation for Clear Vision Through the Rain
Venue: arXiv cs.CV 2018
Year: 2018

Outdoor vision-based systems suffer from atmospheric turbulences, and rain is one of the worst factors for vision degradation. Current rain removal methods show limitations either for complex dynamic scenes, or under torrential rain with opaque occlusions. We propose a novel derain framework which applies superpixel (SP) segmentation to decompose the scene into depth consistent units. Alignment of scene contents are done at the SP level, which proves to be robust against rain occlusion interferences and fast camera motion. Two alignment output tensors, i.e., optimal temporal match tensor and sorted spatial-temporal match tensor, provide informative clues for the location of rain streaks and the occluded background contents. Different classical and novel methods such as Robust Principle Component Analysis and Convolutional Neural Networks are applied and compared for their respective advantages in efficiently exploiting the rich spatial-temporal features provided by the two tensors. Extensive evaluations show that advantage of up to 5dB is achieved on the scene restoration PSNR over state-of-the-art methods, and the advantage is especially obvious with highly complex and dynamic scenes. Visual evaluations show that the proposed framework is not only able to suppress heavy and opaque occluding rain streaks, but also large semi-transparent regional fluctuations and distortions.
A note on the efficiency of position mechanisms with budget constraints
Venue: arXiv cs.GT 2018
Year: 2018

We study the social efficiency of several well-known mechanisms for the allocation of a set of available (advertising) positions to a set of competing budget-constrained users (advertisers). Specifically, we focus on the Generalized Second Price auction (GSP), the Vickrey-Clarke-Groves mechanism (VCG) and the Expressive Generalized First Price auction (EGFP). Using the liquid welfare as our efficiency benchmark, we prove a tight bound of 2 on the liquid price of anarchy and stability of these mechanisms for pure Nash equilibria.
Fast View Synthesis with Deep Stereo Vision
Venue: arXiv cs.CV 2018
Year: 2018

Novel view synthesis is an important problem in computer vision and graphics. Over the years a large number of solutions have been put forward to solve the problem. However, the large-baseline novel view synthesis problem is far from being "solved". Recent works have attempted to use Convolutional Neural Networks (CNNs) to solve view synthesis tasks. Due to the difficulty of learning scene geometry and interpreting camera motion, CNNs are often unable to generate realistic novel views. In this paper, we present a novel view synthesis approach based on stereo-vision and CNNs that decomposes the problem into two sub-tasks: view dependent geometry estimation and texture inpainting. Both tasks are structured prediction problems that could be effectively learned with CNNs. Experiments on the KITTI Odometry dataset show that our approach is more accurate and significantly faster than the current state-of-the-art. The code and supplementary material will be publicly available. Results could be found here https://youtu.be/5pzS9jc-5t0
On the Structure of Unique Shortest Paths in Graphs
Venue: arXiv cs.DS 2018
Year: 2018

This paper develops a structural theory of unique shortest paths in real-weighted graphs. Our main goal is to characterize exactly which sets of node sequences, which we call path systems, can be realized as unique shortest paths in a graph with arbitrary real edge weights. We say that such a path system is strongly metrizable. An easy fact implicit in the literature is that a strongly metrizable path system must be consistent, meaning that no two of its paths may intersect, split apart, and then intersect again. Our main result characterizes strong metrizability via some new forbidden intersection patterns along these lines. In other words, we describe a family of forbidden patterns beyond consistency, and we prove that a path system is strongly metrizable if and only if it is consistent and it avoids all of the patterns in this family. We offer separate (but closely related) characterizations in this way for the settings of directed, undirected, and directed acyclic graphs. Our characterizations are based on a new connection between shortest paths and topology; in particular, our new forbidden patterns are in natural correspondence with two-colored topological $2$-manifolds, which we visualize as polyhedra. We believe that this connection may be of independent interest, and we further show that it implies some additional structural corollaries that seem to suggest new and possibly deep-rooted connections between these areas.
Location-Aware Pilot Allocation in Multi-Cell Multi-User Massive MIMO Networks
Venue: arXiv cs.IT 2018
Year: 2018

We propose a location-aware pilot allocation algorithm for a massive multiple-input multiple-output (MIMO) network with high-mobility users, where the wireless channels are subject to Rician fading. Pilot allocation in massive MIMO is a hard combinatorial problem and depends on the locations of users. As such, it is highly complex to achieve the optimal pilot allocation in real-time for a network with high-mobility users. Against this background, we propose a low-complexity pilot allocation algorithm, which exploits the behavior of line-of-sight (LOS) interference among the users and allocate the same pilot sequence to the users with small LOS interference. Our examination demonstrates that our proposed algorithm significantly outperforms the existing algorithms, even with localization errors. Specifically, for the system considered in this work, our proposed algorithm provides up to 37.26% improvement in sum spectral efficiency (SE) and improves the sum SE of the worst interference-affected users by up to 2.57 bits/sec/Hz, as compared to the existing algorithms.
Post-selected Classical Query Complexity
Venue: arXiv cs.CC 2018
Year: 2018

We study classical query algorithms with post-selection, and find that they are closely connected to rational functions with nonnegative coefficients. We show that the post-selected classical query complexity of a Boolean function is equal to the minimal degree of a rational function with nonnegative coefficients that approximates it (up to a factor of two). For post-selected quantum query algorithms, a similar relationship was shown by Mahadev and de Wolf, where the rational approximations are allowed to have negative coefficients. Using our characterisation, we find an exponentially large separation between post-selected classical query complexity and post-selected quantum query complexity, by proving a lower bound on the degree of rational approximations (with nonnegative coefficients) to the Majority function. This lower bound can be generalised to arbitrary symmetric functions, and allows us to find an unbounded separation between non-deterministic quantum and post-selected classical query complexity. All lower bounds carry over into the communication complexity setting. We show that the zero-error variants of post-selected query algorithms are equivalent to non-deterministic classical query algorithms, which in turn are characterised by nonnegative polynomials, and for some problems require exponentially more queries to the input than their bounded-error counterparts. Finally, we describe a post-selected query algorithm for approximating the Majority function, and an efficient query algorithm for approximate counting.
Time-constrained multi-agent task scheduling based on prescribed performance control
Venue: arXiv cs.SY 2018
Year: 2018

The problem of time-constrained multi-agent task scheduling and control synthesis is addressed. We assume the existence of a high level plan which consists of a sequence of cooperative tasks, each of which is associated with a deadline and several Quality-of-Service levels. By taking into account the reward and cost of satisfying each task, a novel scheduling problem is formulated and a path synthesis algorithm is proposed. Based on the obtained plan, a distributed hybrid control law is further designed for each agent. Under the condition that only a subset of the agents are aware of the high level plan, it is shown that the proposed controller guarantees the satisfaction of time constraints for each task. A simulation example is given to verify the theoretical results.
Structure detection of Wiener-Hammerstein systems with process noise
Venue: arXiv cs.SY 2018
Year: 2018

Identification of nonlinear block-oriented models has been extensively studied. The presence of the process noise, more precisely its location in the block-oriented model influences essentially the development of a consistent identification algorithm. The present work is proposed with the aim to localize the process noise in the block-oriented model for accurate nonlinear modeling. To this end, the response of a Wiener-Hammerstein system is theoretically analyzed, the disturbance component in the output, caused by the process noise preceding the static nonlinearity, is shown to be dependent on the input signal. Inspired by such theoretical observation, a simple and new protocol is developed to determine the location of the process noise with respect to the static nonlinearity by using an input signal that is periodic, but nonstationary within one period. In addition, the proposed technique is promising to detect the type of certain static nonlinearity (e.g., dead-zone, saturation). Finally, it is validated on a simulated example and a real-life benchmark.