OpenRaiser/Intern-Atlas huggingface dataset:
An Agglomeration Law for Sorting Networks and its Application in Functional Programming
Venue: arXiv cs.DS 2017
Year: 2017

In this paper we will present a general agglomeration law for sorting networks. Agglomeration is a common technique when designing parallel programmes to control the granularity of the computation thereby finding a better fit between the algorithm and the machine on which the algorithm runs. Usually this is done by grouping smaller tasks and computing them en bloc within one parallel process. In the case of sorting networks this could be done by computing bigger parts of the network with one process. The agglomeration law in this paper pursues a different strategy: The input data is grouped and the algorithm is generalized to work on the agglomerated input while the original structure of the algorithm remains. This will result in a new access opportunity to sorting networks well-suited for efficient parallelization on modern multicore computers, computer networks or GPGPU programming. Additionally this enables us to use sorting networks as (parallel or distributed) merging stages for arbitrary sorting algorithms, thereby creating new hybrid sorting algorithms with ease. The expressiveness of functional programming languages helps us to apply this law to systematically constructed sorting networks, leading to efficient and easily adaptable sorting algorithms. An application example is given, using the Eden programming language to show the effectiveness of the law. The implementation is compared with different parallel sorting algorithms by runtime behaviour.
Finding Risk-Averse Shortest Path with Time-dependent Stochastic Costs
Venue: arXiv cs.AI 2017
Year: 2017

In this paper, we tackle the problem of risk-averse route planning in a transportation network with time-dependent and stochastic costs. To solve this problem, we propose an adaptation of the A* algorithm that accommodates any risk measure or decision criterion that is monotonic with first-order stochastic dominance. We also present a case study of our algorithm on the Manhattan, NYC, transportation network.
The Complexity of Abstract Machines
Venue: arXiv cs.PL 2017
Year: 2017

The lambda-calculus is a peculiar computational model whose definition does not come with a notion of machine. Unsurprisingly, implementations of the lambda-calculus have been studied for decades. Abstract machines are implementations schema for fixed evaluation strategies that are a compromise between theory and practice: they are concrete enough to provide a notion of machine and abstract enough to avoid the many intricacies of actual implementations. There is an extensive literature about abstract machines for the lambda-calculus, and yet-quite mysteriously-the efficiency of these machines with respect to the strategy that they implement has almost never been studied. This paper provides an unusual introduction to abstract machines, based on the complexity of their overhead with respect to the length of the implemented strategies. It is conceived to be a tutorial, focusing on the case study of implementing the weak head (call-by-name) strategy, and yet it is an original re-elaboration of known results. Moreover, some of the observation contained here never appeared in print before.
Sound Structure-Preserving Transformation for Weakly-Left-Linear Deterministic Conditional Term Rewriting Systems
Venue: arXiv cs.FL 2017
Year: 2017

In this paper, we show that the SR transformation, a computationally equivalent transformation proposed by Serbanuta and Rosu, is a sound structure-preserving transformation for weakly-left-linear deterministic conditional term rewriting systems. More precisely, we show that every weakly-left-linear deterministic conditional term rewriting system can be converted to an equivalent weakly-left-linear and ultra-weakly-left-linear deterministic conditional term rewriting system and prove that the SR transformation is sound for weakly-left-linear and ultra-weakly-left-linear deterministic conditional term rewriting systems. Here, soundness for a conditional term rewriting system means that reduction of the transformed unconditional term rewriting system creates no undesired reduction sequence for the conditional system.
Ambiguity and Incomplete Information in Categorical Models of Language
Venue: arXiv cs.LO 2017
Year: 2017

