OpenRaiser/Intern-Atlas huggingface dataset:
When is Approximate Counting for Conjunctive Queries Tractable?
Venue: arXiv cs.DS 2020
Year: 2020

Conjunctive queries are one of the most common class of queries used in database systems, and the best studied in the literature. A seminal result of Grohe, Schwentick, and Segoufin (STOC 2001) demonstrates that for every class $G$ of graphs, the evaluation of all conjunctive queries whose underlying graph is in $G$ is tractable if, and only if, $G$ has bounded treewidth. In this work, we extend this characterization to the counting problem for conjunctive queries. Specifically, for every class $C$ of conjunctive queries with bounded treewidth, we introduce the first fully polynomial-time randomized approximation scheme (FPRAS) for counting answers to a query in $C$, and the first polynomial-time algorithm for sampling answers uniformly from a query in $C$. As a corollary, it follows that for every class $G$ of graphs, the counting problem for conjunctive queries whose underlying graph is in $G$ admits an FPRAS if, and only if, $G$ has bounded treewidth (unless $\text{BPP} \neq \text{P}$)}. In fact, our FPRAS is more general, and also applies to conjunctive queries with bounded hypertree width, as well as unions of such queries. The key ingredient in our proof is the resolution of a fundamental counting problem from automata theory. Specifically, we demonstrate the first FPRAS and polynomial time sampler for the set of trees of size $n$ accepted by a tree automaton, which improves the prior quasi-polynomial time randomized approximation scheme (QPRAS) and sampling algorithm of Gore, Jerrum, Kannan, Sweedyk, and Mahaney '97. We demonstrate how this algorithm can be used to obtain an FPRAS for many hitherto open problems, such as counting solutions to constraint satisfaction problems (CSP) with bounded hypertree-width, counting the number of error threads in programs with nested call subroutines, and counting valid assignments to structured DNNF circuits.
Securing Digital Systems via Split-Chip Obfuscation
Venue: arXiv cs.CR 2020
Year: 2020

Security is an important facet of integrated circuit design for many applications. IP privacy and Trojan insertion are growing threats as circuit fabrication in advanced nodes almost inevitably relies on untrusted foundries. A proposed solution is Split-Chip Obfuscation that uses a combination trusted and untrusted IC fabrication scheme. By utilizing two CMOS processes, a system is endowed with the stronger security guaranties of a trusted legacy node while also leveraging the performance and density of an advanced untrusted node. Critical to the effectiveness of Split-Chip Obfuscation is finding an optimum partitioning of a system between the two ICs. In this paper, we develop a design flow for the Split-Chip Obfuscation scheme, defining the essential system metrics and creating a tool to rapidly assess the large design space. We demonstrate the concept of such a tool and show its application on an example SoC.
Enabling RAN Slicing Through Carrier Aggregation in mmWave Cellular Networks
Venue: arXiv cs.NI 2020
Year: 2020

The ever increasing number of connected devices and of new and heterogeneous mobile use cases implies that 5G cellular systems will face demanding technical challenges. For example, Ultra-Reliable Low-Latency Communication (URLLC) and enhanced Mobile Broadband (eMBB) scenarios present orthogonal Quality of Service (QoS) requirements that 5G aims to satisfy with a unified Radio Access Network (RAN) design. Network slicing and mmWave communications have been identified as possible enablers for 5G. They provide, respectively, the necessary scalability and flexibility to adapt the network to each specific use case environment, and low latency and multi-gigabit-per-second wireless links, which tap into a vast, currently unused portion of the spectrum. The optimization and integration of these technologies is still an open research challenge, which requires innovations at different layers of the protocol stack. This paper proposes to combine them in a RAN slicing framework for mmWaves, based on carrier aggregation. Notably, we introduce MilliSlice, a cross-carrier scheduling policy that exploits the diversity of the carriers and maximizes their utilization, thus simultaneously guaranteeing high throughput for the eMBB slices and low latency and high reliability for the URLLC flows.
A Metric Learning Approach to Anomaly Detection in Video Games
Venue: arXiv cs.LG 2020
Year: 2020

