OpenRaiser/Intern-Atlas huggingface dataset:
Future of Ultra-Dense Networks Beyond 5G: Harnessing Heterogeneous Moving Cells
Venue: arXiv cs.NI 2019
Year: 2019

For the past 40 years, cellular industry has been relying on static radio access deployments with gross over-provisioning. However, to meet the exponentially growing volumes of irregular data, the very notion of a cell will have to be rethought to allow them be (re-)configured on-demand and in automated manner. This work puts forward a vision of moving networks to match dynamic user demand with network access supply in the beyond-5G cellular systems. The resulting adaptive and flexible network infrastructures will leverage intelligent capable devices (e.g., cars and drones) by employing appropriate user involvement schemes. This work is a recollection of our efforts in this space with the goal to contribute a comprehensive research agenda. Particular attention is paid to quantifying the network performance scaling and session continuity gains with ultra-dense moving cells. Our findings argue for non-incremental benefits of integrating moving access points on a par with conventional (static) cellular access infrastructure.
Recognizing hyperelliptic graphs in polynomial time
Venue: arXiv cs.DS 2019
Year: 2019

Recently, a new set of multigraph parameters was defined, called "gonalities". Gonality bears some similarity to treewidth, and is a relevant graph parameter for problems in number theory and multigraph algorithms. Multigraphs of gonality 1 are trees. We consider so-called "hyperelliptic graphs" (multigraphs of gonality 2) and provide a safe and complete sets of reduction rules for such multigraphs, showing that for three of the flavors of gonality, we can recognize hyperelliptic graphs in O(n log n+m) time, where n is the number of vertices and m the number of edges of the multigraph.
LightBox: Full-stack Protected Stateful Middlebox at Lightning Speed
Venue: arXiv cs.CR 2019
Year: 2019

Running off-site software middleboxes at third-party service providers has been a popular practice. However, routing large volumes of raw traffic, which may carry sensitive information, to a remote site for processing raises severe security concerns. Prior solutions often abstract away important factors pertinent to real-world deployment. In particular, they overlook the significance of metadata protection and stateful processing. Unprotected traffic metadata like low-level headers, size and count, can be exploited to learn supposedly encrypted application contents. Meanwhile, tracking the states of 100,000s of flows concurrently is often indispensable in production-level middleboxes deployed at real networks. We present LightBox, the first system that can drive off-site middleboxes at near-native speed with stateful processing and the most comprehensive protection to date. Built upon commodity trusted hardware, Intel SGX, LightBox is the product of our systematic investigation of how to overcome the inherent limitations of secure enclaves using domain knowledge and customization. First, we introduce an elegant virtual network interface that allows convenient access to fully protected packets at line rate without leaving the enclave, as if from the trusted source network. Second, we provide complete flow state management for efficient stateful processing, by tailoring a set of data structures and algorithms optimized for the highly constrained enclave space. Extensive evaluations demonstrate that LightBox, with all security benefits, can achieve 10Gbps packet I/O, and that with case studies on three stateful middleboxes, it can operate at near-native speed.
Optimal modularity and memory capacity of neural reservoirs
Venue: arXiv cs.NE 2019
Year: 2019

The neural network is a powerful computing framework that has been exploited by biological evolution and by humans for solving diverse problems. Although the computational capabilities of neural networks are determined by their structure, the current understanding of the relationships between a neural network's architecture and function is still primitive. Here we reveal that neural network's modular architecture plays a vital role in determining the neural dynamics and memory performance of the network of threshold neurons. In particular, we demonstrate that there exists an optimal modularity for memory performance, where a balance between local cohesion and global connectivity is established, allowing optimally modular networks to remember longer. Our results suggest that insights from dynamical analysis of neural networks and information spreading processes can be leveraged to better design neural networks and may shed light on the brain's modular organization.
Multi-Label Learning with Label Enhancement
Venue: arXiv cs.LG 2019
Year: 2019

The task of multi-label learning is to predict a set of relevant labels for the unseen instance. Traditional multi-label learning algorithms treat each class label as a logical indicator of whether the corresponding label is relevant or irrelevant to the instance, i.e., +1 represents relevant to the instance and -1 represents irrelevant to the instance. Such label represented by -1 or +1 is called logical label. Logical label cannot reflect different label importance. However, for real-world multi-label learning problems, the importance of each possible label is generally different. For the real applications, it is difficult to obtain the label importance information directly. Thus we need a method to reconstruct the essential label importance from the logical multilabel data. To solve this problem, we assume that each multi-label instance is described by a vector of latent real-valued labels, which can reflect the importance of the corresponding labels. Such label is called numerical label. The process of reconstructing the numerical labels from the logical multi-label data via utilizing the logical label information and the topological structure in the feature space is called Label Enhancement. In this paper, we propose a novel multi-label learning framework called LEMLL, i.e., Label Enhanced Multi-Label Learning, which incorporates regression of the numerical labels and label enhancement into a unified framework. Extensive comparative studies validate that the performance of multi-label learning can be improved significantly with label enhancement and LEMLL can effectively reconstruct latent label importance information from logical multi-label data.
Assortment and Price Optimization Under the Two-Stage Luce model
Venue: arXiv cs.DM 2019
Year: 2019