We investigate notions of ambiguity and partial information in categorical distributional models of natural language. Probabilistic ambiguity has previously been studied using Selinger's CPM construction. This construction works well for models built upon vector spaces, as has been shown in quantum computational applications. Unfortunately, it doesn't seem to provide a satisfactory method for introducing mixing in other compact closed categories such as the category of sets and binary relations. We therefore lack a uniform strategy for extending a category to model imprecise linguistic information. In this work we adopt a different approach. We analyze different forms of ambiguous and incomplete information, both with and without quantitative probabilistic data. Each scheme then corresponds to a suitable enrichment of the category in which we model language. We view different monads as encapsulating the informational behaviour of interest, by analogy with their use in modelling side effects in computation. Previous results of Jacobs then allow us to systematically construct suitable bases for enrichment. We show that we can freely enrich arbitrary dagger compact closed categories in order to capture all the phenomena of interest, whilst retaining the important dagger compact closed structure. This allows us to construct a model with real convex combination of binary relations that makes non-trivial use of the scalars. Finally we relate our various different enrichments, showing that finite subconvex algebra enrichment covers all the effects under consideration.
Removing Depth-Order Cycles Among Triangles: An Efficient Algorithm Generating Triangular Fragments
Venue: arXiv cs.CG 2017
Year: 2017

More than 25 years ago Chazelle~\emph{et al.} (FOCS 1991) studied the following question: Is it possible to cut any set of $n$ lines in ${\Bbb R}^3$ into a subquadratic number of fragments such that the resulting fragments admit a depth order? They proved an $O(n^{9/4})$ bound for the very special case of bipartite weavings of lines. Since then only little progress was made, until a recent breakthrough by Aronov and Sharir (STOC 2016) who showed that $O(n^{3/2}\mathrm{polylog}\; n)$ fragments suffice for any set of lines. In a follow-up paper Aronov, Miller and Sharir (SODA 2017) proved an $O(n^{3/2+\varepsilon})$ bound for triangles, but their method results in pieces with curved boundaries. Moreover, their method uses polynomial partitions, for which currently no algorithm is known. Thus the most natural version of the problem is still wide open: Can we cut any collection of $n$ disjoint triangles in ${\Bbb R}^3$ into a subquadratic number of triangular fragments that admit a depth order? And if so, can we compute the cuts efficiently? We answer this question by presenting an algorithm that cuts any set of $n$ disjoint triangles in ${\Bbb R}^3$ into $O(n^{7/4}\mathrm{polylog}\; n)$ triangular fragments that admit a depth order. The running time of our algorithm is $O(n^{3.69})$. We also prove a refined bound that depends on the number, $K$, of intersections between the projections of the triangle edges onto the $xy$-plane: we show that $O(n^{1+\varepsilon} + n^{1/4} K^{3/4}\mathrm{polylog}\; n)$ fragments suffice to obtain a depth order. This result extends to $xy$-monotone surface patches bounded by a constant number of bounded-degree algebraic arcs, constituting the first subquadratic bound for surface patches. As a byproduct of our approach we obtain a faster algorithm to cut a set of lines into $O(n^{3/2}\mathrm{polylog}\; n)$ fragments that admit a depth order.
The Unum Number Format: Mathematical Foundations, Implementation and Comparison to IEEE 754 Floating-Point Numbers
Venue: arXiv cs.NA 2017
Year: 2017

This thesis examines a modern concept for machine numbers based on interval arithmetic called 'Unums' and compares it to IEEE 754 floating-point arithmetic, evaluating possible uses of this format where floating-point numbers are inadequate. In the course of this examination, this thesis builds theoretical foundations for IEEE 754 floating-point numbers, interval arithmetic based on the projectively extended real numbers and Unums.
Image denoising using group sparsity residual and external nonlocal self-similarity prior
Venue: arXiv cs.CV 2017
Year: 2017

