OpenRaiser/Intern-Atlas huggingface dataset:
Accelerating 3D Deep Learning with PyTorch3D
Venue: arXiv cs.CV 2020
Year: 2020

Deep learning has significantly improved 2D image recognition. Extending into 3D may advance many new applications including autonomous vehicles, virtual and augmented reality, authoring 3D content, and even improving 2D recognition. However despite growing interest, 3D deep learning remains relatively underexplored. We believe that some of this disparity is due to the engineering challenges involved in 3D deep learning, such as efficiently processing heterogeneous data and reframing graphics operations to be differentiable. We address these challenges by introducing PyTorch3D, a library of modular, efficient, and differentiable operators for 3D deep learning. It includes a fast, modular differentiable renderer for meshes and point clouds, enabling analysis-by-synthesis approaches. Compared with other differentiable renderers, PyTorch3D is more modular and efficient, allowing users to more easily extend it while also gracefully scaling to large meshes and images. We compare the PyTorch3D operators and renderer with other implementations and demonstrate significant speed and memory improvements. We also use PyTorch3D to improve the state-of-the-art for unsupervised 3D mesh and point cloud prediction from 2D images on ShapeNet. PyTorch3D is open-source and we hope it will help accelerate research in 3D deep learning.
Accelerating Robustness Verification of Deep Neural Networks Guided by Target Labels
Venue: arXiv cs.LG 2020
Year: 2020

Deep Neural Networks (DNNs) have become key components of many safety-critical applications such as autonomous driving and medical diagnosis. However, DNNs have been shown suffering from poor robustness because of their susceptibility to adversarial examples such that small perturbations to an input result in misprediction. Addressing to this concern, various approaches have been proposed to formally verify the robustness of DNNs. Most of these approaches reduce the verification problem to optimization problems of searching an adversarial example for a given input so that it is not correctly classified to the original label. However, they are limited in accuracy and scalability. In this paper, we propose a novel approach that can accelerate the robustness verification techniques by guiding the verification with target labels. The key insight of our approach is that the robustness verification problem of DNNs can be solved by verifying sub-problems of DNNs, one per target label. Fixing the target label during verification can drastically reduce the search space and thus improve the efficiency. We also propose an approach by leveraging symbolic interval propagation and linear relaxation techniques to sort the target labels in terms of chances that adversarial examples exist. This often allows us to quickly falsify the robustness of DNNs and the verification for remaining target labels could be avoided. Our approach is orthogonal to, and can be integrated with, many existing verification techniques. For evaluation purposes, we integrate it with three recent promising DNN verification tools, i.e., MipVerify, DeepZ, and Neurify. Experimental results show that our approach can significantly improve these tools by 36X speedup when the perturbation distance is set in a reasonable range.
A Smoothed Analysis of Online Lasso for the Sparse Linear Contextual Bandit Problem
Venue: arXiv cs.LG 2020
Year: 2020

We investigate the sparse linear contextual bandit problem where the parameter $θ$ is sparse. To relieve the sampling inefficiency, we utilize the "perturbed adversary" where the context is generated adversarilly but with small random non-adaptive perturbations. We prove that the simple online Lasso supports sparse linear contextual bandit with regret bound $\mathcal{O}(\sqrt{kT\log d})$ even when $d \gg T$ where $k$ and $d$ are the number of effective and ambient dimension, respectively. Compared to the recent work from Sivakumar et al. (2020), our analysis does not rely on the precondition processing, adaptive perturbation (the adaptive perturbation violates the i.i.d perturbation setting) or truncation on the error set. Moreover, the special structures in our results explicitly characterize how the perturbation affects exploration length, guide the design of perturbation together with the fundamental performance limit of perturbation method. Numerical experiments are provided to complement the theoretical analysis.
Planar Distance Oracles with Better Time-Space Tradeoffs
Venue: arXiv cs.DS 2020
Year: 2020

