OpenRaiser/Intern-Atlas huggingface dataset:
Secured Distributed Algorithms Without Hardness Assumptions
Venue: arXiv cs.DC 2021
Year: 2021

We study algorithms in the distributed message-passing model that produce secured output, for an input graph $G$. Specifically, each vertex computes its part in the output, the entire output is correct, but each vertex cannot discover the output of other vertices, with a certain probability. This is motivated by high-performance processors that are embedded nowadays in a large variety of devices. In such situations, it no longer makes sense, and in many cases it is not feasible, to leave the whole processing task to a single computer or even a group of central computers. As the extensive research in the distributed algorithms field yielded efficient decentralized algorithms for many classic problems, the discussion about the security of distributed algorithms was somewhat neglected. Nevertheless, many protocols and algorithms were devised in the research area of secure multi-party computation problem (MPC or SMC). However, the notions and terminology of these protocols are quite different than in classic distributed algorithms. As a consequence, the focus in those protocols was to work for every function $f$ at the expense of increasing the round complexity, or the necessity of several computational assumptions. In this work, we present a novel approach, which rather than turning existing algorithms into secure ones, identifies and develops those algorithms that are inherently secure (which means they do not require any further constructions). This approach yields efficient secure algorithms for various locality problems, such as coloring, network decomposition, forest decomposition, and a variety of additional labeling problems. Remarkably, our approach does not require any hardness assumption, but only a private randomness generator in each vertex. This is in contrast to previously known techniques in this setting that are based on public-key encryption schemes.
Linking Publications to Funding at Project Level: A curated dataset of publications reported by FP7 projects
Venue: arXiv cs.DL 2021
Year: 2021

Datasets explicitly linking publications to funding at project level are the basis of evaluative bibliometric analysis of funding programmes. Analysis of the impact of the EU funding programmes has been often frustrated by the lack of data on publications to which the funding has contributed. Here we present a dataset of scholarly publications reported by the projects funded by the European Union under the 7th Framework Programme. The dataset was created by first consolidating data from different reporting channels and validating the records by systematically matching them to external authoritative sources and assigning them external identifiers. The initial dataset had 305k records linked to one or more projects out of which 69% had a digital object identify (doi). Through the data quality assurance, we validate 93% of the initial records (283k) and assign a doi to 90% of them of them (245k). The resulting dataset has 245k unique dois (linked to one or more projects). It is, to our knowledge, the first comprehensive and curated dataset of scholarly outputs of the Framework Programme as reported by the grant holders. The dataset could only be created thanks to significant improvements and investments made in the reporting systems used by EU funded projects. The dataset is available EU open data portal: https://data.europa.eu/data/datasets/cordisfp7projects
A Modern Compiler for the French Tax Code
Venue: arXiv cs.PL 2021
Year: 2021

In France, income tax is computed from taxpayers' individual returns, using an algorithm that is authored, designed and maintained by the French Public Finances Directorate (DGFiP). This algorithm relies on a legacy custom language and compiler originally designed in 1990, which unlike French wine, did not age well with time. Owing to the shortcomings of the input language and the technical limitations of the compiler, the algorithm is proving harder and harder to maintain, relying on ad-hoc behaviors and workarounds to implement the most recent changes in tax law. Competence loss and aging code also mean that the system does not benefit from any modern compiler techniques that would increase confidence in the implementation. We overhaul this infrastructure and present Mlang, an open-source compiler toolchain whose goal is to replace the existing infrastructure. Mlang is based on a reverse-engineered formalization of the DGFiP's system, and has been thoroughly validated against the private DGFiP test suite. As such, Mlang has a formal semantics; eliminates previous handwritten workarounds in C; compiles to modern languages (Python); and enables a variety of instrumentations, providing deep insights about the essence of French income tax computation. The DGFiP is now officially transitioning to Mlang for their production system.
A Novel Occupancy Mapping Framework for Risk-Aware Path Planning in Unstructured Environments
Venue: arXiv cs.RO 2021
Year: 2021

