OpenRaiser/Intern-Atlas huggingface dataset:
Coded Merkle Tree: Solving Data Availability Attacks in Blockchains
Venue: arXiv cs.CR 2019
Year: 2019

In this paper, we propose coded Merkle tree (CMT), a novel hash accumulator that offers a constant-cost protection against data availability attacks in blockchains, even if the majority of the network nodes are malicious. A CMT is constructed using a family of sparse erasure codes on each layer, and is recovered by iteratively applying a peeling-decoding technique that enables a compact proof for data availability attack on any layer. Our algorithm enables any node to verify the full availability of any data block generated by the system by just downloading a $Θ(1)$ byte block hash commitment and randomly sampling $Θ(\log b)$ bytes, where $b$ is the size of the data block. With the help of only one connected honest node in the system, our method also allows any node to verify any tampering of the coded Merkle tree by just downloading $Θ(\log b)$ bytes. We provide a modular library for CMT in Rust and Python and demonstrate its efficacy inside the Parity Bitcoin client.
A Fast Exponential Time Algorithm for Max Hamming Distance X3SAT
Venue: arXiv cs.CC 2019
Year: 2019

X3SAT is the problem of whether one can satisfy a given set of clauses with up to three literals such that in every clause, exactly one literal is true and the others are false. A related question is to determine the maximal Hamming distance between two solutions of the instance. Dahllöf provided an algorithm for Maximum Hamming Distance XSAT, which is more complicated than the same problem for X3SAT, with a runtime of $O(1.8348^n)$; Fu, Zhou and Yin considered Maximum Hamming Distance for X3SAT and found for this problem an algorithm with runtime $O(1.6760^n)$. In this paper, we propose an algorithm in $O(1.3298^n)$ time to solve the Max Hamming Distance X3SAT problem; the algorithm actually counts for each $k$ the number of pairs of solutions which have Hamming Distance $k$.
Best-first Search Algorithm for Non-convex Sparse Minimization
Venue: arXiv cs.DS 2019
Year: 2019

Non-convex sparse minimization (NSM), or $\ell_0$-constrained minimization of convex loss functions, is an important optimization problem that has many machine learning applications. NSM is generally NP-hard, and so to exactly solve NSM is almost impossible in polynomial time. As regards the case of quadratic objective functions, exact algorithms based on quadratic mixed-integer programming (MIP) have been studied, but no existing exact methods can handle more general objective functions including Huber and logistic losses; this is unfortunate since those functions are prevalent in practice. In this paper, we consider NSM with $\ell_2$-regularized convex objective functions and develop an algorithm by leveraging the efficiency of best-first search (BFS). Our BFS can compute solutions with objective errors at most $Δ\ge0$, where $Δ$ is a controllable hyper-parameter that balances the trade-off between the guarantee of objective errors and computation cost. Experiments demonstrate that our BFS is useful for solving moderate-size NSM instances with non-quadratic objectives and that BFS is also faster than the MIP-based method when applied to quadratic objectives.
From Darwin to Poincaré and von Neumann: Recurrence and Cycles in Evolutionary and Algorithmic Game Theory
Venue: arXiv cs.GT 2019
Year: 2019

Replicator dynamics, the continuous-time analogue of Multiplicative Weights Updates, is the main dynamic in evolutionary game theory. In simple evolutionary zero-sum games, such as Rock-Paper-Scissors, replicator dynamic is periodic \cite{zeeman1980population}, however, its behavior in higher dimensions is not well understood. We provide a complete characterization of its behavior in zero-sum evolutionary games. We prove that, if and only if, the system has an interior Nash equilibrium, the dynamics exhibit Poincaré recurrence, i.e., almost all orbits come arbitrary close to their initial conditions infinitely often. If no interior equilibria exist, then all interior initial conditions converge to the boundary. Specifically, the strategies that are not in the support of any equilibrium vanish in the limit of all orbits. All recurrence results furthermore extend to a class of games that generalize both graphical polymatrix games as well as evolutionary games, establishing a unifying link between evolutionary and algorithmic game theory. We show that two degrees of freedom, as in Rock-Paper-Scissors, is sufficient to prove periodicity.
Topic-aware Pointer-Generator Networks for Summarizing Spoken Conversations
Venue: arXiv cs.CL 2019
Year: 2019