In a recent breakthrough, Charalampopoulos, Gawrychowski, Mozes, and Weimann (STOC 2019) showed that exact distance queries on planar graphs could be answered in $n^{o(1)}$ time by a data structure occupying $n^{1+o(1)}$ space, i.e., up to $o(1)$ terms, optimal exponents in time (0) and space (1) can be achieved simultaneously. Their distance query algorithm is recursive: it makes successive calls to a point-location algorithm for planar Voronoi diagrams, which involves many recursive distance queries. The depth of this recursion is non-constant and the branching factor logarithmic, leading to $(\log n)^{ω(1)} = n^{o(1)}$ query times. In this paper we present a new way to do point-location in planar Voronoi diagrams, which leads to a new exact distance oracle. At the two extremes of our space-time tradeoff curve we can achieve either $n^{1+o(1)}$ space and $\log^{2+o(1)}n$ query time, or $n\log^{2+o(1)}n$ space and $n^{o(1)}$ query time. All previous oracles with $\tilde{O}(1)$ query time occupy space $n^{1+Ω(1)}$, and all previous oracles with space $\tilde{O}(n)$ answer queries in $n^{Ω(1)}$ time.
A Blockchain-based Iterative Double Auction Protocol using Multiparty State Channels
Venue: arXiv cs.CR 2020
Year: 2020

Although the iterative double auction has been widely used in many different applications, one of the major problems in its current implementations is that they rely on a trusted third party to handle the auction process. This imposes the risk of single point of failures, monopoly, and bribery. In this paper, we aim to tackle this problem by proposing a novel decentralized and trustless framework for iterative double auction based on blockchain. Our design adopts the smart contract and state channel technologies to enable a double auction process among parties that do not need to trust each other, while minimizing the blockchain transactions. In specific, we propose an extension to the original concept of state channels that can support multiparty computation. Then we provide a formal development of the proposed framework and prove the security of our design against adversaries. Finally, we develop a proof-of-concept implementation of our framework using Elixir and Solidity, on which we conduct various experiments to demonstrate its feasibility and practicality.
Modal Logics with Composition on Finite Forests: Expressivity and Complexity (Extra Material)
Venue: arXiv cs.LO 2020
Year: 2020

We investigate the expressivity and computational complexity of two modal logics on finite forests equipped with operators to reason on submodels. The logic ML(|) extends the basic modal logic ML with the composition operator | from static ambient logic, whereas ML(*) contains the separating conjunction * from separation logic. Though both operators are second-order in nature, we show that ML(|) is as expressive as the graded modal logic GML (on finite trees) whereas ML(*) lies strictly between ML and GML. Moreover, we establish that the satisfiability problem for ML(*) is Tower-complete, whereas for ML(|) is (only) AExpPol-complete. As a by-product, we solve several open problems related to sister logics, such as static ambient logic, modal separation logic, and second-order modal logic on finite trees.
Outage Analysis in SWIPT Enabled Cooperative AF/DF Relay Assisted Two-Way Spectrum Sharing Communication
Venue: arXiv cs.IT 2020
Year: 2020

This paper reports relative performance of decode-and-forward (DF) and amplify-and-forward (AF) relaying in a multi-antenna cooperative cognitive radio network (CCRN) that supports device-to-device (D2D) communications using spectrum sharing technique in cellular network. In this work, cellular system is considered as primary and internet of things devices (IoDs), engaged in D2D communications, are considered to be secondary system. The devices access the licensed spectrum by means of the cooperation in two-way primary communications. Furthermore, IoDs are energized by harvesting the energy from radio frequency (RF) signals, using simultaneous wireless information and power transfer (SWIPT) protocol. Closed form expressions of outage probability for both cellular and D2D communications are derived and the impact of various design parameters for both AF and DF relaying techniques are studied. Based on the simulation results, it is found that the proposed spectrum sharing protocol, for both DF relaying and AF relaying schemes, outperform another similar network architecture in terms of spectrum efficiency. It is also observed that the performance of the proposed system using DF relaying is better than AF relaying scheme in terms of energy efficiency at same transmit power.
Revisiting Strategic Cyberwar Theory Reaching Decisive Strategic Outcome
Venue: arXiv cs.CY 2020
Year: 2020

