OpenRaiser/Intern-Atlas huggingface dataset:
Parallel and Distributed Algorithms for the housing allocation Problem
Venue: arXiv cs.DC 2019
Year: 2019

We give parallel and distributed algorithms for the housing allocation problem. In this problem, there is a set of agents and a set of houses. Each agent has a strict preference list for a subset of houses. We need to find a matching such that some criterion is optimized. One such criterion is Pareto Optimality. A matching is Pareto optimal if no coalition of agents can be strictly better off by exchanging houses among themselves. We also study the housing market problem, a variant of the housing allocation problem, where each agent initially owns a house. In addition to Pareto optimality, we are also interested in finding the core of a housing market. A matching is in the core if there is no coalition of agents that can be better off by breaking away from other agents and switching houses only among themselves. In the first part of this work, we show that computing a Pareto optimal matching of a house allocation is in {\bf CC} and computing the core of a housing market is {\bf CC}-hard. Given a matching, we also show that verifying whether it is in the core can be done in {\bf NC}. We then give an algorithm to show that computing a maximum Pareto optimal matching for the housing allocation problem is in {\bf RNC}^2 and quasi-{\bf NC}^2. In the second part of this work, we present a distributed version of the top trading cycle algorithm for finding the core of a housing market. To that end, we first present two algorithms for finding all the disjoint cycles in a functional graph: a Las Vegas algorithm which terminates in $O(\log l)$ rounds with high probability, where $l$ is the length of the longest cycle, and a deterministic algorithm which terminates in $O(\log^* n \log l)$ rounds, where $n$ is the number of nodes in the graph. Both algorithms work in the synchronous distributed model and use messages of size $O(\log n)$.
Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization
Venue: arXiv cs.DS 2019
Year: 2019

A matching cut is a partition of the vertex set of a graph into two sets $A$ and $B$ such that each vertex has at most one neighbor in the other side of the cut. The MATCHING CUT problem asks whether a graph has a matching cut, and has been intensively studied in the literature. Motivated by a question posed by Komusiewicz et al. [IPEC 2018], we introduce a natural generalization of this problem, which we call $d$-CUT: for a positive integer $d$, a $d$-cut is a bipartition of the vertex set of a graph into two sets $A$ and $B$ such that each vertex has at most $d$ neighbors across the cut. We generalize (and in some cases, improve) a number of results for the MATCHING CUT problem. Namely, we begin with an NP-hardness reduction for $d$-CUT on $(2d+2)$-regular graphs and a polynomial algorithm for graphs of maximum degree at most $d+2$. The degree bound in the hardness result is unlikely to be improved, as it would disprove a long-standing conjecture in the context of internal partitions. We then give FPT algorithms for several parameters: the maximum number of edges crossing the cut, treewidth, distance to cluster, and distance to co-cluster. In particular, the treewidth algorithm improves upon the running time of the best known algorithm for MATCHING CUT. Our main technical contribution, building on the techniques of Komusiewicz et al. [IPEC 2018], is a polynomial kernel for $d$-CUT for every positive integer $d$, parameterized by the distance to a cluster graph. We also rule out the existence of polynomial kernels when parameterizing simultaneously by the number of edges crossing the cut, the treewidth, and the maximum degree. Finally, we provide an exact exponential algorithm slightly faster than the naive brute force approach running in time $O^*(2^n)$.
Entanglement, and unsorted database search in noise-based logic
Venue: arXiv cs.ET 2019
Year: 2019

We explore the collapse of "wavefunction" and the measurement of entanglement in the superpositions of hyperspace vectors in classical physical instantaneous-noise-based logic (INBL). We find both similarities with and major differences from the related properties of quantum systems. Two search algorithms utilizing the observed features are introduced. For the first one we assume an unsorted names database set up by Alice that is a superposition (unknown by Bob) of up to n=2^N strings; those we call names. Bob has access to the superposition wave and to the 2N reference noises of the INBL system of N noise bits. For Bob, to decide if a given name x is included in the superposition, once the search has begun, it takes N switching operations followed by a single measurement of the superposition wave. Thus the time and hardware complexity of the search algorithm is O[log(n)] which indicates an exponential speedup compared to Grover's quantum algorithm in a corresponding setting. An extra advantage is that the error probability of the search is zero. Moreover, the scheme can also check the existence of a fraction of a string, or several separate string fractions embedded in an arbitrarily long, arbitrary string. In the second algorithm, we expand the above scheme to a phonebook with n names and s phone numbers. When the names and numbers have the same bit resolution, once the search has begun, the time and hardware complexity of this search algorithm is O[log(n)]. In the case of one-to-one correspondence between names and phone numbers (n=s), the algorithm offers inverse phonebook search too. The error probability of this search algorithm is also zero.
Regression from Dependent Observations
Venue: arXiv cs.LG 2019
Year: 2019