Nonlocal image representation has been successfully used in many image-related inverse problems including denoising, deblurring and deblocking. However, a majority of reconstruction methods only exploit the nonlocal self-similarity (NSS) prior of the degraded observation image, it is very challenging to reconstruct the latent clean image. In this paper we propose a novel model for image denoising via group sparsity residual and external NSS prior. To boost the performance of image denoising, the concept of group sparsity residual is proposed, and thus the problem of image denoising is transformed into one that reduces the group sparsity residual. Due to the fact that the groups contain a large amount of NSS information of natural images, we obtain a good estimation of the group sparse coefficients of the original image by the external NSS prior based on Gaussian Mixture model (GMM) learning and the group sparse coefficients of noisy image is used to approximate the estimation. Experimental results have demonstrated that the proposed method not only outperforms many state-of-the-art methods, but also delivers the best qualitative denoising results with finer details and less ringing artifacts.
Security-related Research in Ubiquitous Computing -- Results of a Systematic Literature Review
Venue: arXiv cs.CR 2017
Year: 2017

In an endeavor to reach the vision of ubiquitous computing where users are able to use pervasive services without spatial and temporal constraints, we are witnessing a fast growing number of mobile and sensor-enhanced devices becoming available. However, in order to take full advantage of the numerous benefits offered by novel mobile devices and services, we must address the related security issues. In this paper, we present results of a systematic literature review (SLR) on security-related topics in ubiquitous computing environments. In our study, we found 5165 scientific contributions published between 2003 and 2015. We applied a systematic procedure to identify the threats, vulnerabilities, attacks, as well as corresponding defense mechanisms that are discussed in those publications. While this paper mainly discusses the results of our study, the corresponding SLR protocol which provides all details of the SLR is also publicly available for download.
Constrained Deep Weak Supervision for Histopathology Image Segmentation
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, we develop a new weakly-supervised learning algorithm to learn to segment cancerous regions in histopathology images. Our work is under a multiple instance learning framework (MIL) with a new formulation, deep weak supervision (DWS); we also propose an effective way to introduce constraints to our neural networks to assist the learning process. The contributions of our algorithm are threefold: (1) We build an end-to-end learning system that segments cancerous regions with fully convolutional networks (FCN) in which image-to-image weakly-supervised learning is performed. (2) We develop a deep week supervision formulation to exploit multi-scale learning under weak supervision within fully convolutional networks. (3) Constraints about positive instances are introduced in our approach to effectively explore additional weakly-supervised information that is easy to obtain and enjoys a significant boost to the learning process. The proposed algorithm, abbreviated as DWS-MIL, is easy to implement and can be trained efficiently. Our system demonstrates state-of-the-art results on large-scale histopathology image datasets and can be applied to various applications in medical imaging beyond histopathology images such as MRI, CT, and ultrasound images.
Learning a Mixture of Deep Networks for Single Image Super-Resolution
Venue: arXiv cs.CV 2017
Year: 2017

Single image super-resolution (SR) is an ill-posed problem which aims to recover high-resolution (HR) images from their low-resolution (LR) observations. The crux of this problem lies in learning the complex mapping between low-resolution patches and the corresponding high-resolution patches. Prior arts have used either a mixture of simple regression models or a single non-linear neural network for this propose. This paper proposes the method of learning a mixture of SR inference modules in a unified framework to tackle this problem. Specifically, a number of SR inference modules specialized in different image local patterns are first independently applied on the LR image to obtain various HR estimates, and the resultant HR estimates are adaptively aggregated to form the final HR image. By selecting neural networks as the SR inference module, the whole procedure can be incorporated into a unified network and be optimized jointly. Extensive experiments are conducted to investigate the relation between restoration performance and different network architectures. Compared with other current image SR approaches, our proposed method achieves state-of-the-arts restoration results on a wide range of images consistently while allowing more flexible design choices. The source codes are available in http://www.ifp.illinois.edu/~dingliu2/accv2016.
Loss and Bandwidth Studies on Multimode Polymer Waveguide Components for On-Board High-Speed Optical Interconnects
Venue: arXiv cs.ET 2017
Year: 2017

