OpenRaiser/Intern-Atlas huggingface dataset:
Two-Weight and a Few Weights Trace Codes over $\mathbb{F}_{q}+u\mathbb{F}_{q}$
Venue: arXiv cs.IT 2017
Year: 2017

Let $p$ be a prime number, $q=p^s$ for a positive integer $s$. For any positive divisor $e$ of $q-1$, we construct an infinite family codes of size $q^{2m}$ with few Lee-weight. These codes are defined as trace codes over the ring $R=\mathbb{F}_q + u\mathbb{F}_q$, $u^2 = 0$. Using Gauss sums, their Lee weight distributions are provided. When $\gcd(e,m)=1$, we obtain an infinite family of two-weight codes over the finite field $\mathbb{F}_q$ which meet the Griesmer bound. Moreover, when $\gcd(e,m)=2, 3$ or $4$ we construct new infinite family codes with at most five-weight.
It is undecidable if two regular tree languages can be separated by a deterministic tree-walking automaton
Venue: arXiv cs.LO 2017
Year: 2017

The following problem is shown undecidable: given regular languages L,K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K. The proof uses a technique of Kopczyński from LICS 2016.
Online Learning for Distribution-Free Prediction
Venue: arXiv cs.LG 2017
Year: 2017

We develop an online learning method for prediction, which is important in problems with large and/or streaming data sets. We formulate the learning approach using a covariance-fitting methodology, and show that the resulting predictor has desirable computational and distribution-free properties: It is implemented online with a runtime that scales linearly in the number of samples; has a constant memory requirement; avoids local minima problems; and prunes away redundant feature dimensions without relying on restrictive assumptions on the data distribution. In conjunction with the split conformal approach, it also produces distribution-free prediction confidence intervals in a computationally efficient manner. The method is demonstrated on both real and synthetic datasets.
Joint Epipolar Tracking (JET): Simultaneous optimization of epipolar geometry and feature correspondences
Venue: arXiv cs.CV 2017
Year: 2017

Traditionally, pose estimation is considered as a two step problem. First, feature correspondences are determined by direct comparison of image patches, or by associating feature descriptors. In a second step, the relative pose and the coordinates of corresponding points are estimated, most often by minimizing the reprojection error (RPE). RPE optimization is based on a loss function that is merely aware of the feature pixel positions but not of the underlying image intensities. In this paper, we propose a sparse direct method which introduces a loss function that allows to simultaneously optimize the unscaled relative pose, as well as the set of feature correspondences directly considering the image intensity values. Furthermore, we show how to integrate statistical prior information on the motion into the optimization process. This constructive inclusion of a Bayesian bias term is particularly efficient in application cases with a strongly predictable (short term) dynamic, e.g. in a driving scenario. In our experiments, we demonstrate that the JET algorithm we propose outperforms the classical reprojection error optimization on two synthetic datasets and on the KITTI dataset. The JET algorithm runs in real-time on a single CPU thread.
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps
Venue: arXiv cs.DS 2017
Year: 2017

We study the problem of testing unateness of functions $f:\{0,1\}^d \to \mathbb{R}.$ We give a $O(\frac{d}ε \cdot \log\frac{d}ε)$-query nonadaptive tester and a $O(\frac{d}ε)$-query adaptive tester and show that both testers are optimal for a fixed distance parameter $ε$. Previously known unateness testers worked only for Boolean functions, and their query complexity had worse dependence on the dimension both for the adaptive and the nonadaptive case. Moreover, no lower bounds for testing unateness were known. We also generalize our results to obtain optimal unateness testers for functions $f:[n]^d \to \mathbb{R}$. Our results establish that adaptivity helps with testing unateness of real-valued functions on domains of the form $\{0,1\}^d$ and, more generally, $[n]^d$. This stands in contrast to the situation for monotonicity testing where there is no adaptivity gap for functions $f:[n]^d \to \mathbb{R}$.
Transient Response Improvement for Interconnected Linear Systems: Low-Dimensional Controller Retrofit Approach
Venue: arXiv cs.SY 2017
Year: 2017

