OpenRaiser/Intern-Atlas huggingface dataset:
DeepWiTraffic: Low Cost WiFi-Based Traffic Monitoring System Using Deep Learning
Venue: arXiv cs.CY 2020
Year: 2020

A traffic monitoring system (TMS) is an integral part of Intelligent Transportation Systems (ITS). It is an essential tool for traffic analysis and planning. One of the biggest challenges is, however, the high cost especially in covering the huge rural road network. In this paper, we propose to address the problem by developing a novel TMS called DeepWiTraffic. DeepWiTraffic is a low-cost, portable, and non-intrusive solution that is built only with two WiFi transceivers. It exploits the unique WiFi Channel State Information (CSI) of passing vehicles to perform detection and classification of vehicles. Spatial and temporal correlations of CSI amplitude and phase data are identified and analyzed using a machine learning technique to classify vehicles into five different types: motorcycles, passenger vehicles, SUVs, pickup trucks, and large trucks. A large amount of CSI data and ground-truth video data are collected over a month period from a real-world two-lane rural roadway to validate the effectiveness of DeepWiTraffic. The results validate that DeepWiTraffic is an effective TMS with the average detection accuracy of 99.4% and the average classification accuracy of 91.1% in comparison with state-of-the-art non-intrusive TMSs.
Saturated control without velocity measurements for planar robots with flexible joints
Venue: arXiv cs.SY 2020
Year: 2020

In this work, we propose a passivity-based controller that addresses the problem of set point regulation for planar robots with two links and flexible joints. Moreover, the controller is saturated and does not require velocity measurements. Additionally, we present experiments that corroborate the theoretical results of this note.
On Order Types of Random Point Sets
Venue: arXiv cs.CG 2020
Year: 2020

A simple method to produce a random order type is to take the order type of a random point set. We conjecture that many probability distributions on order types defined in this way are heavily concentrated and therefore sample inefficiently the space of order types. We present two results on this question. First, we study experimentally the bias in the order types of $n$ random points chosen uniformly and independently in a square, for $n$ up to $16$. Second, we study algorithms for determining the order type of a point set in terms of the number of coordinate bits they require to know. We give an algorithm that requires on average $4n \log\_2 n+O(n)$ bits to determine the order type of $P$, and show that any algorithm requires at least $4n \log\_2 n - O(n \log\log n)$ bits. This implies that the concentration conjecture cannot be proven by an "efficient encoding" argument.
Deep Theory of Functional Connections: A New Method for Estimating the Solutions of PDEs
Venue: arXiv cs.NA 2020
Year: 2020

This article presents a new methodology called deep Theory of Functional Connections (TFC) that estimates the solutions of partial differential equations (PDEs) by combining neural networks with TFC. TFC is used to transform PDEs with boundary conditions into unconstrained optimization problems by embedding the boundary conditions into a "constrained expression." In this work, a neural network is chosen as the free function, and used to solve the now unconstrained optimization problem. The loss function is taken as the square of the residual of the PDE. Then, the neural network is trained in an unsupervised manner to solve the unconstrained optimization problem. This methodology has two major differences when compared with popular methods used to estimate the solutions of PDEs. First, this methodology does not need to discretize the domain into a grid, rather, this methodology randomly samples points from the domain during the training phase. Second, after training, this methodology represents a closed form, analytical, differentiable approximation of the solution throughout the entire training domain. In contrast, other popular methods require interpolation if the estimated solution is desired at points that do not lie on the discretized grid. The deep TFC method for estimating the solution of PDEs is demonstrated on four problems with a variety of boundary conditions.
Exploiting non-orthogonal multiple access in downlink coordinated multipoint transmission with the presence of imperfect channel state information
Venue: arXiv cs.IT 2020
Year: 2020

In this paper, the impact of imperfect channel state information (CSI) on a downlink coordinated multipoint (CoMP) transmission system with non-orthogonal multiple access (NOMA) is investigated since perfect knowledge of a channel can not be guaranteed in practice. Furthermore, the channel estimation error is applied to estimate the channel information wherein its priori of variance is assumed to be known. The impact of the number of coordinated base stations (BSs) on downlink CoMP NOMA is investigated. Users are classified into one of two groups according to their position within the cell, namely cell-center user (CCU) and cell-edge user (CEU). In this paper, ergodic capacity and sum capacity for both CCU and CEU are derived as closed form. In addition, various experiments are conducted with different parameters such as SNR, error variance, and power allocation to show their impact on the CoMP method. The results show that CoMP NOMA outperforms the CoMP orthogonal multiple access (OMA) wherein the condition of the channel impacts the performance of CoMP NOMA less. It is worth noting that a higher number of coordinated BSs enhances the total capacity of CoMP NOMA. Finally, the performance analysis is validated due to the close accordance between the analytical and simulation results.
The K-User DM Broadcast Channel with Two Groupcast Messages: Achievable Rate Regions and the Combination Network as a Case Study
Venue: arXiv cs.IT 2020
Year: 2020