Optical interconnects play a key role in the implementation of high-speed short-reach communication links within high-performance electronic systems. Multimode polymer waveguides in particular are strong candidates for use in passive optical backplanes as they can be cost-effectively integrated onto standard PCBs. Various optical backplanes using this technology and featuring a large number of multimode polymer waveguide components have been recently demonstrated. The optimisation of the loss performance of these complex waveguide layouts becomes particularly important at high data rates (>=25 Gb/s) due to the associated stringent power budget requirements. Moreover, launch conditions have to be carefully considered in such systems due to the highly-multimoded nature of this waveguide technology. In this paper therefore, we present thorough loss and bandwidth studies on siloxane-based multimode waveguides and waveguide components (i.e. bends and crossings) that enable the implementation of passive optical backplanes. The performance of these components is experimentally investigated under different launch conditions for different waveguide profiles that can be readily achieved through fabrication. Useful design rules on the use of waveguide bends and crossings are derived for each waveguide type. It is shown that the choice of waveguide parameters depends on the particular waveguide layout, assumed launch conditions and desired link bandwidth. As an application of these studies, the obtained results are employed to optimise the loss performance of a 10-card shuffle router and enable >=40 Gb/s data transmission.
Outage Analysis of Offloading in Heterogeneous Networks: Composite Fading Channels
Venue: arXiv cs.NI 2017
Year: 2017

Small cells deployment is one of the most significant long-term strategic policies of the mobile network operators. In heterogeneous networks (HetNets), small cells serve as offloading spots in the radio access network to offload macro users (MUs) and their associated traffic from congested macrocells. In this paper, we perform analytical analysis and investigate how the radio propagation effects such as multipath and shadowing and small cell base station density affect MUs' offloading to small cell network (SCN). In particular, we exploit composite fading channels in our evaluation when an MU is offloaded to SCN with varying small and macro cell densities in the stochastic HetNets framework. We derive the expressions for outage probability (equivalently success probability) of the MU in macro network and SCN for two different cases, viz.: i) Nakagami-lognormal channel fading; ii) time-shared (combined) shadowed/unshadowed channel fading. We propose efficient approximations for the probability density functions of the channel fading (power) for the above-mentioned fading distributions that do not have closed-form expressions employing Gauss-Hermite integration and finite exponential series, respectively. Finally, the outage probability performance of MU with and without offloading options/services is analyzed for various settings of fading channels.
A Hierarchical Image Matting Model for Blood Vessel Segmentation in Fundus images
Venue: arXiv cs.CV 2017
Year: 2017

In this paper, a hierarchical image matting model is proposed to extract blood vessels from fundus images. More specifically, a hierarchical strategy utilizing the continuity and extendibility of retinal blood vessels is integrated into the image matting model for blood vessel segmentation. Normally the matting models require the user specified trimap, which separates the input image into three regions manually: the foreground, background and unknown regions. However, since creating a user specified trimap is a tedious and time-consuming task, region features of blood vessels are used to generate the trimap automatically in this paper. The proposed model has low computational complexity and outperforms many other state-ofart supervised and unsupervised methods in terms of accuracy, which achieves a vessel segmentation accuracy of 96:0%, 95:7% and 95:1% in an average time of 10:72s, 15:74s and 50:71s on images from three publicly available fundus image datasets DRIVE, STARE, and CHASE DB1, respectively.
Secrecy Outage Analysis for Downlink Transmissions in the Presence of Randomly Located Eavesdroppers
Venue: arXiv cs.IT 2017
Year: 2017

