OpenRaiser/Intern-Atlas huggingface dataset:
Reachability analysis of linear hybrid systems via block decomposition
Venue: arXiv cs.SY 2020
Year: 2020

Reachability analysis aims at identifying states reachable by a system within a given time horizon. This task is known to be computationally expensive for linear hybrid systems. Reachability analysis works by iteratively applying continuous and discrete post operators to compute states reachable according to continuous and discrete dynamics, respectively. In this paper, we enhance both of these operators and make sure that most of the involved computations are performed in low-dimensional state space. In particular, we improve the continuous-post operator by performing computations in high-dimensional state space only for time intervals relevant for the subsequent application of the discrete-post operator. Furthermore, the new discrete-post operator performs low-dimensional computations by leveraging the structure of the guard and assignment of a considered transition. We illustrate the potential of our approach on a number of challenging benchmarks.
Network Coding Gaps for Completion Times of Multiple Unicasts
Venue: arXiv cs.DS 2020
Year: 2020

We study network coding gaps for the problem of makespan minimization of multiple unicasts. In this problem distinct packets at different nodes in a network need to be delivered to a destination specific to each packet, as fast as possible. The network coding gap specifies how much coding packets together in a network can help compared to the more natural approach of routing. While makespan minimization using routing has been intensely studied for the multiple unicasts problem, no bounds on network coding gaps for this problem are known. We develop new techniques which allow us to upper bound the network coding gap for the makespan of $k$ unicasts, proving this gap is at most polylogarithmic in $k$. Complementing this result, we show there exist instances of $k$ unicasts for which this coding gap is polylogarithmic in $k$. Our results also hold for average completion time, and more generally any $\ell_p$ norm of completion times.
Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem
Venue: arXiv cs.LG 2020
Year: 2020

We consider the combinatorial multi-armed bandit (CMAB) problem, where the reward function is nonlinear. In this setting, the agent chooses a batch of arms on each round and receives feedback from each arm of the batch. The reward that the agent aims to maximize is a function of the selected arms and their expectations. In many applications, the reward function is highly nonlinear, and the performance of existing algorithms relies on a global Lipschitz constant to encapsulate the function's nonlinearity. This may lead to loose regret bounds, since by itself, a large gradient does not necessarily cause a large regret, but only in regions where the uncertainty in the reward's parameters is high. To overcome this problem, we introduce a new smoothness criterion, which we term \emph{Gini-weighted smoothness}, that takes into account both the nonlinearity of the reward and concentration properties of the arms. We show that a linear dependence of the regret in the batch size in existing algorithms can be replaced by this smoothness parameter. This, in turn, leads to much tighter regret bounds when the smoothness parameter is batch-size independent. For example, in the probabilistic maximum coverage (PMC) problem, that has many applications, including influence maximization, diverse recommendations and more, we achieve dramatic improvements in the upper bounds. We also prove matching lower bounds for the PMC problem and show that our algorithm is tight, up to a logarithmic factor in the problem's parameters.
Multi-target Detection with an Arbitrary Spacing Distribution
Venue: arXiv cs.IT 2020
Year: 2020

Motivated by the structure reconstruction problem in single-particle cryo-electron microscopy, we consider the multi-target detection model, where multiple copies of a target signal occur at unknown locations in a long measurement, further corrupted by additive Gaussian noise. At low noise levels, one can easily detect the signal occurrences and estimate the signal by averaging. However, in the presence of high noise, which is the focus of this paper, detection is impossible. Here, we propose two approaches---autocorrelation analysis and an approximate expectation maximization algorithm---to reconstruct the signal without the need to detect signal occurrences in the measurement. In particular, our methods apply to an arbitrary spacing distribution of signal occurrences. We demonstrate reconstructions with synthetic data and empirically show that the sample complexity of both methods scales as 1/SNR^3 in the low SNR regime.
Zeros and approximations of Holant polynomials on the complex plane
Venue: arXiv cs.DS 2020
Year: 2020

We present fully polynomial approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
Embedding the intrinsic relevance of vertices in network analysis: the case of centrality metrics
Venue: arXiv cs.SI 2020
Year: 2020