Due to the lack of publicly available resources, conversation summarization has received far less attention than text summarization. As the purpose of conversations is to exchange information between at least two interlocutors, key information about a certain topic is often scattered and spanned across multiple utterances and turns from different speakers. This phenomenon is more pronounced during spoken conversations, where speech characteristics such as backchanneling and false-starts might interrupt the topical flow. Moreover, topic diffusion and (intra-utterance) topic drift are also more common in human-to-human conversations. Such linguistic characteristics of dialogue topics make sentence-level extractive summarization approaches used in spoken documents ill-suited for summarizing conversations. Pointer-generator networks have effectively demonstrated its strength at integrating extractive and abstractive capabilities through neural modeling in text summarization. To the best of our knowledge, to date no one has adopted it for summarizing conversations. In this work, we propose a topic-aware architecture to exploit the inherent hierarchical structure in conversations to further adapt the pointer-generator model. Our approach significantly outperforms competitive baselines, achieves more efficient learning outcomes, and attains more robust performance.
Recognizing the Tractability in Big Data Computing
Venue: arXiv cs.CC 2019
Year: 2019

Due to the limitation on computational power of existing computers, the polynomial time does not works for identifying the tractable problems in big data computing. This paper adopts the sublinear time as the new tractable standard to recognize the tractability in big data computing, and the random-access Turing machine is used as the computational model to characterize the problems that are tractable on big data. First, two pure-tractable classes are first proposed. One is the class $\mathrm{PL}$ consisting of the problems that can be solved in polylogarithmic time by a RATM. The another one is the class $\mathrm{ST}$ including all the problems that can be solved in sublinear time by a RATM. The structure of the two pure-tractable classes is deeply investigated and they are proved $\mathrm{PL^i} \subsetneq \mathrm{PL^{i+1}}$ and $\mathrm{PL} \subsetneq \mathrm{ST}$. Then, two pseudo-tractable classes, $\mathrm{PTR}$ and $\mathrm{PTE}$, are proposed. $\mathrm{PTR}$ consists of all the problems that can solved by a RATM in sublinear time after a PTIME preprocessing by reducing the size of input dataset. $\mathrm{PTE}$ includes all the problems that can solved by a RATM in sublinear time after a PTIME preprocessing by extending the size of input dataset. The relations among the two pseudo-tractable classes and other complexity classes are investigated and they are proved that $\mathrm{PT} \subseteq \mathrm{P}$, $\sqcap'\mathrm{T^0_Q} \subsetneq \mathrm{PTR^0_Q}$ and $\mathrm{PT_P} = \mathrm{P}$.
Can Sentiment Analysis Reveal Structure in a Plotless Novel?
Venue: arXiv cs.CL 2019
Year: 2019

Modernist novels are thought to break with traditional plot structure. In this paper, we test this theory by applying Sentiment Analysis to one of the most famous modernist novels, To the Lighthouse by Virginia Woolf. We first assess Sentiment Analysis in light of the critique that it cannot adequately account for literary language: we use a unique statistical comparison to demonstrate that even simple lexical approaches to Sentiment Analysis are surprisingly effective. We then use the Syuzhet.R package to explore similarities and differences across modeling methods. This comparative approach, when paired with literary close reading, can offer interpretive clues. To our knowledge, we are the first to undertake a hybrid model that fully leverages the strengths of both computational analysis and close reading. This hybrid model raises new questions for the literary critic, such as how to interpret relative versus absolute emotional valence and how to take into account subjective identification. Our finding is that while To the Lighthouse does not replicate a plot centered around a traditional hero, it does reveal an underlying emotional structure distributed between characters - what we term a distributed heroine model. This finding is innovative in the field of modernist and narrative studies and demonstrates that a hybrid method can yield significant discoveries.
Identifying Malicious Players in GWAP-based Disaster Monitoring Crowdsourcing System
Venue: arXiv cs.SI 2019
Year: 2019

