OpenRaiser/Intern-Atlas huggingface dataset:
Applicability of Partial Ternary Full Adder in Ternary Arithmetic Units
Venue: arXiv cs.AR 2019
Year: 2019

This paper explores whether or not a complete ternary full adder, whose input variables can independently be '0', '1', or '2', is indispensable in the arithmetic blocks of adder, subtractor, and multiplier. Our investigations show that none of the mentioned arithmetic units require a complete ternary full adder. Instead, they can be designed by use of partial ternary full adder, whose input carry never becomes '2'. Furthermore, some new ternary compressors are proposed in this paper without the requirement of complete ternary full adder. The usage of partial ternary full adder can help circuit designers to simplify their designs, especially in transistor level.
Characterizing the Integrality Gap of the Subtour LP for the Circulant Traveling Salesman Problem
Venue: arXiv cs.DS 2019
Year: 2019

We consider the integrality gap of the subtour LP relaxation of the Traveling Salesman Problem restricted to circulant instances. De Klerk and Dobre conjectured that the value of the optimal solution to the subtour LP on these instances is equal to an entirely combinatorial lower bound from Van der Veen, Van Dal, and Sierksma. We prove this conjecture by giving an explicit optimal solution to the subtour LP. We then use it to show that the integrality gap of the subtour LP is 2 on circulant instances, making such instances one of the few non-trivial classes of TSP instances for which the integrality gap of the subtour LP is exactly known. We also show that the degree constraints do not strengthen the subtour LP on circulant instances, mimicking the parsimonious property of metric, symmetric TSP instances shown in Goemans and Bertsimas in a distinctly non-metric set of instances.
Motion Equivariant Networks for Event Cameras with the Temporal Normalization Transform
Venue: arXiv cs.CV 2019
Year: 2019

In this work, we propose a novel transformation for events from an event camera that is equivariant to optical flow under convolutions in the 3-D spatiotemporal domain. Events are generated by changes in the image, which are typically due to motion, either of the camera or the scene. As a result, different motions result in a different set of events. For learning based tasks based on a static scene such as classification which directly use the events, we must either rely on the learning method to learn the underlying object distinct from the motion, or to memorize all possible motions for each object with extensive data augmentation. Instead, we propose a novel transformation of the input event data which normalizes the $x$ and $y$ positions by the timestamp of each event. We show that this transformation generates a representation of the events that is equivariant to this motion when the optical flow is constant, allowing a deep neural network to learn the classification task without the need for expensive data augmentation. We test our method on the event based N-MNIST dataset, as well as a novel dataset N-MOVING-MNIST, with significantly more variety in motion compared to the standard N-MNIST dataset. In all sequences, we demonstrate that our transformed network is able to achieve similar or better performance compared to a network with a standard volumetric event input, and performs significantly better when the test set has a larger set of motions than seen at training.
Predicting tongue motion in unlabeled ultrasound videos using convolutional LSTM neural network
Venue: arXiv cs.CV 2019
Year: 2019

A challenge in speech production research is to predict future tongue movements based on a short period of past tongue movements. This study tackles speaker-dependent tongue motion prediction problem in unlabeled ultrasound videos with convolutional long short-term memory (ConvLSTM) networks. The model has been tested on two different ultrasound corpora. ConvLSTM outperforms 3-dimensional convolutional neural network (3DCNN) in predicting the 9\textsuperscript{th} frames based on 8 preceding frames, and also demonstrates good capacity to predict only the tongue contours in future frames. Further tests reveal that ConvLSTM can also learn to predict tongue movements in more distant frames beyond the immediately following frames. Our codes are available at: https://github.com/shuiliwanwu/ConvLstm-ultrasound-videos.
Composing bidirectional programs monadically (with appendices)
Venue: arXiv cs.PL 2019
Year: 2019

