OpenRaiser/Intern-Atlas huggingface dataset:
PUF-FSM: A Controlled Strong PUF
Venue: arXiv cs.CR 2017
Year: 2017

This paper presents the PUF finite state machine (PUF-FSM) that is served as a practical {\it controlled} strong PUF. Previous controlled PUF designs have the difficulties of stabilizing the noisy PUF responses where the error correction logic is required. In addition, the computed helper data to assist error correcting, however, leaks information, which poses the controlled PUF under the threatens of fault attacks or reliability-based attacks. The PUF-FSM eschews the error correction logic and the computation, storage and loading of the helper data on-chip by only employing error-free responses judiciously determined on demand in the absence of an Arbiter PUF with a large CRP space. In addition, the access to the PUF-FSM is controlled by the trusted entity. Control in means of i) restricting challenges presented to the PUF and ii) further preventing repeated response evaluations to gain unreliability side-channel information are foundations of defensing the most powerful modeling attacks. The PUF-FSM goes beyond authentications/identifications to such as key generations and advanced cryptographic applications built upon a shared key.
Vulnerability of Deep Reinforcement Learning to Policy Induction Attacks
Venue: arXiv cs.LG 2017
Year: 2017

Deep learning classifiers are known to be inherently vulnerable to manipulation by intentionally perturbed inputs, named adversarial examples. In this work, we establish that reinforcement learning techniques based on Deep Q-Networks (DQNs) are also vulnerable to adversarial input perturbations, and verify the transferability of adversarial examples across different DQN models. Furthermore, we present a novel class of attacks based on this vulnerability that enable policy manipulation and induction in the learning process of DQNs. We propose an attack mechanism that exploits the transferability of adversarial examples to implement policy induction attacks on DQNs, and demonstrate its efficacy and impact through experimental study of a game-learning scenario.
A Projection Decoding of a Binary Extremal Self-Dual Code of Length $40$
Venue: arXiv cs.IT 2017
Year: 2017

As far as we know, there is no decoding algorithm of any binary self-dual $[40, 20, 8]$ code except for the syndrome decoding applied to the code directly. This syndrome decoding for a binary self-dual $[40,20,8]$ code is not efficient in the sense that it cannot be done by hand due to a large syndrome table. The purpose of this paper is to give two new efficient decoding algorithms for an extremal binary doubly-even self-dual $[40,20, 8]$ code $C_{40,1}^{DE}$ by hand with the help of a Hermitian self-dual $[10,5,4]$ code $E_{10}$ over $GF(4)$. The main idea of this decoding is to project codewords of $C_{40,1}^{DE}$ onto $E_{10}$ so that it reduces the complexity of the decoding of $C_{40,1}^{DE}$. The first algorithm is called the representation decoding algorithm. It is based on the pattern of codewords of $E_{10}$. Using certain automorphisms of $E_{10}$, we show that only eight types of codewords of $E_{10}$ can produce all the codewords of $E_{10}$. The second algorithm is called the syndrome decoding algorithm based on $E_{10}$. It first solves the syndrome equation in $E_{10}$ and finds a corresponding binary codeword of $C_{40,1}^{DE}$.
hMDAP: A Hybrid Framework for Multi-paradigm Data Analytical Processing on Spark
Venue: arXiv cs.DB 2017
Year: 2017

We propose hMDAP, a hybrid framework for large-scale data analytical processing on Spark, to support multi-paradigm process (incl. OLAP, machine learning, and graph analysis etc.) in distributed environments. The framework features a three-layer data process module and a business process module which controls the former. We will demonstrate the strength of hMDAP by using traffic scenarios in a real world.
Stable Wireless Network Control Under Service Constraints
Venue: arXiv cs.IT 2017
Year: 2017

