OpenRaiser/Intern-Atlas huggingface dataset:
On Competitive Analysis for Polling Systems
Venue: arXiv cs.PF 2020
Year: 2020

Polling systems have been widely studied, however most of these studies focus on polling systems with renewal processes for arrivals and random variables for service times. There is a need driven by practical applications to study polling systems with arbitrary arrivals (not restricted to time-varying or in batches) and revealed service time upon a job's arrival. To address that need, our work considers a polling system with generic setting and for the first time provides the worst-case analysis for online scheduling policies in this system. We provide conditions for the existence of constant competitive ratios, and competitive lower bounds for general scheduling policies in polling systems. Our work also bridges the queueing and scheduling communities by proving the competitive ratios for several well-studied policies in the queueing literature, such as cyclic policies with exhaustive, gated or l-limited service disciplines for polling systems.
Quadratically Constrained Two-way Adversarial Channels
Venue: arXiv cs.IT 2020
Year: 2020

We study achievable rates of reliable communication in a power-constrained two-way additive interference channel over the real alphabet where communication is disrupted by a power-constrained jammer. This models the wireless communication scenario where two users Alice and Bob, operating in the full duplex mode, wish to exchange messages with each other in the presence of a jammer, James. Alice and Bob simultaneously transmit their encodings $ \underline{x}_A $ and $\underline{x}_B $ over $ n $ channel uses. It is assumed that James can choose his jamming signal $ \underline{s} $ as a noncausal randomized function of $ \underline{x}_A $ and $ \underline{x}_B $, and the codebooks used by Alice and Bob. Alice and Bob observe $ \underline{x}_A+\underline{x}_B +\underline{s}$, and must recover each others' messages reliably. In this article, we provide upper and lower bounds on the capacity of this channel which match each other and equal $ \frac{1}{2}\log\left(\frac{1}{2} + \mathsf{SNR}\right) $ in the high-$\mathsf{SNR}$ regime (where $\mathsf{SNR}$, signal to noise ratios, is defined as the ratio of the power constraints of the users to the power constraint of the jammer). We give a code construction based on lattice codes, and derive achievable rates for large $\mathsf{SNR}$. We also present upper bounds based on two specific attack strategies for James. Along the way, sumset property of lattices for the achievability and general properties of capacity-achieving codes for memoryless channels for the converse are proved, which might be of independent interest.
An Analysis of Object Representations in Deep Visual Trackers
Venue: arXiv cs.CV 2020
Year: 2020

Fully convolutional deep correlation networks are integral components of state-of the-art approaches to single object visual tracking. It is commonly assumed that these networks perform tracking by detection by matching features of the object instance with features of the entire frame. Strong architectural priors and conditioning on the object representation is thought to encourage this tracking strategy. Despite these strong priors, we show that deep trackers often default to tracking by saliency detection - without relying on the object instance representation. Our analysis shows that despite being a useful prior, salience detection can prevent the emergence of more robust tracking strategies in deep networks. This leads us to introduce an auxiliary detection task that encourages more discriminative object representations that improve tracking performance.
Generating Object Stamps
Venue: arXiv cs.CV 2020
Year: 2020

We present an algorithm to generate diverse foreground objects and composite them into background images using a GAN architecture. Given an object class, a user-provided bounding box, and a background image, we first use a mask generator to create an object shape, and then use a texture generator to fill the mask such that the texture integrates with the background. By separating the problem of object insertion into these two stages, we show that our model allows us to improve the realism of diverse object generation that also agrees with the provided background image. Our results on the challenging COCO dataset show improved overall quality and diversity compared to state-of-the-art object insertion approaches.
iDLG: Improved Deep Leakage from Gradients
Venue: arXiv cs.LG 2020
Year: 2020

It is widely believed that sharing gradients will not leak private training data in distributed learning systems such as Collaborative Learning and Federated Learning, etc. Recently, Zhu et al. presented an approach which shows the possibility to obtain private training data from the publicly shared gradients. In their Deep Leakage from Gradient (DLG) method, they synthesize the dummy data and corresponding labels with the supervision of shared gradients. However, DLG has difficulty in convergence and discovering the ground-truth labels consistently. In this paper, we find that sharing gradients definitely leaks the ground-truth labels. We propose a simple but reliable approach to extract accurate data from the gradients. Particularly, our approach can certainly extract the ground-truth labels as opposed to DLG, hence we name it Improved DLG (iDLG). Our approach is valid for any differentiable model trained with cross-entropy loss over one-hot labels. We mathematically illustrate how our method can extract ground-truth labels from the gradients and empirically demonstrate the advantages over DLG.
Comments on "Physical-layer cryptography through massive MIMO"
Venue: arXiv cs.IT 2020
Year: 2020

