OpenRaiser/Intern-Atlas huggingface dataset:
Improved Lower Bounds for Truthful Scheduling
Venue: arXiv cs.GT 2020
Year: 2020

The problem of scheduling unrelated machines by a truthful mechanism to minimize the makespan was introduced in the seminal "Algorithmic Mechanism Design" paper by Nisan and Ronen. Nisan and Ronen showed that there is a truthful mechanism that provides an approximation ratio of $\min(m,n)$, where $n$ is the number of machines and $m$ is the number of jobs. They also proved that no truthful mechanism can provide an approximation ratio better than $2$. Since then, the lower bound was improved to $1 +\sqrt 2 \approx 2.41$ by Christodoulou, Kotsoupias, and Vidali, and then to $1+ϕ\approx 2.618$ by Kotsoupias and Vidali. Very recently, the lower bound was improved to $2.755$ by Giannakopoulos, Hammerl, and Pocas. In this paper we further improve the bound to $3-δ$, for every constant $δ>0$. Note that a gap between the upper bound and the lower bounds exists even when the number of machines and jobs is very small. In particular, the known $1+\sqrt{2}$ lower bound requires at least $3$ machines and $5$ jobs. In contrast, we show a lower bound of $2.2055$ that uses only $3$ machines and $3$ jobs and a lower bound of $1+\sqrt 2$ that uses only $3$ machines and $4$ jobs. For the case of two machines and two jobs we show a lower bound of $2$. Similar bounds for two machines and two jobs were known before but only via complex proofs that characterized all truthful mechanisms that provide a finite approximation ratio in this setting, whereas our new proof uses a simple and direct approach.
Low Complexity Optimization of the Asymptotic Spectral Efficiency in Massive MIMO NOMA
Venue: arXiv cs.IT 2020
Year: 2020

Massive multiple-input multiple-output (MIMO) technology facilitates huge increases in the capacity of wireless channels, while non-orthogonal multiple access (NOMA) addresses the problem of limited resources in traditional orthogonal multiple access (OMA) techniques, promising enhanced spectral efficiency. This work uses asymptotic capacity computation results to reduce the complexity of a power allocation algorithm for small-scale MIMO-NOMA, so that it may be applied for systems with massive MIMO arrays. The proposed method maximizes the sum-capacity of the considered system, subject to power and performance constraints, and demonstrates greater accuracy than alternative approaches despite remaining low-complexity for arbitrarily large antenna arrays.
Are PETs (Privacy Enhancing Technologies) Giving Protection for Smartphones? -- A Case Study
Venue: arXiv cs.CR 2020
Year: 2020

With smartphone technologies enhanced way of interacting with the world around us, it has also been paving the way for easier access to our private and personal information. This has been amplified by the existence of numerous embedded sensors utilized by millions of apps to users. While mobile apps have positively transformed many aspects of our lives with new functionalities, many of these applications are taking advantage of vast amounts of data, privacy apps, a form of Privacy Enhancing Technology can be an effective privacy management tool for smartphones. To protect against vulnerabilities related to the collection, storage, and sharing of sensitive data, developers are building numerous privacy apps. However, there has been a lack of discretion in this particular area which calls for a proper assessment to understand the far-reaching utilization of these apps among users. During this process we have conducted an evaluation of the most popular privacy apps from our total collection of five hundred and twelve to demonstrate their functionality specific data protections they are claiming to offer, both technologically and conventionally, measuring up to standards. Taking their offered security functionalities as a scale, we conducted forensic experiments to indicate where they are failing to be consistent in maintaining protection. For legitimate validation of security gaps in assessed privacy apps, we have also utilized NIST and OWASP guidelines. We believe this study will be efficacious for continuous improvement and can be considered as a foundation towards a common standard for privacy and security measures for an app's development stage.
NASGEM: Neural Architecture Search via Graph Embedding Method
Venue: arXiv cs.AI 2020
Year: 2020