Complex network theory (CNT) is gaining a lot of attention in the scientific community, due to its capability to model and interpret an impressive number of natural and anthropic phenomena. One of the most active CNT field concerns the evaluation of the centrality of vertices and edges in the network. Several metrics have been proposed, but all of them share a topological point of view, namely centrality descends from the local or global connectivity structure of the network. However, vertices can exhibit their own intrinsic relevance independent from topology; e.g., vertices representing strategic locations (e.g., hospitals, water and energy sources, etc.) or institutional roles (e.g., presidents, agencies, etc.). In these cases, the connectivity network structure and vertex intrinsic relevance mutually concur to define the centrality of vertices and edges. The purpose of this work is to embed the information about the intrinsic relevance of vertices into CNT tools to enhance the network analysis. We focus on the degree, closeness and betweenness metrics, being among the most used. Two examples, concerning a social (the historical Florence family marriage network) and an infrastructure (a water supply system) network, demonstrate the effectiveness of the proposed relevance-embedding extension of the centrality metrics.
Adversarial Image Translation: Unrestricted Adversarial Examples in Face Recognition Systems
Venue: arXiv cs.LG 2020
Year: 2020

Thanks to recent advances in deep neural networks (DNNs), face recognition systems have become highly accurate in classifying a large number of face images. However, recent studies have found that DNNs could be vulnerable to adversarial examples, raising concerns about the robustness of such systems. Adversarial examples that are not restricted to small perturbations could be more serious since conventional certified defenses might be ineffective against them. To shed light on the vulnerability to such adversarial examples, we propose a flexible and efficient method for generating unrestricted adversarial examples using image translation techniques. Our method enables us to translate a source image into any desired facial appearance with large perturbations to deceive target face recognition systems. Our experimental results indicate that our method achieved about $90$ and $80\%$ attack success rates under white- and black-box settings, respectively, and that the translated images are perceptually realistic and maintain the identifiability of the individual while the perturbations are large enough to bypass certified defenses.
Designing technology, developing theory. Towards a symmetrical approach
Venue: arXiv cs.CY 2020
Year: 2020

We focus on collaborative activities that engage computer graphics designers and social scientists in systems design processes. Our conceptual symmetrical account of technology design and theory development is elaborated as a mode of mutual engagement occurring in an interdisciplinary trading zone, where neither discipline is placed at the service of the other, and nor do disciplinary boundaries dissolve. To this end, we draw on analyses of mutual engagements between computer and social scientists stemming from the fields of computer-supported cooperative work (CSCW), human-computer interaction (HCI), and science and technology studies (STS). We especially build on theoretical work in STS concerning information technology (IT) in health care and extend recent contributions from STS with respect to the modes of engagement and trading zones between computer and social sciences. We conceive participative digital systems design as a form of inquiry for the analysis of cooperative work settings, particularly when social science becomes part of design processes. We illustrate our conceptual approach using data from an interdisciplinary project involving computer graphics designers, sociologists, and neurosurgeons with the aim of developing patient-centered visualizations for clinical cooperation on a hospital ward.
Exploiting Complexity in Pen- and Touch-based Signature Biometrics
Venue: arXiv cs.HC 2020
Year: 2020

Biometric signature verification has been traditionally performed in pen-based office-like scenarios using devices specifically designed for acquiring handwriting. However, the high deployment of devices such as smartphones and tablets has given rise to new and thriving scenarios for signature biometrics where handwriting can be performed using not only a pen stylus but also the finger via touch interaction. Some preliminary studies have highlighted the challenge of this new scenario and the necessity of further research on the topic. The main contribution of this work is to propose a new on-line signature verification architecture adapted to the signature complexity in order to tackle this new and challenging scenario. Additionally, an exhaustive comparative analysis of both pen- and touch-based scenarios using our proposed methodology is carried out along with a review of the most relevant and recent studies in the field. Significant improvements of biometric verification performance and practical insights are extracted for the application of signature verification in real scenarios.
On Unlimited Sampling and Reconstruction
Venue: arXiv cs.IT 2020
Year: 2020