A novel class of achievable rate regions is obtained for the K-receiver broadcast channel with two groupcast messages. The associated achievability schemes are parameterized by an expansion of the message set which then determines how random coding techniques are employed, which include generalized versions of {\em up-set} message-splitting, the generation of possibly multiple auxiliary codebooks for certain compositions of split messages using superposition coding, partial interference decoding at all receivers, and joint unique and non-unique decoding. New capacity results are established for certain partially ordered classes of general broadcast channels for certain two non-nested messages. Moreover, when specialized to the combination network (CN), some of the inner bounds are shown, via converse results, to result in the capacity region for (a) the two messages intended for two sets of K-1 receivers each and (b) two nested messages in which one message is intended for one or (c) two (common) receivers. In the latter two cases, we hence recover previous results by Bidokhti et al obtained therein using network coding schemes based on rate-splitting and linear superposition coding. Furthermore, we show the achievability of rate pairs in two examples of CNs, with three and four common receivers each, used in the previous literature to show the sub-optimality of rate-splitting and linear superposition coding, and to motivate a pre-encoding technique and a block-Markov linear superposition coding for the CN, with the latter then lifted to the general broadcast channel. Our results suggest that the proposed framework here, when specialized to the CN, is strong enough to incorporate the enhancements afforded by those two latter techniques, thereby suggesting among other things, that perhaps block-Markov superposition coding is not necessary for the general broadcast channel.
Eyes on the Prize: Improved Biological Surface Registration via Forward Propagation
Venue: arXiv cs.GR 2020
Year: 2020

Many algorithms for surface registration risk producing significant errors if surfaces are significantly nonisometric. Manifold learning has been shown to be effective at improving registration quality, using information from an entire collection of surfaces to correct issues present in pairwise registrations. These methods, however, are not robust to changes in the collection of surfaces, or do not produce accurate registrations at a resolution high enough for subsequent downstream analysis. We propose a novel algorithm for efficiently registering such collections given initial correspondences with varying degrees of accuracy. By combining the initial information with recent developments in manifold learning, we employ a simple metric condition to construct a measure on the space of correspondences between any pair of shapes in our collection, which we then use to distill soft correspondences. We demonstrate that this measure can improve correspondence accuracy between feature points compared to currently employed, less robust methods on a diverse dataset of surfaces from evolutionary biology. We then show how our methods can be used, in combination with recent sampling and interpolation methods, to compute accurate and consistent homeomorphisms between surfaces.
Diffusion multi-rate LMS algorithm for acoustic sensor networks
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, we present a diffusion multi-rate least-mean-square (LMS) algorithm, named DMLMS, which is an effective solution for distributed estimation when two or more observation sequences are available with different sampling rates. Then, we focus on a more practical application in the wireless acoustic sensor networks (ASN). The filtered-x LMS (FxLMS) algorithm is extended to the distributed multi-rate system and it introduces collaboration between nodes following a diffusion strategy. Simulation results show that the effectiveness of the proposed algorithms.
Actor Conditioned Attention Maps for Video Action Detection
Venue: arXiv cs.CV 2020
Year: 2020

While observing complex events with multiple actors, humans do not assess each actor separately, but infer from the context. The surrounding context provides essential information for understanding actions. To this end, we propose to replace region of interest(RoI) pooling with an attention module, which ranks each spatio-temporal region's relevance to a detected actor instead of cropping. We refer to these as Actor-Conditioned Attention Maps (ACAM), which amplify/dampen the features extracted from the entire scene. The resulting actor-conditioned features focus the model on regions that are relevant to the conditioned actor. For actor localization, we leverage pre-trained object detectors, which transfer better. The proposed model is efficient and our action detection pipeline achieves near real-time performance. Experimental results on AVA 2.1 and JHMDB demonstrate the effectiveness of attention maps, with improvements of 7 mAP on AVA and 4 mAP on JHMDB.
Building a Sybil-Resilient Digital Community Utilizing Trust-Graph Connectivity
Venue: arXiv cs.SI 2020
Year: 2020