Neural Architecture Search (NAS) automates and prospers the design of neural networks. Estimator-based NAS has been proposed recently to model the relationship between architectures and their performance to enable scalable and flexible search. However, existing estimator-based methods encode the architecture into a latent space without considering graph similarity. Ignoring graph similarity in node-based search space may induce a large inconsistency between similar graphs and their distance in the continuous encoding space, leading to inaccurate encoding representation and/or reduced representation capacity that can yield sub-optimal search results. To preserve graph correlation information in encoding, we propose NASGEM which stands for Neural Architecture Search via Graph Embedding Method. NASGEM is driven by a novel graph embedding method equipped with similarity measures to capture the graph topology information. By precisely estimating the graph distance and using an auxiliary Weisfeiler-Lehman kernel to guide the encoding, NASGEM can utilize additional structural information to get more accurate graph representation to improve the search efficiency. GEMNet, a set of networks discovered by NASGEM, consistently outperforms networks crafted by existing search methods in classification tasks, i.e., with 0.4%-3.6% higher accuracy while having 11%- 21% fewer Multiply-Accumulates. We further transfer GEMNet for COCO object detection. In both one-stage and twostage detectors, our GEMNet surpasses its manually-crafted and automatically-searched counterparts.
Computing the Largest Bond and the Maximum Connected Cut of a Graph
Venue: arXiv cs.DS 2020
Year: 2020

The cut-set $\partial(S)$ of a graph $G=(V,E)$ is the set of edges that have one endpoint in $S\subset V$ and the other endpoint in $V\setminus S$, and whenever $G[S]$ is connected, the cut $[S,V\setminus S]$ of $G$ is called a connected cut. A bond of a graph $G$ is an inclusion-wise minimal disconnecting set of $G$, i.e., bonds are cut-sets that determine cuts $[S,V\setminus S]$ of $G$ such that $G[S]$ and $G[V\setminus S]$ are both connected. Contrasting with a large number of studies related to maximum cuts, there exist very few results regarding the largest bond of general graphs. In this paper, we aim to reduce this gap on the complexity of computing the largest bond, and the maximum connected cut of a graph. Although cuts and bonds are similar, we remark that computing the largest bond and the maximum connected cut of a graph tends to be harder than computing its maximum cut. We show that it does not exist a constant-factor approximation algorithm to compute the largest bond, unless P = NP. Also, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard even for planar bipartite graphs, whereas \textsc{Maximum Cut} is trivial on bipartite graphs and polynomial-time solvable on planar graphs. In addition, we show that {\sc Largest Bond} and {\sc Maximum Connected Cut} are NP-hard on split graphs, and restricted to graphs of clique-width $w$ they can not be solved in time $f(w)\times n^{o(w)}$ unless the Exponential Time Hypothesis fails, but they can be solved in time $f(w)\times n^{O(w)}$. Finally, we show that both problems are fixed-parameter tractable when parameterized by the size of the solution, the treewidth, and the twin-cover number.
Less is More: Rejecting Unreliable Reviews for Product Question Answering
Venue: arXiv cs.CL 2020
Year: 2020

Promptly and accurately answering questions on products is important for e-commerce applications. Manually answering product questions (e.g. on community question answering platforms) results in slow response and does not scale. Recent studies show that product reviews are a good source for real-time, automatic product question answering (PQA). In the literature, PQA is formulated as a retrieval problem with the goal to search for the most relevant reviews to answer a given product question. In this paper, we focus on the issue of answerability and answer reliability for PQA using reviews. Our investigation is based on the intuition that many questions may not be answerable with a finite set of reviews. When a question is not answerable, a system should return nil answers rather than providing a list of irrelevant reviews, which can have significant negative impact on user experience. Moreover, for answerable questions, only the most relevant reviews that answer the question should be included in the result. We propose a conformal prediction based framework to improve the reliability of PQA systems, where we reject unreliable answers so that the returned results are more concise and accurate at answering the product question, including returning nil answers for unanswerable questions. Experiments on a widely used Amazon dataset show encouraging results of our proposed framework. More broadly, our results demonstrate a novel and effective application of conformal methods to a retrieval task.
Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK
Venue: arXiv cs.LG 2020
Year: 2020

