OpenRaiser/Intern-Atlas huggingface dataset:
Performance Analysis of a Device-to-Device Offloading Scheme in a Vehicular Network Environment
Venue: arXiv cs.NI 2020
Year: 2020

We consider a scheme for offloading the delivery of contents to mobile devices in a vehicular networking scenario. Each content can be delivered to the requesting device either by a neighboring device or, at the expiration of a maximum delay, by the network infrastructure nodes. We compute the analytical expression of the probability that the content delivery is offloaded through a Device-to-Device (D2D) communication as a function of the maximum transmission range allowed for D2D communications, the content popularity, and the vehicles speed. We show that, using the model, it is possible to identify the optimal maximum transmission range, which minimizes the total energy consumption (of the infrastructure plus mobile devices).
A Distributed-Memory Algorithm for Computing a Heavy-Weight Perfect Matching on Bipartite Graphs
Venue: arXiv cs.DC 2020
Year: 2020

We design and implement an efficient parallel algorithm for finding a perfect matching in a weighted bipartite graph such that weights on the edges of the matching are large. This problem differs from the maximum weight matching problem, for which scalable approximation algorithms are known. It is primarily motivated by finding good pivots in scalable sparse direct solvers before factorization. Due to the lack of scalable alternatives, distributed solvers use sequential implementations of maximum weight perfect matching algorithms, such as those available in MC64. To overcome this limitation, we propose a fully parallel distributed memory algorithm that first generates a perfect matching and then iteratively improves the weight of the perfect matching by searching for weight-increasing cycles of length four in parallel. For most practical problems the weights of the perfect matchings generated by our algorithm are very close to the optimum. An efficient implementation of the algorithm scales up to 256 nodes (17,408 cores) on a Cray XC40 supercomputer and can solve instances that are too large to be handled by a single node using the sequential algorithm.
PrivPy: Enabling Scalable and General Privacy-Preserving Machine Learning
Venue: arXiv cs.CR 2020
Year: 2020

We introduce PrivPy, a practical privacy-preserving collaborative computation framework, especially optimized for machine learning tasks. PrivPy provides an easy-to-use and highly compatible Python programming front-end which supports high-level array operations and different secure computation engines to allow for security assumptions and performance trade-offs. With PrivPy, programmers can write modern machine learning algorithms conveniently and efficiently in Python. We also design and implement a new efficient computation engine, with which people can use competing cloud providers to efficiently perform general arithmetics over real numbers. We demonstrate the usability and scalability of PrivPy using common machine learning models (e.g. logistic regression and convolutional neural networks) and real-world datasets (including a 5000-by-1-million matrix).
Call-by-name Gradual Type Theory
Venue: arXiv cs.PL 2020
Year: 2020

We present gradual type theory, a logic and type theory for call-by-name gradual typing. We define the central constructions of gradual typing (the dynamic type, type casts and type error) in a novel way, by universal properties relative to new judgments for gradual type and term dynamism, which were developed in blame calculi and to state the "gradual guarantee" theorem of gradual typing. Combined with the ordinary extensionality ($η$) principles that type theory provides, we show that most of the standard operational behavior of casts is uniquely determined by the gradual guarantee. This provides a semantic justification for the definitions of casts, and shows that non-standard definitions of casts must violate these principles. Our type theory is the internal language of a certain class of preorder categories called equipments. We give a general construction of an equipment interpreting gradual type theory from a 2-category representing non-gradual types and programs, which is a semantic analogue of Findler and Felleisen's definitions of contracts, and use it to build some concrete domain-theoretic models of gradual typing.
Exact algorithms for semidefinite programs with degenerate feasible set
Venue: arXiv cs.SC 2020
Year: 2020

