OpenRaiser/Intern-Atlas huggingface dataset:
Tetrisation of triangular meshes and its application in shape blending
Venue: arXiv cs.GR 2016
Year: 2016

The As-Rigid-As-Possible (ARAP) shape deformation framework is a versatile technique for morphing, surface modelling, and mesh editing. We discuss an improvement of the ARAP framework in a few aspects: 1. Given a triangular mesh in 3D space, we introduce a method to associate a tetrahedral structure, which encodes the geometry of the original mesh. 2. We use a Lie algebra based method to interpolate local transformation, which provides better handling of rotation with large angle. 3. We propose a new error function to compile local transformations into a global piecewise linear map, which is rotation invariant and easy to minimise. We implemented a shape blender based on our algorithm and its MIT licensed source code is available online.
PN-Net: Conjoined Triple Deep Network for Learning Local Image Descriptors
Venue: arXiv cs.CV 2016
Year: 2016

In this paper we propose a new approach for learning local descriptors for matching image patches. It has recently been demonstrated that descriptors based on convolutional neural networks (CNN) can significantly improve the matching performance. Unfortunately their computational complexity is prohibitive for any practical application. We address this problem and propose a CNN based descriptor with improved matching performance, significantly reduced training and execution time, as well as low dimensionality. We propose to train the network with triplets of patches that include a positive and negative pairs. To that end we introduce a new loss function that exploits the relations within the triplets. We compare our approach to recently introduced MatchNet and DeepCompare and demonstrate the advantages of our descriptor in terms of performance, memory footprint and speed i.e. when run in GPU, the extraction time of our 128 dimensional feature is comparable to the fastest available binary descriptors such as BRIEF and ORB.
ARL Libraries and Research: Correlates of Grant Funding
Venue: arXiv cs.DL 2016
Year: 2016

While providing the resources and tools that make advanced research possible is a primary mission of academic libraries at large research universities, many other elements also contribute to the success of the research enterprise, such as institutional funding, staffing, labs, and equipment. This study focuses on U.S. members of the ARL, the Association for Research Libraries. Research success is measured by the total grant funding received by the University, creating an ordered set of categories. Combining data from the NSF National Center for Science and Engineering Statistics, ARL Statistics, and IPEDS, the primary explanatory factors for research success are examined. Using linear regression, logistic regression, and the cumulative logit model, the best-fitting models generated by ARL data, NSF data, and the combined data set for both nominal and per capita funding are compared. These models produce the most relevant explanatory variables for research funding, which do not include library-related variables in most cases.
On Secure Network Coding for Two Unicast Sessions
Venue: arXiv cs.IT 2016
Year: 2016

This paper characterizes the secret message capacity of three networks where two unicast sessions share some of the communication resources. Each network consists of erasure channels with state feedback. A passive eavesdropper is assumed to wiretap any one of the links. The capacity achieving schemes as well as the outer bounds are formulated as linear programs. The proposed strategies are then numerically evaluated and shown to achieve higher rate performances (up to a double single- or sum-rate) with respect to alternative strategies, where the network resources are time-shared among the two sessions. These results represent a step towards the secure capacity characterization for general networks. They also show that, even in configurations for which network coding does not offer benefits in absence of security, it can become beneficial under security constraints.
Systematic Block Markov Superposition Transmission of Repetition Codes
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we propose systematic block Markov superposition transmission of repetition~(BMST-R) codes, which can support a wide range of code rates but maintain essentially the same encoding/decoding hardware structure. The systematic BMST-R codes resemble the classical rate-compatible punctured convolutional~(RCPC) codes, except that they are typically non-decodable by the Viterbi algorithm due to the huge constraint length induced by the block-oriented encoding process. The information sequence is partitioned equally into blocks and transmitted directly, while their replicas are interleaved and transmitted in a block Markov superposition manner. By taking into account that the codes are systematic, we derive both upper and lower bounds on the bit-error-rate~(BER) under maximum {\em a posteriori}~(MAP) decoding. The derived lower bound reveals connections among BER, encoding memory and code rate, which provides a way to design good systematic BMST-R codes and also allows us to make trade-offs among efficiency, performance and complexity. Numerical results show that:~1)~the proposed bounds are tight in the high signal-to-noise ratio~(SNR) region;~2)~systematic BMST-R codes perform well in a wide range of code rates, and~3)~systematic BMST-R codes outperform spatially coupled low-density parity-check~(SC-LDPC) codes under an equal decoding latency constraint.
An Alternative Decoding Method for Gabidulin Codes in Characteristic Zero
Venue: arXiv cs.IT 2016
Year: 2016

