OpenRaiser/Intern-Atlas huggingface dataset:
Tableau-based decision procedure for full coalitional multiagent temporal-epistemic logic of linear time
Venue: arXiv cs.LO 2019
Year: 2019

We develop a tableau-based decision procedure for the full coalitional multiagent temporal-epistemic logic of linear time CMATEL(CD+LT). It extends LTL with operators of common and distributed knowledge for all coalitions of agents. The tableau procedure runs in exponential time, matching the lower bound obtained by Halpern and Vardi for a fragment of our logic, thus providing a complexity-optimal decision procedure for CMATEL(CD+LT).
Deterministic Algorithms for the Lovasz Local Lemma
Venue: arXiv cs.DS 2019
Year: 2019

The Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d <= 2^k/e other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser. Subsequently Moser and Tardos gave a randomized algorithm to construct the structures guaranteed by the LLL in a very general algorithmic framework. We address the main problem left open by Moser and Tardos of derandomizing these algorithms efficiently. Specifically, for a k-CNF formula with m clauses and d <= 2^{k/(1+\eps)}/e for any \eps\in (0,1), we give an algorithm that finds a satisfying assignment in time \tilde{O}(m^{2(1+1/\eps)}). This improves upon the deterministic algorithms of Moser and of Moser-Tardos with running time m^{Ω(k^2)} which is superpolynomial for k=ω(1) and upon other previous algorithms which work only for d\leq 2^{k/16}/4. Our algorithm works efficiently for a general version of LLL under the algorithmic framework of Moser and Tardos, and is also parallelizable, i.e., has polylogarithmic running time using polynomially many processors.
Trace transform based method for color image domain identification
Venue: arXiv cs.CV 2019
Year: 2019

Context categorization is a fundamental pre-requisite for multi-domain multimedia content analysis applications in order to manage contextual information in an efficient manner. In this paper, we introduce a new color image context categorization method (DITEC) based on the trace transform. The problem of dimensionality reduction of the obtained trace transform signal is addressed through statistical descriptors that keep the underlying information. These extracted features offer a highly discriminant behavior for content categorization. The theoretical properties of the method are analyzed and validated experimentally through two different datasets.
A Conceptual Network-Based Approach to Inferring the Cultural Evolutionary History of the Baltic Psaltery
Venue: arXiv cs.DL 2019
Year: 2019

The application of conventional phylogenetic techniques for inferring cultural history is problematic due to differences in the nature of information transmission in biological and cultural realms. In culture, units of transmission are not just measurable attributes, but communicable concepts. Therefore, relatedness amongst cultural elements often resides at the conceptual level not captured by traditional phylogenetic methods. This paper takes a cognitively inspired approach to analyzing material cultural history. We show that combining data for physical attributes of cultural artifacts with conceptual information can uncover cultural influences among different ethnolinguistic groups, and reveal new patterns of cultural ancestry. Using the Baltic psaltery, a musical instrument with a well-documented ethnographic and archaeological record, we recovered a previously unacknowledged pattern of historical relationship that is more congruent with geographical distribution and temporal data than is obtained with other approaches.
Size versus truthfulness in the House Allocation problem
Venue: arXiv cs.GT 2019
Year: 2019

We study the House Allocation problem (also known as the Assignment problem), i.e., the problem of allocating a set of objects among a set of agents, where each agent has ordinal preferences (possibly involving ties) over a subset of the objects. We focus on truthful mechanisms without monetary transfers for finding large Pareto optimal matchings. It is straightforward to show that no deterministic truthful mechanism can approximate a maximum cardinality Pareto optimal matching with ratio better than 2. We thus consider randomised mechanisms. We give a natural and explicit extension of the classical Random Serial Dictatorship Mechanism (RSDM) specifically for the House Allocation problem where preference lists can include ties. We thus obtain a universally truthful randomised mechanism for finding a Pareto optimal matching and show that it achieves an approximation ratio of $\frac{e}{e-1}$. The same bound holds even when agents have priorities (weights) and our goal is to find a maximum weight (as opposed to maximum cardinality) Pareto optimal matching. On the other hand we give a lower bound of $\frac{18}{13}$ on the approximation ratio of any universally truthful Pareto optimal mechanism in settings with strict preferences. In the case that the mechanism must additionally be non-bossy with an additional technical assumption, we show by utilising a result of Bade that an improved lower bound of $\frac{e}{e-1}$ holds. This lower bound is tight since RSDM for strict preference lists is non-bossy. We moreover interpret our problem in terms of the classical secretary problem and prove that our mechanism provides the best randomised strategy of the administrator who interviews the applicants.
Price of Anarchy for Auction Revenue
Venue: arXiv cs.GT 2019
Year: 2019