We present two attacks on two different versions of physical layer cryptography schemes based on massive multiple-input multiple-output (MIMO). Both cryptosystems employ a singular value decomposition (SVD) precoding technique. For the first one, we show that the eavesdropper (who knows its own channel and the channel between legitimate users) can decrypt the information data under the same condition as the legitimate receiver. We study the signal-to-noise advantage ratio for decoding by the legitimate user over the eavesdropper in a more generalized scheme when an arbitrary precoder at the transmitter is employed. On the negative side, we show that if the eavesdropper uses a number of receive antennas much larger than the number of legitimate user antennas, then there is no advantage, independent of the precoding scheme employed at the transmitter. On the positive side, for the case where the adversary is limited to have the same number of antennas as legitimate users, we give an $O\left(n^2\right)$ upper bound on the advantage and show that this bound can be approached using an inverse precoder. For the second cryptosystem, we show that the required security conditions prevent the legitimate user from decoding the plaintext uniquely.
Techniques d'anonymisation tabulaire : concepts et mise en oeuvre
Venue: arXiv cs.CR 2020
Year: 2020

In this document, we present a state of the art of anonymization techniques for classical tabular datasets. This article is geared towards a general public having some knowledge of mathematics and computer science, but with no need for specific knowledge in anonymization. The objective of this document it to explain anonymization concepts in order to be able to sanitize a dataset and compute reindentification risk. The document contains a large number of examples to help understand the calculations. ----- Dans ce document, nous présentons l'état de l'art des techniques d'anonymisation pour des bases de données classiques (i.e. des tables), à destination d'un public technique ayant une formation universitaire de base en mathématiques et informatique, mais non spécialiste. L'objectif de ce document est d'expliquer les concepts permettant de réaliser une anonymisation de données tabulaires, et de calculer les risques de réidentification. Le document est largement composé d'exemples permettant au lecteur de comprendre comment mettre en oeuvre les calculs.
REST: A Thread Embedding Approach for Identifying and Classifying User-specified Information in Security Forums
Venue: arXiv cs.CL 2020
Year: 2020

How can we extract useful information from a security forum? We focus on identifying threads of interest to a security professional: (a) alerts of worrisome events, such as attacks, (b) offering of malicious services and products, (c) hacking information to perform malicious acts, and (d) useful security-related experiences. The analysis of security forums is in its infancy despite several promising recent works. Novel approaches are needed to address the challenges in this domain: (a) the difficulty in specifying the "topics" of interest efficiently, and (b) the unstructured and informal nature of the text. We propose, REST, a systematic methodology to: (a) identify threads of interest based on a, possibly incomplete, bag of words, and (b) classify them into one of the four classes above. The key novelty of the work is a multi-step weighted embedding approach: we project words, threads and classes in appropriate embedding spaces and establish relevance and similarity there. We evaluate our method with real data from three security forums with a total of 164k posts and 21K threads. First, REST robustness to initial keyword selection can extend the user-provided keyword set and thus, it can recover from missing keywords. Second, REST categorizes the threads into the classes of interest with superior accuracy compared to five other methods: REST exhibits an accuracy between 63.3-76.9%. We see our approach as a first step for harnessing the wealth of information of online forums in a user-friendly way, since the user can loosely specify her keywords of interest.
XOR-based Source Routing
Venue: arXiv cs.NI 2020
Year: 2020

We introduce a XOR-based source routing (XSR) scheme as a novel approach to enable fast forwarding and low-latency communications. XSR uses linear encoding operation to both 1)~build the path labels of unicast and multicast data transfers; 2)~perform fast computational efficient routing decisions compared to standard table lookup procedure without any packet modification all along the path. XSR specifically focuses on decreasing the complexity of forwarding router operations. This allows packet switches (e.g, link-layer switch or router) to perform only simple linear operations over a binary vector label which embeds the path. XSR provides the building blocks to speed up the forwarding plane and can be applied to different data planes such as MPLS or IPv6. Compared to recent approaches based on modular arithmetic, XSR computes the smallest label possible and presents strong scalable properties allowing to be deployed over any kind of core vendor or datacenter networks. At last but not least, the same computed label can be used interchangeably to cross the path forward or reverse in the context of unicast communication.
Understanding the Use of Crisis Informatics Technology among Older Adults
Venue: arXiv cs.HC 2020
Year: 2020

