OpenRaiser/Intern-Atlas huggingface dataset:
One-Dimensional Phase Retrieval: Regularization, Box Relaxation and Uniqueness
Venue: arXiv cs.IT 2020
Year: 2020

Recovering a signal from its Fourier magnitude is referred to as phase retrieval, which occurs in different fields of engineering and applied physics. This paper gives a new characterization of the phase retrieval problem. Particularly useful is the analysis revealing that the common gradient-based regularization does not restrict the set of solutions to a smaller set. Specifically focusing on binary signals, we show that a box relaxation is equivalent to the binary constraint for Fourier-types of phase retrieval. We further prove that binary signals can be recovered uniquely up to trivial ambiguities under certain conditions. Finally, we use the characterization theorem to develop an efficient denoising algorithm.
When Smoothness is Not Enough: Toward Exact Quantification and Optimization of the Price-of-Anarchy
Venue: arXiv cs.SY 2020
Year: 2020

Today's multiagent systems have grown too complex to rely on centralized controllers, prompting increasing interest in the design of distributed algorithms. In this respect, game theory has emerged as a valuable tool to complement more traditional techniques. The fundamental idea behind this approach is the assignment of agents' local cost functions, such that their selfish minimization attains, or is provably close to, the global objective. Any algorithm capable of computing an equilibrium of the corresponding game inherits an approximation ratio that is, in the worst case, equal to its price-of-anarchy. Therefore, a successful application of the game design approach hinges on the possibility to quantify and optimize the equilibrium performance. Toward this end, we introduce the notion of generalized smoothness, and show that the resulting efficiency bounds are significantly tighter compared to those obtained using the traditional smoothness approach. Leveraging this newly-introduced notion, we quantify the equilibrium performance for the class of local resource allocation games. Finally, we show how the agents' local decision rules can be designed in order to optimize the efficiency of the corresponding equilibria, by means of a tractable linear program.
Counting the Number of Crossings in Geometric Graphs
Venue: arXiv cs.CG 2020
Year: 2020

A geometric graph is a graph whose vertices are points in general position in the plane and its edges are straight line segments joining these points. In this paper we give an $O(n^2 \log n)$ algorithm to compute the number of pairs of edges that cross in a geometric graph on $n$ points. For layered, and convex geometric graphs the algorithm takes $O(n^2)$ time.
On the Complexity of Local Graph Transformations
Venue: arXiv cs.DC 2020
Year: 2020

We consider the problem of transforming a given graph $G_s$ into a desired graph $G_t$ by applying a minimum number primitives from a particular set of local graph transformation primitives. These primitives are local in the sense that each node can apply them based on local knowledge and by affecting only its $1$-neighborhood. Although the specific set of primitives we consider makes it possible to transform any (weakly) connected graph into any other (weakly) connected graph consisting of the same nodes, they cannot disconnect the graph or introduce new nodes into the graph, making them ideal in the context of supervised overlay network transformations. We prove that computing a minimum sequence of primitive applications (even centralized) for arbitrary $G_s$ and $G_t$ is NP-hard, which we conjecture to hold for any set of local graph transformation primitives satisfying the aforementioned properties. On the other hand, we show that this problem admits a polynomial time algorithm with a constant approximation ratio.
Transformers with convolutional context for ASR
Venue: arXiv cs.CL 2020
Year: 2020

The recent success of transformer networks for neural machine translation and other NLP tasks has led to a surge in research work trying to apply it for speech recognition. Recent efforts studied key research questions around ways of combining positional embedding with speech features, and stability of optimization for large scale learning of transformer networks. In this paper, we propose replacing the sinusoidal positional embedding for transformers with convolutionally learned input representations. These contextual representations provide subsequent transformer blocks with relative positional information needed for discovering long-range relationships between local concepts. The proposed system has favorable optimization characteristics where our reported results are produced with fixed learning rate of 1.0 and no warmup steps. The proposed model achieves a competitive 4.7% and 12.9% WER on the Librispeech ``test clean'' and ``test other'' subsets when no extra LM text is provided.
Robust Metric Learning based on the Rescaled Hinge Loss
Venue: arXiv cs.LG 2020
Year: 2020