The standard linear and logistic regression models assume that the response variables are independent, but share the same linear relationship to their corresponding vectors of covariates. The assumption that the response variables are independent is, however, too strong. In many applications, these responses are collected on nodes of a network, or some spatial or temporal domain, and are dependent. Examples abound in financial and meteorological applications, and dependencies naturally arise in social networks through peer effects. Regression with dependent responses has thus received a lot of attention in the Statistics and Economics literature, but there are no strong consistency results unless multiple independent samples of the vectors of dependent responses can be collected from these models. We present computationally and statistically efficient methods for linear and logistic regression models when the response variables are dependent on a network. Given one sample from a networked linear or logistic regression model and under mild assumptions, we prove strong consistency results for recovering the vector of coefficients and the strength of the dependencies, recovering the rates of standard regression under independent observations. We use projected gradient descent on the negative log-likelihood, or negative log-pseudolikelihood, and establish their strong convexity and consistency using concentration of measure for dependent random variables.
Learning to Evolve
Venue: arXiv cs.NE 2019
Year: 2019

Evolution and learning are two of the fundamental mechanisms by which life adapts in order to survive and to transcend limitations. These biological phenomena inspired successful computational methods such as evolutionary algorithms and deep learning. Evolution relies on random mutations and on random genetic recombination. Here we show that learning to evolve, i.e. learning to mutate and recombine better than at random, improves the result of evolution in terms of fitness increase per generation and even in terms of attainable fitness. We use deep reinforcement learning to learn to dynamically adjust the strategy of evolutionary algorithms to varying circumstances. Our methods outperform classical evolutionary algorithms on combinatorial and continuous optimization problems.
Fairness across Network Positions in Cyberbullying Detection Algorithms
Venue: arXiv cs.SI 2019
Year: 2019

Cyberbullying, which often has a deeply negative impact on the victim, has grown as a serious issue in Online Social Networks. Recently, researchers have created automated machine learning algorithms to detect Cyberbullying using social and textual features. However, the very algorithms that are intended to fight off one threat (cyberbullying) may inadvertently be falling prey to another important threat (bias of the automatic detection algorithms). This is exacerbated by the fact that while the current literature on algorithmic fairness has multiple empirical results, metrics, and algorithms for countering bias across immediately observable demographic characteristics (e.g. age, race, gender), there have been no efforts at empirically quantifying the variation in algorithmic performance based on the network role or position of individuals. We audit an existing cyberbullying algorithm using Twitter data for disparity in detection performance based on the network centrality of the potential victim and then demonstrate how this disparity can be countered using an Equalized Odds post-processing technique. The results pave way for more accurate and fair cyberbullying detection algorithms.
Adaptive Guaranteed-Performance Consensus Control for Multiagent Systems With an Adjustable Convergence Speed
Venue: arXiv cs.SY 2019
Year: 2019

Adaptive guaranteed-performance consensus control problems for multi-agent systems are investigated, where the adjustable convergence speed is discussed. This paper firstly proposes a novel adaptive guaranteed-performance consensus protocol, where the communication weights can be adaptively regulated. By the state space decomposition method and the stability theory, sufficient conditions for guaranteed-performance consensus are obtained, as well as the guaranteed-performance cost. Moreover, since the convergence speed is usually adjusted by changing the algebraic connectivity in existing works, which increases the communication burden and the load of the controller, and the system topology is always given in practical applications, the lower bound of the convergence coefficient for multi-agent systems with the adaptive guaranteed-performance consensus protocol is deduced, which is linearly adjustable approximately by changing the adaptive control gain. Finally, simulation examples are introduced to demonstrate theoretical results.
Path Design for Cellular-Connected UAV with Reinforcement Learning
Venue: arXiv cs.NI 2019
Year: 2019

This paper studies the path design problem for cellular-connected unmanned aerial vehicle (UAV), which aims to minimize its mission completion time while maintaining good connectivity with the cellular network. We first argue that the conventional path design approach via formulating and solving optimization problems faces several practical challenges, and then propose a new reinforcement learning-based UAV path design algorithm by applying \emph{temporal-difference} method to directly learn the \emph{state-value function} of the corresponding Markov Decision Process. The proposed algorithm is further extended by using linear function approximation with tile coding to deal with large state space. The proposed algorithms only require the raw measured or simulation-generated signal strength as the input and are suitable for both online and offline implementations. Numerical results show that the proposed path designs can successfully avoid the coverage holes of cellular networks even in the complex urban environment.
Grand Challenge of 106-Point Facial Landmark Localization
Venue: arXiv cs.CV 2019
Year: 2019