In the context of autonomous robots, one of the most important tasks is to prevent potential damage to the robot during navigation. For this purpose, it is often assumed that one must deal with known probabilistic obstacles, then compute the probability of collision with each obstacle. However, in complex scenarios or unstructured environments, it might be difficult to detect such obstacles. In these cases, a metric map is used, where each position stores the information of occupancy. The most common type of metric map is the Bayesian occupancy map. However, this type of map is not well suited for computing risk assessments for continuous paths due to its discrete nature. Hence, we introduce a novel type of map called the Lambda Field, which is specially designed for risk assessment. We first propose a way to compute such a map and the expectation of a generic risk over a path. Then, we demonstrate the benefits of our generic formulation with a use case defining the risk as the expected collision force over a path. Using this risk definition and the Lambda Field, we show that our framework is capable of doing classical path planning while having a physical-based metric. Furthermore, the Lambda Field gives a natural way to deal with unstructured environments, such as tall grass. Where standard environment representations would always generate trajectories going around such obstacles, our framework allows the robot to go through the grass while being aware of the risk taken.
Strongly Connected Components in Stream Graphs: Computation and Experimentations
Venue: arXiv cs.SI 2021
Year: 2021

Stream graphs model highly dynamic networks in which nodes and/or links arrive and/or leave over time. Strongly connected components in stream graphs were defined recently, but no algorithm was provided to compute them. We present here several solutions with polynomial time and space complexities, each with its own strengths and weaknesses. We provide an implementation and experimentally compare the algorithms in a wide variety of practical cases. In addition, we propose an approximation scheme that significantly reduces computation costs, and gives even more insight on the dataset.
Memory-Rate Tradeoff for Caching with Uncoded Placement under Nonuniform File Popularity
Venue: arXiv cs.IT 2021
Year: 2021

For caching with nonuniform file popularity, we aim to characterize the memory-rate tradeoff under uncoded cache placement. We consider the recently proposed Modified Coded Caching Scheme (MCCS) with the optimized cache placement based on the popularity-first approach to minimize the average delivery rate. We introduce two information-theoretic lower bounds on the average rate for caching under uncoded placement. For $K = 2$ users, we show that the optimized MCCS attains the lower bound and is optimal for caching with uncoded placement. For general $K$ users with distinct file requests, the optimized MCCS attains the popularity-first-based lower bound. When there are redundant file requests among $K$ users, we show a possible gap between the optimized MCCS and the lower bounds, which is attributed to zero-padding commonly used for coded delivery. We analyze the impact of zero-padding and its limitation. Simulation study shows that the loss is very small in general and only exists in some limited cases.
Anonymizing Sensor Data on the Edge: A Representation Learning and Transformation Approach
Venue: arXiv cs.LG 2021
Year: 2021

The abundance of data collected by sensors in Internet of Things (IoT) devices, and the success of deep neural networks in uncovering hidden patterns in time series data have led to mounting privacy concerns. This is because private and sensitive information can be potentially learned from sensor data by applications that have access to this data. In this paper, we aim to examine the tradeoff between utility and privacy loss by learning low-dimensional representations that are useful for data obfuscation. We propose deterministic and probabilistic transformations in the latent space of a variational autoencoder to synthesize time series data such that intrusive inferences are prevented while desired inferences can still be made with sufficient accuracy. In the deterministic case, we use a linear transformation to move the representation of input data in the latent space such that the reconstructed data is likely to have the same public attribute but a different private attribute than the original input data. In the probabilistic case, we apply the linear transformation to the latent representation of input data with some probability. We compare our technique with autoencoder-based anonymization techniques and additionally show that it can anonymize data in real time on resource-constrained edge devices.
On the Capacity of Intensity-Modulation Direct-Detection Gaussian Optical Wireless Communication Channels: A Tutorial
Venue: arXiv cs.IT 2021
Year: 2021