Given symmetric matrices $A_0, A_1, \ldots, A_n$ of size $m$ with rational entries, the set of real vectors $x = (x_1, \ldots, x_n)$ such that the matrix $A_0 + x_1 A_1 + \cdots + x_n A_n$ has non-negative eigenvalues is called a spectrahedron. Minimization of linear functions over spectrahedra is called semidefinite programming. Such problems appear frequently in control theory and real algebra, especially in the context of nonnegativity certificates for multivariate polynomials based on sums of squares. Numerical software for semidefinite programming are mostly based on interior point methods, assuming non-degeneracy properties such as the existence of an interior point in the spectrahedron. In this paper, we design an exact algorithm based on symbolic homotopy for solving semidefinite programs without assumptions on the feasible set, and we analyze its complexity. Because of the exactness of the output, it cannot compete with numerical routines in practice. However, we prove that solving such problems can be done in polynomial time if either $n$ or $m$ is fixed.
Competitive caching with machine learned advice
Venue: arXiv cs.DS 2020
Year: 2020

Traditional online algorithms encapsulate decision making under uncertainty, and give ways to hedge against all possible future events, while guaranteeing a nearly optimal solution as compared to an offline optimum. On the other hand, machine learning algorithms are in the business of extrapolating patterns found in the data to predict the future, and usually come with strong guarantees on the expected generalization error. In this work we develop a framework for augmenting online algorithms with a machine learned oracle to achieve competitive ratios that provably improve upon unconditional worst case lower bounds when the oracle has low error. Our approach treats the oracle as a complete black box, and is not dependent on its inner workings, or the exact distribution of its errors. We apply this framework to the traditional caching problem -- creating an eviction strategy for a cache of size $k$. We demonstrate that naively following the oracle's recommendations may lead to very poor performance, even when the average error is quite low. Instead we show how to modify the Marker algorithm to take into account the oracle's predictions, and prove that this combined approach achieves a competitive ratio that both (i) decreases as the oracle's error decreases, and (ii) is always capped by $O(\log k)$, which can be achieved without any oracle input. We complement our results with an empirical evaluation of our algorithm on real world datasets, and show that it performs well empirically even using simple off-the-shelf predictions.
Security and Privacy Approaches in Mixed Reality: A Literature Survey
Venue: arXiv cs.CR 2020
Year: 2020

Mixed reality (MR) technology development is now gaining momentum due to advances in computer vision, sensor fusion, and realistic display technologies. With most of the research and development focused on delivering the promise of MR, there is only barely a few working on the privacy and security implications of this technology. This survey paper aims to put in to light these risks, and to look into the latest security and privacy work on MR. Specifically, we list and review the different protection approaches that have been proposed to ensure user and data security and privacy in MR. We extend the scope to include work on related technologies such as augmented reality (AR), virtual reality (VR), and human-computer interaction (HCI) as crucial components, if not the origins, of MR, as well as numerous related work from the larger area of mobile devices, wearables, and Internet-of-Things (IoT). We highlight the lack of investigation, implementation, and evaluation of data protection approaches in MR. Further challenges and directions on MR security and privacy are also discussed.
Image Forensics: Detecting duplication of scientific images with manipulation-invariant image similarity
Venue: arXiv cs.CV 2020
Year: 2020

Manipulation and re-use of images in scientific publications is a concerning problem that currently lacks a scalable solution. Current tools for detecting image duplication are mostly manual or semi-automated, despite the availability of an overwhelming target dataset for a learning-based approach. This paper addresses the problem of determining if, given two images, one is a manipulated version of the other by means of copy, rotation, translation, scale, perspective transform, histogram adjustment, or partial erasing. We propose a data-driven solution based on a 3-branch Siamese Convolutional Neural Network. The ConvNet model is trained to map images into a 128-dimensional space, where the Euclidean distance between duplicate images is smaller than or equal to 1, and the distance between unique images is greater than 1. Our results suggest that such an approach has the potential to improve surveillance of the published and in-peer-review literature for image manipulation.
Machine Learning Methods for Data Association in Multi-Object Tracking
Venue: arXiv cs.CV 2020
Year: 2020

