OpenRaiser/Intern-Atlas huggingface dataset:
Flexible Load Balancing with Multi-dimensional State-space Collapse: Throughput and Heavy-traffic Delay Optimality
Venue: arXiv cs.DC 2018
Year: 2018

Heavy traffic analysis for load balancing policies has relied heavily on the condition of state-space collapse onto a single-dimensional line in previous works. In this paper, via Lyapunov-drift analysis, we rigorously prove that even under a multi-dimensional state-space collapse, steady-state heavy-traffic delay optimality can still be achieved for a general load balancing system. This result directly implies that achieving steady-state heavy-traffic delay optimality simply requires that no server is idling while others are busy at heavy loads, thus complementing and extending the result obtained by diffusion approximations. Further, we explore the greater flexibility provided by allowing a multi-dimensional state-space collapse in designing new load balancing policies that are both throughput optimal and heavy-traffic delay optimal in steady state. This is achieved by overcoming various technical challenges, and the methods used in this paper could be of independent interest.
SupportNet: solving catastrophic forgetting in class incremental learning with support data
Venue: arXiv cs.NE 2018
Year: 2018

A plain well-trained deep learning model often does not have the ability to learn new knowledge without forgetting the previously learned knowledge, which is known as catastrophic forgetting. Here we propose a novel method, SupportNet, to efficiently and effectively solve the catastrophic forgetting problem in the class incremental learning scenario. SupportNet combines the strength of deep learning and support vector machine (SVM), where SVM is used to identify the support data from the old data, which are fed to the deep learning model together with the new data for further training so that the model can review the essential information of the old data when learning the new information. Two powerful consolidation regularizers are applied to stabilize the learned representation and ensure the robustness of the learned model. We validate our method with comprehensive experiments on various tasks, which show that SupportNet drastically outperforms the state-of-the-art incremental learning methods and even reaches similar performance as the deep learning model trained from scratch on both old and new data. Our program is accessible at: https://github.com/lykaust15/SupportNet
On self-dual and LCD double circulant and double negacirculant codes over $\mathbb{F}_q + u\mathbb{F}_q$
Venue: arXiv cs.IT 2018
Year: 2018

Double circulant codes of length $2n$ over the semilocal ring $R = \mathbb{F}_q + u\mathbb{F}_q,\, u^2=u,$ are studied when $q$ is an odd prime power, and $-1$ is a square in $\mathbb{F}_q.$ Double negacirculant codes of length $2n$ are studied over $R$ when $n$ is even and $q$ is an odd prime power. Exact enumeration of self-dual and LCD such codes for given length $2n$ is given. Employing a duality-preserving Gray map, self-dual and LCD codes of length $4n$ over $\mathbb{F}_q$ are constructed. Using random coding and the Artin conjecture, the relative distance of these codes is bounded below. The parameters of examples of the modest length are computed. Several such codes are optimal.
RGCNN: Regularized Graph CNN for Point Cloud Segmentation
Venue: arXiv cs.CV 2018
Year: 2018

Point cloud, an efficient 3D object representation, has become popular with the development of depth sensing and 3D laser scanning techniques. It has attracted attention in various applications such as 3D tele-presence, navigation for unmanned vehicles and heritage reconstruction. The understanding of point clouds, such as point cloud segmentation, is crucial in exploiting the informative value of point clouds for such applications. Due to the irregularity of the data format, previous deep learning works often convert point clouds to regular 3D voxel grids or collections of images before feeding them into neural networks, which leads to voluminous data and quantization artifacts. In this paper, we instead propose a regularized graph convolutional neural network (RGCNN) that directly consumes point clouds. Leveraging on spectral graph theory, we treat features of points in a point cloud as signals on graph, and define the convolution over graph by Chebyshev polynomial approximation. In particular, we update the graph Laplacian matrix that describes the connectivity of features in each layer according to the corresponding learned features, which adaptively captures the structure of dynamic graphs. Further, we deploy a graph-signal smoothness prior in the loss function, thus regularizing the learning process. Experimental results on the ShapeNet part dataset show that the proposed approach significantly reduces the computational complexity while achieving competitive performance with the state of the art. Also, experiments show RGCNN is much more robust to both noise and point cloud density in comparison with other methods. We further apply RGCNN to point cloud classification and achieve competitive results on ModelNet40 dataset.
PAC Ranking from Pairwise and Listwise Queries: Lower Bounds and Upper Bounds
Venue: arXiv cs.LG 2018
Year: 2018