Facial landmark localization is a very crucial step in numerous face related applications, such as face recognition, facial pose estimation, face image synthesis, etc. However, previous competitions on facial landmark localization (i.e., the 300-W, 300-VW and Menpo challenges) aim to predict 68-point landmarks, which are incompetent to depict the structure of facial components. In order to overcome this problem, we construct a challenging dataset, named JD-landmark. Each image is manually annotated with 106-point landmarks. This dataset covers large variations on pose and expression, which brings a lot of difficulties to predict accurate landmarks. We hold a 106-point facial landmark localization competition1 on this dataset in conjunction with IEEE International Conference on Multimedia and Expo (ICME) 2019. The purpose of this competition is to discover effective and robust facial landmark localization approaches.
Methodology for accurately assessing the quality perceived by users on 360VR contents
Venue: arXiv cs.MM 2019
Year: 2019

To properly evaluate the performance of 360VR-specific encoding and transmission schemes, and particularly of the solutions based on viewport adaptation, it is necessary to consider not only the bandwidth saved, but also the quality of the portion of the scene actually seen by users over time. With this motivation, we propose a robust, yet flexible methodology for accurately assessing the quality within the viewport along the visualization session. This procedure is based on a complete analysis of the geometric relations involved. Moreover, the designed methodology allows for both offline and online usage thanks to the use of different approximations. In this way, our methodology can be used regardless of the approach to properly evaluate the implemented strategy, obtaining a fairer comparison between them.
Enhanced Performance and Privacy for TLS over TCP Fast Open
Venue: arXiv cs.CR 2019
Year: 2019

Small TCP flows make up the majority of web flows. For them, the TCP three-way handshake induces significant delay overhead. The TCP Fast Open (TFO) protocol can significantly decrease this delay via zero round-trip time (0-RTT) handshakes for all TCP handshakes that follow a full initial handshake to the same host. However, this comes at the cost of privacy limitations and also has some performance limitations. In this paper, we investigate the TFP deployment on popular websites and browsers. We found that a client revisiting a web site for the first time fails to use an abbreviated TFO handshake in 40% of all cases due to web server load-balancing using multiple IP addresses. Our analysis further reveals significant privacy problems of the protocol design and implementation. Network-based attackers and online trackers can exploit TFO to track the online activities of users. As a countermeasure, we introduce a novel protocol called TCP Fast Open Privacy (FOP). TCP FOP prevents tracking by network attackers and impedes third-party tracking, while still allowing 0-RTT handshakes as in TFO. As a proof-of-concept, we have implemented the proposed protocol for the Linux kernel and a TLS library. Our measurements indicate that TCP FOP outperforms TLS over TFO when websites are served from multiple IP addresses.
D2-Net: A Trainable CNN for Joint Detection and Description of Local Features
Venue: arXiv cs.CV 2019
Year: 2019

In this work we address the problem of finding reliable pixel-level correspondences under difficult imaging conditions. We propose an approach where a single convolutional neural network plays a dual role: It is simultaneously a dense feature descriptor and a feature detector. By postponing the detection to a later stage, the obtained keypoints are more stable than their traditional counterparts based on early detection of low-level structures. We show that this model can be trained using pixel correspondences extracted from readily available large-scale SfM reconstructions, without any further annotations. The proposed method obtains state-of-the-art performance on both the difficult Aachen Day-Night localization dataset and the InLoc indoor localization benchmark, as well as competitive performance on other benchmarks for image matching and 3D reconstruction.
TRIDEnT: Building Decentralized Incentives for Collaborative Security
Venue: arXiv cs.CR 2019
Year: 2019

Sophisticated mass attacks, especially when exploiting zero-day vulnerabilities, have the potential to cause destructive damage to organizations and critical infrastructure. To timely detect and contain such attacks, collaboration among the defenders is critical. By correlating real-time detection information (alerts) from multiple sources (collaborative intrusion detection), defenders can detect attacks and take the appropriate defensive measures in time. However, although the technical tools to facilitate collaboration exist, real-world adoption of such collaborative security mechanisms is still underwhelming. This is largely due to a lack of trust and participation incentives for companies and organizations. This paper proposes TRIDEnT, a novel collaborative platform that aims to enable and incentivize parties to exchange network alert data, thus increasing their overall detection capabilities. TRIDEnT allows parties that may be in a competitive relationship, to selectively advertise, sell and acquire security alerts in the form of (near) real-time peer-to-peer streams. To validate the basic principles behind TRIDEnT, we present an intuitive game-theoretic model of alert sharing, that is of independent interest, and show that collaboration is bound to take place infinitely often. Furthermore, to demonstrate the feasibility of our approach, we instantiate our design in a decentralized manner using Ethereum smart contracts and provide a fully functional prototype.
AI Enabling Technologies: A Survey
Venue: arXiv cs.AI 2019
Year: 2019