Preventing fake or duplicate digital identities (aka sybils) from joining a digital community may be crucial to its survival, especially if it utilizes a consensus protocol among its members or employs democratic governance, where sybils can undermine consensus, tilt decisions, or even take over. Here, we explore the use of a trust-graph of identities, with edges representing trust among identity owners, to allow a community to grow indefinitely without increasing its sybil penetration. Since identities are admitted to the digital community based on their trust by existing digital community members, corrupt identities, which may trust sybils, also pose a threat to the digital community. Sybils and their corrupt perpetrators are together referred to as byzantines, and the overarching aim is to limit their penetration into a digital community. We propose two alternative tools to achieve this goal. One is graph conductance, which works under the assumption that honest people are averse to corrupt ones and tend to distrust them. The second is vertex expansion, which relies on the assumption that there are not too many corrupt identities in the community. Of particular interest is keeping the fraction of byzantines below one third, as it would allow the use of Byzantine Agreement [15] for consensus as well as for sybil-resilient social choice [19]. This paper considers incrementally growing a trust graph and shows that, under its key assumptions and additional requirements, including keeping the conductance or vertex expansion of the community trust graph sufficiently high, a community may grow safely, indefinitely.
The Arbitrarily Varying Channel with Colored Gaussian Noise
Venue: arXiv cs.IT 2020
Year: 2020

We address the arbitrarily varying channel (AVC) with colored Gaussian noise. The work consists of three parts. First, we study the general discrete AVC with fixed parameters, where the channel depends on two state sequences, one arbitrary and the other fixed and known. This model can be viewed as a combination of the AVC and the time-varying channel. We determine both the deterministic code capacity and the random code capacity. Super-additivity is demonstrated, showing that the deterministic code capacity can be strictly larger than the weighted sum of the parametric capacities. In the second part, we consider the arbitrarily varying Gaussian product channel (AVGPC). Hughes and Narayan characterized the random code capacity through min-max optimization leading to a "double" water filling solution. Here, we establish the deterministic code capacity and also discuss the game-theoretic meaning and the connection between double water filling and Nash equilibrium. As in the case of the standard Gaussian AVC, the deterministic code capacity is discontinuous in the input constraint, and depends on which of the input or state constraint is higher. As opposed to Shannon's classic water filling solution, it is observed that deterministic coding using independent scalar codes is suboptimal for the AVGPC. Finally, we establish the capacity of the AVC with colored Gaussian noise, where double water filling is performed in the frequency domain. The analysis relies on our preceding results, on the AVC with fixed parameters and the AVGPC.
A New Approach to Multi-Party Peer-to-Peer Communication Complexity
Venue: arXiv cs.CC 2020
Year: 2020

We introduce new models and new information theoretic measures for the study of communication complexity in the natural peer-to-peer, multi-party, number-in-hand setting. We prove a number of properties of our new models and measures, and then, in order to exemplify their effectiveness, we use them to prove two lower bounds. The more elaborate one is a tight lower bound of $Ω(kn)$ on the multi-party peer-to-peer randomized communication complexity of the $k$-player, $n$-bit Disjointness function. The other one is a tight lower bound of $Ω(kn)$ on the multi-party peer-to-peer randomized communication complexity of the $k$-player, $n$-bit bitwise parity function. Both lower bounds hold when ${n=Ω(k)}$. The lower bound for Disjointness improves over the lower bound that can be inferred from the result of Braverman et al.~(FOCS 2013), which was proved in the coordinator model and can yield a lower bound of $Ω(kn/\log k)$ in the peer-to-peer model. To the best of our knowledge, our lower bounds are the first tight (non-trivial)lower bounds on communication complexity in the natural {\em peer-to-peer} multi-party setting. In addition to the above results for communication complexity, we also prove, using the same tools, an $Ω(n)$ lower bound on the number of random bits necessary for the (information theoretic) private computation of the $k$-player, $n$-bit Disjointness function .
Differentially Private ADMM for Distributed Medical Machine Learning
Venue: arXiv cs.LG 2020
Year: 2020

Due to massive amounts of data distributed across multiple locations, distributed machine learning has attracted a lot of research interests. Alternating Direction Method of Multipliers (ADMM) is a powerful method of designing distributed machine learning algorithm, whereby each agent computes over local datasets and exchanges computation results with its neighbor agents in an iterative procedure. There exists significant privacy leakage during this iterative process if the local data is sensitive. In this paper, we propose a differentially private ADMM algorithm (P-ADMM) to provide dynamic zero-concentrated differential privacy (dynamic zCDP), by inserting Gaussian noise with linearly decaying variance. We prove that P-ADMM has the same convergence rate compared to the non-private counterpart, i.e., $\mathcal{O}(1/K)$ with $K$ being the number of iterations and linear convergence for general convex and strongly convex problems while providing differentially private guarantee. Moreover, through our experiments performed on real-world datasets, we empirically show that P-ADMM has the best-known performance among the existing differentially private ADMM based algorithms.
Interpretable CNNs for Object Classification
Venue: arXiv cs.LG 2020
Year: 2020