In this paper, we propose a method of designing low-dimensional retrofit controllers for interconnected linear systems. In the proposed method, by retrofitting an additional low-dimensional controller to a preexisting control system, we aim at improving transient responses caused by spatially local state deflections, which can be regarded as a local fault occurring at a specific subsystem. It is found that a type of state-space expansion, called hierarchical state-space expansion, is the key to systematically designing a low-dimensional retrofit controller, whose action is specialized to controlling the corresponding subsystem. Furthermore, the state-space expansion enables theoretical clarification of the fact that the performance index of the transient response control is improved by appropriately tuning the retrofit controller. The efficiency of the proposed method is shown through a motivating example of power system control where we clarify the trade-off relation between the dimension of a retrofit controller and its control performance.
Compiling Purely Functional Structured Programs
Venue: arXiv cs.PL 2017
Year: 2017

We present a marriage of functional and structured imperative programming that embeds in pure lambda calculus. We describe how we implement the core of this language in a monadic DSL which is structurally equivalent to our intended source language and which, when evaluated, generates pure lambda terms in continuation-passing-style.
Modeling and Identification of Worst-Case Cascading Failures in Power Systems
Venue: arXiv cs.SY 2017
Year: 2017

Cascading failures in power systems normally occur as a result of initial disturbance or faults on electrical elements, closely followed by errors of human operators. It remains a great challenge to systematically trace the source of cascading failures in power systems. In this paper, we develop a mathematical model to describe the cascading dynamics of transmission lines in power networks. In particular, the direct current (DC) power flow equation is employed to calculate the transmission power on the branches. By regarding the disturbances on the elements as the control inputs, we formulate the problem of determining the initial disturbances causing the cascading blackout of power grids in the framework of optimal control theory, and the magnitude of disturbances or faults on the selected branch can be obtained by solving the system of algebraic equations. Moreover, an iterative search algorithm is proposed to look for the optimal solution leading to the worst case of cascading failures. Theoretical analysis guarantees the asymptotic convergence of the iterative search algorithm. Finally, numerical simulations are carried out in IEEE 9 Bus System and IEEE 14 Bus System to validate the proposed approach.
InScript: Narrative texts annotated with script information
Venue: arXiv cs.CL 2017
Year: 2017

This paper presents the InScript corpus (Narrative Texts Instantiating Script structure). InScript is a corpus of 1,000 stories centered around 10 different scenarios. Verbs and noun phrases are annotated with event and participant types, respectively. Additionally, the text is annotated with coreference information. The corpus shows rich lexical variation and will serve as a unique resource for the study of the role of script knowledge in natural language processing.
Neural Networks for Beginners. A fast implementation in Matlab, Torch, TensorFlow
Venue: arXiv cs.LG 2017
Year: 2017

This report provides an introduction to some Machine Learning tools within the most common development environments. It mainly focuses on practical problems, skipping any theoretical introduction. It is oriented to both students trying to approach Machine Learning and experts looking for new frameworks.
An Efficient Runtime Validation Framework based on the Theory of Refinement
Venue: arXiv cs.LO 2017
Year: 2017

We introduce a new methodology based on refinement for testing the functional correctness of hardware and low-level software. Our methodology overcomes several major drawbacks of the de facto testing methodologies used in industry: (1) it is difficult to determine completeness of the properties and tests under consideration (2) defining oracles for tests is expensive and error-prone (3) properties are defined in terms of low-level designs. Our approach compiles a formal refinement conjecture into a runtime check that is performed during simulation. We describe our methodology, discuss algorithmic issues, and provide experimental validation using a 5-stage RISCV pipelined microprocessor and hypervisor.
Spectral Clustering Methods for Multiplex Networks
Venue: arXiv cs.SI 2017
Year: 2017