We consider the dynamic of gradient descent for learning a two-layer neural network. We assume the input $x\in\mathbb{R}^d$ is drawn from a Gaussian distribution and the label of $x$ satisfies $f^{\star}(x) = a^{\top}|W^{\star}x|$, where $a\in\mathbb{R}^d$ is a nonnegative vector and $W^{\star} \in\mathbb{R}^{d\times d}$ is an orthonormal matrix. We show that an over-parametrized two-layer neural network with ReLU activation, trained by gradient descent from random initialization, can provably learn the ground truth network with population loss at most $o(1/d)$ in polynomial time with polynomial samples. On the other hand, we prove that any kernel method, including Neural Tangent Kernel, with a polynomial number of samples in $d$, has population loss at least $Ω(1 / d)$.
Weakness Analysis of Cyberspace Configuration Based on Reinforcement Learning
Venue: arXiv cs.AI 2020
Year: 2020

In this work, we present a learning-based approach to analysis cyberspace configuration. Unlike prior methods, our approach has the ability to learn from past experience and improve over time. In particular, as we train over a greater number of agents as attackers, our method becomes better at rapidly finding attack paths for previously hidden paths, especially in multiple domain cyberspace. To achieve these results, we pose finding attack paths as a Reinforcement Learning (RL) problem and train an agent to find multiple domain attack paths. To enable our RL policy to find more hidden attack paths, we ground representation introduction an multiple domain action select module in RL. By designing a simulated cyberspace experimental environment to verify our method. Our objective is to find more hidden attack paths, to analysis the weakness of cyberspace configuration. The experimental results show that our method can find more hidden multiple domain attack paths than existing baselines methods.
Multi-Granularity Modularized Network for Abstract Visual Reasoning
Venue: arXiv cs.AI 2020
Year: 2020

Abstract visual reasoning connects mental abilities to the physical world, which is a crucial factor in cognitive development. Most toddlers display sensitivity to this skill, but it is not easy for machines. Aimed at it, we focus on the Raven Progressive Matrices Test, designed to measure cognitive reasoning. Recent work designed some black-boxes to solve it in an end-to-end fashion, but they are incredibly complicated and difficult to explain. Inspired by cognitive studies, we propose a Multi-Granularity Modularized Network (MMoN) to bridge the gap between the processing of raw sensory information and symbolic reasoning. Specifically, it learns modularized reasoning functions to model the semantic rule from the visual grounding in a neuro-symbolic and semi-supervision way. To comprehensively evaluate MMoN, our experiments are conducted on the dataset of both seen and unseen reasoning rules. The result shows that MMoN is well suited for abstract visual reasoning and also explainable on the generalization test.
How URLLC can Benefit from NOMA-based Retransmissions
Venue: arXiv cs.IT 2020
Year: 2020

Among the new types of connectivity unleashed by the emerging 5G wireless systems, Ultra-Reliable Low Latency Communication (URLLC) is perhaps the most innovative, yet challenging one. Ultra-reliability requires high levels of diversity, however, the reactive approach based on packet retransmission in HARQ protocols should be applied carefully to conform to the stringent latency constraints. The main premise of this paper is that the NOMA principle can be used to achieve highly efficient retransmissions by allowing concurrent use of wireless resources in the uplink. We introduce a comprehensive solution that accommodates multiple intermittently active users, each with its own HARQ process. The performance is investigated under two different assumptions about the Channel State Information (CSI) availability: statistical and instantaneous. The results show that NOMA can indeed lead to highly efficient system operation compared to the case in which all HARQ processes are run orthogonally.
Challenges of AI in Wireless Networks for IoT
Venue: arXiv cs.NI 2020
Year: 2020