Artificial Intelligence (AI) has the opportunity to revolutionize the way the United States Department of Defense (DoD) and Intelligence Community (IC) address the challenges of evolving threats, data deluge, and rapid courses of action. Developing an end-to-end artificial intelligence system involves parallel development of different pieces that must work together in order to provide capabilities that can be used by decision makers, warfighters and analysts. These pieces include data collection, data conditioning, algorithms, computing, robust artificial intelligence, and human-machine teaming. While much of the popular press today surrounds advances in algorithms and computing, most modern AI systems leverage advances across numerous different fields. Further, while certain components may not be as visible to end-users as others, our experience has shown that each of these interrelated components play a major role in the success or failure of an AI system. This article is meant to highlight many of these technologies that are involved in an end-to-end AI system. The goal of this article is to provide readers with an overview of terminology, technical details and recent highlights from academia, industry and government. Where possible, we indicate relevant resources that can be used for further reading and understanding.
Multiplicação de matrizes: uma comparação entre as abordagens sequencial (CPU) e paralela (GPU)
Venue: arXiv cs.PF 2019
Year: 2019

Designing problems using matrices is very important in Computer Science. Fields like graph computer, graphs theory, and machine learning use matrices very often to solve their own problems. The most often matrix operation is the multiplication. It may be time-consuming if the matrices to be multiplied are large. For this reason, the parallel computer became a must to tackle this problem. In this report, it is presented a comparison between sequential and parallel approaches to computing the matrix multiplication using CUDA and openMP. The results show the importance of parallelizing mainly when the matrices are large. A modelagem de problemas utilizando matrizes é de extrema importância para Ciência da Computação. Áreas como computação gráfica, grafos e aprendizado de máquina utilizam matrizes com alta frequência para solucionar seus respectivos problemas. Dessa forma, operar matrizes de maneira eficiente é muito importante para o desempenho de algoritmos. Uma das operações de matrizes mais utilizadas é a multiplicação, que se torna um empecilho para o desempenho computacional de algoritmos na medida que o tamanho das matrizes a serem multiplicadas aumentam. Por conta disso, a computação paralela se tornou uma solução padrão para abordar tal problema. Neste trabalho é apresentado uma comparação entre as abordagens sequencial e paralela para multiplicação de matrizes utilizando CUDA e OpenMP. O resultado da análise realizada entre o tamanho da matriz e o desempenho da multiplicação mostra a importância da paralelização principalmente para matrizes de ordem elevada.
Forecasting Pedestrian Trajectory with Machine-Annotated Training Data
Venue: arXiv cs.CV 2019
Year: 2019

Reliable anticipation of pedestrian trajectory is imperative for the operation of autonomous vehicles and can significantly enhance the functionality of advanced driver assistance systems. While significant progress has been made in the field of pedestrian detection, forecasting pedestrian trajectories remains a challenging problem due to the unpredictable nature of pedestrians and the huge space of potentially useful features. In this work, we present a deep learning approach for pedestrian trajectory forecasting using a single vehicle-mounted camera. Deep learning models that have revolutionized other areas in computer vision have seen limited application to trajectory forecasting, in part due to the lack of richly annotated training data. We address the lack of training data by introducing a scalable machine annotation scheme that enables our model to be trained using a large dataset without human annotation. In addition, we propose Dynamic Trajectory Predictor (DTP), a model for forecasting pedestrian trajectory up to one second into the future. DTP is trained using both human and machine-annotated data, and anticipates dynamic motion that is not captured by linear models. Experimental evaluation confirms the benefits of the proposed model.
Deep AutoEncoder-based Lossy Geometry Compression for Point Clouds
Venue: arXiv cs.CV 2019
Year: 2019

Point cloud is a fundamental 3D representation which is widely used in real world applications such as autonomous driving. As a newly-developed media format which is characterized by complexity and irregularity, point cloud creates a need for compression algorithms which are more flexible than existing codecs. Recently, autoencoders(AEs) have shown their effectiveness in many visual analysis tasks as well as image compression, which inspires us to employ it in point cloud compression. In this paper, we propose a general autoencoder-based architecture for lossy geometry point cloud compression. To the best of our knowledge, it is the first autoencoder-based geometry compression codec that directly takes point clouds as input rather than voxel grids or collections of images. Compared with handcrafted codecs, this approach adapts much more quickly to previously unseen media contents and media formats, meanwhile achieving competitive performance. Our architecture consists of a pointnet-based encoder, a uniform quantizer, an entropy estimation block and a nonlinear synthesis transformation module. In lossy geometry compression of point cloud, results show that the proposed method outperforms the test model for categories 1 and 3 (TMC13) published by MPEG-3DG group on the 125th meeting, and on average a 73.15\% BD-rate gain is achieved.