Gabidulin codes, originally defined over finite fields, are an important class of rank metric codes with various applications. Recently, their definition was generalized to certain fields of characteristic zero and a Welch--Berlekamp like algorithm with complexity $O(n^3)$ was given. We propose a new application of Gabidulin codes over infinite fields: low-rank matrix recovery. Also, an alternative decoding approach is presented based on a Gao type key equation, reducing the complexity to at least $O(n^2)$. This method immediately connects the decoding problem to well-studied problems, which have been investigated in terms of coefficient growth and numerical stability.
Limited-Magnitude Error-Correcting Gray Codes for Rank Modulation
Venue: arXiv cs.IT 2016
Year: 2016

We construct Gray codes over permutations for the rank-modulation scheme, which are also capable of correcting errors under the infinity-metric. These errors model limited-magnitude or spike errors, for which only single-error-detecting Gray codes are currently known. Surprisingly, the error-correcting codes we construct achieve a better asymptotic rate than that of presently known constructions not having the Gray property, and exceed the Gilbert-Varshamov bound. Additionally, we present efficient ranking and unranking procedures, as well as a decoding procedure that runs in linear time. Finally, we also apply our methods to solve an outstanding issue with error-detecting rank-modulation Gray codes (snake-in-the-box codes) under a different metric, the Kendall $τ$-metric, in the group of permutations over an even number of elements $S_{2n}$, where we provide asymptotically optimal codes.
A High-Level LTL Synthesis Format: TLSF v1.0
Venue: arXiv cs.LO 2016
Year: 2016

We present the Temporal Logic Synthesis Format (TLSF), a high-level format to describe synthesis problems via Linear Temporal Logic (LTL). The format builds upon standard LTL, but additionally allows to use high level constructs, such as sets and functions, to provide a compact and human readable representation. Furthermore, the format allows to identify parameters of a specification such that a single description can be used to define a family of problems. We also present a tool to automatically translate the format into plain LTL, which then can be used for synthesis by a solver. The tool also allows to adjust parameters of the specification and to apply standard transformations on the resulting formula.
Asymptotic Close to Optimal Resource Allocation in Centralized Multi-band Wireless Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper concerns sub-channel allocation in multi-user wireless networks with a view to increasing the network throughput. It is assumed there are some sub-channels to be equally divided among active links, such that the total sum rate increases, where it is assumed each link is subject to a maximum transmit power constraint. This problem is found to be a non-convex optimization problem and is hard to deal with for large number of sub channels and/or users. However, relying on some approximation methods, it is demonstrated that the proposed sub-optimal problem has roots in combinatorial optimization, termed as Assignment problem which can be tackled through the so called Hungarian method. Simulation results demonstrate that the proposed method outperforms existing works addressed in the literature.
Combined Compute and Storage: Configurable Memristor Arrays to Accelerate Search
Venue: arXiv cs.ET 2016
Year: 2016

Emerging technologies present opportunities for system designers to meet the challenges presented by competing trends of big data analytics and limitations on CMOS scaling. Specifically, memristors are an emerging high-density technology where the individual memristors can be used as storage or to perform computation. The voltage applied across a memristor determines its behavior (storage vs. compute), which enables a configurable memristor substrate that can embed computation with storage. This paper explores accelerating point and range search queries as instances of the more general configurable combined compute and storage capabilities of memristor arrays. We first present MemCAM, a configurable memristor-based content addressable memory for the cases when fast, infrequent searches over large datasets are required. For frequent searches, memristor lifetime becomes a concern. To increase memristor array lifetime we introduce hybrid data structures that combine trees with MemCAM using conventional CMOS processor/cache hierarchies for the upper levels of the tree and configurable memristor technologies for lower levels. We use SPICE to analyze energy consumption and access time of memristors and use analytic models to evaluate the performance of configurable hybrid data structures. The results show that with acceptable energy consumption our configurable hybrid data structures improve performance of search intensive applications and achieve lifetime in years or decades under continuous queries. Furthermore, the configurability of memristor arrays and the proposed data structures provide opportunities to tune the trade- off between performance and lifetime and the data structures can be easily adapted to future memristors or other technologies with improved endurance.
Downlink and Uplink Cell Association with Traditional Macrocells and Millimeter Wave Small Cells
Venue: arXiv cs.IT 2016
Year: 2016

Millimeter wave (mmWave) links will offer high capacity but are poor at penetrating into or diffracting around solid objects. Thus, we consider a hybrid cellular network with traditional sub 6 GHz macrocells coexisting with denser mmWave small cells, where a mobile user can connect to either opportunistically. We develop a general analytical model to characterize and derive the uplink and downlink cell association in view of the SINR and rate coverage probabilities in such a mixed deployment. We offer extensive validation of these analytical results (which rely on several simplifying assumptions) with simulation results. Using the analytical results, different decoupled uplink and downlink cell association strategies are investigated and their superiority is shown compared to the traditional coupled approach. Finally, small cell biasing in mmWave is studied, and we show that unprecedented biasing values are desirable due to the wide bandwidth.
Architecture-Aware Optimization of an HEVC decoder on Asymmetric Multicore Processors
Venue: arXiv cs.DC 2016
Year: 2016