We consider the design of wireless queueing network control policies with particular focus on combining stability with additional application-dependent requirements. Thereby, we consequently pursue a cost function based approach that provides the flexibility to incorporate constraints and requirements of particular services or applications. As typical examples of such requirements, we consider the reduction of buffer underflows in case of streaming traffic, and energy efficiency in networks of battery powered nodes. Compared to the classical throughput optimal control problem, such requirements significantly complicate the control problem. We provide easily verifyable theoretical conditions for stability, and, additionally, compare various candidate cost functions applied to wireless networks with streaming media traffic. Moreover, we demonstrate how the framework can be applied to the problem of energy efficient routing, and we demonstrate the aplication of our framework in cross-layer control problems for wireless multihop networks, using an advanced power control scheme for interference mitigation, based on successive convex approximation. In all scenarios, the performance of our control framework is evaluated using extensive numerical simulations.
Bandwidth limited object recognition in high resolution imagery
Venue: arXiv cs.CV 2017
Year: 2017

This paper proposes a novel method to optimize bandwidth usage for object detection in critical communication scenarios. We develop two operating models of active information seeking. The first model identifies promising regions in low resolution imagery and progressively requests higher resolution regions on which to perform recognition of higher semantic quality. The second model identifies promising regions in low resolution imagery while simultaneously predicting the approximate location of the object of higher semantic quality. From this general framework, we develop a car recognition system via identification of its license plate and evaluate the performance of both models on a car dataset that we introduce. Results are compared with traditional JPEG compression and demonstrate that our system saves up to one order of magnitude of bandwidth while sacrificing little in terms of recognition performance.
Auxiliary Multimodal LSTM for Audio-visual Speech Recognition and Lipreading
Venue: arXiv cs.CV 2017
Year: 2017

The Aduio-visual Speech Recognition (AVSR) which employs both the video and audio information to do Automatic Speech Recognition (ASR) is one of the application of multimodal leaning making ASR system more robust and accuracy. The traditional models usually treated AVSR as inference or projection but strict prior limits its ability. As the revival of deep learning, Deep Neural Networks (DNN) becomes an important toolkit in many traditional classification tasks including ASR, image classification, natural language processing. Some DNN models were used in AVSR like Multimodal Deep Autoencoders (MDAEs), Multimodal Deep Belief Network (MDBN) and Multimodal Deep Boltzmann Machine (MDBM) that actually work better than traditional methods. However, such DNN models have several shortcomings: (1) They don't balance the modal fusion and temporal fusion, or even haven't temporal fusion; (2)The architecture of these models isn't end-to-end, the training and testing getting cumbersome. We propose a DNN model, Auxiliary Multimodal LSTM (am-LSTM), to overcome such weakness. The am-LSTM could be trained and tested once, moreover easy to train and preventing overfitting automatically. The extensibility and flexibility are also take into consideration. The experiments show that am-LSTM is much better than traditional methods and other DNN models in three datasets.
About the efficient reduction of lambda terms
Venue: arXiv cs.LO 2017
Year: 2017

There is still a lot of confusion about "optimal" sharing in the lambda calculus, and its actual efficiency. In this article, we shall try to clarify some of these issues.
Geometric features for voxel-based surface recognition
Venue: arXiv cs.CV 2017
Year: 2017

We introduce a library of geometric voxel features for CAD surface recognition/retrieval tasks. Our features include local versions of the intrinsic volumes (the usual 3D volume, surface area, integrated mean and Gaussian curvature) and a few closely related quantities. We also compute Haar wavelet and statistical distribution features by aggregating raw voxel features. We apply our features to object classification on the ESB data set and demonstrate accurate results with a small number of shallow decision trees.
Generalized Expectation Consistent Signal Recovery for Nonlinear Measurements
Venue: arXiv cs.IT 2017
Year: 2017

In this paper, we propose a generalized expectation consistent signal recovery algorithm to estimate the signal $\mathbf{x}$ from the nonlinear measurements of a linear transform output $\mathbf{z}=\mathbf{A}\mathbf{x}$. This estimation problem has been encountered in many applications, such as communications with front-end impairments, compressed sensing, and phase retrieval. The proposed algorithm extends the prior art called generalized turbo signal recovery from a partial discrete Fourier transform matrix $\mathbf{A}$ to a class of general matrices. Numerical results show the excellent agreement of the proposed algorithm with the theoretical Bayesian-optimal estimator derived using the replica method.
Poisson Vector Graphics (PVG) and Its Closed-Form Solver
Venue: arXiv cs.GR 2017
Year: 2017