Distance/Similarity learning is a fundamental problem in machine learning. For example, kNN classifier or clustering methods are based on a distance/similarity measure. Metric learning algorithms enhance the efficiency of these methods by learning an optimal distance function from data. Most metric learning methods need training information in the form of pair or triplet sets. Nowadays, this training information often is obtained from the Internet via crowdsourcing methods. Therefore, this information may contain label noise or outliers leading to the poor performance of the learned metric. It is even possible that the learned metric functions perform worse than the general metrics such as Euclidean distance. To address this challenge, this paper presents a new robust metric learning method based on the Rescaled Hinge loss. This loss function is a general case of the popular Hinge loss and initially introduced in (Xu et al. 2017) to develop a new robust SVM algorithm. In this paper, we formulate the metric learning problem using the Rescaled Hinge loss function and then develop an efficient algorithm based on HQ (Half-Quadratic) to solve the problem. Experimental results on a variety of both real and synthetic datasets confirm that our new robust algorithm considerably outperforms state-of-the-art metric learning methods in the presence of label noise and outliers.
Cryptanalysis of a System Based on Twisted Reed-Solomon Codes
Venue: arXiv cs.IT 2020
Year: 2020

Twisted Reed-Solomon (TRS) codes are a family of codes that contains a large number of maximum distance separable codes that are non-equivalent to Reed--Solomon codes. TRS codes were recently proposed as an alternative to Goppa codes for the McEliece code-based cryptosystem, resulting in a potential reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has been motivated by the fact that a large subfamily of TRS codes is resilient to a direct use of known algebraic key-recovery methods. In this paper, an efficient key-recovery attack on the TRS variant that was used in the McEliece cryptosystem is presented. The algorithm exploits a new approach based on recovering the structure of a well-chosen subfield subcode of the public code. It is proved that the attack always succeeds and breaks the system for all practical parameters in $O(n^4)$ field operations. A software implementation of the algorithm retrieves a valid private key from the public key within a few minutes, for parameters claiming a security level of 128 bits. The success of the attack also indicates that, contrary to common beliefs, subfield subcodes of the public code need to be precisely analyzed when proposing a McEliece-type code-based cryptosystem. Finally, the paper discusses an attempt to repair the scheme and a modification of the attack aiming at Gabidulin-Paramonov-Tretjakov cryptosystems based on twisted Gabidulin codes.
Dynamic inference in probabilistic graphical models
Venue: arXiv cs.DS 2020
Year: 2020

Probabilistic graphical models, such as Markov random fields (MRFs), are useful for describing high-dimensional distributions in terms of local dependence structures. The probabilistic inference is a fundamental problem related to graphical models, and sampling is a main approach for the problem. In this paper, we study probabilistic inference problems when the graphical model itself is changing dynamically with time. Such dynamic inference problems arise naturally in today's application, e.g.~multivariate time-series data analysis and practical learning procedures. We give a dynamic algorithm for sampling-based probabilistic inferences in MRFs, where each dynamic update can change the underlying graph and all parameters of the MRF simultaneously, as long as the total amount of changes is bounded. More precisely, suppose that the MRF has $n$ variables and polylogarithmic-bounded maximum degree, and $N(n)$ independent samples are sufficient for the inference for a polynomial function $N(\cdot)$. Our algorithm dynamically maintains an answer to the inference problem using $\widetilde{O}(n N(n))$ space cost, and $\widetilde{O}(N(n) + n)$ incremental time cost upon each update to the MRF, as long as the well-known Dobrushin-Shlosman condition is satisfied by the MRFs. Compared to the static case, which requires $Ω(n N(n))$ time cost for redrawing all $N(n)$ samples whenever the MRF changes, our dynamic algorithm gives a $\widetildeΩ(\min\{n, N(n)\})$-factor speedup. Our approach relies on a novel dynamic sampling technique, which transforms local Markov chains (a.k.a. single-site dynamics) to dynamic sampling algorithms, and an "algorithmic Lipschitz" condition that we establish for sampling from graphical models, namely, when the MRF changes by a small difference, samples can be modified to reflect the new distribution, with cost proportional to the difference on MRF.
RCS: a fast path planning algorithm for Unmanned Aerial Vehicles
Venue: arXiv cs.RO 2020
Year: 2020