Low-power asymmetric multicore processors (AMPs) attract considerable attention due to their appealing performance-power ratio for energy-constrained environments. However, these processors pose a significant programming challenge due to the integration of cores with different performance capabilities, asking for an asymmetry-aware scheduling solution that carefully distributes the workload. The recent HEVC standard, which offers several high-level parallelization strategies, is an important application that can benefit from an implementation tailored for the low-power AMPs present in many current mobile or hand-held devices. In this scenario, we present an architecture-aware implementation of an HEVC decoder that embeds a criticality-aware scheduling strategy tuned for a Samsung Exynos 5422 system-on-chip furnished with an ARM big.LITTLE AMP. The performance and energy efficiency of our solution is further enhanced by exploiting the NEON vector engine available in the ARM big.LITTLE architecture. Experimental results expose a 1080p real-time HEVC decoding at 24 frames/sec, and a reduction of energy consumption over 20%.
Towards a Theory of Affect and Software Developers' Performance
Venue: arXiv cs.SE 2016
Year: 2016

For more than thirty years, it has been claimed that a way to improve software developers' productivity and software quality is to focus on people. The underlying assumption seems to be that "happy and satisfied software developers perform better". More specifically, affects-emotions and moods-have an impact on cognitive activities and the working performance of individuals. Development tasks are undertaken heavily through cognitive processes, yet software engineering research (SE) lacks theory on affects and their impact on software development activities. This PhD dissertation supports the advocates of studying the human and social aspects of SE and the psychology of programming. This dissertation aims to theorize on the link between affects and software development performance. A mixed method approach was employed, which comprises studies of the literature in psychology and SE, quantitative experiments, and a qualitative study, for constructing a multifaceted theory of the link between affects and programming performance. The theory explicates the linkage between affects and analytical problem-solving performance of developers, their software development task productivity, and the process behind the linkage. The results are novel in the domains of SE and psychology, and they fill an important lack that had been raised by both previous research and by practitioners. The implications of this PhD lie in setting out the basic building blocks for researching and understanding the affect of software developers, and how it is related to software development performance. Overall, the evidence hints that happy software developers perform better in analytic problem solving, are more productive while developing software, are prone to share their feelings in order to let researchers and managers understand them, and are susceptible to interventions for enhancing their affects on the job.
Deep Perceptual Mapping for Cross-Modal Face Recognition
Venue: arXiv cs.CV 2016
Year: 2016

Cross modal face matching between the thermal and visible spectrum is a much desired capability for night-time surveillance and security applications. Due to a very large modality gap, thermal-to-visible face recognition is one of the most challenging face matching problem. In this paper, we present an approach to bridge this modality gap by a significant margin. Our approach captures the highly non-linear relationship between the two modalities by using a deep neural network. Our model attempts to learn a non-linear mapping from visible to thermal spectrum while preserving the identity information. We show substantive performance improvement on three difficult thermal-visible face datasets. The presented approach improves the state-of-the-art by more than 10\% on UND-X1 dataset and by more than 15-30\% on NVESD dataset in terms of Rank-1 identification. Our method bridges the drop in performance due to the modality gap by more than 40\%.
Bounds on the Communication Rate Needed to Achieve SK Capacity in the Hypergraphical Source Model
Venue: arXiv cs.IT 2016
Year: 2016

In the multiterminal source model of Csisz$\text{á}$r and Narayan, the communication complexity, $R_{\text{SK}}$, for secret key (SK) generation is the minimum rate of communication required to achieve SK capacity. An obvious upper bound to $R_{\text{SK}}$ is given by $R_{\text{CO}}$, which is the minimum rate of communication required for \emph{omniscience}. In this paper we derive a better upper bound to $R_{\text{SK}}$ for the hypergraphical source model, which is a special instance of the multiterminal source model. The upper bound is based on the idea of fractional removal of hyperedges. It is further shown that this upper bound can be computed in polynomial time. We conjecture that our upper bound is tight. For the special case of a graphical source model, we also give an explicit lower bound on $R_{\text{SK}}$. This bound, however, is not tight, as demonstrated by a counterexample.
QuickSched: Task-based parallelism with dependencies and conflicts
Venue: arXiv cs.DC 2016
Year: 2016