Disaster monitoring is challenging due to the lake of infrastructures in monitoring areas. Based on the theory of Game-With-A-Purpose (GWAP), this paper contributes to a novel large-scale crowdsourcing disaster monitoring system. The system analyzes tagged satellite pictures from anonymous players, and then reports aggregated and evaluated monitoring results to its stakeholders. An algorithm based on directed graph centralities is presented to address the core issues of malicious user detection and disaster level calculation. Our method can be easily applied in other human computation systems. In the end, some issues with possible solutions are discussed for our future work.
Analyzing Control Flow Integrity with LLVM-CFI
Venue: arXiv cs.CR 2019
Year: 2019

Control-flow hijacking attacks are used to perform malicious com-putations. Current solutions for assessing the attack surface afteracontrol flow integrity(CFI) policy was applied can measure onlyindirect transfer averages in the best case without providing anyinsights w.r.t. the absolute calltarget reduction per callsite, and gad-get availability. Further, tool comparison is underdeveloped or notpossible at all. CFI has proven to be one of the most promising pro-tections against control flow hijacking attacks, thus many effortshave been made to improve CFI in various ways. However, there isa lack of systematic assessment of existing CFI protections. In this paper, we presentLLVM-CFI, a static source code analy-sis framework for analyzing state-of-the-art static CFI protectionsbased on the Clang/LLVM compiler framework.LLVM-CFIworksby precisely modeling a CFI policy and then evaluating it within aunified approach.LLVM-CFIhelps determine the level of securityoffered by different CFI protections, after the CFI protections weredeployed, thus providing an important step towards exploit cre-ation/prevention and stronger defenses. We have usedLLVM-CFIto assess eight state-of-the-art static CFI defenses on real-worldprograms such as Google Chrome and Apache Httpd.LLVM-CFIprovides a precise analysis of the residual attack surfaces, andaccordingly ranks CFI policies against each other.LLVM-CFIalsosuccessfully paves the way towards construction of COOP-like codereuse attacks and elimination of the remaining attack surface bydisclosing protected calltargets under eight restrictive CFI policies.
Introducing multilayer stream graphs and layer centralities
Venue: arXiv cs.SI 2019
Year: 2019

Graphs are commonly used in mathematics to represent some relationships between items. However, as simple objects, they sometimes fail to capture all relevant aspects of real-world data. To address this problem, we generalize them and model interactions over time with multilayer structure. We build and test several centralities to assess the importance of layers of such structures. In order to showcase the relevance of this new model with centralities, we give examples on two large-scale datasets of interactions, involving individuals and flights, and show that we are able to explain subtle behaviour patterns in both cases.
Capacity Characterization for Intelligent Reflecting Surface Aided MIMO Communication
Venue: arXiv cs.IT 2019
Year: 2019

Intelligent reflecting surface (IRS) is a promising solution to enhance the wireless communication capacity both cost-effectively and energy-efficiently, by properly altering the signal propagation via tuning a large number of passive reflecting units. In this paper, we aim to characterize the fundamental capacity limit of IRS-aided point-to-point multiple-input multiple-output (MIMO) communication systems with multi-antenna transmitter and receiver in general, by jointly optimizing the IRS reflection coefficients and the MIMO transmit covariance matrix. First, we consider narrowband transmission under frequency-flat fading channels, and develop an efficient alternating optimization algorithm to find a locally optimal solution by iteratively optimizing the transmit covariance matrix or one of the reflection coefficients with the others being fixed. Next, we consider capacity maximization for broadband transmission in a general MIMO orthogonal frequency division multiplexing (OFDM) system under frequency-selective fading channels, where transmit covariance matrices can be optimized for different subcarriers while only one common set of IRS reflection coefficients can be designed to cater to all subcarriers. To tackle this more challenging problem, we propose a new alternating optimization algorithm based on convex relaxation to find a high-quality suboptimal solution. Numerical results show that our proposed algorithms achieve substantially increased capacity compared to traditional MIMO channels without the IRS, and also outperform various benchmark schemes. In particular, it is shown that with the proposed algorithms, various key parameters of the IRS-aided MIMO channel such as channel total power, rank, and condition number can be significantly improved for capacity enhancement.
Partial differential equation regularization for supervised machine learning
Venue: arXiv cs.LG 2019
Year: 2019