Optical wireless communication (OWC) using intensity-modulation and direct-detection (IM/DD) has a channel model which possesses unique features, due to the constraints imposed on the channel input. The aim of this tutorial is to overview results on the capacity of IM/DD channels with input-independent Gaussian noise as a model of OWC channels. It provides the reader with an entry point to the topic, and highlights some major contributions in this area. It begins with a discussion on channel models and how this IM/DD Gaussian channel model comes about, in addition to an explanation of input constraints. Then, it discusses the capacity of the single-input single-output channel, its computation, and capacity bounds and asymptotic capacity results. Then, it extends the discussion to the multiple-input multiple-output setup, and reviews capacity bounds for this channel model. Finally, it discusses multi-user channels modelled as a broadcast channel (downlink) or a multiple-access channel (uplink), with their associated capacity bounds.
Reachability-based Trajectory Safeguard (RTS): A Safe and Fast Reinforcement Learning Safety Layer for Continuous Control
Venue: arXiv cs.RO 2021
Year: 2021

Reinforcement Learning (RL) algorithms have achieved remarkable performance in decision making and control tasks due to their ability to reason about long-term, cumulative reward using trial and error. However, during RL training, applying this trial-and-error approach to real-world robots operating in safety critical environment may lead to collisions. To address this challenge, this paper proposes a Reachability-based Trajectory Safeguard (RTS), which leverages reachability analysis to ensure safety during training and operation. Given a known (but uncertain) model of a robot, RTS precomputes a Forward Reachable Set of the robot tracking a continuum of parameterized trajectories. At runtime, the RL agent selects from this continuum in a receding-horizon way to control the robot; the FRS is used to identify if the agent's choice is safe or not, and to adjust unsafe choices. The efficacy of this method is illustrated on three nonlinear robot models, including a 12-D quadrotor drone, in simulation and in comparison with state-of-the-art safe motion planning methods.
Shared Cross-Modal Trajectory Prediction for Autonomous Driving
Venue: arXiv cs.CV 2021
Year: 2021

Predicting future trajectories of traffic agents in highly interactive environments is an essential and challenging problem for the safe operation of autonomous driving systems. On the basis of the fact that self-driving vehicles are equipped with various types of sensors (e.g., LiDAR scanner, RGB camera, radar, etc.), we propose a Cross-Modal Embedding framework that aims to benefit from the use of multiple input modalities. At training time, our model learns to embed a set of complementary features in a shared latent space by jointly optimizing the objective functions across different types of input data. At test time, a single input modality (e.g., LiDAR data) is required to generate predictions from the input perspective (i.e., in the LiDAR space), while taking advantages from the model trained with multiple sensor modalities. An extensive evaluation is conducted to show the efficacy of the proposed framework using two benchmark driving datasets.
The Potential of Multilayered Hierarchical Nonterrestrial Networks for 6G: A Comparative Analysis Among Networking Architectures
Venue: arXiv cs.NI 2021
Year: 2021

6th generation (6G) communication research is currently focusing on non-terrestrial networks (NTNs) to promote ubiquitous and ultra-high-capacity global connectivity. Specifically, multi-layered hierarchical networks, i.e., the orchestration among different aerial/space platforms, including Low and High Altitude Platforms (LAPs and HAPs), and satellites co-operating at different altitudes, currently represent one the most attractive technological options to solve coverage and latency constraints associated with the NTN paradigm. However, there are still several issues to be resolved for proper network design. In this work, we evaluate the performance of different multi-layered non-terrestrial configurations, and provide guidelines on the optimal working point(s) for which it is possible to achieve a good compromise between improved system flexibility and network performance, with respect to a baseline standalone deployment.
Multi-frame Feature Aggregation for Real-time Instrument Segmentation in Endoscopic Video
Venue: arXiv cs.CV 2021
Year: 2021