Shannon's sampling theorem is one of the cornerstone topics that is well understood and explored, both mathematically and algorithmically. That said, practical realization of this theorem still suffers from a severe bottleneck due to the fundamental assumption that the samples can span an arbitrary range of amplitudes. In practice, the theorem is realized using so-called analog-to-digital converters (ADCs) which clip or saturate whenever the signal amplitude exceeds the maximum recordable ADC voltage thus leading to a significant information loss. In this paper, we develop an alternative paradigm for sensing and recovery, called the Unlimited Sampling Framework. It is based on the observation that when a signal is mapped to an appropriate bounded interval via a modulo operation before entering the ADC, the saturation problem no longer exists, but one rather encounters a different type of information loss due to the modulo operation. Such an alternative setup can be implemented, for example, via so-called folding or self-reset ADCs, as they have been proposed in various contexts in the circuit design literature. The key task that we need to accomplish in order to cope with this new type of information loss is to recover a bandlimited signal from its modulo samples. In this paper we derive conditions when perfect recovery is possible and complement them with a stable recovery algorithm. The sampling density required to guarantee recovery is independent of the maximum recordable ADC voltage and depends on the signal bandwidth only. Our recovery guarantees extend to measurements affected by bounded noise, which includes the case of round-off quantization. Numerical experiments validate our approach. Applications of the unlimited sampling paradigm can be found in a number of fields such as signal processing, communication and imaging.
Reinforcement Learning in Non-Stationary Environments
Venue: arXiv cs.LG 2020
Year: 2020

Reinforcement learning (RL) methods learn optimal decisions in the presence of a stationary environment. However, the stationary assumption on the environment is very restrictive. In many real world problems like traffic signal control, robotic applications, one often encounters situations with non-stationary environments and in these scenarios, RL methods yield sub-optimal decisions. In this paper, we thus consider the problem of developing RL methods that obtain optimal decisions in a non-stationary environment. The goal of this problem is to maximize the long-term discounted reward achieved when the underlying model of the environment changes over time. To achieve this, we first adapt a change point algorithm to detect change in the statistics of the environment and then develop an RL algorithm that maximizes the long-run reward accrued. We illustrate that our change point method detects change in the model of the environment effectively and thus facilitates the RL algorithm in maximizing the long-run reward. We further validate the effectiveness of the proposed solution on non-stationary random Markov decision processes, a sensor energy management problem and a traffic signal control problem.
Survey on Evaluation Methods for Dialogue Systems
Venue: arXiv cs.CL 2020
Year: 2020

In this paper we survey the methods and concepts developed for the evaluation of dialogue systems. Evaluation is a crucial part during the development process. Often, dialogue systems are evaluated by means of human evaluations and questionnaires. However, this tends to be very cost and time intensive. Thus, much work has been put into finding methods, which allow to reduce the involvement of human labour. In this survey, we present the main concepts and methods. For this, we differentiate between the various classes of dialogue systems (task-oriented dialogue systems, conversational dialogue systems, and question-answering dialogue systems). We cover each class by introducing the main technologies developed for the dialogue systems and then by presenting the evaluation methods regarding this class.
Optimal Auctions vs. Anonymous Pricing: Beyond Linear Utility
Venue: arXiv cs.GT 2020
Year: 2020

The revenue optimal mechanism for selling a single item to agents with independent but non-identically distributed values is complex for agents with linear utility (Myerson,1981) and has no closed-form characterization for agents with non-linear utility (cf. Alaei et al., 2012). Nonetheless, for linear utility agents satisfying a natural regularity property, Alaei et al. (2018) showed that simply posting an anonymous price is an e-approximation. We give a parameterization of the regularity property that extends to agents with non-linear utility and show that the approximation bound of anonymous pricing for regular agents approximately extends to agents that satisfy this approximate regularity property. We apply this approximation framework to prove that anonymous pricing is a constant approximation to the revenue optimal single-item auction for agents with public-budget utility, private-budget utility, and (a special case of) risk-averse utility.
Average Weights and Power in Weighted Voting Games
Venue: arXiv cs.GT 2020
Year: 2020

We investigate a class of weighted voting games for which weights are randomly distributed over the standard probability simplex. We provide close-formed formulae for the expectation and density of the distribution of weight of the $k$-th largest player under the uniform distribution. We analyze the average voting power of the $k$-th largest player and its dependence on the quota, obtaining analytical and numerical results for small values of $n$ and a general theorem about the functional form of the relation between the average Penrose--Banzhaf power index and the quota for the uniform measure on the simplex. We also analyze the power of a collectivity to act (Coleman efficiency index) of random weighted voting games, obtaining analytical upper bounds therefor.
Influencing Opinions of Heterogeneous Populations over Finite Time Horizons
Venue: arXiv cs.SI 2020
Year: 2020