Software frequently converts data from one representation to another and vice versa. Naively specifying both conversion directions separately is error prone and introduces conceptual duplication. Instead, bidirectional programming techniques allow programs to be written which can be interpreted in both directions. However, these techniques often employ unfamiliar programming idioms via restricted, specialised combinator libraries. Instead, we introduce a framework for composing bidirectional programs monadically, enabling bidirectional programming with familiar abstractions in functional languages such as Haskell. We demonstrate the generality of our approach applied to parsers/printers, lenses, and generators/predicates. We show how to leverage compositionality and equational reasoning for the verification of round-tripping properties for such monadic bidirectional programs.
Dynamical Privacy in Distributed Computing -- Part I: Privacy Loss and PPSC Mechanism
Venue: arXiv cs.SY 2019
Year: 2019

A distributed computing protocol consists of three components: (i) Data Localization: a network-wide dataset is decomposed into local datasets separately preserved at a network of nodes; (ii) Node Communication: the nodes hold individual dynamical states and communicate with the neighbors about these dynamical states; (iii) Local Computation: state recursions are computed at each individual node. Information about the local datasets enters the computation process through the node-to-node communication and the local computations, which may be leaked to dynamics eavesdroppers having access to global or local node states. In this paper, we systematically investigate this potential computational privacy risks in distributed computing protocols in the form of structured system identification, and then propose and thoroughly analyze a Privacy-Preserving-Summation-Consistent (PPSC) mechanism as a generic privacy encryption subroutine for consensus-based distributed computations. The central idea is that the consensus manifold is where we can both hide node privacy and achieve computational accuracy. In this first part of the paper, we demonstrate the computational privacy risks in distributed algorithms against dynamics eavesdroppers and particularly in distributed linear equation solvers, and then propose the PPSC mechanism and illustrate its usefulness.
Equivalence of finite-valued streaming string transducers is decidable
Venue: arXiv cs.FL 2019
Year: 2019

In this paper we provide a positive answer to a question left open by Alur and and Deshmukh in 2011 by showing that equivalence of finite-valued copyless streaming string transducers is decidable.
Hardness of Exact Distance Queries in Sparse Graphs Through Hub Labeling
Venue: arXiv cs.DS 2019
Year: 2019

A distance labeling scheme is an assignment of bit-labels to the vertices of an undirected, unweighted graph such that the distance between any pair of vertices can be decoded solely from their labels. An important class of distance labeling schemes is that of hub labelings, where a node $v \in G$ stores its distance to the so-called hubs $S_v \subseteq V$, chosen so that for any $u,v \in V$ there is $w \in S_u \cap S_v$ belonging to some shortest $uv$ path. Notice that for most existing graph classes, the best distance labelling constructions existing use at some point a hub labeling scheme at least as a key building block. Our interest lies in hub labelings of sparse graphs, i.e., those with $|E(G)| = O(n)$, for which we show a lowerbound of $\frac{n}{2^{O(\sqrt{\log n})}}$ for the average size of the hubsets. Additionally, we show a hub-labeling construction for sparse graphs of average size $O(\frac{n}{RS(n)^{c}})$ for some $0 < c < 1$, where $RS(n)$ is the so-called Ruzsa-Szemer{é}di function, linked to structure of induced matchings in dense graphs. This implies that further improving the lower bound on hub labeling size to $\frac{n}{2^{(\log n)^{o(1)}}}$ would require a breakthrough in the study of lower bounds on $RS(n)$, which have resisted substantial improvement in the last 70 years. For general distance labeling of sparse graphs, we show a lowerbound of $\frac{1}{2^{O(\sqrt{\log n})}} SumIndex(n)$, where $SumIndex(n)$ is the communication complexity of the Sum-Index problem over $Z_n$. Our results suggest that the best achievable hub-label size and distance-label size in sparse graphs may be $Θ(\frac{n}{2^{(\log n)^c}})$ for some $0<c < 1$.
Variational Regularized Transmission Refinement for Image Dehazing
Venue: arXiv cs.CV 2019
Year: 2019