This article is an overview of supervised machine learning problems for regression and classification. Topics include: kernel methods, training by stochastic gradient descent, deep learning architecture, losses for classification, statistical learning theory, and dimension independent generalization bounds. Implicit regularization in deep learning examples are presented, including data augmentation, adversarial training, and additive noise. These methods are reframed as explicit gradient regularization.
APEX: Adaptive Ext4 File System for Enhanced Data Recoverability in Edge Devices
Venue: arXiv cs.OS 2019
Year: 2019

Recently Edge Computing paradigm has gained significant popularity both in industry and academia. With its increased usage in real-life scenarios, security, privacy and integrity of data in such environments have become critical. Malicious deletion of mission-critical data due to ransomware, trojans and viruses has been a huge menace and recovering such lost data is an active field of research. As most of Edge computing devices have compute and storage limitations, difficult constraints arise in providing an optimal scheme for data protection. These devices mostly use Linux/Unix based operating systems. Hence, this work focuses on extending the Ext4 file system to APEX (Adaptive Ext4): a file system based on novel on-the-fly learning model that provides an Adaptive Recover-ability Aware file allocation platform for efficient post-deletion data recovery and therefore maintaining data integrity. Our recovery model and its lightweight implementation allow significant improvement in recover-ability of lost data with lower compute, space, time, and cost overheads compared to other methods. We demonstrate the effectiveness of APEX through a case study of overwriting surveillance videos by CryPy malware on Raspberry-Pi based Edge deployment and show 678% and 32% higher recovery than Ext4 and current state-of-the-art File Systems. We also evaluate the overhead characteristics and experimentally show that they are lower than other related works.
Fluid Flow Mass Transport for Generative Networks
Venue: arXiv cs.LG 2019
Year: 2019

Generative Adversarial Networks have been shown to be powerful in generating content. To this end, they have been studied intensively in the last few years. Nonetheless, training these networks requires solving a saddle point problem that is difficult to solve and slowly converging. Motivated from techniques in the registration of point clouds and by the fluid flow formulation of mass transport, we investigate a new formulation that is based on strict minimization, without the need for the maximization. The formulation views the problem as a matching problem rather than an adversarial one and thus allows us to quickly converge and obtain meaningful metrics in the optimization path.
Bounds for Approximate Regret-Matching Algorithms
Venue: arXiv cs.LG 2019
Year: 2019

A dominant approach to solving large imperfect-information games is Counterfactural Regret Minimization (CFR). In CFR, many regret minimization problems are combined to solve the game. For very large games, abstraction is typically needed to render CFR tractable. Abstractions are often manually tuned, possibly removing important strategic differences in the full game and harming performance. Function approximation provides a natural solution to finding good abstractions to approximate the full game. A common approach to incorporating function approximation is to learn the inputs needed for a regret minimizing algorithm, allowing for generalization across many regret minimization problems. This paper gives regret bounds when a regret minimizing algorithm uses estimates instead of true values. This form of analysis is the first to generalize to a larger class of $(Φ, f)$-regret matching algorithms, and includes different forms of regret such as swap, internal, and external regret. We demonstrate how these results give a slightly tighter bound for Regression Regret-Matching (RRM), and present a novel bound for combining regression with Hedge.
Context-Aware Graph Attention Networks
Venue: arXiv cs.LG 2019
Year: 2019