The Internet of Things (IoT), hailed as the enabler of the next industrial revolution, will require ubiquitous connectivity, context-aware and dynamic service mobility, and extreme security through the wireless network infrastructure. Artificial Intelligence (AI), thus, will play a major role in the underlying network infrastructure. However, a number of challenges will surface while using the concepts, tools and algorithms of AI in wireless networks used by IoT. In this article, the main challenges in using AI in the wireless network infrastructure that facilitate end-to-end IoT communication are highlighted with potential generalized solution and future research directions.
Animated GIF optimization by adaptive color local table management
Venue: arXiv cs.CV 2020
Year: 2020

After thirty years of the GIF file format, today is becoming more popular than ever: being a great way of communication for friends and communities on Instant Messengers and Social Networks. While being so popular, the original compression method to encode GIF images have not changed a bit. On the other hand popularity means that storage saving becomes an issue for hosting platforms. In this paper a parametric optimization technique for animated GIFs will be presented. The proposed technique is based on Local Color Table selection and color remapping in order to create optimized animated GIFs while preserving the original format. The technique achieves good results in terms of byte reduction with limited or no loss of perceived color quality. Tests carried out on 1000 GIF files demonstrate the effectiveness of the proposed optimization strategy.
A Hybrid Evolutionary Algorithm for Reliable Facility Location Problem
Venue: arXiv cs.NE 2020
Year: 2020

The reliable facility location problem (RFLP) is an important research topic of operational research and plays a vital role in the decision-making and management of modern supply chain and logistics. Through solving RFLP, the decision-maker can obtain reliable location decisions under the risk of facilities' disruptions or failures. In this paper, we propose a novel model for the RFLP. Instead of assuming allocating a fixed number of facilities to each customer as in the existing works, we set the number of allocated facilities as an independent variable in our proposed model, which makes our model closer to the scenarios in real life but more difficult to be solved by traditional methods. To handle it, we propose EAMLS, a hybrid evolutionary algorithm, which combines a memorable local search (MLS) method and an evolutionary algorithm (EA). Additionally, a novel metric called l3-value is proposed to assist the analysis of the algorithm's convergence speed and exam the process of evolution. The experimental results show the effectiveness and superior performance of our EAMLS, compared to a CPLEX solver and a Genetic Algorithm (GA), on large-scale problems.
Long Short-Term Memory Spiking Networks and Their Applications
Venue: arXiv cs.NE 2020
Year: 2020

Recent advances in event-based neuromorphic systems have resulted in significant interest in the use and development of spiking neural networks (SNNs). However, the non-differentiable nature of spiking neurons makes SNNs incompatible with conventional backpropagation techniques. In spite of the significant progress made in training conventional deep neural networks (DNNs), training methods for SNNs still remain relatively poorly understood. In this paper, we present a novel framework for training recurrent SNNs. Analogous to the benefits presented by recurrent neural networks (RNNs) in learning time series models within DNNs, we develop SNNs based on long short-term memory (LSTM) networks. We show that LSTM spiking networks learn the timing of the spikes and temporal dependencies. We also develop a methodology for error backpropagation within LSTM-based SNNs. The developed architecture and method for backpropagation within LSTM-based SNNs enable them to learn long-term dependencies with comparable results to conventional LSTMs.
Outage Analysis of Downlink URLLC in Massive MIMO systems with Power Allocation
Venue: arXiv cs.IT 2020
Year: 2020