This paper presents Poisson vector graphics, an extension of the popular first-order diffusion curves, for generating smooth-shaded images. Armed with two new types of primitives, namely Poisson curves and Poisson regions, PVG can easily produce photorealistic effects such as specular highlights, core shadows, translucency and halos. Within the PVG framework, users specify color as the Dirichlet boundary condition of diffusion curves and control tone by offsetting the Laplacian, where both controls are simply done by mouse click and slider dragging. The separation of color and tone not only follows the basic drawing principle that is widely adopted by professional artists, but also brings three unique features to PVG, i.e., local hue change, ease of extrema control, and permit of intersection among geometric primitives, making PVG an ideal authoring tool. To render PVG, we develop an efficient method to solve 2D Poisson's equations with piecewise constant Laplacians. In contrast to the conventional finite element method that computes numerical solutions only, our method expresses the solution using harmonic B-spline, whose basis functions can be constructed locally and the control coefficients are obtained by solving a small sparse linear system. Our closed-form solver is numerically stable and it supports random access evaluation, zooming-in of arbitrary resolution and anti-aliasing. Although the harmonic B-spline based solutions are approximate, computational results show that the relative mean error is less than 0.3%, which cannot be distinguished by naked eyes.
Transactional Partitioning: A New Abstraction for Main-Memory Databases
Venue: arXiv cs.DB 2017
Year: 2017

The growth in variety and volume of OLTP (Online Transaction Processing) applications poses a challenge to OLTP systems to meet performance and cost demands in the existing hardware landscape. These applications are highly interactive (latency sensitive) and require update consistency. They target commodity hardware for deployment and demand scalability in throughput with increasing clients and data. Currently, OLTP systems used by these applications provide trade-offs in performance and ease of development over a variety of applications. In order to bridge the gap between performance and ease of development, we propose an intuitive, high-level programming model which allows OLTP applications to be modeled as a cluster of application logic units. By extending transactions guaranteeing full ACID semantics to provide the proposed model, we maintain ease of application development. The model allows the application developer to reason about program performance, and to influence it without the involvement of OLTP system designers (database designers) and/or DBAs. As a result, the database designer is free to focus on efficient running of programs to ensure optimal cluster resource utilization.
A Tutorial on Using Dafny to Construct Verified Software
Venue: arXiv cs.SE 2017
Year: 2017

This paper is a tutorial for newcomers to the field of automated verification tools, though we assume the reader to be relatively familiar with Hoare-style verification. In this paper, besides introducing the most basic features of the language and verifier Dafny, we place special emphasis on how to use Dafny as an assistant in the development of verified programs. Our main aim is to encourage the software engineering community to make the move towards using formal verification tools.
Towards a New Interpretation of Separable Convolutions
Venue: arXiv cs.LG 2017
Year: 2017

In recent times, the use of separable convolutions in deep convolutional neural network architectures has been explored. Several researchers, most notably (Chollet, 2016) and (Ghosh, 2017) have used separable convolutions in their deep architectures and have demonstrated state of the art or close to state of the art performance. However, the underlying mechanism of action of separable convolutions are still not fully understood. Although their mathematical definition is well understood as a depthwise convolution followed by a pointwise convolution, deeper interpretations such as the extreme Inception hypothesis (Chollet, 2016) have failed to provide a thorough explanation of their efficacy. In this paper, we propose a hybrid interpretation that we believe is a better model for explaining the efficacy of separable convolutions.
Towards prediction of rapid intensification in tropical cyclones with recurrent neural networks
Venue: arXiv cs.LG 2017
Year: 2017

The problem where a tropical cyclone intensifies dramatically within a short period of time is known as rapid intensification. This has been one of the major challenges for tropical weather forecasting. Recurrent neural networks have been promising for time series problems which makes them appropriate for rapid intensification. In this paper, recurrent neural networks are used to predict rapid intensification cases of tropical cyclones from the South Pacific and South Indian Ocean regions. A class imbalanced problem is encountered which makes it very challenging to achieve promising performance. A simple strategy was proposed to include more positive cases for detection where the false positive rate was slightly improved. The limitations of building an efficient system remains due to the challenges of addressing the class imbalance problem encountered for rapid intensification prediction. This motivates further research in using innovative machine learning methods.
Sum of squares lower bounds for refuting any CSP
Venue: arXiv cs.CC 2017
Year: 2017