This paper develops tools for welfare and revenue analyses of Bayes-Nash equilibria in asymmetric auctions with single-dimensional agents. We employ these tools to derive price of anarchy results for social welfare and revenue. Our approach separates the standard smoothness framework into two distinct parts, isolating the analysis common to any auction from the analysis specific to a given auction. The first part relates a bidder's contribution to welfare in equilibrium to their contribution to welfare in the optimal auction using the price the bidder faces for additional allocation. Intuitively, either an agent's utility and hence contribution to welfare is high, or the price she has to pay for additional allocation is high relative to her value. We call this condition value covering; it holds in every Bayes-Nash equilibrium of any auction. The second part, revenue covering, relates the prices bidders face for additional allocation to the revenue of the auction, using an auction's rules and feasibility constraints. Combining the two parts gives approximation results to the optimal welfare, and, under the right conditions, the optimal revenue. In mechanisms with reserve prices, our welfare results show approximation with respect to the optimal mechanism with the same reserves. As a center-piece result, we analyze the single-item first-price auction with individual monopoly reserves. When each distribution satisfies a regularity condition the auction's revenue is at least a $2e/(e-1) \approx 3.16$ approximation to the revenue of the optimal auction. We also give bounds for matroid auctions with first-price or all-pay semantics, and the generalized first-price position auction. Finally, we give an extension theorem for simultaneous composition, i.e., when multiple auctions are run simultaneously, with single-valued, unit-demand agents.
RMT Estimator with Adaptive Decision Criteria for Estimating the Number of Signals Based on Random Matrix Theory
Venue: arXiv cs.IT 2019
Year: 2019

Estimating the number of signals embedded in noise is a fundamental problem in signal processing. As a classic estimator based on random matrix theory (RMT), the RMT estimator estimates the number of signals via sequentially testing the likelihood of an eigenvalue as arising from a signal or noise for a given over-detection probability. However, it tends to under-estimate the number of signals as weak signal eigenvalues may be immersed in the non-negligible bias term among eigenvalues for finite sample size. In order to solve this problem, we propose an RMT estimator with adaptive decision criterion (termed as RMT-ADC estimator) by adaptively incorporating the bias term into the decision criterion of the RMT estimator. Firstly, we analyze the effect of this bias term among eigenvalues on the estimation performance of the RMT estimator. Then, we derive both the decreased over-estimation probability and the increased under-estimation probability of the RMT estimator incurred by the bias term when assuming the eigenvalue being tested is arising from a signal, and also derive the increased under-estimation probability of the RMT estimator incurred by the bias term when assuming the eigenvalue being tested is arising from noise. Based on these results, the RMT-ADC estimator can adaptively determine whether the noise variance should be estimated under the assumption that the eigenvalue being tested is arising from a signal or from noise, and thus can adaptively select its decision criterion. Moreover, the RMT-ADC estimator can adaptively determine whether the bias term among eigenvalues should be incorporated into the selected decision criterion or not. Therefore, the RMT-ADC estimator can avoid the higher under-estimation probability of the RMT estimator. Finally, simulation results are presented to show that the proposed RMT-ADC estimator significantly outperforms the existing estimators.
On The Scalability of P2P Swarming Systems
Venue: arXiv cs.NI 2019
Year: 2019

One of the fundamental problems in the realm of peer-to-peer systems is that of determining their service capacities. In this paper, we focus on P2P scalability issues and propose models to compute the achievable throughput under distinct policies for selecting both peers and blocks. From these models, we obtain novel insights on the behavior of P2P swarming systems that motivate new mechanisms for publishers and peers to improve the overall performance. In particular, we obtain operational regions for swarm system. In addition, we show that system capacity significantly increases if publishers adopt the most deprived peer selection and peers reduce their service rates when they have all the file blocks but one.
Guaranteed Scalable Learning of Latent Tree Models
Venue: arXiv cs.LG 2019
Year: 2019

We present an integrated approach for structure and parameter estimation in latent tree graphical models. Our overall approach follows a "divide-and-conquer" strategy that learns models over small groups of variables and iteratively merges onto a global solution. The structure learning involves combinatorial operations such as minimum spanning tree construction and local recursive grouping; the parameter learning is based on the method of moments and on tensor decompositions. Our method is guaranteed to correctly recover the unknown tree structure and the model parameters with low sample complexity for the class of linear multivariate latent tree models which includes discrete and Gaussian distributions, and Gaussian mixtures. Our bulk asynchronous parallel algorithm is implemented in parallel and the parallel computation complexity increases only logarithmically with the number of variables and linearly with dimensionality of each variable.
NESTA, The NICTA Energy System Test Case Archive
Venue: arXiv cs.AI 2019
Year: 2019