Multiplex networks offer an important tool for the study of complex systems and extending techniques originally designed for single--layer networks is an important area of study. One of the most important methods for analyzing networks is clustering the nodes into communities that represent common connectivity patterns. In this paper we extend spectral clustering to multiplex structures and discuss some of the difficulties that arise in attempting to define a natural generalization. In order to analyze our approach, we describe three simple, synthetic multiplex networks and compare the performance of different multiplex models. Our results suggest that a dynamically motivated model is more successful than a structurally motivated model in discovering the appropriate communities.
Proof of Luck: an Efficient Blockchain Consensus Protocol
Venue: arXiv cs.CR 2017
Year: 2017

In the paper, we present designs for multiple blockchain consensus primitives and a novel blockchain system, all based on the use of trusted execution environments (TEEs), such as Intel SGX-enabled CPUs. First, we show how using TEEs for existing proof of work schemes can make mining equitably distributed by preventing the use of ASICs. Next, we extend the design with proof of time and proof of ownership consensus primitives to make mining energy- and time-efficient. Further improving on these designs, we present a blockchain using a proof of luck consensus protocol. Our proof of luck blockchain uses a TEE platform's random number generation to choose a consensus leader, which offers low-latency transaction validation, deterministic confirmation time, negligible energy consumption, and equitably distributed mining. Lastly, we discuss a potential protection against up to a constant number of compromised TEEs.
Distributed Kalman filtering with minimum-time consensus algorithm
Venue: arXiv cs.SY 2017
Year: 2017

Fueled by applications in sensor networks, these years have witnessed a surge of interest in distributed estimation and filtering. A new approach is hereby proposed for the Distributed Kalman Filter (DKF) by integrating a local covariance computation scheme. Compared to existing well-established DKF methods, the virtue of the present approach lies in accelerating the convergence of the state estimates to those of the Centralized Kalman Filter (CKF). Meanwhile, an algorithm is proposed that allows each node to compute the averaged measurement noise covariance matrix within a minimal discrete-time running steps in a distributed way. Both theoretical analysis and extensive numerical simulations are conducted to show the feasibility and superiority of the proposed method.
Relaxing state-access constraints in stateful programmable data planes
Venue: arXiv cs.NI 2017
Year: 2017

Supporting the programming of stateful packet forwarding functions in hardware has recently attracted the interest of the research community. When designing such switching chips, the challenge is to guarantee the ability to program functions that can read and modify data plane's state, while keeping line rate performance and state consistency. Current state-of-the-art designs are based on a very conservative all-or-nothing model: programmability is limited only to those functions that are guaranteed to sustain line rate, with any traffic workload. In effect, this limits the maximum time to execute state update operations. In this paper, we explore possible options to relax these constraints by using simulations on real traffic traces. We then propose a model in which functions can be executed in a larger but bounded time, while preventing data hazards with memory locking. We present results showing that such flexibility can be supported with little or no throughput degradation.
Destructive Read by Wave Interference for Arbitration
Venue: arXiv cs.ET 2017
Year: 2017

With the advent of big data and deep learning, computation power has become a bottleneck for many applications. Network-on-Chip (NoC) has been proposed to enable multiprocessor acceleration for deep learning computation, and efficient arbitration is a key issue for high performance. In this paper, an arbitration scheme based on interference of wave is proposed. In this scheme, home node sends out multiple tokens in different frequencies, and nodes that are competing for bus can capture token by sending out wave that cancels its specific wave token. In this scheme, speed-of-light arbitration can be achieved, and full information is available to all nodes in arbitration.
Stabilizing switching signals: a transition from point-wise to asymptotic conditions
Venue: arXiv cs.SY 2017
Year: 2017

Characterization of classes of switching signals that ensure stability of switched systems occupies a significant portion of the switched systems literature. This article collects a multitude of stabilizing switching signals under an umbrella framework. We achieve this in two steps: Firstly, given a family of systems, possibly containing unstable dynamics, we propose a new and general class of stabilizing switching signals. Secondly, we demonstrate that prior results based on both point-wise and asymptotic characterizations follow our result. This is the first attempt in the switched systems literature where these switching signals are unified under one banner.
Behavioral an real-time verification of a pipeline in the COSMA environment
Venue: arXiv cs.SE 2017
Year: 2017