Let $P:\{0,1\}^k \to \{0,1\}$ be a nontrivial $k$-ary predicate. Consider a random instance of the constraint satisfaction problem $\mathrm{CSP}(P)$ on $n$ variables with $Δn$ constraints, each being $P$ applied to $k$ randomly chosen literals. Provided the constraint density satisfies $Δ\gg 1$, such an instance is unsatisfiable with high probability. The \emph{refutation} problem is to efficiently find a proof of unsatisfiability. We show that whenever the predicate $P$ supports a $t$-\emph{wise uniform} probability distribution on its satisfying assignments, the sum of squares (SOS) algorithm of degree $d = Θ(\frac{n}{Δ^{2/(t-1)} \log Δ})$ (which runs in time $n^{O(d)}$) \emph{cannot} refute a random instance of $\mathrm{CSP}(P)$. In particular, the polynomial-time SOS algorithm requires $\widetildeΩ(n^{(t+1)/2})$ constraints to refute random instances of CSP$(P)$ when $P$ supports a $t$-wise uniform distribution on its satisfying assignments. Together with recent work of Lee et al. [LRS15], our result also implies that \emph{any} polynomial-size semidefinite programming relaxation for refutation requires at least $\widetildeΩ(n^{(t+1)/2})$ constraints. Our results (which also extend with no change to CSPs over larger alphabets) subsume all previously known lower bounds for semialgebraic refutation of random CSPs. For every constraint predicate~$P$, they give a three-way hardness tradeoff between the density of constraints, the SOS degree (hence running time), and the strength of the refutation. By recent algorithmic results of Allen et al. [AOW15] and Raghavendra et al. [RRS16], this full three-way tradeoff is \emph{tight}, up to lower-order factors.
Analytic Connectivity in General Hypergraphs
Venue: arXiv cs.DM 2017
Year: 2017

In this paper we extend the known results of analytic connectivity to non-uniform hypergraphs. We prove a modified Cheeger's inequality and also give a bound on analytic connectivity with respect to the degree sequence and diameter of a hypergraph.
Faster K-Means Cluster Estimation
Venue: arXiv cs.LG 2017
Year: 2017