High-quality dehazing performance is highly dependent upon the accurate estimation of transmission map. In this work, the coarse estimation version is first obtained by weightedly fusing two different transmission maps, which are generated from foreground and sky regions, respectively. A hybrid variational model with promoted regularization terms is then proposed to assisting in refining transmission map. The resulting complicated optimization problem is effectively solved via an alternating direction algorithm. The final haze-free image can be effectively obtained according to the refined transmission map and atmospheric scattering model. Our dehazing framework has the capacity of preserving important image details while suppressing undesirable artifacts, even for hazy images with large sky regions. Experiments on both synthetic and realistic images have illustrated that the proposed method is competitive with or even outperforms the state-of-the-art dehazing techniques under different imaging conditions.
Analysis and Detection of Information Types of Open Source Software Issue Discussions
Venue: arXiv cs.SE 2019
Year: 2019

Most modern Issue Tracking Systems (ITSs) for open source software (OSS) projects allow users to add comments to issues. Over time, these comments accumulate into discussion threads embedded with rich information about the software project, which can potentially satisfy the diverse needs of OSS stakeholders. However, discovering and retrieving relevant information from the discussion threads is a challenging task, especially when the discussions are lengthy and the number of issues in ITSs are vast. In this paper, we address this challenge by identifying the information types presented in OSS issue discussions. Through qualitative content analysis of 15 complex issue threads across three projects hosted on GitHub, we uncovered 16 information types and created a labeled corpus containing 4656 sentences. Our investigation of supervised, automated classification techniques indicated that, when prior knowledge about the issue is available, Random Forest can effectively detect most sentence types using conversational features such as the sentence length and its position. When classifying sentences from new issues, Logistic Regression can yield satisfactory performance using textual features for certain information types, while falling short on others. Our work represents a nontrivial first step towards tools and techniques for identifying and obtaining the rich information recorded in the ITSs to support various software engineering activities and to satisfy the diverse needs of OSS stakeholders.
Towards Edge-assisted Internet of Things: From Security and Efficiency Perspectives
Venue: arXiv cs.CR 2019
Year: 2019

As we are moving towards the Internet of Things (IoT) era, the number of connected physical devices is increasing at a rapid pace. Mobile edge computing is emerging to handle the sheer volume of produced data and reach the latency demand of computation-intensive IoT applications. Although the advance of mobile edge computing on service latency is studied solidly, security and efficiency on data usage in mobile edge computing have not been clearly identified. In this article, we examine the architecture of mobile edge computing and explore the potentials of utilizing mobile edge computing to enhance data analysis for IoT applications, while achieving data security and computational efficiency. Specifically, we first introduce the overall architecture and several promising edge-assisted IoT applications. We then study the security, privacy and efficiency challenges in data processing for mobile edge computing, and discuss the opportunities to enhance data security and improve computational efficiency with the assistance of edge computing, including secure data aggregation, secure data deduplication and secure computational offloading. Finally, several interesting directions on edge-empowered data analysis are presented for future research.
Cost-Sensitive Diagnosis and Learning Leveraging Public Health Data
Venue: arXiv cs.LG 2019
Year: 2019

Traditionally, machine learning algorithms rely on the assumption that all features of a given dataset are available for free. However, there are many concerns such as monetary data collection costs, patient discomfort in medical procedures, and privacy impacts of data collection that require careful consideration in any real-world health analytics system. An efficient solution would only acquire a subset of features based on the value it provides while considering acquisition costs. Moreover, datasets that provide feature costs are very limited, especially in healthcare. In this paper, we provide a health dataset as well as a method for assigning feature costs based on the total level of inconvenience asking for each feature entails. Furthermore, based on the suggested dataset, we provide a comparison of recent and state-of-the-art approaches to cost-sensitive feature acquisition and learning. Specifically, we analyze the performance of major sensitivity-based and reinforcement learning based methods in the literature on three different problems in the health domain, including diabetes, heart disease, and hypertension classification.
Few-Bit CSI Acquisition for Centralized Cell-Free Massive MIMO with Spatial Correlation
Venue: arXiv cs.IT 2019
Year: 2019