This paper explores the adaptive (active) PAC (probably approximately correct) top-$k$ ranking (i.e., top-$k$ item selection) and total ranking problems from $l$-wise ($l\geq 2$) comparisons under the multinomial logit (MNL) model. By adaptively choosing sets to query and observing the noisy output of the most favored item of each query, we want to design ranking algorithms that recover the top-$k$ or total ranking using as few queries as possible. For the PAC top-$k$ ranking problem, we derive a lower bound on the sample complexity (aka number of queries), and propose an algorithm that is sample-complexity-optimal up to an $O(\log(k+l)/\log{k})$ factor. When $l=2$ (i.e., pairwise comparisons) or $l=O(poly(k))$, this algorithm matches the lower bound. For the PAC total ranking problem, we derive a tight lower bound, and propose an algorithm that matches the lower bound. When $l=2$, the MNL model reduces to the popular Plackett-Luce (PL) model. In this setting, our results still outperform the state-of-the-art both theoretically and numerically. We also compare our algorithms with the state-of-the-art using synthetic data as well as real-world data to verify the efficiency of our algorithms.
An Industrial Social Network for Sharing Knowledge Among Operators
Venue: arXiv cs.HC 2018
Year: 2018

Due to the increasing complexity of modern automatic machines typically used in several industrial applications, the need for assistive technologies is becoming very relevant. Typical approaches consist in designing advanced and adaptive human-machine interfaces (HMIs) that can be effectively used by any operator and that provide guided procedures for the most common situations. However, when dealing with complex systems, infrequent and unforeseen situations may happen, whose solution require the experience owned by a limited number of skilled operators. To this end, in this paper we propose an industrial social network concept to allow an effective exchange of information among the operators and to facilitate the solution of unforeseen events, such as unscheduled maintenance activities or troubleshooting.
The Twin Conjugacy Search Problem and Applications
Venue: arXiv cs.CR 2018
Year: 2018

We propose a new computational problem over the noncommutative group, called the twin conjugacy search problem. This problem is related to the conjugacy search problem and can be used for almost all of the same cryptographic constructions that are based on the conjugacy search problem. However, our new problem is at least hard as the conjugacy search problem. Moreover, the twin conjugacy search problem have many applications. One of the most important applications, we propose a trapdoor test which can replace the function of the decision oracle. We also show other applications of the problem, including: a non-interactive key exchange protocol and a key exchange protocol, a new encryption scheme which is secure against chosen ciphertext attack, with a very simple and tight security proof and short ciphertexts, under a weak assumption, in the random oracle model.
Quantum Penny Flip game with unawareness
Venue: arXiv cs.GT 2018
Year: 2018

Games with unawareness model strategic situations in which players' perceptions about the game are limited. They take into account the fact that the players may be unaware of some of the strategies available to them or their opponents as well as the players may have a restricted view about the number of players participating in the game. The aim of the research is to introduce this notion into theory of quantum games. We shall focus on PQ Penny Flip game introduced by D. Meyer. We shall formalize the previous results and consider other cases of unawareness in the game.
Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
Venue: arXiv cs.CR 2018
Year: 2018

Crypto-currencies are digital assets designed to work as a medium of exchange, e.g., Bitcoin, but they are susceptible to attacks (dishonest behavior of participants). A framework for the analysis of attacks in crypto-currencies requires (a) modeling of game-theoretic aspects to analyze incentives for deviation from honest behavior; (b) concurrent interactions between participants; and (c) analysis of long-term monetary gains. Traditional game-theoretic approaches for the analysis of security protocols consider either qualitative temporal properties such as safety and termination, or the very special class of one-shot (stateless) games. However, to analyze general attacks on protocols for crypto-currencies, both stateful analysis and quantitative objectives are necessary. In this work our main contributions are as follows: (a) we show how a class of concurrent mean-payoff games, namely ergodic games, can model various attacks that arise naturally in crypto-currencies; (b) we present the first practical implementation of algorithms for ergodic games that scales to model realistic problems for crypto-currencies; and (c) we present experimental results showing that our framework can handle games with thousands of states and millions of transitions.
Periodic Pólya urns and an application to Young tableaux
Venue: arXiv cs.DM 2018
Year: 2018

P{ó}lya urns are urns where at each unit of time a ball is drawn and is replaced with some other balls according to its colour. We introduce a more general model: The replacement rule depends on the colour of the drawn ball and the value of the time (mod p). We discuss some intriguing properties of the differential operators associated to the generating functions encoding the evolution of these urns. The initial partial differential equation indeed leads to ordinary linear differential equations and we prove that the moment generating functions are D-finite. For a subclass, we exhibit a closed form for the corresponding generating functions (giving the exact state of the urns at time n). When the time goes to infinity, we show that these periodic P{ó}lya urns follow a rich variety of behaviours: their asymptotic fluctuations are described by a family of distributions, the generalized Gamma distributions, which can also be seen as powers of Gamma distributions. En passant, we establish some enumerative links with other combinatorial objects, and we give an application for a new result on the asymptotics of Young tableaux: This approach allows us to prove that the law of the lower right corner in a triangular Young tableau follows asymptotically a product of generalized Gamma distributions.
Evaluating CBR Similarity Functions for BAM Switching in Networks with Dynamic Traffic Profile
Venue: arXiv cs.NI 2018
Year: 2018