This paper describes QuickSched, a compact and efficient Open-Source C-language library for task-based shared-memory parallel programming. QuickSched extends the standard dependency-only scheme of task-based programming with the concept of task conflicts, i.e.~sets of tasks that can be executed in any order, yet not concurrently. These conflicts are modelled using exclusively lockable hierarchical resources. The scheduler itself prioritizes tasks along the critical path of execution and is shown to perform and scale well on a 64-core parallel shared-memory machine for two example problems: A tiled QR decomposition and a task-based Barnes-Hut tree code.
Efficient Compilation to Event-Driven Task Programs
Venue: arXiv cs.DC 2016
Year: 2016

As illustrated by the emergence of a class of new languages and runtimes, it is expected that a large portion of the programs to run on extreme scale computers will need to be written as graphs of event-driven tasks (EDTs). EDT runtime systems, which schedule such collections of tasks, enable more concurrency than traditional runtimes by reducing the amount of inter-task synchronization, improving dynamic load balancing and making more operations asynchronous. We present an efficient technique to generate such task graphs from a polyhedral representation of a program, both in terms of compilation time and asymptotic execution time. Task dependences become materialized in different forms, depending upon the synchronization model available with the targeted runtime. We explore the different ways of programming EDTs using each synchronization model, and identify important sources of overhead associated with them. We evaluate these programming schemes according to the cost they entail in terms of sequential start-up, in-flight task management, space used for synchronization objects, and garbage collection of these objects. While our implementation and evaluation take place in a polyhedral compiler, the presented overhead cost analysis is useful in the more general context of automatic code generation.
Autoreducibility of NP-Complete Sets
Venue: arXiv cs.CC 2016
Year: 2016

We study the polynomial-time autoreducibility of NP-complete sets and obtain separations under strong hypotheses for NP. Assuming there is a p-generic set in NP, we show the following: - For every $k \geq 2$, there is a $k$-T-complete set for NP that is $k$-T autoreducible, but is not $k$-tt autoreducible or $(k-1)$-T autoreducible. - For every $k \geq 3$, there is a $k$-tt-complete set for NP that is $k$-tt autoreducible, but is not $(k-1)$-tt autoreducible or $(k-2)$-T autoreducible. - There is a tt-complete set for NP that is tt-autoreducible, but is not btt-autoreducible. Under the stronger assumption that there is a p-generic set in NP $\cap$ coNP, we show: - For every $k \geq 2$, there is a $k$-tt-complete set for NP that is $k$-tt autoreducible, but is not $(k-1)$-T autoreducible. Our proofs are based on constructions from separating NP-completeness notions. For example, the construction of a 2-T-complete set for NP that is not 2-tt-complete also separates 2-T-autoreducibility from 2-tt-autoreducibility.
COGENT: Certified Compilation for a Functional Systems Language
Venue: arXiv cs.PL 2016
Year: 2016

We present a self-certifying compiler for the COGENT systems language. COGENT is a restricted, polymorphic, higher-order, and purely functional language with linear types and without the need for a trusted runtime or garbage collector. It compiles to efficient C code that is designed to interoperate with existing C functions. The language is suited for layered systems code with minimal sharing such as file systems or network protocol control code. For a well-typed COGENT program, the compiler produces C code, a high-level shallow embedding of its semantics in Isabelle/HOL, and a proof that the C code correctly implements this embedding. The aim is for proof engineers to reason about the full semantics of real-world systems code productively and equationally, while retaining the interoperability and leanness of C. We describe the formal verification stages of the compiler, which include automated formal refinement calculi, a switch from imperative update semantics to functional value semantics formally justified by the linear type system, and a number of standard compiler phases such as type checking and monomorphisation. The compiler certificate is a series of language-level meta proofs and per-program translation validation phases, combined into one coherent top-level theorem in Isabelle/HOL.
Single- and Multi-level Network Sparsification by Algebraic Distance
Venue: arXiv cs.SI 2016
Year: 2016

Network sparsification methods play an important role in modern network analysis when fast estimation of computationally expensive properties (such as the diameter, centrality indices, and paths) is required. We propose a method of network sparsification that preserves a wide range of structural properties. Depending on the analysis goals, the method allows to distinguish between local and global range edges that can be filtered out during the sparsification. First we rank edges by their algebraic distances and then we sample them. We also introduce a multilevel framework for sparsification that can be used to control the sparsification process at various coarse-grained resolutions. Based primarily on the matrix-vector multiplications, our method is easily parallelized for different architectures.
SibRank: Signed Bipartite Network Analysis for Neighbor-based Collaborative Ranking
Venue: arXiv cs.SI 2016
Year: 2016

Collaborative ranking is an emerging field of recommender systems that utilizes users' preference data rather than rating values. Unfortunately, neighbor-based collaborative ranking has gained little attention despite its more flexibility and justifiability. This paper proposes a novel framework, called SibRank that seeks to improve the state of the art neighbor-based collaborative ranking methods. SibRank represents users' preferences as a signed bipartite network, and finds similar users, through a novel personalized ranking algorithm in signed networks.