OpenRaiser/Intern-Atlas huggingface dataset:
The efficiency of resource allocation mechanisms for budget-constrained users
Venue: arXiv cs.GT 2020
Year: 2020

We study the efficiency of mechanisms for allocating a divisible resource. Given scalar signals submitted by all users, such a mechanism decides the fraction of the resource that each user will receive and a payment that will be collected from her. Users are self-interested and aim to maximize their utility (defined as their value for the resource fraction they receive minus their payment). Starting with the seminal work of Johari and Tsitsiklis [Mathematics of Operations Research, 2004], a long list of papers studied the price of anarchy (in terms of the social welfare --- the total users' value) of resource allocation mechanisms for a variety of allocation and payment rules. Here, we further assume that each user has a budget constraint that invalidates strategies that yield a payment that is higher than the user's budget. This subtle assumption, which is arguably more realistic, constitutes the traditional price of anarchy analysis meaningless as the set of equilibria may change drastically and their social welfare can be arbitrarily far from optimal. Instead, we study the price of anarchy using the liquid welfare benchmark that measures efficiency taking budget constraints into account. We show a tight bound of 2 on the liquid price of anarchy of the well-known Kelly mechanism and prove that this result is essentially best possible among all multi-user resource allocation mechanisms. This comes in sharp contrast to the no-budget setting where there are mechanisms that considerably outperform Kelly in terms of social welfare and even achieve full efficiency. In our proofs, we exploit the particular structure of worst-case games and equilibria, which also allows us to design (nearly) optimal two-player mechanisms by solving simple differential equations.
Fine-grained reductions from approximate counting to decision
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we introduce a general framework for fine-grained reductions of approximate counting problems to their decision versions. (Thus we use an oracle that decides whether any witness exists to multiplicatively approximate the number of witnesses with minimal overhead.) This mirrors a foundational result of Sipser (STOC 1983) and Stockmeyer (SICOMP 1985) in the polynomial-time setting, and a similar result of Müller (IWPEC 2006) in the FPT setting. Using our framework, we obtain such reductions for some of the most important problems in fine-grained complexity: the Orthogonal Vectors problem, 3SUM, and the Negative-Weight Triangle problem (which is closely related to All-Pairs Shortest Path). We also provide a fine-grained reduction from approximate #SAT to SAT. Suppose the Strong Exponential Time Hypothesis (SETH) is false, so that for some $1<c<2$ and all $k$ there is an $O(c^n)$-time algorithm for k-SAT. Then we prove that for all $k$, there is an $O((c+o(1))^n)$-time algorithm for approximate #$k$-SAT. In particular, our result implies that the Exponential Time Hypothesis (ETH) is equivalent to the seemingly-weaker statement that there is no algorithm to approximate #3-SAT to within a factor of $1+ε$ in time $2^{o(n)}/ε^2$ (taking $ε> 0$ as part of the input).
Optimal Universal Controllers for Roll Stabilization
Venue: arXiv cs.SY 2020
Year: 2020

Roll stabilization is an important problem of ship motion control. This problem becomes especially difficult if the same set of actuators (e.g. a single rudder) has to be used for roll stabilization and heading control of the vessel, so that the roll stabilizing system interferes with the ship autopilot. Finding the "trade-off" between the concurrent goals of accurate vessel steering and roll stabilization usually reduces to an optimization problem, which has to be solved in presence of an unknown wave disturbance. Standard approaches to this problem (loop-shaping, LQG, $H_{\infty}$-control etc.) require to know the spectral density of the disturbance, considered to be a \colored noise". In this paper, we propose a novel approach to optimal roll stabilization, approximating the disturbance by a polyharmonic signal with known frequencies yet uncertain amplitudes and phase shifts. Linear quadratic optimization problems in presence of polyharmonic disturbances can be solved by means of the theory of universal controllers developed by V.A. Yakubovich. An optimal universal controller delivers the optimal solution for any uncertain amplitudes and phases. Using Marine Systems Simulator (MSS) Toolbox that provides a realistic vessel's model, we compare our design method with classical approaches to optimal roll stabilization. Among three controllers providing the same quality of yaw steering, OUC stabilizes the roll motion most efficiently.
Tensor Regression Networks
Venue: arXiv cs.LG 2020
Year: 2020

Convolutional neural networks typically consist of many convolutional layers followed by one or more fully connected layers. While convolutional layers map between high-order activation tensors, the fully connected layers operate on flattened activation vectors. Despite empirical success, this approach has notable drawbacks. Flattening followed by fully connected layers discards multilinear structure in the activations and requires many parameters. We address these problems by incorporating tensor algebraic operations that preserve multilinear structure at every layer. First, we introduce Tensor Contraction Layers (TCLs) that reduce the dimensionality of their input while preserving their multilinear structure using tensor contraction. Next, we introduce Tensor Regression Layers (TRLs), which express outputs through a low-rank multilinear mapping from a high-order activation tensor to an output tensor of arbitrary order. We learn the contraction and regression factors end-to-end, and produce accurate nets with fewer parameters. Additionally, our layers regularize networks by imposing low-rank constraints on the activations (TCL) and regression weights (TRL). Experiments on ImageNet show that, applied to VGG and ResNet architectures, TCLs and TRLs reduce the number of parameters compared to fully connected layers by more than 65% while maintaining or increasing accuracy. In addition to the space savings, our approach's ability to leverage topological structure can be crucial for structured data such as MRI. In particular, we demonstrate significant performance improvements over comparable architectures on three tasks associated with the UK Biobank dataset.
Grid Obstacle Representation of Graphs
Venue: arXiv cs.CG 2020
Year: 2020

The grid obstacle representation, or alternately, $\ell_1$-obstacle representation of a graph $G=(V,E)$ is an injective function $f:V \rightarrow \mathbb{Z}^2$ and a set of point obstacles $\mathcal{O}$ on the grid points of $\mathbb{Z}^2$ (where no vertex of $V$ has been mapped) such that $uv$ is an edge in $G$ if and only if there exists a Manhattan path between $f(u)$ and $f(v)$ in $\mathbb{Z}^2$ avoiding the obstacles of $\mathcal{O}$ and points in $f(V)$. This work shows that planar graphs admit such a representation while there exist some non-planar graphs that do not admit such a representation. Moreover, we show that every graph admits a grid obstacle representation in $\mathbb{Z}^3$. We also show NP-hardness result for the point set embeddability of an $\ell_1$-obstacle representation.
An Introduction to Quantum Computing, Without the Physics
Venue: arXiv cs.DM 2020
Year: 2020

This paper is a gentle but rigorous introduction to quantum computing intended for discrete mathematicians. Starting from a small set of assumptions on the behavior of quantum computing devices, we analyze their main characteristics, stressing the differences with classical computers, and finally describe two well-known algorithms (Simon's algorithm and Grover's algorithm) using the formalism developed in previous sections. This paper does not touch on the physics of the devices, and therefore does not require any notion of quantum mechanics. Numerical examples on an implementation of Grover's algorithm using open-source software are provided.
Event-Triggered Stabilization of Nonlinear Systems with Time-Varying Sensing and Actuation Delay
Venue: arXiv cs.SY 2020
Year: 2020

This paper studies the problem of stabilization of a nonlinear system with time-varying delays in both sensing and actuation using event-triggered control. Our proposed strategy seeks to opportunistically minimize the number of control updates while guaranteeing stabilization and builds on predictor feedback to compensate for arbitrarily large known time-varying delays. We establish, using a Lyapunov approach, the global asymptotic stability of the closed-loop system as long as the open-loop system is globally input-to-state stabilizable in the absence of time delays and sampling. We further prove that the proposed event-triggered law has inter-event times that are uniformly lower bounded and hence does not exhibit Zeno behavior. For the particular case of a stabilizable linear system, we show global exponential stability of the closed-loop system and analyze the trade-off between the rate of exponential convergence and a bound on the sampling frequency. We illustrate these results in simulation and also examine the properties of the proposed event-triggered strategy beyond the class of systems for which stabilization can be guaranteed.
Coding for Positive Rate in the Source Model Key Agreement Problem
Venue: arXiv cs.IT 2020
Year: 2020

A two-party key agreement problem with public discussion, known as the source model problem, is considered. By relating key agreement to hypothesis testing, a new coding scheme is developed that yields a sufficient condition to achieve a positive secret-key (SK) rate in terms of Rényi divergence. The merits of this coding scheme are illustrated by applying it to an erasure model for Eve's side information, and by deriving an upper bound on Eve's erasure probabilities for which the SK capacity is zero. This bound strictly improves on the best known single-letter lower bound on the SK capacity. Moreover, the bound is tight when Alice's or Bob's source is binary, which extends a previous result for a doubly symmetric binary source. The results motivate a new measure for the correlation between two random variables, which is of independent interest.
Learning of Colors from Color Names: Distribution and Point Estimation
Venue: arXiv cs.CL 2020
Year: 2020

Color names are often made up of multiple words. As a task in natural language understanding we investigate in depth the capacity of neural networks based on sums of word embeddings (SOWE), recurrence (LSTM and GRU based RNNs) and convolution (CNN), to estimate colors from sequences of terms. We consider both point and distribution estimates of color. We argue that the latter has a particular value as there is no clear agreement between people as to what a particular color describes -- different people have a different idea of what it means to be ``very dark orange'', for example. Surprisingly, despite it's simplicity, the sum of word embeddings generally performs the best on almost all evaluations.
Usable & Scalable Learning Over Relational Data With Automatic Language Bias
Venue: arXiv cs.DB 2020
Year: 2020

Relational databases are valuable resources for learning novel and interesting relations and concepts. In order to constraint the search through the large space of candidate definitions, users must tune the algorithm by specifying a language bias. Unfortunately, specifying the language bias is done via trial and error and is guided by the expert's intuitions. We propose AutoBias, a system that leverages information in the schema and content of the database to automatically induce the language bias used by popular relational learning systems. We show that AutoBias delivers the same accuracy as using manually-written language bias by imposing only a slight overhead on the running time of the learning algorithm.
Skyline Computation with Noisy Comparisons
Venue: arXiv cs.DS 2020
Year: 2020

Given a set of $n$ points in a $d$-dimensional space, we seek to compute the skyline, i.e., those points that are not strictly dominated by any other point, using few comparisons between elements. We adopt the noisy comparison model [FRPU94] where comparisons fail with constant probability and confidence can be increased through independent repetitions of a comparison. In this model motivated by Crowdsourcing applications, Groz & Milo [GM15] show three bounds on the query complexity for the skyline problem. We improve significantly on that state of the art and provide two output-sensitive algorithms computing the skyline with respective query complexity $O(nd\log (dk/δ))$ and $O(ndk\log (k/δ))$ where $k$ is the size of the skyline and $δ$ the expected probability that our algorithm fails to return the correct answer. These results are tight for low dimensions.
Strategies to Inject Spoofed Measurement Data to Mislead Kalman Filter
Venue: arXiv cs.SY 2020
Year: 2020

We study the problem of designing false measurement data that is injected to corrupt and mislead the output of a Kalman filter. Unlike existing works that focus on detection and filtering algorithms for the observer, we study the problem from the attacker's point-of-view. In our model, the attacker can corrupt the measurements by injecting additive spoofing signals. The attacker seeks to create a separation between the estimate of the Kalman filter with and without spoofed signals. We present a number of results on how to inject spoofing signals while minimizing the magnitude of the injected signals. The resulting strategies are evaluated through simulations along with theoretical proofs. We also evaluate the spoofing strategy in the presence of a $χ^2$ spoof detector. Building on our main result, we present a strategy that is proven to successfully mislead a Kalman filter while ensuring it is not detected.
Forward Analysis for WSTS, Part III: Karp-Miller Trees
Venue: arXiv cs.LO 2020
Year: 2020

This paper is a sequel of "Forward Analysis for WSTS, Part I: Completions" [STACS 2009, LZI Intl. Proc. in Informatics 3, 433-444] and "Forward Analysis for WSTS, Part II: Complete WSTS" [Logical Methods in Computer Science 8(3), 2012]. In these two papers, we provided a framework to conduct forward reachability analyses of WSTS, using finite representations of downward-closed sets. We further develop this framework to obtain a generic Karp-Miller algorithm for the new class of very-WSTS. This allows us to show that coverability sets of very-WSTS can be computed as their finite ideal decompositions. Under natural effectiveness assumptions, we also show that LTL model checking for very-WSTS is decidable. The termination of our procedure rests on a new notion of acceleration levels, which we study. We characterize those domains that allow for only finitely many accelerations, based on ordinal ranks.
Meta-Key: A Secure Data-Sharing Protocol under Blockchain-Based Decentralised Storage Architecture
Venue: arXiv cs.DC 2020
Year: 2020

In this letter we propose Meta-key, a data-sharing mechanism that enables users share their encrypted data under a blockchain-based decentralized storage architecture. All the data-encryption keys are encrypted by the owner's public key and put onto the blockchain for safe and secure storage and easy key-management. Encrypted data are stored in dedicated storage nodes and proxy re-encryption mechanism is used to ensure secure data-sharing in the untrusted environment. Security analysis of our model shows that the proxy re-encryption adopted in our system is naturally free from collusion-attack due to the specific architecture of Meta-key.
Two dichotomies for model-checking in multi-layer structures
Venue: arXiv cs.DM 2020
Year: 2020

Multi-layer graphs can capture qualitatively different types of connection between entities, and networks of this kind are prevalent in biological and social systems: for example, a social contact network typically involves both virtual and face-to-face interactions between individuals. Since each layer is likely to exhibit stronger and/or more easily identifiable structurally properties than the overall system, it is natural to ask whether we can exploit the structural properties of individual layers to solve NP-hard problems efficiently on the overall network. In this paper we provide a complete characterisation of the structural properties required in each layer to guarantee the existence of an FPT algorithm to solve problems definable in either first-order or monadic second-order logic on the overall system, subject to the assumption that the structural properties are preserved under deletion of vertices and/or edges.
Efficiently Trainable Text-to-Speech System Based on Deep Convolutional Networks with Guided Attention
Venue: arXiv cs.SD 2020
Year: 2020

This paper describes a novel text-to-speech (TTS) technique based on deep convolutional neural networks (CNN), without use of any recurrent units. Recurrent neural networks (RNN) have become a standard technique to model sequential data recently, and this technique has been used in some cutting-edge neural TTS techniques. However, training RNN components often requires a very powerful computer, or a very long time, typically several days or weeks. Recent other studies, on the other hand, have shown that CNN-based sequence synthesis can be much faster than RNN-based techniques, because of high parallelizability. The objective of this paper is to show that an alternative neural TTS based only on CNN alleviate these economic costs of training. In our experiment, the proposed Deep Convolutional TTS was sufficiently trained overnight (15 hours), using an ordinary gaming PC equipped with two GPUs, while the quality of the synthesized speech was almost acceptable.
Controlled Sequential Information Fusion with Social Sensors
Venue: arXiv cs.SI 2020
Year: 2020

A sequence of social sensors estimate an unknown parameter (modeled as a state of nature) by performing Bayesian Social Learning, and myopically optimize individual reward functions. The decisions of the social sensors contain quantized information about the underlying state. How should a fusion center dynamically incentivize the social sensors for acquiring information about the underlying state? This paper presents five results. First, sufficient conditions on the model parameters are provided under which the optimal policy for the fusion center has a threshold structure. The optimal policy is determined in closed form, and is such that it switches between two exactly specified incentive policies at the threshold. Second, it is shown that the optimal incentive sequence is a sub-martingale, i.e, the optimal incentives increase on average over time. Third, it is shown that it is possible for the fusion center to learn the true state asymptotically by employing a sub-optimal policy; in other words, controlled information fusion with social sensors can be consistent. Fourth, uniform bounds on the average additional cost incurred by the fusion center for employing a sub-optimal policy are provided. This characterizes the trade-off between the cost of information acquisition and consistency for the fusion center. Finally, when it is sufficient to estimate the state with a degree of confidence, uniform bounds on the budget saved by employing policies that guarantee state estimation in finite time are provided.
Gaussian Kernel in Quantum Learning
Venue: arXiv cs.LG 2020
Year: 2020

The Gaussian kernel is a very popular kernel function used in many machine learning algorithms, especially in support vector machines (SVMs). It is more often used than polynomial kernels when learning from nonlinear datasets, and is usually employed in formulating the classical SVM for nonlinear problems. In [3], Rebentrost et al. discussed an elegant quantum version of a least square support vector machine using quantum polynomial kernels, which is exponentially faster than the classical counterpart. This paper demonstrates a quantum version of the Gaussian kernel and analyzes its runtime complexity using the quantum random access memory (QRAM) in the context of quantum SVM. Our analysis shows that the runtime computational complexity of the quantum Gaussian kernel seems to be significantly faster as compared to its classical version.
On the Numerical Solution of Fourth-Order Linear Two-Point Boundary Value Problems
Venue: arXiv cs.NA 2020
Year: 2020

This paper introduces a fast and numerically stable algorithm for the solution of fourth-order linear boundary value problems on an interval. This type of equation arises in a variety of settings in physics and signal processing. Our method reformulates the equation as a collection of second-kind integral equations defined on local subdomains. Each such equation can be stably discretized and solved. The boundary values of these local solutions are matched by solving a banded linear system. The method of deferred corrections is then used to increase the accuracy of the scheme. Deferred corrections requires applying the integral operator to a function on the entire domain, for which we provide an algorithm with linear cost. We illustrate the performance of our method on several numerical examples.
Rumor Source Detection under Querying with Untruthful Answers
Venue: arXiv cs.SI 2020
Year: 2020

Social networks are the major routes for most individuals to exchange their opinions about new products, social trends and political issues via their interactions. It is often of significant importance to figure out who initially diffuses the information, ie, finding a rumor source or a trend setter. It is known that such a task is highly challenging and the source detection probability cannot be beyond 31 percent for regular trees, if we just estimate the source from a given diffusion snapshot. In practice, finding the source often entails the process of querying that asks "Are you the rumor source?" or "Who tells you the rumor?" that would increase the chance of detecting the source. In this paper, we consider two kinds of querying: (a) simple batch querying and (b) interactive querying with direction under the assumption that queries can be untruthful with some probability. We propose estimation algorithms for those queries, and quantify their detection performance and the amount of extra budget due to untruthfulness, analytically showing that querying significantly improves the detection performance. We perform extensive simulations to validate our theoretical findings over synthetic and real-world social network topologies.
Robust Object Tracking Based on Self-adaptive Search Area
Venue: arXiv cs.CV 2020
Year: 2020

Discriminative correlation filter (DCF) based trackers have recently achieved excellent performance with great computational efficiency. However, DCF based trackers suffer boundary effects, which result in unstable performance in challenging situations exhibiting fast motion. In this paper, we propose a novel method to mitigate this side-effect in DCF based trackers. We change the search area according to the prediction of target motion. When the object moves fast, broad search area could alleviate boundary effects and reserve the probability of locating the object. When the object moves slowly, narrow search area could prevent effect of useless background information and improve computational efficiency to attain real-time performance. This strategy can impressively soothe boundary effects in situations exhibiting fast motion and motion blur, and it can be used in almost all DCF based trackers. The experiments on OTB benchmark show that the proposed framework improves the performance compared with the baseline trackers.