In this work, we focus on strategies to influence the opinion dynamics of a well-connected society. We propose a generalization of the popular voter model. This variant of the voter model can capture a wide range of individuals including strong-willed individuals whose opinion evolution is independent of their neighbors as well as conformist/rebel individuals who tend to adopt the opinion of the majority/minority. Motivated by political campaigns which aim to influence opinion dynamics by the end of a fixed deadline, we focus on influencing strategies for finite time horizons. We characterize the nature of optimal influencing strategies as a function of the nature of individuals forming the society. Using this, we show that for a society consisting of predominantly strong-willed/rebel individuals, the optimal strategy is to influence towards the end of the finite time horizon, whereas, for a society predominantly consisting of conformist individuals who try to adopt the opinion of the majority, it could be optimal to influence in the initial phase of the finite time horizon.
Another Look at ALGORAND
Venue: arXiv cs.CR 2020
Year: 2020

ALGORAND is a celebrated public ledger technology. In this paper, we identify several design flaws of the ALGORAND protocol. In particular, we show that the claimed (proved) fork-free property is not true and several assumptions in ALGORAND are not realistic in practice. The ALGORAND wiki page https://golden.com/wiki/Algorand claims that "the probability of a fork in the protocol is estimated at 1/1,000,000,000 and therefore blocks can be considered final upon validation". However, our first attack in this paper shows that a malicious adversary who controls less than 1/3 of the users (or money units) could fork the ALGORAND chain very easily. Our second attack shows that a malicious adversary could use a bribery attack to fork the ALGORAND chain very easily also. Furthermore, we show that the celebrated Byzantine Agreement component in ALGORAND is not necessary. The Byzantine Agreement is the most expensive part and one of the most innovative parts in the ALGORAND protocol. It is used to avoid forks in ALGORAND. We show that a simple majority vote could be used to achieve the same property that Byzantine Agreement achieves in ALGORAND under the same network assumption.
Illumination-Adaptive Person Re-identification
Venue: arXiv cs.CV 2020
Year: 2020

Most person re-identification (ReID) approaches assume that person images are captured under relatively similar illumination conditions. In reality, long-term person retrieval is common, and person images are often captured under different illumination conditions at different times across a day. In this situation, the performances of existing ReID models often degrade dramatically. This paper addresses the ReID problem with illumination variations and names it as {\em Illumination-Adaptive Person Re-identification (IA-ReID)}. We propose an Illumination-Identity Disentanglement (IID) network to dispel different scales of illuminations away while preserving individuals' identity information. To demonstrate the illumination issue and to evaluate our model, we construct two large-scale simulated datasets with a wide range of illumination variations. Experimental results on the simulated datasets and real-world images demonstrate the effectiveness of the proposed framework.
HLO: Half-kernel Laplacian Operator for Surface Smoothing
Venue: arXiv cs.CG 2020
Year: 2020

This paper presents a simple yet effective method for feature-preserving surface smoothing. Through analyzing the differential property of surfaces, we show that the conventional discrete Laplacian operator with uniform weights is not applicable to feature points at which the surface is non-differentiable and the second order derivatives do not exist. To overcome this difficulty, we propose a Half-kernel Laplacian Operator (HLO) as an alternative to the conventional Laplacian. Given a vertex v, HLO first finds all pairs of its neighboring vertices and divides each pair into two subsets (called half windows); then computes the uniform Laplacians of all such subsets and subsequently projects the computed Laplacians to the full-window uniform Laplacian to alleviate flipping and degeneration. The half window with least regularization energy is then chosen for v. We develop an iterative approach to apply HLO for surface denoising. Our method is conceptually simple and easy to use because it has a single parameter, i.e., the number of iterations for updating vertices. We show that our method can preserve features better than the popular uniform Laplacian-based denoising and it significantly alleviates the shrinkage artifact. Extensive experimental results demonstrate that HLO is better than or comparable to state-of-the-art techniques both qualitatively and quantitatively and that it is particularly good at handling meshes with high noise. We will make our source code publicly available.
Explicit approximation of stochastic optimal feedback control for combined therapy of cancer
Venue: arXiv cs.SY 2020
Year: 2020

In this paper, a tractable methodology is proposed to approximate stochastic optimal feedback treatment in the context of mixed immuno-chemo therapy of cancer. The method uses a fixed-point value iteration that approximately solves a stochastic dynamic programming-like equation. It is in particular shown that the introduction of a variance-related penalty in the latter induces better results that cope with the consequences of softening the health safety constraints in the cost function. The convergence of the value function iteration is revisited in the presence of the variance related term. The implementation involves some Machine Learning tools in order to represent the optimal function and to perform complexity reduction by clustering. Quantitative illustration is given using a commonly used model of combined therapy involving twelve highly uncertain parameters.