Deep learning-based methods have achieved promising results on surgical instrument segmentation. However, the high computation cost may limit the application of deep models to time-sensitive tasks such as online surgical video analysis for robotic-assisted surgery. Moreover, current methods may still suffer from challenging conditions in surgical images such as various lighting conditions and the presence of blood. We propose a novel Multi-frame Feature Aggregation (MFFA) module to aggregate video frame features temporally and spatially in a recurrent mode. By distributing the computation load of deep feature extraction over sequential frames, we can use a lightweight encoder to reduce the computation costs at each time step. Moreover, public surgical videos usually are not labeled frame by frame, so we develop a method that can randomly synthesize a surgical frame sequence from a single labeled frame to assist network training. We demonstrate that our approach achieves superior performance to corresponding deeper segmentation models on two public surgery datasets.
Facial Expressions as a Vulnerability in Face Recognition
Venue: arXiv cs.CV 2021
Year: 2021

This work explores facial expression bias as a security vulnerability of face recognition systems. Despite the great performance achieved by state-of-the-art face recognition systems, the algorithms are still sensitive to a large range of covariates. We present a comprehensive analysis of how facial expression bias impacts the performance of face recognition technologies. Our study analyzes: i) facial expression biases in the most popular face recognition databases; and ii) the impact of facial expression in face recognition performances. Our experimental framework includes two face detectors, three face recognition models, and three different databases. Our results demonstrate a huge facial expression bias in the most widely used databases, as well as a related impact of face expression in the performance of state-of-the-art algorithms. This work opens the door to new research lines focused on mitigating the observed vulnerability.
Towards Improved and Interpretable Deep Metric Learning via Attentive Grouping
Venue: arXiv cs.CV 2021
Year: 2021

Grouping has been commonly used in deep metric learning for computing diverse features. However, current methods are prone to overfitting and lack interpretability. In this work, we propose an improved and interpretable grouping method to be integrated flexibly with any metric learning framework. Our method is based on the attention mechanism with a learnable query for each group. The query is fully trainable and can capture group-specific information when combined with the diversity loss. An appealing property of our method is that it naturally lends itself interpretability. The attention scores between the learnable query and each spatial position can be interpreted as the importance of that position. We formally show that our proposed grouping method is invariant to spatial permutations of features. When used as a module in convolutional neural networks, our method leads to translational invariance. We conduct comprehensive experiments to evaluate our method. Our quantitative results indicate that the proposed method outperforms prior methods consistently and significantly across different datasets, evaluation metrics, base models, and loss functions. For the first time to the best of our knowledge, our interpretation results clearly demonstrate that the proposed method enables the learning of distinct and diverse features across groups. The code is available on https://github.com/XinyiXuXD/DGML-master.
Exact nuclear norm, completion and decomposition for random overcomplete tensors via degree-4 SOS
Venue: arXiv cs.DS 2021
Year: 2021

In this paper we show that simple semidefinite programs inspired by degree $4$ SOS can exactly solve the tensor nuclear norm, tensor decomposition, and tensor completion problems on tensors with random asymmetric components. More precisely, for tensor nuclear norm and tensor decomposition, we show that w.h.p. these semidefinite programs can exactly find the nuclear norm and components of an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m\leq n^{3/2}/polylog(n)$ random asymmetric components. Unlike most of the previous algorithms, our algorithm provides a certificate for the decomposition, does not require knowledge about the number of components in the decomposition and does not make any assumptions on the sizes of the coefficients in the decomposition. As a byproduct, we show that w.h.p. the nuclear norm decomposition exactly coincides with the minimum rank decomposition for tensors with $m\leq n^{3/2}/polylog(n)$ random asymmetric components. For tensor completion, we show that w.h.p. the semidefinite program, introduced by Potechin & Steurer (2017) for tensors with orthogonal components, can exactly recover an $(n\times n\times n)$-tensor $\mathcal{T}$ with $m$ random asymmetric components from only $n^{3/2}m polylog(n)$ randomly observed entries. For non-orthogonal tensors, this improves the dependence on $m$ of the number of entries needed for exact recovery over all previously known algorithms and provides the first theoretical guarantees for exact tensor completion in the overcomplete regime.
EasyTransfer -- A Simple and Scalable Deep Transfer Learning Platform for NLP Applications
Venue: arXiv cs.CL 2021
Year: 2021