There has been considerable work on improving popular clustering algorithm `K-means' in terms of mean squared error (MSE) and speed, both. However, most of the k-means variants tend to compute distance of each data point to each cluster centroid for every iteration. We propose a fast heuristic to overcome this bottleneck with only marginal increase in MSE. We observe that across all iterations of K-means, a data point changes its membership only among a small subset of clusters. Our heuristic predicts such clusters for each data point by looking at nearby clusters after the first iteration of k-means. We augment well known variants of k-means with our heuristic to demonstrate effectiveness of our heuristic. For various synthetic and real-world datasets, our heuristic achieves speed-up of up-to 3 times when compared to efficient variants of k-means.
Une mesure d'expertise pour le crowdsourcing
Venue: arXiv cs.AI 2017
Year: 2017

Crowdsourcing, a major economic issue, is the fact that the firm outsources internal task to the crowd. It is a form of digital subcontracting for the general public. The evaluation of the participants work quality is a major issue in crowdsourcing. Indeed, contributions must be controlled to ensure the effectiveness and relevance of the campaign. We are particularly interested in small, fast and not automatable tasks. Several methods have been proposed to solve this problem, but they are applicable when the "golden truth" is not always known. This work has the particularity to propose a method for calculating the degree of expertise in the presence of gold data in crowdsourcing. This method is based on the belief function theory and proposes a structuring of data using graphs. The proposed approach will be assessed and applied to the data.
Intrinsically Motivated Acquisition of Modular Slow Features for Humanoids in Continuous and Non-Stationary Environments
Venue: arXiv cs.AI 2017
Year: 2017

A compact information-rich representation of the environment, also called a feature abstraction, can simplify a robot's task of mapping its raw sensory inputs to useful action sequences. However, in environments that are non-stationary and only partially observable, a single abstraction is probably not sufficient to encode most variations. Therefore, learning multiple sets of spatially or temporally local, modular abstractions of the inputs would be beneficial. How can a robot learn these local abstractions without a teacher? More specifically, how can it decide from where and when to start learning a new abstraction? A recently proposed algorithm called Curious Dr. MISFA addresses this problem. The algorithm is based on two underlying learning principles called artificial curiosity and slowness. The former is used to make the robot self-motivated to explore by rewarding itself whenever it makes progress learning an abstraction; the later is used to update the abstraction by extracting slowly varying components from raw sensory inputs. Curious Dr. MISFA's application is, however, limited to discrete domains constrained by a pre-defined state space and has design limitations that make it unstable in certain situations. This paper presents a significant improvement that is applicable to continuous environments, is computationally less expensive, simpler to use with fewer hyper parameters, and stable in certain non-stationary environments. We demonstrate the efficacy and stability of our method in a vision-based robot simulator.
Blind Deconvolution with Additional Autocorrelations via Convex Programs
Venue: arXiv cs.IT 2017
Year: 2017

In this work we characterize all ambiguities of the linear (aperiodic) one-dimensional convolution on two fixed finite-dimensional complex vector spaces. It will be shown that the convolution ambiguities can be mapped one-to-one to factorization ambiguities in the $z-$domain, which are generated by swapping the zeros of the input signals. We use this polynomial description to show a deterministic version of a recently introduced masked Fourier phase retrieval design. In the noise-free case a (convex) semi-definite program can be used to recover exactly the input signals if they share no common factors (zeros). Then, we reformulate the problem as deterministic blind deconvolution with prior knowledge of the autocorrelations. Numerically simulations show that our approach is also robust against additive noise.
Faster Algorithms for Weighted Recursive State Machines
Venue: arXiv cs.PL 2017
Year: 2017

Pushdown systems (PDSs) and recursive state machines (RSMs), which are linearly equivalent, are standard models for interprocedural analysis. Yet RSMs are more convenient as they (a) explicitly model function calls and returns, and (b) specify many natural parameters for algorithmic analysis, e.g., the number of entries and exits. We consider a general framework where RSM transitions are labeled from a semiring and path properties are algebraic with semiring operations, which can model, e.g., interprocedural reachability and dataflow analysis problems. Our main contributions are new algorithms for several fundamental problems. As compared to a direct translation of RSMs to PDSs and the best-known existing bounds of PDSs, our analysis algorithm improves the complexity for finite-height semirings (that subsumes reachability and standard dataflow properties). We further consider the problem of extracting distance values from the representation structures computed by our algorithm, and give efficient algorithms that distinguish the complexity of a one-time preprocessing from the complexity of each individual query. Another advantage of our algorithm is that our improvements carry over to the concurrent setting, where we improve the best-known complexity for the context-bounded analysis of concurrent RSMs. Finally, we provide a prototype implementation that gives a significant speed-up on several benchmarks from the SLAM/SDV project.
Compression of Deep Neural Networks for Image Instance Retrieval
Venue: arXiv cs.CV 2017
Year: 2017

Image instance retrieval is the problem of retrieving images from a database which contain the same object. Convolutional Neural Network (CNN) based descriptors are becoming the dominant approach for generating {\it global image descriptors} for the instance retrieval problem. One major drawback of CNN-based {\it global descriptors} is that uncompressed deep neural network models require hundreds of megabytes of storage making them inconvenient to deploy in mobile applications or in custom hardware. In this work, we study the problem of neural network model compression focusing on the image instance retrieval task. We study quantization, coding, pruning and weight sharing techniques for reducing model size for the instance retrieval problem. We provide extensive experimental results on the trade-off between retrieval performance and model size for different types of networks on several data sets providing the most comprehensive study on this topic. We compress models to the order of a few MBs: two orders of magnitude smaller than the uncompressed models while achieving negligible loss in retrieval performance.