This paper studies assortment and pricing optimization problems under the Two-Stage Luce model (2SLM), a discrete choice model introduced by Echenique and Saito (2018) that generalizes the multinomial logit model (MNL). The model employs an utility function as in the the MNL, and a dominance relation between products. When consumers are offered an assortmentS , they first discard all dominated products in S and then select one of the remaining products using the standard MNL. This model may violate the regularity condition, which states that the probability of choosing a product cannot increase if the offer set is enlarged. Therefore, the 2SLM falls outside the large family of discrete choice models based on random utility which contains almost all choice models studied in revenue management. We prove that the assortment problem under the 2SLM is polynomial-time solvable. Moreover, we show that the capacitated assortment optimization problem is NP-hard and but it admits polynomial-time algorithms for the relevant special cases cases where (1) the dominance relation is attractiveness-correlated and (2) its transitive reduction is a forest. The proofs exploit a strong connection between assortments under the 2SLM and independent sets in comparability graphs. Finally, we study the associated joint pricing and assortment problem under this model. First, we show that well known optimal pricing policy for the MNL can be arbitrarily bad. Our main result in this section is the development of an efficient algorithm for this pricing problem. The resulting optimal pricing strategy is simple to describe: it assigns the same price for all products, except for the one with the highest attractiveness and as well as for the one with the lowest attractiveness.
The Complexity of Counting Surjective Homomorphisms and Compactions
Venue: arXiv cs.CC 2019
Year: 2019

A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertices of H and it is a compaction if it uses all of the vertices of H and all of the non-loop edges of H. Hell and Nesetril gave a complete characterisation of the complexity of deciding whether there is a homomorphism from an input graph G to a fixed graph H. A complete characterisation is not known for surjective homomorphisms or for compactions, though there are many interesting results. Dyer and Greenhill gave a complete characterisation of the complexity of counting homomorphisms from an input graph G to a fixed graph H. In this paper, we give a complete characterisation of the complexity of counting surjective homomorphisms from an input graph G to a fixed graph H and we also give a complete characterisation of the complexity of counting compactions from an input graph G to a fixed graph H. In an addendum we use our characterisations to point out a dichotomy for the complexity of the respective approximate counting problems (in the connected case).
A Pig, an Angel and a Cactus Walk Into a Blender: A Descriptive Approach to Visual Blending
Venue: arXiv cs.AI 2019
Year: 2019

A descriptive approach for automatic generation of visual blends is presented. The implemented system, the Blender, is composed of two components: the Mapper and the Visual Blender. The approach uses structured visual representations along with sets of visual relations which describe how the elements (in which the visual representation can be decomposed) relate among each other. Our system is a hybrid blender, as the blending process starts at the Mapper (conceptual level) and ends at the Visual Blender (visual representation level). The experimental results show that the Blender is able to create analogies from input mental spaces and produce well-composed blends, which follow the rules imposed by its base-analogy and its relations. The resulting blends are visually interesting and some can be considered as unexpected.
Perceptual Adversarial Networks for Image-to-Image Transformation
Venue: arXiv cs.CV 2019
Year: 2019

In this paper, we propose a principled Perceptual Adversarial Networks (PAN) for image-to-image transformation tasks. Unlike existing application-specific algorithms, PAN provides a generic framework of learning mapping relationship between paired images (Fig. 1), such as mapping a rainy image to its de-rained counterpart, object edges to its photo, semantic labels to a scenes image, etc. The proposed PAN consists of two feed-forward convolutional neural networks (CNNs), the image transformation network T and the discriminative network D. Through combining the generative adversarial loss and the proposed perceptual adversarial loss, these two networks can be trained alternately to solve image-to-image transformation tasks. Among them, the hidden layers and output of the discriminative network D are upgraded to continually and automatically discover the discrepancy between the transformed image and the corresponding ground-truth. Simultaneously, the image transformation network T is trained to minimize the discrepancy explored by the discriminative network D. Through the adversarial training process, the image transformation network T will continually narrow the gap between transformed images and ground-truth images. Experiments evaluated on several image-to-image transformation tasks (e.g., image de-raining, image inpainting, etc.) show that the proposed PAN outperforms many related state-of-the-art methods.
Network Topology Inference Using Information Cascades with Limited Statistical Knowledge
Venue: arXiv cs.SI 2019
Year: 2019