The case study analyzed in the paper illustrates the example of model checking in the COSMA environment. The system itself is a three-stage pipeline consisting of mutually concurrent modules which also compete for a shared resource. System components are specified in terms of Concurrent State Machines (CSM) The paper shows verification of behavioral properties, model reduction technique, analysis of counter-example and checking of real time properties.
System level specification and verification using Concurrent State Machines and COSMA environment
Venue: arXiv cs.SE 2017
Year: 2017

Traffic Light Controller, a typical benchmark device, is specified and verified using of a formal model called Concurrent State Machines (CSM) and the software environment COSMA 2.0, which supports the system level specification and analysis of concurrent, asynchronous and communicating units. The TLC itself is a system of three concurrent components (the controller and two timers). The paper introduces briefly the CSM model and illustrates how system components are specified, how the reachability graph of a system is obtained and how the requirements are formally verified. Finally, the hints for the generation of VHDL code for the TLC are given.
Improving TSP tours using dynamic programming over tree decomposition
Venue: arXiv cs.DS 2017
Year: 2017

Given a traveling salesman problem (TSP) tour $H$ in graph $G$ a $k$-move is an operation which removes $k$ edges from $H$, and adds $k$ edges of $G$ so that a new tour $H'$ is formed. The popular $k$-OPT heuristics for TSP finds a local optimum by starting from an arbitrary tour $H$ and then improving it by a sequence of $k$-moves. Until 2016, the only known algorithm to find an improving $k$-move for a given tour was the naive solution in time $O(n^k)$. At ICALP'16 de Berg, Buchin, Jansen and Woeginger showed an $O(n^{\lfloor 2/3k \rfloor+1})$-time algorithm. We show an algorithm which runs in $O(n^{(1/4+ε_k)k})$ time, where $\lim ε_k = 0$. We are able to show that it improves over the state of the art for every $k=5,\ldots,10$. For the most practically relevant case $k=5$ we provide a slightly refined algorithm running in $O(n^{3.4})$ time. We also show that for the $k=4$ case, improving over the $O(n^3)$-time algorithm of de Berg et al. would be a major breakthrough: an $O(n^{3-ε})$-time algorithm for any $ε>0$ would imply an $O(n^{3-δ})$-time algorithm for the ALL PAIRS SHORTEST PATHS problem, for some $δ>0$.
From visual words to a visual grammar: using language modelling for image classification
Venue: arXiv cs.CV 2017
Year: 2017

The Bag--of--Visual--Words (BoVW) is a visual description technique that aims at shortening the semantic gap by partitioning a low--level feature space into regions of the feature space that potentially correspond to visual concepts and by giving more value to this space. In this paper we present a conceptual analysis of three major properties of language grammar and how they can be adapted to the computer vision and image understanding domain based on the bag of visual words paradigm. Evaluation of the visual grammar shows that a positive impact on classification accuracy and/or descriptor size is obtained when the technique are applied when the proposed techniques are applied.
ParaGraphE: A Library for Parallel Knowledge Graph Embedding
Venue: arXiv cs.AI 2017
Year: 2017

Knowledge graph embedding aims at translating the knowledge graph into numerical representations by transforming the entities and relations into continuous low-dimensional vectors. Recently, many methods [1, 5, 3, 2, 6] have been proposed to deal with this problem, but existing single-thread implementations of them are time-consuming for large-scale knowledge graphs. Here, we design a unified parallel framework to parallelize these methods, which achieves a significant time reduction without influencing the accuracy. We name our framework as ParaGraphE, which provides a library for parallel knowledge graph embedding. The source code can be downloaded from https://github.com/LIBBLE/LIBBLE-MultiThread/tree/master/ParaGraphE .
Replicable Parallel Branch and Bound Search
Venue: arXiv cs.DC 2017
Year: 2017