Each strategy has a foundation, an overarching way of explaining why things are the way we see them and how to successfully reach our goals. Therefore, strategy is theory based because theory provides an intellectual framework for predicting outcomes leading to the end goal the strategy pursues. This article will present a theory, strategic cyberwar theory, that states that the utility of strategic cyberwar is tied to the likelihood of institutional instability in the targeted nation. In an ideal scenario, the cyber attacks are systematically attacking the targeted adversary institutions triggering the dormant entropy embedded in a nation with weak institutions. This will lead to submission to foreign policy and intent. The current alternative to strategic cyberwar theory is to unsystematically attack the adversary with cyber attacks where exploitation opportunities occur, which is likely to degrade parts of the information infrastructure, but it will not reach any strategic goals. If an adversarial society is unaffected by a cyber conflict, the conflict itself has not reached a decisive outcome, and results only in tit for tat game or stalemate. In strategic cyberwar theory1, the concept is to cyber attack the core of the institutional framework of the adversarial nation in pursuit of destabilization.
Explainable Deep Learning for Uncovering Actionable Scientific Insights for Materials Discovery and Design
Venue: arXiv cs.LG 2020
Year: 2020

The scientific community has been increasingly interested in harnessing the power of deep learning to solve various domain challenges. However, despite the effectiveness in building predictive models, fundamental challenges exist in extracting actionable knowledge from deep neural networks due to their opaque nature. In this work, we propose techniques for exploring the behavior of deep learning models by injecting domain-specific actionable attributes as tunable "knobs" in the analysis pipeline. By incorporating the domain knowledge in a generative modeling framework, we are not only able to better understand the behavior of these black-box models, but also provide scientists with actionable insights that can potentially lead to fundamental discoveries.
Evaluating Community Detection Algorithms for Progressively Evolving Graphs
Venue: arXiv cs.SI 2020
Year: 2020

Many algorithms have been proposed in the last ten years for the discovery of dynamic communities. However, these methods are seldom compared between themselves. In this article, we propose a generator of dynamic graphs with planted evolving community structure, as a benchmark to compare and evaluate such algorithms. Unlike previously proposed benchmarks, it is able to specify any desired evolving community structure through a descriptive language, and then to generate the corresponding progressively evolving network. We empirically evaluate six existing algorithms for dynamic community detection in terms of instantaneous and longitudinal similarity with the planted ground truth, smoothness of dynamic partitions, and scalability. We notably observe different types of weaknesses depending on their approach to ensure smoothness, namely Glitches, Oversimplification and Identity loss. Although no method arises as a clear winner, we observe clear differences between methods, and we identified the fastest, those yielding the most smoothed or the most accurate solutions at each step.
Descriptive Set Theory and $ω$-Powers of Finitary Languages
Venue: arXiv cs.LO 2020
Year: 2020

The $ω$-power of a finitary language L over a finite alphabet $Σ$ is the language of infinite words over $Σ$ defined by L $\infty$ := {w 0 w 1. .. $\in$ $Σ$ $ω$ | $\forall$i $\in$ $ω$ w i $\in$ L}. The $ω$-powers appear very naturally in Theoretical Computer Science in the characterization of several classes of languages of infinite words accepted by various kinds of automata, like B{ü}chi automata or B{ü}chi pushdown automata. We survey some recent results about the links relating Descriptive Set Theory and $ω$-powers.
Graph Neural Networks for Node-Level Predictions
Venue: arXiv cs.LG 2020
Year: 2020

The success of deep learning has revolutionized many fields of research including areas of computer vision, text and speech processing. Enormous research efforts have led to numerous methods that are capable of efficiently analyzing data, especially in the Euclidean space. However, many problems are posed in non-Euclidean domains modeled as general graphs with complex connection patterns. Increased problem complexity and computational power constraints have limited early approaches to static and small-sized graphs. In recent years, a rising interest in machine learning on graph-structured data has been accompanied by improved methods that overcome the limitations of their predecessors. These methods paved the way for dealing with large-scale and time-dynamic graphs. This work aims to provide an overview of early and modern graph neural network based machine learning methods for node-level prediction tasks. Under the umbrella of taxonomies already established in the literature, we explain the core concepts and provide detailed explanations for convolutional methods that have had strong impact. In addition, we introduce common benchmarks and present selected applications from various areas. Finally, we discuss open problems for further research.
Spin-Hall MTJ Cells for Intra-Column Competition in Hierarchical Temporal Memory
Venue: arXiv cs.ET 2020
Year: 2020