With the aim of designing automated tools that assist in the video game quality assurance process, we frame the problem of identifying bugs in video games as an anomaly detection (AD) problem. We develop State-State Siamese Networks (S3N) as an efficient deep metric learning approach to AD in this context and explore how it may be used as part of an automated testing tool. Finally, we show by empirical evaluation on a series of Atari games, that S3N is able to learn a meaningful embedding, and consequently is able to identify various common types of video game bugs.
Oriented Convex Containers of Polygons -- II
Venue: arXiv cs.CG 2020
Year: 2020

We define an 'oriented convex region' as a convex region with a direction of symmetry. An earlier article had touched upon isosceles triangles, rectangles and ellipses. Here, we examine some more possible oriented containers - semicircles, segments of circles and sectors - and raise some questions.
Model-Based Robust Deep Learning: Generalizing to Natural, Out-of-Distribution Data
Venue: arXiv cs.LG 2020
Year: 2020

While deep learning has resulted in major breakthroughs in many application domains, the frameworks commonly used in deep learning remain fragile to artificially-crafted and imperceptible changes in the data. In response to this fragility, adversarial training has emerged as a principled approach for enhancing the robustness of deep learning with respect to norm-bounded perturbations. However, there are other sources of fragility for deep learning that are arguably more common and less thoroughly studied. Indeed, natural variation such as lighting or weather conditions can significantly degrade the accuracy of trained neural networks, proving that such natural variation presents a significant challenge for deep learning. In this paper, we propose a paradigm shift from perturbation-based adversarial robustness toward model-based robust deep learning. Our objective is to provide general training algorithms that can be used to train deep neural networks to be robust against natural variation in data. Critical to our paradigm is first obtaining a model of natural variation which can be used to vary data over a range of natural conditions. Such models may be either known a priori or else learned from data. In the latter case, we show that deep generative models can be used to learn models of natural variation that are consistent with realistic conditions. We then exploit such models in three novel model-based robust training algorithms in order to enhance the robustness of deep learning with respect to the given model. Our extensive experiments show that across a variety of naturally-occurring conditions and across various datasets, deep neural networks trained with our model-based algorithms significantly outperform both standard deep learning algorithms as well as norm-bounded robust deep learning algorithms.
Machine Identification of High Impact Research through Text and Image Analysis
Venue: arXiv cs.IR 2020
Year: 2020

The volume of academic paper submissions and publications is growing at an ever increasing rate. While this flood of research promises progress in various fields, the sheer volume of output inherently increases the amount of noise. We present a system to automatically separate papers with a high from those with a low likelihood of gaining citations as a means to quickly find high impact, high quality research. Our system uses both a visual classifier, useful for surmising a document's overall appearance, and a text classifier, for making content-informed decisions. Current work in the field focuses on small datasets composed of papers from individual conferences. Attempts to use similar techniques on larger datasets generally only considers excerpts of the documents such as the abstract, potentially throwing away valuable data. We rectify these issues by providing a dataset composed of PDF documents and citation counts spanning a decade of output within two separate academic domains: computer science and medicine. This new dataset allows us to expand on current work in the field by generalizing across time and academic domain. Moreover, we explore inter-domain prediction models - evaluating a classifier's performance on a domain it was not trained on - to shed further insight on this important problem.
A Unifying Model for Locally Constrained Spanning Tree Problems
Venue: arXiv cs.CC 2020
Year: 2020