The availability and accuracy of Channel State Information (CSI) play a crucial role for coherent detection in almost every communication system. Particularly in the recently proposed cell-free massive MIMO system, in which a large number of distributed Access Points (APs) is connected to a Central processing Unit (CPU) for joint decoding, acquiring CSI at the CPU may improve performance through the use of detection algorithms such as minimum mean square error (MMSE) or zero forcing (ZF). There are also significant challenges, especially the increase in fronthaul load arising from the transfer of high precision CSI, with the resulting complexity and scalability issues. In this paper, we address these CSI acquisition problems by utilizing vector quantization with precision of only a few bits and we show that the accuracy of the channel estimate at the CPU can be increased by exploiting the spatial correlation subject to this limited fronthaul load. Further, we derive an estimator for the simple \emph{Quantize-and-Estimate} (QE) strategy based on the Bussgang theorem and compare its performance to \emph{Estimate-and-Quantize} (EQ) in terms of Mean Squared Error (MSE). Our simulation results indicate that the QE with few-bit vector quantization can outperform EQ and individual scalar quantization at moderate SNR for small numbers of bits per dimension.
Elementary-base cirquent calculus II: Choice quantifiers
Venue: arXiv cs.LO 2019
Year: 2019

Cirquent calculus is a novel proof theory permitting component-sharing between logical expressions. Using it, the predecessor article "Elementary-base cirquent calculus I: Parallel and choice connectives" built the sound and complete axiomatization CL16 of a propositional fragment of computability logic (see http://www.csc.villanova.edu/~japaridz/CL/ ). The atoms of the language of CL16 represent elementary, i.e., moveless, games, and the logical vocabulary consists of negation, parallel connectives and choice connectives. The present paper constructs the first-order version CL17 of CL16, also enjoying soundness and completeness. The language of CL17 augments that of CL18 by including choice quantifiers. Unlike classical predicate calculus, CL17 turns out to be decidable.
Interpolation of scattered data in $\mathbb{R}^3$ using minimum $L_p$-norm networks, $1<p<\infty$
Venue: arXiv cs.NA 2019
Year: 2019

We consider the extremal problem of interpolation of scattered data in $\mathbb{R}^3$ by smooth curve networks with minimal $L_p$-norm of the second derivative for $1<p<\infty$. The problem for $p=2$ was set and solved by Nielson (1983). Andersson et al. (1995) gave a new proof of Nielson's result by using a different approach. Partial results for the problem for $1<p<\infty$ were announced without proof in (Vlachkova (1992)). Here we present a complete characterization of the solution for $1<p<\infty$. Numerical experiments are visualized and presented to illustrate and support our results.
Semantic Neural Machine Translation using AMR
Venue: arXiv cs.CL 2019
Year: 2019

It is intuitive that semantic representations can be useful for machine translation, mainly because they can help in enforcing meaning preservation and handling data sparsity (many sentences correspond to one meaning) of machine translation models. On the other hand, little work has been done on leveraging semantics for neural machine translation (NMT). In this work, we study the usefulness of AMR (short for abstract meaning representation) on NMT. Experiments on a standard English-to-German dataset show that incorporating AMR as additional knowledge can significantly improve a strong attention-based sequence-to-sequence neural translation model.
Secure Distributed Dynamic State Estimation in Wide-Area Smart Grids
Venue: arXiv cs.CR 2019
Year: 2019

Smart grid is a large complex network with a myriad of vulnerabilities, usually operated in adversarial settings and regulated based on estimated system states. In this study, we propose a novel highly secure distributed dynamic state estimation mechanism for wide-area (multi-area) smart grids, composed of geographically separated subregions, each supervised by a local control center. We firstly propose a distributed state estimator assuming regular system operation, that achieves near-optimal performance based on the local Kalman filters and with the exchange of necessary information between local centers. To enhance the security, we further propose to (i) protect the network database and the network communication channels against attacks and data manipulations via a blockchain (BC)-based system design, where the BC operates on the peer-to-peer network of local centers, (ii) locally detect the measurement anomalies in real-time to eliminate their effects on the state estimation process, and (iii) detect misbehaving (hacked/faulty) local centers in real-time via a distributed trust management scheme over the network. We provide theoretical guarantees regarding the false alarm rates of the proposed detection schemes, where the false alarms can be easily controlled. Numerical studies illustrate that the proposed mechanism offers reliable state estimation under regular system operation, timely and accurate detection of anomalies, and good state recovery performance in case of anomalies.
A linear complexity analysis of quadratic residues and primitive roots spacings
Venue: arXiv cs.IT 2019
Year: 2019

We investigate the linear complexities of the periodic 0-1 infinite sequences in which the periods are the sequence of the parities of the spacings between quadratic residues modulo a prime p, and the sequence of the parities of the spacings between primitive roots modulo p, respectively. In either case, the Berlekamp-Massey algorithm running on MAPLE computer algebra software shows very good to perfect linear complexities.
Video Face Recognition: Component-wise Feature Aggregation Network (C-FAN)
Venue: arXiv cs.CV 2019
Year: 2019

We propose a new approach to video face recognition. Our component-wise feature aggregation network (C-FAN) accepts a set of face images of a subject as an input, and outputs a single feature vector as the face representation of the set for the recognition task. The whole network is trained in two steps: (i) train a base CNN for still image face recognition; (ii) add an aggregation module to the base network to learn the quality value for each feature component, which adaptively aggregates deep feature vectors into a single vector to represent the face in a video. C-FAN automatically learns to retain salient face features with high quality scores while suppressing features with low quality scores. The experimental results on three benchmark datasets, YouTube Faces, IJB-A, and IJB-S show that the proposed C-FAN network is capable of generating a compact feature vector with 512 dimensions for a video sequence by efficiently aggregating feature vectors of all the video frames to achieve state of the art performance.
Design and Performance Analysis of Secure Multicasting Cooperative Protocol for Wireless Sensor Network Applications
Venue: arXiv cs.CR 2019
Year: 2019

This paper proposes a new security cooperative protocol, for dual phase amplify-and-forward large wireless sensor networks. In such a network, a portion of the K relays can be potential eavesdroppers. The source agrees to share with the destination a given channel state information (CSI) of a source-trusted relay-destination link to encode the message. Then, in the first hop, the source will use this CSI to map the right message to a certain sector while transmitting fake messages to the other sectors using sectoral transmission thanks to analog beamforming. In the second hop, the relays retransmit their received signals to the destination, using the distributed beamforming technique. We derived the secrecy outage probability and demonstrated that the probability of receiving the right encoded information by an untrustworthy relay is inversely proportional to the number of sectors. We also showed that the aggressive behavior of the cooperating untrusted relays is not effective compared to the case where each untrusted relay is trying to intercept the transmitted message individually.
Analytic Model for Quadruped Locomotion Task-Space Planning
Venue: arXiv cs.RO 2019
Year: 2019

Despite the extensive presence of the legged locomotion in animals, it is extremely challenging to be reproduced with robots. Legged locomotion is an dynamic task which benefits from a planning that takes advantage of the gravitational pull on the system. However, the computational cost of such optimization rapidly increases with the complexity of kinematic structures, rendering impossible real-time deployment in unstructured environments. This paper proposes a simplified method that can generate desired centre of mass and feet trajectory for quadrupeds. The model describes a quadruped as two bipeds connected via their centres of mass, and it is based on the extension of an algebraic bipedal model that uses the topology of the gravitational attractor to describe bipedal locomotion strategies. The results show that the model generates trajectories that agrees with previous studies. The model will be deployed in the future as seed solution for whole-body trajectory optimization in the attempt to reduce the computational cost and obtain real-time planning of complex action in challenging environments.