In an increasingly complex scenario for network management, a solution that allows configuration in more autonomous way with less intervention of the network manager is expected. This paper presents an evaluation of similarity functions that are necessary in the context of using a learning strategy for finding solutions. The learning approach considered is based on Case-Based Reasoning (CBR) and is applied to a network scenario where different Bandwidth Allocation Models (BAMs) behaviors are used and must be eventually switched looking for the best possible network operation. In this context, it is required to identify and configure an adequate similarity function that will be used in the learning process to recover similar solutions previously considered. This paper introduces the similarity functions, explains the relevant aspects of the learning process in which the similarity function plays a role and, finally, presents a proof of concept for a specific similarity function adopted. Results show that the similarity function was capable to get similar results from the existing use case database. As such, the use of similarity functions with CBR technique has proved to be potentially satisfactory for supporting BAM switching decisions mostly driven by the dynamics of input traffic profile.
On Critical Threshold Value for Simple Games
Venue: arXiv cs.GT 2018
Year: 2018

In this note, we show that for every simple game with n players the critical threshold value is at most n/4. This verifies the conjecture of Freixas and Kurz.
Surgical Data Science: A Consensus Perspective
Venue: arXiv cs.CY 2018
Year: 2018

Surgical data science is a scientific discipline with the objective of improving the quality of interventional healthcare and its value through capturing, organization, analysis, and modeling of data. The goal of the 1st workshop on Surgical Data Science was to bring together researchers working on diverse topics in surgical data science in order to discuss existing challenges, potential standards and new research directions in the field. Inspired by current open space and think tank formats, it was organized in June 2016 in Heidelberg. While the first day of the workshop, which was dominated by interactive sessions, was open to the public, the second day was reserved for a board meeting on which the information gathered on the public day was processed by (1) discussing remaining open issues, (2) deriving a joint definition for surgical data science and (3) proposing potential strategies for advancing the field. This document summarizes the key findings.
Low-Complexity Multiuser QAM Detection for Uplink 1-bit Massive MIMO
Venue: arXiv cs.IT 2018
Year: 2018

This work studies multiuser detection for one-bit massive multiple-input multiple-output (MIMO) systems in order to diminish the power consumption at the base station (BS). A low-complexity near-maximum-likelihood (nML) multiuser detection algorithm is designed, assuming that each BS antenna port is connected with a pair of single-bit resolution analog-to-digital converters (ADCs) and each user equipment (UE) transmits symbols from a quadrature amplitude modulation (QAM) constellation. First, a novel convex program is formulated as a convex surrogate of the ML detector and subsequently solved through an accelerated first-order method. Then, the solution of the convex optimization problem is harnessed to solve a refined combinatorial problem with reduced search space, requiring non-exponential complexity on the number of the UEs. Judicious simulation study corroborates the efficacy of the resulting two-phase detection algorithm. The proposed two-phase algorithm can achieve symbol error rate (SER) performance close to the ML detector, with significantly reduced computation cost compared to the nML detection schemes in prior art.
Intelligently-automated facilities expansion with the HEPCloud Decision Engine
Venue: arXiv cs.DC 2018
Year: 2018

The next generation of High Energy Physics experiments are expected to generate exabytes of data---two orders of magnitude greater than the current generation. In order to reliably meet peak demands, facilities must either plan to provision enough resources to cover the forecasted need, or find ways to elastically expand their computational capabilities. Commercial cloud and allocation-based High Performance Computing (HPC) resources both have explicit and implicit costs that must be considered when deciding when to provision these resources, and to choose an appropriate scale. In order to support such provisioning in a manner consistent with organizational business rules and budget constraints, we have developed a modular intelligent decision support system (IDSS) to aid in the automatic provisioning of resources---spanning multiple cloud providers, multiple HPC centers, and grid computing federations.
Automatic View Planning with Multi-scale Deep Reinforcement Learning Agents
Venue: arXiv cs.CV 2018
Year: 2018

We propose a fully automatic method to find standardized view planes in 3D image acquisitions. Standard view images are important in clinical practice as they provide a means to perform biometric measurements from similar anatomical regions. These views are often constrained to the native orientation of a 3D image acquisition. Navigating through target anatomy to find the required view plane is tedious and operator-dependent. For this task, we employ a multi-scale reinforcement learning (RL) agent framework and extensively evaluate several Deep Q-Network (DQN) based strategies. RL enables a natural learning paradigm by interaction with the environment, which can be used to mimic experienced operators. We evaluate our results using the distance between the anatomical landmarks and detected planes, and the angles between their normal vector and target. The proposed algorithm is assessed on the mid-sagittal and anterior-posterior commissure planes of brain MRI, and the 4-chamber long-axis plane commonly used in cardiac MRI, achieving accuracy of 1.53mm, 1.98mm and 4.84mm, respectively.
Simulating Vehicle Movement and Multi-Hop Connectivity from Basic Safety Messages
Venue: arXiv cs.CY 2018
Year: 2018