We propose a dedicated winner-take-all circuit to efficiently implement the intra-column competition between cells in Hierarchical Temporal Memory which is a crucial part of the algorithm. All inputs and outputs are charge-based for compatibility with standard CMOS. The circuit incorporates memristors for competitive advantage to emulate a column with a cell in a predictive state. The circuit can also detect columns 'bursting' by passive averaging and comparison of the cell outputs. The proposed spintronic devices and circuit are thoroughly described and a series of simulations are used to predict the performance. The simulations indicate that the circuit can complete a nine-cell, nine-input competition operation in under 15 ns at a cost of about 25 pJ.
Anisotropic Mesh Adaptation for Image Segmentation Based on Mumford-Shah Functional
Venue: arXiv cs.CV 2020
Year: 2020

As the resolution of digital images increase significantly, the processing of images becomes more challenging in terms of accuracy and efficiency. In this paper, we consider image segmentation by solving a partial differentiation equation (PDE) model based on the Mumford-Shah functional. We develop a new algorithm by combining anisotropic mesh adaptation for image representation and finite element method for solving the PDE model. Comparing to traditional algorithms solved by finite difference method, our algorithm provides faster and better results without the need to resizing the images to lower quality. We also extend the algorithm to segment images with multiple regions.
PThammer: Cross-User-Kernel-Boundary Rowhammer through Implicit Accesses
Venue: arXiv cs.CR 2020
Year: 2020

Rowhammer is a hardware vulnerability in DRAM memory, where repeated access to memory can induce bit flips in neighboring memory locations. Being a hardware vulnerability, rowhammer bypasses all of the system memory protection, allowing adversaries to compromise the integrity and confidentiality of data. Rowhammer attacks have shown to enable privilege escalation, sandbox escape, and cryptographic key disclosures. Recently, several proposals suggest exploiting the spatial proximity between the accessed memory location and the location of the bit flip for a defense against rowhammer. These all aim to deny the attacker's permission to access memory locations near sensitive data. In this paper, we question the core assumption underlying these defenses. We present PThammer, a confused-deputy attack that causes accesses to memory locations that the attacker is not allowed to access. Specifically, PThammer exploits the address translation process of modern processors, inducing the processor to generate frequent accesses to protected memory locations. We implement PThammer, demonstrating that it is a viable attack, resulting in a system compromise (e.g., kernel privilege escalation). We further evaluate the effectiveness of proposed software-only defenses showing that PThammer can overcome those.
Scalable Methods for Calculating Term Co-Occurrence Frequencies
Venue: arXiv cs.IR 2020
Year: 2020

Search techniques make use of elementary information such as term frequencies and document lengths in computation of similarity weighting. They can also exploit richer statistics, in particular the number of documents in which any two terms co-occur. In this paper we propose alternative methods for computing this statistic, a challenging task because the number of distinct pairs of terms is vast -- around 100,000 in a typical 1000-word news article, for example. In contrast, we do not employ approximation algorithms, as we want to be able to find exact counts. We explore their efficiency, finding that a naïve approach based on a dictionary is indeed very slow, while methods based on a combination of inverted indexes and linear scanning provide both massive speed-ups and better observed asymptotic behaviour. Our careful implementation shows that, with our novel list-pairs approach it is possible to process over several hundred thousand documents per hour.
Augmented Understanding and Automated Adaptation of Curation Rules
Venue: arXiv cs.IR 2020
Year: 2020