Mass emergencies increasingly pose significant threats to human life, with a disproportionate burden being incurred by older adults. Research has explored how mobile technology can mitigate the effects of mass emergencies. However, less work has examined how mobile technologies support older adults during emergencies, considering their unique needs. To address this research gap, we interviewed 16 older adults who had recent experience with an emergency evacuation to understand the perceived value of using mobile technology during emergencies. We found that there was a lack of awareness and engagement with existing crisis apps. Our findings characterize the ways in which our participants did and did not feel crisis informatics tools address human values, including basic needs and esteem needs. We contribute an understanding of how older adults used mobile technology during emergencies and their perspectives on how well such tools address human values.
Practical method to reclassify Web of Science articles into unique subject categories and broad disciplines
Venue: arXiv cs.DL 2020
Year: 2020

Classification of bibliographic items into subjects and disciplines in large databases is essential for many quantitative science studies. The Web of Science classification of journals into ~250 subject categories, which has served as a basis for many studies, is known to have some fundamental problems and several practical limitations that may affect the results from such studies. Here we present an easily reproducible method to perform reclassification of the Web of Science into existing subject categories and into 14 broad areas. Our reclassification is at a level of articles, so it preserves disciplinary differences that may exist among individual articles published in the same journal. Reclassification also eliminates ambiguous (multiple) categories that are found for 50% of items, and assigns a discipline/field category to all articles that come from broad-coverage journals such as Nature and Science. The correctness of the assigned subject categories is evaluated manually and is found to be ~95%.
Toward Generalized Clustering through an One-Dimensional Approach
Venue: arXiv cs.CV 2020
Year: 2020

After generalizing the concept of clusters to incorporate clusters that are linked to other clusters through some relatively narrow bridges, an approach for detecting patches of separation between these clusters is developed based on an agglomerative clustering, more specifically the single-linkage, applied to one-dimensional slices obtained from respective feature spaces. The potential of this method is illustrated with respect to the analyses of clusterless uniform and normal distributions of points, as well as a one-dimensional clustering model characterized by two intervals with high density of points separated by a less dense interstice. This partial clustering method is then considered as a means of feature selection and cluster identification, and two simple but potentially effective respective methods are described and illustrated with respect to some hypothetical situations.
Learning landmark guided embeddings for animal re-identification
Venue: arXiv cs.CV 2020
Year: 2020

Re-identification of individual animals in images can be ambiguous due to subtle variations in body markings between different individuals and no constraints on the poses of animals in the wild. Person re-identification is a similar task and it has been approached with a deep convolutional neural network (CNN) that learns discriminative embeddings for images of people. However, learning discriminative features for an individual animal is more challenging than for a person's appearance due to the relatively small size of ecological datasets compared to labelled datasets of person's identities. We propose to improve embedding learning by exploiting body landmarks information explicitly. Body landmarks are provided to the input of a CNN as confidence heatmaps that can be obtained from a separate body landmark predictor. The model is encouraged to use heatmaps by learning an auxiliary task of reconstructing input heatmaps. Body landmarks guide a feature extraction network to learn the representation of a distinctive pattern and its position on the body. We evaluate the proposed method on a large synthetic dataset and a small real dataset. Our method outperforms the same model without body landmarks input by 26% and 18% on the synthetic and the real datasets respectively. The method is robust to noise in input coordinates and can tolerate an error in coordinates up to 10% of the image size.
Macroscopic Analysis of Vector Approximate Message Passing in a Model Mismatch Setting
Venue: arXiv cs.IT 2020
Year: 2020

Vector approximate message passing (VAMP) is an efficient approximate inference algorithm used for generalized linear models. Although VAMP exhibits excellent performance, particularly when measurement matrices are sampled from rotationally invariant ensembles, existing convergence and performance analyses have been limited mostly to cases in which the correct posterior distribution is available. Here, we extend the analyses for cases in which the correct posterior distribution is not used in the inference stage. We derive state evolution equations, which macroscopically describe the dynamics of VAMP, and show that their fixed point is consistent with the replica symmetric solution obtained by the replica method of statistical mechanics. We also show that the fixed point of VAMP can exhibit a microscopic instability, the critical condition of which agrees with that for breaking the replica symmetry. The results of numerical experiments support our findings.
Best Relay Selection in Gaussian Half-Duplex Diamond Networks
Venue: arXiv cs.IT 2020
Year: 2020