We study the problem of inferring network topology from information cascades, in which the amount of time taken for information to diffuse across an edge in the network follows an unknown distribution. Unlike previous studies, which assume knowledge of these distributions, we only require that diffusion along different edges in the network be independent together with limited moment information (e.g., the means). We introduce the concept of a separating vertex set for a graph, which is a set of vertices in which for any two given distinct vertices of the graph, there exists a vertex whose distance to them are different. We show that a necessary condition for reconstructing a tree perfectly using distance information between pairs of vertices is given by the size of an observed separating vertex set. We then propose an algorithm to recover the tree structure using infection times, whose differences have means corresponding to the distance between two vertices. To improve the accuracy of our algorithm, we propose the concept of redundant vertices, which allows us to perform averaging to better estimate the distance between two vertices. Though the theory is developed mainly for tree networks, we demonstrate how the algorithm can be extended heuristically to general graphs. Simulations using synthetic and real networks, and experiments using real-world data suggest that our proposed algorithm performs better than some current state-of-the-art network reconstruction methods.
Power domination in maximal planar graphs
Venue: arXiv cs.DM 2019
Year: 2019

Power domination in graphs emerged from the problem of monitoring an electrical system by placing as few measurement devices in the system as possible. It corresponds to a variant of domination that includes the possibility of propagation. For measurement devices placed on a set S of vertices of a graph G, the set of monitored vertices is initially the set S together with all its neighbors. Then iteratively, whenever some monitored vertex v has a single neighbor u not yet monitored, u gets monitored. A set S is said to be a power dominating set of the graph G if all vertices of G eventually are monitored. The power domination number of a graph is the minimum size of a power dominating set. In this paper, we prove that any maximal planar graph of order n $\ge$ 6 admits a power dominating set of size at most (n--2)/4 .
Cache Oblivious Algorithms for Computing the Triplet Distance Between Trees
Venue: arXiv cs.DS 2019
Year: 2019

We study the problem of computing the triplet distance between two rooted unordered trees with $n$ labeled leafs. Introduced by Dobson 1975, the triplet distance is the number of leaf triples that induce different topologies in the two trees. The current theoretically best algorithm is an $\mathrm{O}(n \log n)$ time algorithm by Brodal et al. (SODA 2013). Recently Jansson and Rajaby proposed a new algorithm that, while slower in theory, requiring $\mathrm{O}(n \log^3 n)$ time, in practice it outperforms the theoretically faster $\mathrm{O}(n \log n)$ algorithm. Both algorithms do not scale to external memory. We present two cache oblivious algorithms that combine the best of both worlds. The first algorithm is for the case when the two input trees are binary trees and the second a generalized algorithm for two input trees of arbitrary degree. Analyzed in the RAM model, both algorithms require $\mathrm{O}(n \log n)$ time, and in the cache oblivious model $\mathrm{O}(\frac{n}{B} \log_{2} \frac{n}{M})$ I/Os. Their relative simplicity and the fact that they scale to external memory makes them achieve the best practical performance. We note that these are the first algorithms that scale to external memory, both in theory and practice, for this problem.
AMP: A Better Multipath TCP for Data Center Networks
Venue: arXiv cs.NI 2019
Year: 2019

In recent years several multipath data transport mechanisms, such as MPTCP and XMP, have been introduced to effectively exploit the path diversity of data center networks (DCNs). However, these multipath schemes have not been widely deployed in DCNs. We argue that two key factors among others impeded their adoption: TCP incast and minimum window syndrome. First, these mechanisms are ill-suited for workloads with a many-to-one communication pattern, commonly found in DCNs, causing frequent TCP incast collapses. Second, the syndrome we discover for the first time, results in 2-5 times lower throughput for single-path flows than multipath flows, thus severely violating network fairness. To effectively tackle these problems, we propose AMP: an adaptive multipath congestion control mechanism that quickly detects the onset of these problems and transforms its multipath flow into a single-path flow. Once these problems disappear, AMP safely reverses this transformation and continues its data transmission via multiple paths. Our evaluation results under a diverse set of scenarios in a fat-tree topology with realistic workloads demonstrate that AMP is robust to the TCP incast problem and improves network fairness between multipath and single-path flows significantly with little performance loss.
Learning to Design Games: Strategic Environments in Reinforcement Learning
Venue: arXiv cs.AI 2019
Year: 2019