Over the past years, there has been many efforts to curate and increase the added value of the raw data. Data curation has been defined as activities and processes an analyst undertakes to transform the raw data into contextualized data and knowledge. Data curation enables decision-makers and data analyst to extract value and derive insight from the raw data. However, to curate the raw data, an analyst needs to carry out various curation tasks including, extraction linking, classification, and indexing, which are error-prone, tedious and challenging. Besides, deriving insight require analysts to spend a long period of time to scan and analyze the curation environments. This problem is exacerbated when the curation environment is large, and the analyst needs to curate a varied and comprehensive list of data. To address these challenges, in this dissertation, we present techniques, algorithms and systems for augmenting analysts in curation tasks. We propose: ~(1) a feature-based and automated technique for curating the raw data. ~(2) We propose an autonomic approach for adapting data curation rules. ~(3) We provide a solution to augment users in formulating their preferences while curating data in large scale information spaces. ~(4) We implement a set of APIs for automating the basic curation tasks, including Named Entity extraction, POS tags, classification, and etc.
Task-oriented Motion Mapping on Robots of Various Configuration using Body Role Division
Venue: arXiv cs.RO 2020
Year: 2020

Many works in robot teaching either focus only on teaching task knowledge, such as geometric constraints, or motion knowledge, such as the motion for accomplishing a task. However, to effectively teach a complex task sequence to a robot, it is important to take advantage of both task and motion knowledge. The task knowledge provides the goals of each individual task within the sequence and reduces the number of required human demonstrations, whereas the motion knowledge contain the task-to-task constraints that would otherwise require expert knowledge to model the problem. In this paper, we propose a body role division approach that combines both types of knowledge using a single human demonstration. The method is inspired by facts on human body motion and uses a body structural analogy to decompose a robot's body configuration into different roles: body parts that are dominant for imitating the human motion and body parts that are substitutional for adjusting the imitation with respect to the task knowledge. Our results show that our method scales to robots of different number of arm links, guides a robot's configuration to one that achieves an upcoming task, and is potentially beneficial for teaching a range of task sequences.
Proactive Network Maintenance using Fast, Accurate Anomaly Localization and Classification on 1-D Data Series
Venue: arXiv cs.CV 2020
Year: 2020

Proactive network maintenance (PNM) is the concept of using data from a network to identify and locate network faults, many or all of which could worsen to become service failures. The separation between the network fault and the service failure affords early detection of problems in the network to allow PNM to take place. Consequently, PNM is a form of prognostics and health management (PHM). The problem of localizing and classifying anomalies on 1-dimensional data series has been under research for years. We introduce a new algorithm that leverages Deep Convolutional Neural Networks to efficiently and accurately detect anomalies and events on data series, and it reaches 97.82% mean average precision (mAP) in our evaluation.
Adaptive Exact Learning in a Mixed-Up World: Dealing with Periodicity, Errors and Jumbled-Index Queries in String Reconstruction
Venue: arXiv cs.DS 2020
Year: 2020

We study the query complexity of exactly reconstructing a string from adaptive queries, such as substring, subsequence, and jumbled-index queries. Such problems have applications, e.g., in computational biology. We provide a number of new and improved bounds for exact string reconstruction for settings where either the string or the queries are "mixed-up". For example, we show that a periodic (i.e., "mixed-up") string, $S=p^kp'$, of smallest period $p$, where $|p'|<|p|$, can be reconstructed using $O(σ|p|+\lg n)$ substring queries, where $σ$ is the alphabet size, if $n=|S|$ is unknown. We also show that we can reconstruct $S$ after having been corrupted by a small number of errors $d$, measured by Hamming distance. In this case, we give an algorithm that uses $O(dσ|p| + d|p|\lg \frac{n}{d+1})$ queries. In addition, we show that a periodic string can be reconstructed using $2σ\lceil\lg n\rceil + 2|p|\lceil\lg σ\rceil$ subsequence queries, and that general strings can be reconstructed using $2σ\lceil\lg n\rceil + n\lceil\lg σ\rceil$ subsequence queries, without knowledge of $n$ in advance. This latter result improves the previous best, decades-old result, by Skiena and Sundaram. Finally, we believe we are the first to study the exact-learning query complexity for string reconstruction using jumbled-index queries, which are a "mixed-up" typeA of query that have received much attention of late.