Given a graph $G$ and a digraph $D$ whose vertices are the edges of $G$, we investigate the problem of finding a spanning tree of $G$ that satisfies the constraints imposed by $D$. The restrictions to add an edge in the tree depend on its neighborhood in $D$. Here, we generalize previously investigated problems by also considering as input functions $\ell$ and $u$ on $E(G)$ that give a lower and an upper bound, respectively, on the number of constraints that must be satisfied by each edge. The produced feasibility problem is denoted by \texttt{G-DCST}, while the optimization problem is denoted by \texttt{G-DCMST}. We show that \texttt{G-DCST} is NP-complete even under strong assumptions on the structures of $G$ and $D$, as well as on functions $\ell$ and $u$. On the positive side, we prove two polynomial results, one for \texttt{G-DCST} and another for \texttt{G-DCMST}, and also give a simple exponential-time algorithm along with a proof that it is asymptotically optimal under the Ð. Finally, we prove that other previously studied constrained spanning tree (\textsc{CST}) problems can be modeled within our framework, namely, the \textsc{Conflict CST}, the \textsc{Forcing CS, the \textsc{At Least One/All Dependency CST}, the \textsc{Maximum Degree CST}, the \textsc{Minimum Degree CST}, and the \textsc{Fixed-Leaves Minimum Degree CST}.
Modeling Physical/Digital Systems: Formal Event-B vs. Diagrammatic Thinging Machine
Venue: arXiv cs.SE 2020
Year: 2020

Models are centrally important in many scientific fields. A model is a representation of a selected part of the world, which is the model s target system. Here, a system consists of a software portion as a component among many others. Event-B is a modeling method for formalizing and developing systems whose components can be modeled based on set theory and first-order logic. The thinging machine (TM) is a diagram-based model establishes three levels of representation: (1) a static structural description, which is constructed upon the flow of things in five generic operations (activities; i.e., create, process, release, transfer, and receive); (2) a dynamic representation, which identifies hierarchies of events based on five generic events; and (3) a behavioral representation according to the chronology of events. This paper is an exercise in contrasting the formal Event-B to the diagrammatic TM. The purpose is to further understand modeling in computer science. This is motivated by the claim that computer scientists should not invent specific languages to do the modeling. Important notions such as events and behavior are contrasted, and a case study system of traffic on a bridge is modeled in Event-B and TM. The results seem to indicate the need for both modeling approaches.
WHENet: Real-time Fine-Grained Estimation for Wide Range Head Pose
Venue: arXiv cs.CV 2020
Year: 2020

We present an end-to-end head-pose estimation network designed to predict Euler angles through the full range head yaws from a single RGB image. Existing methods perform well for frontal views but few target head pose from all viewpoints. This has applications in autonomous driving and retail. Our network builds on multi-loss approaches with changes to loss functions and training strategies adapted to wide range estimation. Additionally, we extract ground truth labelings of anterior views from a current panoptic dataset for the first time. The resulting Wide Headpose Estimation Network (WHENet) is the first fine-grained modern method applicable to the full-range of head yaws (hence wide) yet also meets or beats state-of-the-art methods for frontal head pose estimation. Our network is compact and efficient for mobile devices and applications.
Information Acquisition Under Resource Limitations in a Noisy Environment
Venue: arXiv cs.AI 2020
Year: 2020

We introduce a theoretical model of information acquisition under resource limitations in a noisy environment. An agent must guess the truth value of a given Boolean formula $φ$ after performing a bounded number of noisy tests of the truth values of variables in the formula. We observe that, in general, the problem of finding an optimal testing strategy for $ϕ$ is hard, but we suggest a useful heuristic. The techniques we use also give insight into two apparently unrelated, but well-studied problems: (1) \emph{rational inattention}, that is, when it is rational to ignore pertinent information (the optimal strategy may involve hardly ever testing variables that are clearly relevant to $ϕ$), and (2) what makes a formula hard to learn/remember.
Why distillation helps: a statistical perspective
Venue: arXiv cs.LG 2020
Year: 2020

Knowledge distillation is a technique for improving the performance of a simple "student" model by replacing its one-hot training labels with a distribution over labels obtained from a complex "teacher" model. While this simple approach has proven widely effective, a basic question remains unresolved: why does distillation help? In this paper, we present a statistical perspective on distillation which addresses this question, and provides a novel connection to extreme multiclass retrieval techniques. Our core observation is that the teacher seeks to estimate the underlying (Bayes) class-probability function. Building on this, we establish a fundamental bias-variance tradeoff in the student's objective: this quantifies how approximate knowledge of these class-probabilities can significantly aid learning. Finally, we show how distillation complements existing negative mining techniques for extreme multiclass retrieval, and propose a unified objective which combines these ideas.
Sparse Tensor Transpositions
Venue: arXiv cs.DS 2020
Year: 2020

We present a new algorithm for transposing sparse tensors called Quesadilla. The algorithm converts the sparse tensor data structure to a list of coordinates and sorts it with a fast multi-pass radix algorithm that exploits knowledge of the requested transposition and the tensors input partial coordinate ordering to provably minimize the number of parallel partial sorting passes. We evaluate both a serial and a parallel implementation of Quesadilla on a set of 19 tensors from the FROSTT collection, a set of tensors taken from scientific and data analytic applications. We compare Quesadilla and a generalization, Top-2-sadilla to several state of the art approaches, including the tensor transposition routine used in the SPLATT tensor factorization library. In serial tests, Quesadilla was the best strategy for 60% of all tensor and transposition combinations and improved over SPLATT by at least 19% in half of the combinations. In parallel tests, at least one of Quesadilla or Top-2-sadilla was the best strategy for 52% of all tensor and transposition combinations.
Conversational End-to-End TTS for Voice Agent
Venue: arXiv cs.SD 2020
Year: 2020

End-to-end neural TTS has achieved superior performance on reading style speech synthesis. However, it's still a challenge to build a high-quality conversational TTS due to the limitations of the corpus and modeling capability. This study aims at building a conversational TTS for a voice agent under sequence to sequence modeling framework. We firstly construct a spontaneous conversational speech corpus well designed for the voice agent with a new recording scheme ensuring both recording quality and conversational speaking style. Secondly, we propose a conversation context-aware end-to-end TTS approach which has an auxiliary encoder and a conversational context encoder to reinforce the information about the current utterance and its context in a conversation as well. Experimental results show that the proposed methods produce more natural prosody in accordance with the conversational context, with significant preference gains at both utterance-level and conversation-level. Moreover, we find that the model has the ability to express some spontaneous behaviors, like fillers and repeated words, which makes the conversational speaking style more realistic.
CPOT: Channel Pruning via Optimal Transport
Venue: arXiv cs.LG 2020
Year: 2020

Recent advances in deep neural networks (DNNs) lead to tremendously growing network parameters, making the deployments of DNNs on platforms with limited resources extremely difficult. Therefore, various pruning methods have been developed to compress the deep network architectures and accelerate the inference process. Most of the existing channel pruning methods discard the less important filters according to well-designed filter ranking criteria. However, due to the limited interpretability of deep learning models, designing an appropriate ranking criterion to distinguish redundant filters is difficult. To address such a challenging issue, we propose a new technique of Channel Pruning via Optimal Transport, dubbed CPOT. Specifically, we locate the Wasserstein barycenter for channels of each layer in the deep models, which is the mean of a set of probability distributions under the optimal transport metric. Then, we prune the redundant information located by Wasserstein barycenters. At last, we empirically demonstrate that, for classification tasks, CPOT outperforms the state-of-the-art methods on pruning ResNet-20, ResNet-32, ResNet-56, and ResNet-110. Furthermore, we show that the proposed CPOT technique is good at compressing the StarGAN models by pruning in the more difficult case of image-to-image translation tasks.
Everything is a Race and Nakamoto Always Wins
Venue: arXiv cs.CR 2020
Year: 2020

Nakamoto invented the longest chain protocol, and claimed its security by analyzing the private double-spend attack, a race between the adversary and the honest nodes to grow a longer chain. But is it the worst attack? We answer the question in the affirmative for three classes of longest chain protocols, designed for different consensus models: 1) Nakamoto's original Proof-of-Work protocol; 2) Ouroboros and SnowWhite Proof-of-Stake protocols; 3) Chia Proof-of-Space protocol. As a consequence, exact characterization of the maximum tolerable adversary power is obtained for each protocol as a function of the average block time normalized by the network delay. The security analysis of these protocols is performed in a unified manner by a novel method of reducing all attacks to a race between the adversary and the honest nodes.
Communication Complexity of Distributed High Dimensional Correlation Testing
Venue: arXiv cs.IT 2020
Year: 2020