Data association is a key step within the multi-object tracking pipeline that is notoriously challenging due to its combinatorial nature. A popular and general way to formulate data association is as the NP-hard multidimensional assignment problem (MDAP). Over the last few years, data-driven approaches to assignment have become increasingly prevalent as these techniques have started to mature. We focus this survey solely on learning algorithms for the assignment step of multi-object tracking, and we attempt to unify various methods by highlighting their connections to linear assignment as well as to the MDAP. First, we review probabilistic and end-to-end optimization approaches to data association, followed by methods that learn association affinities from data. We then compare the performance of the methods presented in this survey, and conclude by discussing future research directions.
A Survey on the Security of Blockchain Systems
Venue: arXiv cs.CR 2020
Year: 2020

Since its inception, the blockchain technology has shown promising application prospects. From the initial cryptocurrency to the current smart contract, blockchain has been applied to many fields. Although there are some studies on the security and privacy issues of blockchain, there lacks a systematic examination on the security of blockchain systems. In this paper, we conduct a systematic study on the security threats to blockchain and survey the corresponding real attacks by examining popular blockchain systems. We also review the security enhancement solutions for blockchain, which could be used in the development of various blockchain systems, and suggest some future directions to stir research efforts into this area.
Epistemic Graphs for Representing and Reasoning with Positive and Negative Influences of Arguments
Venue: arXiv cs.AI 2020
Year: 2020

This paper introduces epistemic graphs as a generalization of the epistemic approach to probabilistic argumentation. In these graphs, an argument can be believed or disbelieved up to a given degree, thus providing a more fine--grained alternative to the standard Dung's approaches when it comes to determining the status of a given argument. Furthermore, the flexibility of the epistemic approach allows us to both model the rationale behind the existing semantics as well as completely deviate from them when required. Epistemic graphs can model both attack and support as well as relations that are neither support nor attack. The way other arguments influence a given argument is expressed by the epistemic constraints that can restrict the belief we have in an argument with a varying degree of specificity. The fact that we can specify the rules under which arguments should be evaluated and we can include constraints between unrelated arguments permits the framework to be more context--sensitive. It also allows for better modelling of imperfect agents, which can be important in multi--agent applications.
Learning Mixtures of Linear Regressions with Nearly Optimal Complexity
Venue: arXiv cs.LG 2020
Year: 2020

Mixtures of Linear Regressions (MLR) is an important mixture model with many applications. In this model, each observation is generated from one of the several unknown linear regression components, where the identity of the generated component is also unknown. Previous works either assume strong assumptions on the data distribution or have high complexity. This paper proposes a fixed parameter tractable algorithm for the problem under general conditions, which achieves global convergence and the sample complexity scales nearly linearly in the dimension. In particular, different from previous works that require the data to be from the standard Gaussian, the algorithm allows the data from Gaussians with different covariances. When the conditional number of the covariances and the number of components are fixed, the algorithm has nearly optimal sample complexity $N = \tilde{O}(d)$ as well as nearly optimal computational complexity $\tilde{O}(Nd)$, where $d$ is the dimension of the data space. To the best of our knowledge, this approach provides the first such recovery guarantee for this general setting.
The geometry of off-the-grid compressed sensing
Venue: arXiv cs.IT 2020
Year: 2020