Path planning is a major problem in autonomous vehicles. In recent years, with the increase in applications of Unmanned Aerial Vehicles (UAVs), one of the main challenges is path planning, particularly in adversarial environments. In this paper, we consider the problem of planning a collision-free path for a UAV in a polygonal domain from a source point to a target point. Based on the characteristics of UAVs, we assume two basic limitations on the generated paths: an upper bound on the turning angle at each turning point (maximum turning angle) and a lower bound on the distance between two consecutive turns (minimum route leg length). We describe an algorithm that runs in $O(n^2 \log n)$ time and finds a feasible path in accordance with the above limitations, where $n$ is the number of obstacle vertices. As shown by experiments, the output of the algorithm is much close to the shortest path with this requirements. We further demonstrate how to decompose the algorithm into two phases, a preprocessing and a query phase. In this way, given a fixed start point and a set of obstacles, we can preprocess a data structure of size $O(n^2)$ in $O(n^2 \log n)$ time, such that for any query target point we can find a path with the given requirements in $O(n \log n)$ time. Finally, we modify the algorithm to find a feasible (almost shortest) path that reach the target point within a given range of directions.
Deep-MAPS: Machine Learning based Mobile Air Pollution Sensing
Venue: arXiv cs.LG 2020
Year: 2020

Mobile and ubiquitous sensing of urban air quality has received increased attention as an economically and operationally viable means to survey atmospheric environment with high spatial-temporal resolution. This paper proposes a machine learning based mobile air pollution sensing framework, called Deep-MAPS, and demonstrates its scientific and financial values in the following aspects. (1) Based on a network of fixed and mobile air quality sensors, we perform spatial inference of PM2.5 concentrations in Beijing (3,025 km2, 19 Jun-16 Jul 2018) for a spatial-temporal resolution of 1km-by-1km and 1 hour, with over 85% accuracy. (2) We leverage urban big data to generate insights regarding the potential cause of pollution, which facilitates evidence-based sustainable urban management. (3) To achieve such spatial-temporal coverage and accuracy, Deep-MAPS can save up to 90% hardware investment, compared with ubiquitous sensing that relies primarily on fixed sensors.
EV-Action: Electromyography-Vision Multi-Modal Action Dataset
Venue: arXiv cs.CV 2020
Year: 2020

Multi-modal human action analysis is a critical and attractive research topic. However, the majority of the existing datasets only provide visual modalities (i.e., RGB, depth and skeleton). To make up this, we introduce a new, large-scale EV-Action dataset in this work, which consists of RGB, depth, electromyography (EMG), and two skeleton modalities. Compared with the conventional datasets, EV-Action dataset has two major improvements: (1) we deploy a motion capturing system to obtain high quality skeleton modality, which provides more comprehensive motion information including skeleton, trajectory, acceleration with higher accuracy, sampling frequency, and more skeleton markers. (2) we introduce an EMG modality which is usually used as an effective indicator in the biomechanics area, also it has yet to be well explored in motion related research. To the best of our knowledge, this is the first action dataset with EMG modality. The details of EV-Action dataset are clarified, meanwhile, a simple yet effective framework for EMG-based action recognition is proposed. Moreover, state-of-the-art baselines are applied to evaluate the effectiveness of all the modalities. The obtained result clearly shows the validity of EMG modality in human action analysis tasks. We hope this dataset can make significant contributions to human motion analysis, computer vision, machine learning, biomechanics, and other interdisciplinary fields.
IRONHIDE: A Secure Multicore that Efficiently Mitigates Microarchitecture State Attacks for Interactive Applications
Venue: arXiv cs.CR 2020
Year: 2020