The Basic Safety Message (BSM) is a standardized communication packet that is sent every tenth of a second between connected vehicles using Dedicated Short Range Communication (DSRC). BSMs contain data about the sending vehicle's state, such as speed, location, and the status of the turn signal. Currently, many BSM datasets are available through the connected vehicle testbeds of U.S. Department of Transportation from all over the country. However, without a proper visualization tool, it is not possible to analyze or visually get an overview of the spatio-temporal distribution of the data. With this goal, a web application has been developed which can ingest a raw BSM dataset and display a time-based simulation of vehicle movement. The simulation also displays multi-hop vehicular network connectivity over DSRC. This paper gives details about the application, including an explanation of the multi-hop partitioning algorithm used to classify the vehicles into separate network partitions. A performance analysis for the simulation is included, in which it is suggested that calculating a connectivity matrix with the multi-hop partitioning algorithm is computationally expensive for large number of vehicles.
Matching Startup Founders to Investors: a Tool and a Study
Venue: arXiv cs.CY 2018
Year: 2018

The process of matching startup founders with venture capital investors is a necessary first step for many modern technology companies, yet there have been few attempts to study the characteristics of the two parties and their interactions. Surprisingly little has been shown quantitatively about the process, and many of the common assumptions are based on anecdotal evidence. In this thesis, we aim to learn more about the matching component of the startup fundraising process. We begin with a tool (VCWiz), created from the current set of best-practices to help inexperienced founders navigate the founder-investor matching process. The goal of this tool is to increase efficiency and equitability, while collecting data to inform further studies. We use this data, combined with public data on venture investments in the USA, to draw conclusions about the characteristics of venture financing rounds. Finally, we explore the communication data contributed to the tool by founders who are actively fundraising, and use it to learn which social attributes are most beneficial for individuals to possess when soliciting investments.
AI Should Not Be an Open Source Project
Venue: arXiv cs.CY 2018
Year: 2018

Who should own the Artificial Intelligence technology? It should belong to everyone, properly said not the technology per se, but the fruits that can be reaped from it. Obviously, we should not let AI end up in the hands of irresponsible persons. Likewise, nuclear technology should benefit all, however it should be kept secret and inaccessible by the public at large.
A vendors evaluation using AHP for an Indian steel pipe manufacturing company
Venue: arXiv cs.CY 2018
Year: 2018

To improve a firms supply chain performance it is essential to have a vendor evaluation process to be able to showcase an organizations success in the present aggressive market. Hence, the process of evaluating the vendor is a crucial task of the purchasing executives in supply chain management. The objective of this research is to propose a methodology to evaluate the vendors for a steel pipe manufacturing firm in Gujarat, India. For the purpose of the study, the Analytical Hierarchy Process was used to evaluate the best raw material vendor for this company. Multiple qualitative and quantitative criteria are involved in the vendor evaluation process. To solve the complex problem of vendor evaluation, a tradeoff between this multicriteria is important. The outcomes indicated that the AHP technique makes it simpler to assign weights for the different criteria for evaluating the vendor. Research findings showed that quality is the most important criterion followed by delivery, cost and vendor relationship management.
Badger: Complexity Analysis with Fuzzing and Symbolic Execution
Venue: arXiv cs.SE 2018
Year: 2018

Hybrid testing approaches that involve fuzz testing and symbolic execution have shown promising results in achieving high code coverage, uncovering subtle errors and vulnerabilities in a variety of software applications. In this paper we describe Badger - a new hybrid approach for complexity analysis, with the goal of discovering vulnerabilities which occur when the worst-case time or space complexity of an application is significantly higher than the average case. Badger uses fuzz testing to generate a diverse set of inputs that aim to increase not only coverage but also a resource-related cost associated with each path. Since fuzzing may fail to execute deep program paths due to its limited knowledge about the conditions that influence these paths, we complement the analysis with a symbolic execution, which is also customized to search for paths that increase the resource-related cost. Symbolic execution is particularly good at generating inputs that satisfy various program conditions but by itself suffers from path explosion. Therefore, Badger uses fuzzing and symbolic execution in tandem, to leverage their benefits and overcome their weaknesses. We implemented our approach for the analysis of Java programs, based on Kelinci and Symbolic PathFinder. We evaluated Badger on Java applications, showing that our approach is significantly faster in generating worst-case executions compared to fuzzing or symbolic execution on their own.