The literature has witnessed the success of leveraging Pre-trained Language Models (PLMs) and Transfer Learning (TL) algorithms to a wide range of Natural Language Processing (NLP) applications, yet it is not easy to build an easy-to-use and scalable TL toolkit for this purpose. To bridge this gap, the EasyTransfer platform is designed to develop deep TL algorithms for NLP applications. EasyTransfer is backended with a high-performance and scalable engine for efficient training and inference, and also integrates comprehensive deep TL algorithms, to make the development of industrial-scale TL applications easier. In EasyTransfer, the built-in data and model parallelism strategies, combined with AI compiler optimization, show to be 4.0x faster than the community version of distributed training. EasyTransfer supports various NLP models in the ModelZoo, including mainstream PLMs and multi-modality models. It also features various in-house developed TL algorithms, together with the AppZoo for NLP applications. The toolkit is convenient for users to quickly start model training, evaluation, and online deployment. EasyTransfer is currently deployed at Alibaba to support a variety of business scenarios, including item recommendation, personalized search, conversational question answering, etc. Extensive experiments on real-world datasets and online applications show that EasyTransfer is suitable for online production with cutting-edge performance for various applications. The source code of EasyTransfer is released at Github (https://github.com/alibaba/EasyTransfer).
Efficient Full Higher-Order Unification
Venue: arXiv cs.LO 2021
Year: 2021

We developed a procedure to enumerate complete sets of higher-order unifiers based on work by Jensen and Pietrzykowski. Our procedure removes many redundant unifiers by carefully restricting the search space and tightly integrating decision procedures for fragments that admit a finite complete set of unifiers. We identify a new such fragment and describe a procedure for computing its unifiers. Our unification procedure, together with new higher-order term indexing data structures, is implemented in the Zipperposition theorem prover. Experimental evaluation shows a clear advantage over Jensen and Pietrzykowski's procedure.
Optimal Multi-Dimensional Mechanisms are not Locally-Implementable
Venue: arXiv cs.GT 2021
Year: 2021

We introduce locality: a new property of multi-bidder auctions that formally separates the simplicity of optimal single-dimensional multi-bidder auctions from the complexity of optimal multi-dimensional multi-bidder auctions. Specifically, consider the revenue-optimal, Bayesian Incentive Compatible auction for buyers with valuations drawn from $\vec{D}:=\times_i D_i$, where each distribution has support-size $n$. This auction takes as input a valuation profile $\vec{v}$ and produces as output an allocation of the items and prices to charge, $Opt_{\vec{D}}(\vec{v})$. When each $D_i$ is single-dimensional, this mapping is locally-implementable: defining each input $v_i$ requires $Θ(\log n)$ bits, and $Opt_{\vec{D}}(\vec{v})$ can be fully determined using just $Θ(\log n)$ bits from each $D_i$. This follows immediately from Myerson's virtual value theory [Mye81]. Our main result establishes that optimal multi-dimensional mechanisms are not locally-implementable: in order to determine the output $Opt_{\vec{D}}(\vec{v})$ on one particular input $\vec{v}$, one still needs to know (essentially) the entire distribution $\vec{D}$. Formally, $Ω(n)$ bits from each $D_i$ is necessary: (essentially) enough to fully describe $D_i$, and exponentially more than the $Θ(\log n)$ needed to define the input $v_i$. We show that this phenomenon already occurs with just two bidders, even when one bidder is single-dimensional, and when the other bidder is barely multi-dimensional. More specifically, the multi-dimensional bidder is ``inter-dimensional'' from the FedEx setting with just two days [FGKK16]. Our techniques are fairly robust: we additionally establish that optimal mechanisms for single-dimensional buyers with budget constraints are not locally-implementable. This occurs with just two bidders, even when one has no budget constraint, and even when the other's budget is public.