Combinatorial branch and bound searches are a common technique for solving global optimisation and decision problems. Their performance often depends on good search order heuristics, refined over decades of algorithms research. Parallel search necessarily deviates from the sequential search order, sometimes dramatically and unpredictably, e.g. by distributing work at random. This can disrupt effective search order heuristics and lead to unexpected and highly variable parallel performance. The variability makes it hard to reason about the parallel performance of combinatorial searches. This paper presents a generic parallel branch and bound skeleton, implemented in Haskell, with replicable parallel performance. The skeleton aims to preserve the search order heuristic by distributing work in an ordered fashion, closely following the sequential search order. We demonstrate the generality of the approach by applying the skeleton to 40 instances of three combinatorial problems: Maximum Clique, 0/1 Knapsack and Travelling Salesperson. The overheads of our Haskell skeleton are reasonable: giving slowdown factors of between 1.9 and 6.2 compared with a class-leading, dedicated, and highly optimised C++ Maximum Clique solver. We demonstrate scaling up to 200 cores of a Beowulf cluster, achieving speedups of 100x for several Maximum Clique instances. We demonstrate low variance of parallel performance across all instances of the three combinatorial problems and at all scales up to 200 cores, with median Relative Standard Deviation (RSD) below 2%. Parallel solvers that do not follow the sequential search order exhibit far higher variance, with median RSD exceeding 85% for Knapsack.
Segmented and Directional Impact Detection for Parked Vehicles using Mobile Devices
Venue: arXiv cs.CV 2017
Year: 2017

Mutual usage of vehicles as well as car sharing became more and more attractive during the last years. Especially in urban environments with limited parking possibilities and a higher risk for traffic jams, car rentals and sharing services may save time and money. But when renting a vehicle it could already be damaged (e.g., scratches or bumps inflicted by a previous user) without the damage being perceived by the service provider. In order to address such problems, we present an automated, motion-based system for impact detection, that facilitates a common smartphone as a sensor platform. The system is capable of detecting the impact segment and the point of time of an impact event on a vehicle's surface, as well as its direction of origin. With this additional specific knowledge, it may be possible to reconstruct the circumstances of an impact event, e.g., to prove possible innocence of a service's customer.
A 588 Gbps LDPC Decoder Based on Finite-Alphabet Message Passing
Venue: arXiv cs.AR 2017
Year: 2017

An ultra-high throughput low-density parity check (LDPC) decoder with an unrolled full-parallel architecture is proposed, which achieves the highest decoding throughput compared to previously reported LDPC decoders in the literature. The decoder benefits from a serial message-transfer approach between the decoding stages to alleviate the well-known routing congestion problem in parallel LDPC decoders. Furthermore, a finite-alphabet message passing algorithm is employed to replace the variable node update rule of the standard min-sum decoder with look-up tables, which are designed in a way that maximizes the mutual information between decoding messages. The proposed algorithm results in an architecture with reduced bit-width messages, leading to a significantly higher decoding throughput and to a lower area as compared to a min-sum decoder when serial message-transfer is used. The architecture is placed and routed for the standard min-sum reference decoder and for the proposed finite-alphabet decoder using a custom pseudo-hierarchical backend design strategy to further alleviate routing congestions and to handle the large design. Post-layout results show that the finite-alphabet decoder with the serial message-transfer architecture achieves a throughput as large as 588 Gbps with an area of 16.2 mm$^2$ and dissipates an average power of 22.7 pJ per decoded bit in a 28 nm FD-SOI library. Compared to the reference min-sum decoder, this corresponds to 3.1 times smaller area and 2 times better energy efficiency.
Medical Image Watermarking using 2D-DWT with Enhanced security and capacity
Venue: arXiv cs.MM 2017
Year: 2017

Teleradiology enables medical images to be transferred over the computer networks for many purposes including clinical interpretation, diagnosis, archive, etc. In telemedicine, medical images can be manipulated while transferring. In addition, medical information security requirements are specified by the legislative rules, and concerned entities must adhere to them. In this research, we propose a new scheme based on 2-dimensional Discrete Wavelet Transform (2D DWT) to improve the robustness and authentication of medical images. In addition, the current research improves security and capacity of watermarking using encryption and compression in medical images. The evaluation is performed on the personal dataset, which contains 194 CTI and 68 MRI cases.