This paper presents a sharp geometric analysis of the recovery performance of sparse regularization. More specifically, we analyze the BLASSO method which estimates a sparse measure (sum of Dirac masses) from randomized sub-sampled measurements. This is a "continuous", often called off-the-grid, extension of the compressed sensing problem, where the $\ell^1$ norm is replaced by the total variation of measures. This extension is appealing from a numerical perspective because it avoids to discretize the the space by some grid. But more importantly, it makes explicit the geometry of the problem since the positions of the Diracs can now freely move over the parameter space. On a methodological level, our contribution is to propose the Fisher geodesic distance on this parameter space as the canonical metric to analyze super-resolution in a way which is invariant to reparameterization of this space. Switching to the Fisher metric allows us to take into account measurement operators which are not translation invariant, which is crucial for applications such as Laplace inversion in imaging, Gaussian mixtures estimation and training of multilayer perceptrons with one hidden layer. On a theoretical level, our main contribution shows that if the Fisher distance between spikes is larger than a Rayleigh separation constant, then the BLASSO recovers in a stable way a stream of Diracs, provided that the number of measurements is proportional (up to log factors) to the number of Diracs. We measure the stability using an optimal transport distance constructed on top of the Fisher geodesic distance. Our result is (up to log factor) sharp and does not require any randomness assumption on the amplitudes of the underlying measure. Our proof technique relies on an infinite-dimensional extension of the so-called "golfing scheme" which operates over the space of measures and is of general interest.
On the Broadcast Routing Problem in Computer Networks
Venue: arXiv cs.DS 2020
Year: 2020

Given an undirected graph $G = (V, E)$, and a vertex $r\in V$, an $r$-acyclic orientation of $G$ is an orientation $OE$ of the edges of $G$ such that the digraph $OG = (V, OE)$ is acyclic and $r$ is the unique vertex with indegree equal to 0. For $w\in \mathbb{R}^E_+$, $k(G, w)$ is the value of the $w$-maximum packing of $r$-arborescences for all $r\in V$ and all $r$-acyclic orientations $OE$ of $G$. In this case, the Broadcast Routing (in Computers Networks) Problem (BRP) is to compute $k(G, w)$, by finding an optimal $r$ and an optimal $r$-acyclic orientation. BRP is a mathematical formulation of multipath broadcast routing in computer networks. In this paper, we provide a polynomial time algorithm to solve BRP in outerplanar graphs. Outerplanar graphs are encountered in many applications such as computational geometry, robotics, etc.
i3PosNet: Instrument Pose Estimation from X-Ray in temporal bone surgery
Venue: arXiv cs.CV 2020
Year: 2020

Purpose: Accurate estimation of the position and orientation (pose) of surgical instruments is crucial for delicate minimally invasive temporal bone surgery. Current techniques lack in accuracy and/or line-of-sight constraints (conventional tracking systems) or expose the patient to prohibitive ionizing radiation (intra-operative CT). A possible solution is to capture the instrument with a c-arm at irregular intervals and recover the pose from the image. Methods: i3PosNet infers the position and orientation of instruments from images using a pose estimation network. Said framework considers localized patches and outputs pseudo-landmarks. The pose is reconstructed from pseudo-landmarks by geometric considerations. Results: We show i3PosNet reaches errors less than 0.05mm. It outperforms conventional image registration-based approaches reducing average and maximum errors by at least two thirds. i3PosNet trained on synthetic images generalizes to real x-rays without any further adaptation. Conclusion: The translation of Deep Learning based methods to surgical applications is difficult, because large representative datasets for training and testing are not available. This work empirically shows sub-millimeter pose estimation trained solely based on synthetic training data.
Temporal Graph Classes: A View Through Temporal Separators
Venue: arXiv cs.CC 2020
Year: 2020

We investigate the computational complexity of separating two distinct vertices s and z by vertex deletion in a temporal graph. In a temporal graph, the vertex set is fixed but the edges have (discrete) time labels. Since the corresponding Temporal (s, z)-Separation problem is NP-hard, it is natural to investigate whether relevant special cases exist that are computationally tractable. To this end, we study restrictions of the underlying (static) graph---there we observe polynomial-time solvability in the case of bounded treewidth---as well as restrictions concerning the "temporal evolution" along the time steps. Systematically studying partially novel concepts in this direction, we identify sharp borders between tractable and intractable cases.
ZebraLancer: Decentralized Crowdsourcing of Human Knowledge atop Open Blockchain
Venue: arXiv cs.HC 2020
Year: 2020