Two parties observe independent copies of a $d$-dimensional vector and a scalar. They seek to test if their data is correlated or not, namely they seek to test if the norm $\|ρ\|_2$ of the correlation vector $ρ$ between their observations exceeds $τ$ or is it $0$. To that end, they communicate interactively and declare the output of the test. We show that roughly order $d/τ^2$ bits of communication are sufficient and necessary for resolving the distributed correlation testing problem above. Furthermore, we establish a lower bound of roughly $d^2/τ^2$ bits for communication needed for distributed correlation estimation, rendering the estimate-and-test approach suboptimal in communication required for distributed correlation testing. For the one-dimensional case with one-way communication, our bounds are tight even in the constant and provide a precise dependence of communication complexity on the probabilities of error of two types.
Sequential Recommendation with Self-Attentive Multi-Adversarial Network
Venue: arXiv cs.IR 2020
Year: 2020

Recently, deep learning has made significant progress in the task of sequential recommendation. Existing neural sequential recommenders typically adopt a generative way trained with Maximum Likelihood Estimation (MLE). When context information (called factor) is involved, it is difficult to analyze when and how each individual factor would affect the final recommendation performance. For this purpose, we take a new perspective and introduce adversarial learning to sequential recommendation. In this paper, we present a Multi-Factor Generative Adversarial Network (MFGAN) for explicitly modeling the effect of context information on sequential recommendation. Specifically, our proposed MFGAN has two kinds of modules: a Transformer-based generator taking user behavior sequences as input to recommend the possible next items, and multiple factor-specific discriminators to evaluate the generated sub-sequence from the perspectives of different factors. To learn the parameters, we adopt the classic policy gradient method, and utilize the reward signal of discriminators for guiding the learning of the generator. Our framework is flexible to incorporate multiple kinds of factor information, and is able to trace how each factor contributes to the recommendation decision over time. Extensive experiments conducted on three real-world datasets demonstrate the superiority of our proposed model over the state-of-the-art methods, in terms of effectiveness and interpretability.
Transfer learning based multi-fidelity physics informed deep neural network
Venue: arXiv cs.LG 2020
Year: 2020

For many systems in science and engineering, the governing differential equation is either not known or known in an approximate sense. Analyses and design of such systems are governed by data collected from the field and/or laboratory experiments. This challenging scenario is further worsened when data-collection is expensive and time-consuming. To address this issue, this paper presents a novel multi-fidelity physics informed deep neural network (MF-PIDNN). The framework proposed is particularly suitable when the physics of the problem is known in an approximate sense (low-fidelity physics) and only a few high-fidelity data are available. MF-PIDNN blends physics informed and data-driven deep learning techniques by using the concept of transfer learning. The approximate governing equation is first used to train a low-fidelity physics informed deep neural network. This is followed by transfer learning where the low-fidelity model is updated by using the available high-fidelity data. MF-PIDNN is able to encode useful information on the physics of the problem from the {\it approximate} governing differential equation and hence, provides accurate prediction even in zones with no data. Additionally, no low-fidelity data is required for training this model. Applicability and utility of MF-PIDNN are illustrated in solving four benchmark reliability analysis problems. Case studies to illustrate interesting features of the proposed approach are also presented.