Graph Neural Networks (GNNs) have been widely studied for graph data representation and learning. However, existing GNNs generally conduct context-aware learning on node feature representation only which usually ignores the learning of edge (weight) representation. In this paper, we propose a novel unified GNN model, named Context-aware Adaptive Graph Attention Network (CaGAT). CaGAT aims to learn a context-aware attention representation for each graph edge by further exploiting the context relationships among different edges. In particular, CaGAT conducts context-aware learning on both node feature representation and edge (weight) representation simultaneously and cooperatively in a unified manner which can boost their respective performance in network training. We apply CaGAT on semi-supervised learning tasks. Promising experimental results on several benchmark datasets demonstrate the effectiveness and benefits of CaGAT.
Cross-Layer Strategic Ensemble Defense Against Adversarial Examples
Venue: arXiv cs.LG 2019
Year: 2019

Deep neural network (DNN) has demonstrated its success in multiple domains. However, DNN models are inherently vulnerable to adversarial examples, which are generated by adding adversarial perturbations to benign inputs to fool the DNN model to misclassify. In this paper, we present a cross-layer strategic ensemble framework and a suite of robust defense algorithms, which are attack-independent, and capable of auto-repairing and auto-verifying the target model being attacked. Our strategic ensemble approach makes three original contributions. First, we employ input-transformation diversity to design the input-layer strategic transformation ensemble algorithms. Second, we utilize model-disagreement diversity to develop the output-layer strategic model ensemble algorithms. Finally, we create an input-output cross-layer strategic ensemble defense that strengthens the defensibility by combining diverse input transformation based model ensembles with diverse output verification model ensembles. Evaluated over 10 attacks on ImageNet dataset, we show that our strategic ensemble defense algorithms can achieve high defense success rates and are more robust with high attack prevention success rates and low benign false negative rates, compared to existing representative defense methods.
Conditional out-of-sample generation for unpaired data using trVAE
Venue: arXiv cs.LG 2019
Year: 2019

While generative models have shown great success in generating high-dimensional samples conditional on low-dimensional descriptors (learning e.g. stroke thickness in MNIST, hair color in CelebA, or speaker identity in Wavenet), their generation out-of-sample poses fundamental problems. The conditional variational autoencoder (CVAE) as a simple conditional generative model does not explicitly relate conditions during training and, hence, has no incentive of learning a compact joint distribution across conditions. We overcome this limitation by matching their distributions using maximum mean discrepancy (MMD) in the decoder layer that follows the bottleneck. This introduces a strong regularization both for reconstructing samples within the same condition and for transforming samples across conditions, resulting in much improved generalization. We refer to the architecture as \emph{transformer} VAE (trVAE). Benchmarking trVAE on high-dimensional image and tabular data, we demonstrate higher robustness and higher accuracy than existing approaches. In particular, we show qualitatively improved predictions for cellular perturbation response to treatment and disease based on high-dimensional single-cell gene expression data, by tackling previously problematic minority classes and multiple conditions. For generic tasks, we improve Pearson correlations of high-dimensional estimated means and variances with their ground truths from 0.89 to 0.97 and 0.75 to 0.87, respectively.
Motion Planning through Demonstration to Deal with Complex Motions in Assembly Process
Venue: arXiv cs.RO 2019
Year: 2019

Complex and skillful motions in actual assembly process are challenging for the robot to generate with existing motion planning approaches, because some key poses during the human assembly can be too skillful for the robot to realize automatically. In order to deal with this problem, this paper develops a motion planning method using skillful motions from demonstration, which can be applied to complete robotic assembly process including complex and skillful motions. In order to demonstrate conveniently without redundant third-party devices, we attach augmented reality (AR) markers to the manipulated object to track and capture poses of the object during the human assembly process, which are employed as key poses to execute motion planning by the planner. Derivative of every key pose serves as criterion to determine the priority of use of key poses in order to accelerate the motion planning. The effectiveness of the presented method is verified through some numerical examples and actual robot experiments.