In recent years the power systems research community has seen an explosion of work applying operations research techniques to challenging power network optimization problems. Regardless of the application under consideration, all of these works rely on power system test cases for evaluation and validation. However, many of the well established power system test cases were developed as far back as the 1960s with the aim of testing AC power flow algorithms. It is unclear if these power flow test cases are suitable for power system optimization studies. This report surveys all of the publicly available AC transmission system test cases, to the best of our knowledge, and assess their suitability for optimization tasks. It finds that many of the traditional test cases are missing key network operation constraints, such as line thermal limits and generator capability curves. To incorporate these missing constraints, data driven models are developed from a variety of publicly available data sources. The resulting extended test cases form a compressive archive, NESTA, for the evaluation and validation of power system optimization algorithms.
Asynchronous Approximation of a Single Component of the Solution to a Linear System
Venue: arXiv cs.DS 2019
Year: 2019

We present a distributed asynchronous algorithm for approximating a single component of the solution to a system of linear equations $Ax = b$, where $A$ is a positive definite real matrix, and $b \in \mathbb{R}^n$. This is equivalent to solving for $x_i$ in $x = Gx + z$ for some $G$ and $z$ such that the spectral radius of $G$ is less than 1. Our algorithm relies on the Neumann series characterization of the component $x_i$, and is based on residual updates. We analyze our algorithm within the context of a cloud computation model, in which the computation is split into small update tasks performed by small processors with shared access to a distributed file system. We prove a robust asymptotic convergence result when the spectral radius $ρ(|G|) < 1$, regardless of the precise order and frequency in which the update tasks are performed. We provide convergence rate bounds which depend on the order of update tasks performed, analyzing both deterministic update rules via counting weighted random walks, as well as probabilistic update rules via concentration bounds. The probabilistic analysis requires analyzing the product of random matrices which are drawn from distributions that are time and path dependent. We specifically consider the setting where $n$ is large, yet $G$ is sparse, e.g., each row has at most $d$ nonzero entries. This is motivated by applications in which $G$ is derived from the edge structure of an underlying graph. Our results prove that if the local neighborhood of the graph does not grow too quickly as a function of $n$, our algorithm can provide significant reduction in computation cost as opposed to any algorithm which computes the global solution vector $x$. Our algorithm obtains an $ε\|x\|_2$ additive approximation for $x_i$ in constant time with respect to the size of the matrix when the maximum row sparsity $d = O(1)$ and $1/(1-\|G\|_2) = O(1)$.
Coinduction: an elementary approach
Venue: arXiv cs.LO 2019
Year: 2019

The main aim of this paper is to promote a certain style of doing coinductive proofs, similar to inductive proofs as commonly done by mathematicians. For this purpose, we provide a reasonably direct justification for coinductive proofs written in this style, i.e., converting a coinductive proof into a non-coinductive argument is purely a matter of routine. In this way, we provide an elementary explanation of how to interpret coinduction in set theory.
A More Human Way to Play Computer Chess
Venue: arXiv cs.AI 2019
Year: 2019

This paper suggests a forward-pruning technique for computer chess that uses 'Move Tables', which are like Transposition Tables, but for moves not positions. They use an efficient memory structure and has put the design into the context of long and short-term memories. The long-term memory updates a play path with weight reinforcement, while the short-term memory can be immediately added or removed. With this, 'long branches' can play a short path, before returning to a full search at the resulting leaf nodes. Re-using an earlier search path allows the tree to be forward-pruned, which is known to be dangerous, because it removes part of the search process. Additional checks are therefore made and moves can even be re-added when the search result is unsatisfactory. Automatic feature analysis is now central to the algorithm, where key squares and related squares can be generated automatically and used to guide the search process. Using this analysis, if a search result is inferior, it can re-insert un-played moves that cover these key squares only. On the tactical side, a type of move that the forward-pruning will fail on is recognised and a pattern-based solution to that problem is suggested. This has completed the theory of an earlier paper and resulted in a more human-like approach to searching for a chess move. Tests demonstrate that the obvious blunders associated with forward pruning are no longer present and that it can compete at the top level with regard to playing strength.
What the F-measure doesn't measure: Features, Flaws, Fallacies and Fixes
Venue: arXiv cs.IR 2019
Year: 2019

The F-measure or F-score is one of the most commonly used single number measures in Information Retrieval, Natural Language Processing and Machine Learning, but it is based on a mistake, and the flawed assumptions render it unsuitable for use in most contexts! Fortunately, there are better alternatives.
Minimal conditions for parametric continuity of a utility representation
Venue: arXiv cs.GT 2019
Year: 2019