We analyze the secrecy outage probability in the downlink for wireless networks with spatially (Poisson) distributed eavesdroppers (EDs) under the assumption that the base station employs transmit antenna selection (TAS) to enhance secrecy performance. We compare the cases where the receiving user equipment (UE) operates in half-duplex (HD) mode and full-duplex (FD) mode. In the latter case, the UE simultaneously receives the intended downlink message and transmits a jamming signal to strengthen secrecy. We investigate two models of (semi)passive eavesdropping: (1) EDs act independently and (2) EDs collude to intercept the transmitted message. For both of these models, we obtain expressions for the secrecy outage probability in the downlink for HD and FD UE operation. The expressions for HD systems have very accurate approximate or exact forms in terms of elementary and/or special functions for all path loss exponents. Those related to the FD systems have exact integral forms for general path loss exponents, while exact closed forms are given for specific exponents. A closed-form approximation is also derived for the FD case with colluding EDs. The resulting analysis shows that the reduction in the secrecy outage probability is logarithmic in the number of antennas used for TAS and identifies conditions under which HD operation should be used instead of FD jamming at the UE. These performance trends and exact relations between system parameters can be used to develop adaptive power allocation and duplex operation methods in practice. Examples of such techniques are alluded to herein.
Single Letter Expression of Capacity for a Class of Channels with Memory
Venue: arXiv cs.IT 2017
Year: 2017

We study finite alphabet channels with Unit Memory on the previous Channel Outputs called UMCO channels. We identify necessary and sufficient conditions, to test whether the capacity achieving channel input distributions with feedback are time-invariant, and whether feedback capacity is characterized by single letter, expressions, similar to that of memoryless channels. The method is based on showing that a certain dynamic programming equation, which in general, is a nested optimization problem over the sequence of channel input distributions, reduces to a non-nested optimization problem. Moreover, for UMCO channels, we give a simple expression for the ML error exponent, and we identify sufficient conditions to test whether feedback does not increase capacity. We derive similar results, when transmission cost constraints are imposed. We apply the results to a special class of the UMCO channels, the Binary State Symmetric Channel (BSSC) with and without transmission cost constraints, to show that the optimization problem of feedback capacity is non-nested, the capacity achieving channel input distribution and the corresponding channel output transition probability distribution are time-invariant, and feedback capacity is characterized by a single letter formulae, precisely as Shannon's single letter characterization of capacity of memoryless channels. Then we derive closed form expressions for the capacity achieving channel input distribution and feedback capacity. We use the closed form expressions to evaluate an error exponent for ML decoding.
A Generalization of Quasi-twisted Codes: Multi-twisted codes
Venue: arXiv cs.IT 2017
Year: 2017

Cyclic codes and their various generalizations, such as quasi-twisted (QT) codes, have a special place in algebraic coding theory. Among other things, many of the best-known or optimal codes have been obtained from these classes. In this work we introduce a new generalization of QT codes that we call multi-twisted (MT) codes and study some of their basic properties. Presenting several methods of constructing codes in this class and obtaining bounds on the minimum distances, we show that there exist codes with good parameters in this class that cannot be obtained as QT or constacyclic codes. This suggests that considering this larger class in computer searches is promising for constructing codes with better parameters than currently best-known linear codes. Working with this new class of codes motivated us to consider a problem about binomials over finite fields and to discover a result that is interesting in its own right.
Estimating Quality in Multi-Objective Bandits Optimization
Venue: arXiv cs.LG 2017
Year: 2017

Many real-world applications are characterized by a number of conflicting performance measures. As optimizing in a multi-objective setting leads to a set of non-dominated solutions, a preference function is required for selecting the solution with the appropriate trade-off between the objectives. The question is: how good do estimations of these objectives have to be in order for the solution maximizing the preference function to remain unchanged? In this paper, we introduce the concept of preference radius to characterize the robustness of the preference function and provide guidelines for controlling the quality of estimations in the multi-objective setting. More specifically, we provide a general formulation of multi-objective optimization under the bandits setting. We show how the preference radius relates to the optimal gap and we use this concept to provide a theoretical analysis of the Thompson sampling algorithm from multivariate normal priors. We finally present experiments to support the theoretical results and highlight the fact that one cannot simply scalarize multi-objective problems into single-objective problems.