Microprocessors enable aggressive hardware virtualization by means of which multiple processes temporally execute on the system. These security-critical and ordinary processes interact with each other to assure application progress. However, temporal sharing of hardware resources exposes the processor to various microarchitecture state attacks. State-of-the-art secure processors, such as MI6 adopt Intel's SGX enclave execution model. MI6 architects strong isolation by statically isolating shared memory state, and purging the microarchitecture state of private core, cache, and TLB resources on every enclave entry and exit. The purging overhead significantly impacts performance as the interactivity across the secure and insecure processes increases. This paper proposes IRONHIDE that implements strong isolation in the context of multicores to form spatially isolated secure and insecure clusters of cores. For an interactive application comprising of secure and insecure processes, IRONHIDE pins the secure process(es) to the secure cluster, where they execute and interact with the insecure process(es) without incurring the microarchitecture state purging overheads on every interaction event. IRONHIDE improves performance by 2.1x over the MI6 baseline for a set of user and OS interactive applications. Moreover, IRONHIDE improves performance by 20% over an SGX-like baseline, while also ensuring strong isolation guarantees against microarchitecture state attacks.
A Simple Derivation of the Refined Sphere Packing Bound Under Certain Symmetry Hypotheses
Venue: arXiv cs.IT 2020
Year: 2020