We design and implement the first private and anonymous decentralized crowdsourcing system ZebraLancer, and overcome two fundamental challenges of decentralizing crowdsourcing, i.e., data leakage and identity breach. First, our outsource-then-prove methodology resolves the tension between the blockchain transparency and the data confidentiality to guarantee the basic utilities/fairness requirements of data crowdsourcing, thus ensuring: (i) a requester will not pay more than what data deserve, according to a policy announced when her task is published via the blockchain; (ii) each worker indeed gets a payment based on the policy, if he submits data to the blockchain; (iii) the above properties are realized not only without a central arbiter, but also without leaking the data to the open blockchain. Second, the transparency of blockchain allows one to infer private information about workers and requesters through their participation history. Simply enabling anonymity is seemingly attempting but will allow malicious workers to submit multiple times to reap rewards. ZebraLancer also overcomes this problem by allowing anonymous requests/submissions without sacrificing accountability. The idea behind is a subtle linkability: if a worker submits twice to a task, anyone can link the submissions, or else he stays anonymous and unlinkable across tasks. To realize this delicate linkability, we put forward a novel cryptographic concept, i.e., the common-prefix-linkable anonymous authentication. We remark the new anonymous authentication scheme might be of independent interest. Finally, we implement our protocol for a common image annotation task and deploy it in a test net of Ethereum. The experiment results show the applicability of our protocol atop the existing real-world blockchain.
Optimal Substring-Equality Queries with Applications to Sparse Text Indexing
Venue: arXiv cs.DS 2020
Year: 2020

We consider the problem of encoding a string of length $n$ from an integer alphabet of size $σ$ so that access and substring equality queries (that is, determining the equality of any two substrings) can be answered efficiently. Any uniquely-decodable encoding supporting access must take $n\logσ+ Θ(\log (n\logσ))$ bits. We describe a new data structure matching this lower bound when $σ\leq n^{O(1)}$ while supporting both queries in optimal $O(1)$ time. Furthermore, we show that the string can be overwritten in-place with this structure. The redundancy of $Θ(\log n)$ bits and the constant query time break exponentially a lower bound that is known to hold in the read-only model. Using our new string representation, we obtain the first in-place subquadratic (indeed, even sublinear in some cases) algorithms for several string-processing problems in the restore model: the input string is rewritable and must be restored before the computation terminates. In particular, we describe the first in-place subquadratic Monte Carlo solutions to the sparse suffix sorting, sparse LCP array construction, and suffix selection problems. With the sole exception of suffix selection, our algorithms are also the first running in sublinear time for small enough sets of input suffixes. Combining these solutions, we obtain the first sublinear-time Monte Carlo algorithm for building the sparse suffix tree in compact space. We also show how to derandomize our algorithms using small space. This leads to the first Las Vegas in-place algorithm computing the full LCP array in $O(n\log n)$ time and to the first Las Vegas in-place algorithms solving the sparse suffix sorting and sparse LCP array construction problems in $O(n^{1.5}\sqrt{\log σ})$ time. Running times of these Las Vegas algorithms hold in the worst case with high probability.
Gerrymandering and Compactness: Implementation Flexibility and Abuse
Venue: arXiv cs.CY 2020
Year: 2020

Political districts may be drawn to favor one group or political party over another, or gerrymandered. A number of measurements have been suggested as ways to detect and prevent such behavior. These measures give concrete axes along which districts and districting plans can be compared. However, measurement values are affected by both noise and the compounding effects of seemingly innocuous implementation decisions. Such issues will arise for any measure. As a case study demonstrating the effect, we show that commonly-used measures of geometric compactness for district boundaries are affected by several factors irrelevant to fairness or compliance with civil rights law. We further show that an adversary could manipulate measurements to affect the assessment of a given plan. This instability complicates using these measurements as legislative or judicial standards to counteract unfair redistricting practices. This paper accompanies the release of packages in C++, Python, and R that correctly, efficiently, and reproducibly calculate a variety of compactness scores.