This paper considers Gaussian half-duplex diamond $n$-relay networks, where a source communicates with a destination by hopping information through one layer of $n$ non-communicating relays that operate in half-duplex. The main focus consists of investigating the following question: What is the contribution of a single relay on the approximate capacity of the entire network? In particular, approximate capacity refers to a quantity that approximates the Shannon capacity within an additive gap which only depends on $n$, and is independent of the channel parameters. This paper answers the above question by providing a fundamental bound on the ratio between the approximate capacity of the highest-performing single relay and the approximate capacity of the entire network, for any number $n$. Surprisingly, it is shown that such a ratio guarantee is $f = 1/(2+2\cos(2π/(n+2)))$, that is a sinusoidal function of $n$, which decreases as $n$ increases. It is also shown that the aforementioned ratio guarantee is tight, i.e., there exist Gaussian half-duplex diamond $n$-relay networks, where the highest-performing relay has an approximate capacity equal to an $f$ fraction of the approximate capacity of the entire network.
Multirobot Coverage of Linear Modular Environments
Venue: arXiv cs.MA 2020
Year: 2020

Multirobot systems for covering environments are increasingly used in applications like cleaning, industrial inspection, patrolling, and precision agriculture. The problem of covering a given environment using multiple robots can be naturally formulated and studied as a multi-Traveling Salesperson Problem (mTSP). In a mTSP, the environment is represented as a graph and the goal is to find tours (starting and ending at the same depot) for the robots in order to visit all the vertices with minimum global cost, namely the length of the longest tour. The mTSP is an NP-hard problem for which several approximation algorithms have been proposed. These algorithms usually assume generic environments, but tighter approximation bounds can be reached focusing on specific environments. In this paper, we address the case of environments composed of sub-parts, called modules, that can be reached from each other only through some linking structures. Examples are multi-floor buildings, in which the modules are the floors and the linking structures are the staircases or the elevators, and floors of large hotels or hospitals, in which the modules are the rooms and the linking structures are the corridors. We focus on linear modular environments, with the modules organized sequentially, presenting an efficient (with polynomial worst-case time complexity) algorithm that finds a solution for the mTSP whose cost is within a bounded distance from the cost of the optimal solution. The main idea of our algorithm is to allocate disjoint "blocks" of adjacent modules to the robots, in such a way that each module is covered by only one robot. We experimentally compare our algorithm against some state-of-the-art algorithms for solving mTSPs in generic environments and show that it is able to provide solutions with lower makespan and spending a computing time several orders of magnitude shorter.
Conversational Search for Learning Technologies
Venue: arXiv cs.AI 2020
Year: 2020

Conversational search is based on a user-system cooperation with the objective to solve an information-seeking task. In this report, we discuss the implication of such cooperation with the learning perspective from both user and system side. We also focus on the stimulation of learning through a key component of conversational search, namely the multimodality of communication way, and discuss the implication in terms of information retrieval. We end with a research road map describing promising research directions and perspectives.
LibreSocial: A Peer-to-Peer Framework for Online Social Networks
Venue: arXiv cs.SI 2020
Year: 2020

Distributed online social networks (DOSNs) were first proposed to solve the problem of privacy, security and scalability. A significant amount of research was undertaken to offer viable DOSN solutions that were capable of competing with the existing centralized OSN applications such as Facebook, LinkedIn and Instagram. This research led to the emergence of the use of peer-to-peer (P2P) networks as a possible solution, upon which several OSNs such as LifeSocial.KOM, Safebook, PeerSoN among others were based. In this paper, we define the basic requirements for a P2P OSN. We then revisit one of the first P2P-based OSNs, LifeSocial.KOM, that is now called LibreSocial, which evolved in the past years to address the challenges of running a completely decentralized social network. Over the course of time, several essential new technologies have been incorporated within LibreSocial for better functionalities. We describe the architecture and each individual component of LibreSocial and point out how LibreSocial meets the basic requirements for a fully functional distributed OSN.
Closed-loop deep learning: generating forward models with back-propagation
Venue: arXiv cs.LG 2020
Year: 2020

A reflex is a simple closed loop control approach which tries to minimise an error but fails to do so because it will always react too late. An adaptive algorithm can use this error to learn a forward model with the help of predictive cues. For example a driver learns to improve their steering by looking ahead to avoid steering in the last minute. In order to process complex cues such as the road ahead deep learning is a natural choice. However, this is usually only achieved indirectly by employing deep reinforcement learning having a discrete state space. Here, we show how this can be directly achieved by embedding deep learning into a closed loop system and preserving its continuous processing. We show specifically how error back-propagation can be achieved in z-space and in general how gradient based approaches can be analysed in such closed loop scenarios. The performance of this learning paradigm is demonstrated using a line-follower both in simulation and on a real robot that show very fast and continuous learning.