This paper proposes a generic method to learn interpretable convolutional filters in a deep convolutional neural network (CNN) for object classification, where each interpretable filter encodes features of a specific object part. Our method does not require additional annotations of object parts or textures for supervision. Instead, we use the same training data as traditional CNNs. Our method automatically assigns each interpretable filter in a high conv-layer with an object part of a certain category during the learning process. Such explicit knowledge representations in conv-layers of CNN help people clarify the logic encoded in the CNN, i.e., answering what patterns the CNN extracts from an input image and uses for prediction. We have tested our method using different benchmark CNNs with various structures to demonstrate the broad applicability of our method. Experiments have shown that our interpretable filters are much more semantically meaningful than traditional filters.
Secure list decoding
Venue: arXiv cs.IT 2020
Year: 2020

We propose a new concept of secure list decoding. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions. The first additional security condition is the impossibility of the correct decoding, i.e., the receiver cannot uniquely identify the transmitted message even though the transmitted message is contained in the list. This condition can be trivially satisfied when the transmission rate is larger than the channel capacity. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. This protocol can be used for anonymous auction, which realizes the anonymity for bidding.
Humanoid: A Deep Learning-based Approach to Automated Black-box Android App Testing
Venue: arXiv cs.SE 2020
Year: 2020

Automated input generators are widely used for large-scale dynamic analysis of mobile apps. Such input generators must constantly choose which UI element to interact with and how to interact with it, in order to achieve high coverage with a limited time budget. Currently, most input generators adopt pseudo-random or brute-force searching strategies, which may take very long to find the correct combination of inputs that can drive the app into new and important states. In this paper, we propose Humanoid, a deep learning-based approach to GUI test input generation by learning from human interactions. Our insight is that if we can learn from human-generated interaction traces, it is possible to automatically prioritize test inputs based on their importance as perceived by users. We design and implement a deep neural network model to learn how end-users would interact with an app (specifically, which UI elements to interact with and how). Our experiments showed that the interaction model can successfully prioritize user-preferred inputs for any new UI (with a top-1 accuracy of 51.2% and a top-10 accuracy of 85.2%). We implemented an input generator for Android apps based on the learned model and evaluated it on both open-source apps and market apps. The results indicated that Humanoid was able to achieve higher coverage than six state-of-the-art test generators. However, further analysis showed that the learned model was not the main reason of coverage improvement. Although the learned interaction pattern could drive the app into some important GUI states with higher probabilities, it had limited effect on the width and depth of GUI state search, which is the key to improve test coverage in the long term. Whether and how human interaction patterns can be used to improve coverage is still an unknown and challenging problem.
A Deterministic Algorithm for the Capacity of Finite-State Channels
Venue: arXiv cs.IT 2020
Year: 2020

We propose two modified versions of the classical gradient ascent method to compute the capacity of finite-state channels with Markovian inputs. For the case that the channel mutual information is strongly concave in a parameter taking values in a compact convex subset of some Euclidean space, our first algorithm proves to achieve polynomial accuracy in polynomial time and, moreover, for some special families of finite-state channels our algorithm can achieve exponential accuracy in polynomial time under some technical conditions. For the case that the channel mutual information may not be strongly concave, our second algorithm proves to be at least locally convergent.
Entropy Bounds for Grammar-Based Tree Compressors
Venue: arXiv cs.DS 2020
Year: 2020

The definition of $k^{th}$-order empirical entropy of strings is extended to node labelled binary trees. A suitable binary encoding of tree straight-line programs (that have been used for grammar-based tree compression before) is shown to yield binary tree encodings of size bounded by the $k^{th}$-order empirical entropy plus some lower order terms. This generalizes recent results for grammar-based string compression to grammar-based tree compression.
Integrating Blocking and Non-Blocking MPI Primitives with Task-Based Programming Models
Venue: arXiv cs.DC 2020
Year: 2020

In this paper we present the Task-Aware MPI library (TAMPI) that integrates both blocking and non-blocking MPI primitives with task-based programming models. The TAMPI library leverages two new runtime APIs to improve both programmability and performance of hybrid applications. The first API allows to pause and resume the execution of a task depending on external events. This API is used to improve the interoperability between blocking MPI communication primitives and tasks. When an MPI operation executed inside a task blocks, the task running is paused so that the runtime system can schedule a new task on the core that became idle. Once the blocked MPI operation is completed, the paused task is put again on the runtime system's ready queue, so eventually it will be scheduled again and its execution will be resumed. The second API defers the release of dependencies associated with a task completion until some external events are fulfilled. This API is composed only of two functions, one to bind external events to a running task and another function to notify about the completion of external events previously bound. TAMPI leverages this API to bind non-blocking MPI operations with tasks, deferring the release of their task dependencies until both task execution and all its bound MPI operations are completed. Our experiments reveal that the enhanced features of TAMPI not only simplify the development of hybrid MPI+OpenMP applications that use blocking or non-blocking MPI primitives but they also naturally overlap computation and communication phases, which improves application performance and scalability by removing artificial dependencies across communication tasks.