In typical reinforcement learning (RL), the environment is assumed given and the goal of the learning is to identify an optimal policy for the agent taking actions through its interactions with the environment. In this paper, we extend this setting by considering the environment is not given, but controllable and learnable through its interaction with the agent at the same time. This extension is motivated by environment design scenarios in the real-world, including game design, shopping space design and traffic signal design. Theoretically, we find a dual Markov decision process (MDP) w.r.t. the environment to that w.r.t. the agent, and derive a policy gradient solution to optimizing the parametrized environment. Furthermore, discontinuous environments are addressed by a proposed general generative framework. Our experiments on a Maze game design task show the effectiveness of the proposed algorithms in generating diverse and challenging Mazes against various agent settings.
A Similarity Measure for GPU Kernel Subgraph Matching
Venue: arXiv cs.DC 2019
Year: 2019

Accelerator architectures specialize in executing SIMD (single instruction, multiple data) in lockstep. Because the majority of CUDA applications are parallelized loops, control flow information can provide an in-depth characterization of a kernel. CUDAflow is a tool that statically separates CUDA binaries into basic block regions and dynamically measures instruction and basic block frequencies. CUDAflow captures this information in a control flow graph (CFG) and performs subgraph matching across various kernel's CFGs to gain insights to an application's resource requirements, based on the shape and traversal of the graph, instruction operations executed and registers allocated, among other information. The utility of CUDAflow is demonstrated with SHOC and Rodinia application case studies on a variety of GPU architectures, revealing novel thread divergence characteristics that facilitates end users, autotuners and compilers in generating high performing code.
Purely Combinatorial Algorithms for Approximate Directed Minimum Degree Spanning Trees
Venue: arXiv cs.DS 2019
Year: 2019

Given a directed graph $G$ on $n$ vertices with a special vertex $s$, the directed minimum degree spanning tree problem requires computing a incoming spanning tree rooted at $s$ whose maximum tree in-degree is the smallest among all such trees. The problem is known to be NP-hard, since it generalizes the Hamiltonian path problem. The best LP-based polynomial time algorithm can achieve an approximation of $Δ^*+2$ [Bansal et al, 2009], where $Δ^*$ denotes the optimal maximum tree in-degree. As for purely combinatorial algorithms (algorithms that do not use LP), the best approximation is $O(Δ^*+\log n)$ [Krishnan and Raghavachari, 2001] but the running time is quasi-polynomial. In this paper, we focus on purely combinatorial algorithms and try to bridge the gap between LP-based approaches and purely combinatorial approaches. As a result, we propose a purely combinatorial polynomial time algorithm that also achieves an $O(Δ^* + \log n)$ approximation. Then we improve this algorithm to obtain a $(1+ε)Δ^* + O(\frac{\log n}{\log\log n})$ for any constant $0<ε<1$ approximation in polynomial time.
On Thin Air Reads: Towards an Event Structures Model of Relaxed Memory
Venue: arXiv cs.PL 2019
Year: 2019

To model relaxed memory, we propose confusion-free event structures over an alphabet with a justification relation. Executions are modeled by justified configurations, where every read event has a justifying write event. Justification alone is too weak a criterion, since it allows cycles of the kind that result in so-called thin-air reads. Acyclic justification forbids such cycles, but also invalidates event reorderings that result from compiler optimizations and dynamic instruction scheduling. We propose the notion of well-justification, based on a game-like model, which strikes a middle ground. We show that well-justified configurations satisfy the DRF theorem: in any data-race free program, all well-justified configurations are sequentially consistent. We also show that rely-guarantee reasoning is sound for well-justified configurations, but not for justified configurations. For example, well-justified configurations are type-safe. Well-justification allows many, but not all reorderings performed by relaxed memory. In particular, it fails to validate the commutation of independent reads. We discuss variations that may address these shortcomings.
STag: A Stable Fiducial Marker System
Venue: arXiv cs.CV 2019
Year: 2019

Fiducial markers provide better-defined features than the ones naturally available in the scene. For this reason, they are widely utilized in computer vision applications where reliable pose estimation is required. Factors such as imaging noise and subtle changes in illumination induce jitter on the estimated pose. Jitter impairs robustness in vision and robotics applications, and deteriorates the sense of presence and immersion in AR/VR applications. In this paper, we propose STag, a fiducial marker system that provides stable pose estimation. STag is designed to be robust against jitter factors, thus sustains pose stability better than the existing solutions. This is achieved by utilizing geometric features that can be localized more repeatably. The outer square border of the marker is used for detection and homography estimation. This is followed by a novel homography refinement step using the inner circular border. After refinement, the pose can be estimated stably and robustly across viewing conditions. These features are demonstrated with a comprehensive set of experiments, including comparisons with the state of the art fiducial marker systems.