Dependence on the parameter is continuous when perturbations of the parameter preserves strict preference for one alternative over another. We characterise this property via a utility function over alternatives that depends continuously on the parameter. The class of parameter spaces where such a representation is guaranteed to exist is also identified. When the parameter is the type or belief of a player, these results have implications for Bayesian and psychological games. When alternatives are discrete, the representation is jointly continuous and an extension of Berge's theorem of the maximum yields a continuous value function. We apply this result to generalise a standard consumer choice problem where parameters are price-wealth vectors. When the parameter space is lexicographically ordered, a novel application to reference-dependent preferences is possible.
Real root finding for low rank linear matrices
Venue: arXiv cs.SC 2019
Year: 2019

We consider $m \times s$ matrices (with $m\geq s$) in a real affine subspace of dimension $n$. The problem of finding elements of low rank in such spaces finds many applications in information and systems theory, where low rank is synonymous of structure and parsimony. We design computer algebra algorithms, based on advanced methods for polynomial system solving, to solve this problem efficiently and exactly: the input are the rational coefficients of the matrices spanning the affine subspace as well as the expected maximum rank, and the output is a rational parametrization encoding a finite set of points that intersects each connected component of the low rank real algebraic set. The complexity of our algorithm is studied thoroughly. It is polynomial in $\binom{n+m(s-r)}{n}$. It improves on the state-of-the-art in computer algebra and effective real algebraic geometry. Moreover, computer experiments show the practical efficiency of our approach.
Defending Against Stealthy Attacks on Multiple Nodes with Limited Resources: A Game-Theoretic Analysis
Venue: arXiv cs.GT 2019
Year: 2019

Stealthy attacks are a major cyber-security threat. In practice, both attackers and defenders have resource constraints that could limit their capabilities. Hence, to develop robust defense strategies, a promising approach is to utilize game theory to understand the fundamental trade-offs involved. Previous works in this direction, however, mainly focus on the single-node case without considering strict resource constraints. In this paper, a game-theoretic model for protecting a system of multiple nodes against stealthy attacks is proposed. We consider the practical setting where the frequencies of both attack and defense are constrained by limited resources, and an asymmetric feedback structure where the attacker can fully observe the states of nodes while largely hiding its actions from the defender. We characterize the best response strategies for both attacker and defender in the space of both non-adaptive and adaptive strategies, and study the Nash Equilibria of the game. We further study a sequential game where the defender first announces its strategy and the attacker then responds accordingly, and design an algorithm that finds a nearly optimal strategy for the defender to commit to.
Perspectives on stability and mobility of transit passenger's travel behaviour through smart card data
Venue: arXiv cs.CY 2019
Year: 2019

Existing studies have extensively used spatiotemporal data to discover the mobility patterns of various types of travellers. Smart card data (SCD) collected by the automated fare collection systems can reflect a general view of the mobility pattern of public transit riders. Mobility patterns of transit riders are temporally and spatially dynamic, and therefore difficult to measure. However, few existing studies measure both the mobility and stability of transit riders' travel patterns over a long period of time. To analyse the long-term changes of transit riders' travel behaviour, the authors define a metric for measuring the similarity between SCD, in this study. Also an improved density-based clustering algorithm, simplified smoothed ordering points to identify the clustering structure (SS-OPTICS), to identify transit rider clusters is proposed. Compared to the original OPTICS, SS-OPTICS needs fewer parameters and has better generalisation ability. Further, the generated clusters are categorized according to their features of regularity and occasionality. Based on the generated clusters and categories, fine- and coarse-grained travel pattern transitions of transit riders over four years from 2010 to 2014 are measured. By combining socioeconomic data of Beijing in the year of 2010 and 2014, the interdependence between stability and mobility of transit riders' travel behaviour is also discussed.
Shortest paths in one-counter systems
Venue: arXiv cs.FL 2019
Year: 2019

We show that any one-counter automaton with $n$ states, if its language is non-empty, accepts some word of length at most $O(n^2)$. This closes the gap between the previously known upper bound of $O(n^3)$ and lower bound of $Ω(n^2)$. More generally, we prove a tight upper bound on the length of shortest paths between arbitrary configurations in one-counter transition systems (weaker bounds have previously appeared in the literature).
The height of piecewise-testable languages and the complexity of the logic of subwords
Venue: arXiv cs.LO 2019
Year: 2019

The height of a piecewise-testable language $L$ is the maximum length of the words needed to define $L$ by excluding and requiring given subwords. The height of $L$ is an important descriptive complexity measure that has not yet been investigated in a systematic way. This article develops a series of new techniques for bounding the height of finite languages and of languages obtained by taking closures by subwords, superwords and related operations. As an application of these results, we show that $\mathsf{FO}^2(A^*,\sqsubseteq)$, the two-variable fragment of the first-order logic of sequences with the subword ordering, can only express piecewise-testable properties and has elementary complexity.