A judicious application of the Berry-Esseen theorem via suitable Augustin information measures is demonstrated to be sufficient for deriving the sphere packing bound with a prefactor that is $\mathitΩ\left(n^{-0.5(1-E_{sp}'(R))}\right)$ for all codes on certain families of channels -- including the Gaussian channels and the non-stationary Renyi symmetric channels -- and for the constant composition codes on stationary memoryless channels. The resulting non-asymptotic bounds have definite approximation error terms. As a preliminary result that might be of interest on its own, the trade-off between type I and type II error probabilities in the hypothesis testing problem with (possibly non-stationary) independent samples is determined up to some multiplicative constants, assuming that the probabilities of both types of error are decaying exponentially with the number of samples, using the Berry-Esseen theorem.
Theoretical, Measured and Subjective Responsibility in Aided Decision Making
Venue: arXiv cs.HC 2020
Year: 2020

When humans interact with intelligent systems, their causal responsibility for outcomes becomes equivocal. We analyze the descriptive abilities of a newly developed responsibility quantification model (ResQu) to predict actual human responsibility and perceptions of responsibility in the interaction with intelligent systems. In two laboratory experiments, participants performed a classification task. They were aided by classification systems with different capabilities. We compared the predicted theoretical responsibility values to the actual measured responsibility participants took on and to their subjective rankings of responsibility. The model predictions were strongly correlated with both measured and subjective responsibility. A bias existed only when participants with poor classification capabilities relied less-than-optimally on a system that had superior classification capabilities and assumed higher-than-optimal responsibility. The study implies that when humans interact with advanced intelligent systems, with capabilities that greatly exceed their own, their comparative causal responsibility will be small, even if formally the human is assigned major roles. Simply putting a human into the loop does not assure that the human will meaningfully contribute to the outcomes. The results demonstrate the descriptive value of the ResQu model to predict behavior and perceptions of responsibility by considering the characteristics of the human, the intelligent system, the environment and some systematic behavioral biases. The ResQu model is a new quantitative method that can be used in system design and can guide policy and legal decisions regarding human responsibility in events involving intelligent systems.
Polar Codes for the Deletion Channel: Weak and Strong Polarization
Venue: arXiv cs.IT 2020
Year: 2020

This paper presents the first proof of polarization for the deletion channel with a constant deletion rate and a regular hidden-Markov input distribution. A key part of this work involves representing the deletion channel using a trellis and describing the plus and minus polar-decoding operations on that trellis. In particular, the plus and minus operations can be seen as combining adjacent trellis stages to yield a new trellis with half as many stages. Using this viewpoint, we prove a weak polarization theorem for standard polar codes on the deletion channel. To achieve strong polarization, we modify this scheme by adding guard bands of repeated zeros between various parts of the codeword. This gives a scheme whose rate approaches the mutual information and whose probability of error decays exponentially in the cube-root of the block length. We conclude by showing that this scheme can achieve capacity on the deletion channel by proving that the capacity of the deletion channel can be achieved by a sequence of regular hidden-Markov input distributions.
Computing the hull number in toll convexity
Venue: arXiv cs.DM 2020
Year: 2020

A walk $W$ between vertices $u$ and $v$ of a graph $G$ is called a {\em tolled walk between $u$ and $v$} if $u$, as well as $v$, has exactly one neighbour in $W$. A set $S \subseteq V(G)$ is {\em toll convex} if the vertices contained in any tolled walk between two vertices of $S$ are contained in $S$. The {\em toll convex hull of $S$} is the minimum toll convex set containing~$S$. The {\em toll hull number of $G$} is the minimum cardinality of a set $S$ such that the toll convex hull of $S$ is $V(G)$. The main contribution of this work is an algorithm for computing the toll hull number of a general graph in polynomial time.
Using Non-Linear Difference Equations to Study Quicksort Algorithms
Venue: arXiv cs.DS 2020
Year: 2020

Using non-linear difference equations, combined with symbolic computations, we make a detailed study of the running times of numerous variants of the celebrated Quicksort algorithms, where we consider the variants of single-pivot and multi-pivot Quicksort algorithms as discrete probability problems. With non-linear difference equations, recurrence relations and experimental mathematics techniques, explicit expressions for expectations, variances and even higher moments of their numbers of comparisons and swaps can be obtained. For some variants, Monte Carlo experiments are performed, the numerical results are demonstrated and the scaled limiting distribution is also discussed.
Beyond Mobile Apps: A Survey of Technologies for Mental Well-being
Venue: arXiv cs.CY 2020
Year: 2020

Mental health problems are on the rise globally and strain national health systems worldwide. Mental disorders are closely associated with fear of stigma, structural barriers such as financial burden, and lack of available services and resources which often prohibit the delivery of frequent clinical advice and monitoring. Technologies for mental well-being exhibit a range of attractive properties, which facilitate the delivery of state-of-the-art clinical monitoring. This review article provides an overview of traditional techniques followed by their technological alternatives, sensing devices, behaviour changing tools, and feedback interfaces. The challenges presented by these technologies are then discussed with data collection, privacy, and battery life being some of the key issues which need to be carefully considered for the successful deployment of mental health toolkits. Finally, the opportunities this growing research area presents are discussed including the use of portable tangible interfaces combining sensing and feedback technologies. Capitalising on the data these ubiquitous devices can record, state of the art machine learning algorithms can lead to the development of robust clinical decision support tools towards diagnosis and improvement of mental well-being delivery in real-time.
SmartTrack: Efficient Predictive Race Detection
Venue: arXiv cs.SE 2020
Year: 2020

Widely used data race detectors, including the state-of-the-art FastTrack algorithm, incur performance costs that are acceptable for regular in-house testing, but miss races detectable from the analyzed execution. Predictive analyses detect more data races in an analyzed execution than FastTrack detects, but at significantly higher performance cost. This paper presents SmartTrack, an algorithm that optimizes predictive race detection analyses, including two analyses from prior work and a new analysis introduced in this paper. SmartTrack's algorithm incorporates two main optimizations: (1) epoch and ownership optimizations from prior work, applied to predictive analysis for the first time; and (2) novel conflicting critical section optimizations introduced by this paper. Our evaluation shows that SmartTrack achieves performance competitive with FastTrack-a qualitative improvement in the state of the art for data race detection.