Massive MIMO is seen as a main enabler for low latency communications, thanks to its high spatial degrees of freedom. The channel hardening and favorable propagation properties of Massive MIMO are particularly important for multiplexing several URLLC devices. However, the actual utility of channel hardening and spatial multiplexing is dependent critically on the accuracy of channel knowledge. When several low latency devices are multiplexed, the cost for acquiring accurate knowledge becomes critical, and it is not evident how many devices can be served with a latency-reliability requirement and how many pilot symbols should be allocated. This paper investigates the trade-off between achieving high spectral efficiency and high reliability in the downlink, by employing various power allocation strategies, for maximum ratio and minimum mean square error precoders. The results show that using max-min SINR power allocation achieves the best reliability, at the expense of lower sum spectral efficiency.
Geometric Bounds for Convergence Rates of Averaging Algorithms
Venue: arXiv cs.MA 2020
Year: 2020

We develop a generic method for bounding the convergence rate of an averaging algorithm running in a multi-agent system with a time-varying network, where the associated stochastic matrices have a time-independent Perron vector. This method provides bounds on convergence rates that unify and refine most of the previously known bounds. They depend on geometric parameters of the dynamic communication graph such as the normalized diameter or the bottleneck measure. As corollaries of these geometric bounds, we show that the convergence rate of the Metropolis algorithm in a system of $n$ agents is less than $1-1/4n^2$ with any communication graph that may vary in time, but is permanently connected and bidirectional. We prove a similar upper bound for the EqualNeighbor algorithm under the additional assumptions that the number of neighbors of each agent is constant and that the communication graph is not too irregular. Moreover our bounds offer improved convergence rates for several averaging algorithms and specific families of communication graphs. Finally we extend our methodology to a time-varying Perron vector and show how convergence times may dramatically degrade with even limited variations of Perron vectors.
Universal Algebra in UniMath
Venue: arXiv cs.LO 2020
Year: 2020

We present an ongoing effort to implement Universal Algebra in the UniMath system. Our aim is to develop a general framework for formalizing and studying Universal Algebra in a proof assistant. By constituting a formal system for isolating the invariants of the theory we are interested in -- that is, general algebraic structures modulo isomorphism -- Univalent Mathematics seems to provide a suitable environment to carry on our endeavour.
Patient-Specific Domain Adaptation for Fast Optical Flow Based on Teacher-Student Knowledge Transfer
Venue: arXiv cs.CV 2020
Year: 2020

Fast motion feedback is crucial in computer-aided surgery (CAS) on moving tissue. Image-assistance in safety-critical vision applications requires a dense tracking of tissue motion. This can be done using optical flow (OF). Accurate motion predictions at high processing rates lead to higher patient safety. Current deep learning OF models show the common speed vs. accuracy trade-off. To achieve high accuracy at high processing rates, we propose patient-specific fine-tuning of a fast model. This minimizes the domain gap between training and application data, while reducing the target domain to the capability of the lower complex, fast model. We propose to obtain training sequences pre-operatively in the operation room. We handle missing ground truth, by employing teacher-student learning. Using flow estimations from teacher model FlowNet2 we specialize a fast student model FlowNet2S on the patient-specific domain. Evaluation is performed on sequences from the Hamlyn dataset. Our student model shows very good performance after fine-tuning. Tracking accuracy is comparable to the teacher model at a speed up of factor six. Fine-tuning can be performed within minutes, making it feasible for the operation room. Our method allows to use a real-time capable model that was previously not suited for this task. This method is laying the path for improved patient-specific motion estimation in CAS.
A Generative Graph Method to Solve the Travelling Salesman Problem
Venue: arXiv cs.AI 2020
Year: 2020

The Travelling Salesman Problem (TSP) is a challenging graph task in combinatorial optimization that requires reasoning about both local node neighborhoods and global graph structure. In this paper, we propose to use the novel Graph Learning Network (GLN), a generative approach, to approximately solve the TSP. GLN model learns directly the pattern of TSP instances as training dataset, encodes the graph properties, and merge the different node embeddings to output node-to-node an optimal tour directly or via graph search technique that validates the final tour. The preliminary results of the proposed novel approach proves its applicability to this challenging problem providing a low optimally gap with significant computation saving compared to the optimal solution.