OpenRaiser/Intern-Atlas huggingface dataset:
Distributed Selection in $O ( \log n )$ Time with $O ( n \log \log n )$ Messages
Venue: arXiv cs.DS 2017
Year: 2017

We consider the selection problem on a completely connected network of $n$ processors with no shared memory. Each processor initially holds a given numeric item of $b$ bits allowed to send a message of $\max ( b, \lg n )$ bits to another processor at a time. On such a communication network ${\cal G}$, we show that the $k$th smallest of the $n$ inputs can be detected in $O ( \log n )$ time with $O ( n \log \log n )$ messages. The possibility of such a parallel algorithm for this distributed $k$-selection problem has been unknown despite the intensive investigation on many variations of the selection problem carried out since 1970s. The main trick of our algorithm is to simulate the comparisons and swaps performed by the AKS sorting network, the $n$-input sorting network of logarithmic depth discovered by Ajtai, Koml{ó}s and Szemer{é}di in 1983. We also show the universal time lower bound $\lg n$ for many basic data aggregation problems on ${\cal G}$, confirming the asymptotic time optimality of our parallel algorithm.
Almost-globally stable tracking for on compact Riemannian manifolds
Venue: arXiv cs.SY 2017
Year: 2017

In this article, we propose a control law for almost-global asymptotic tracking (AGAT) of a smooth reference trajectory for a fully actuated simple mechanical system (SMS) evolving on a Riemannian manifold which can be embedded in a Euclidean space. The existing results on tracking for an SMS are either local, or almost-global, only in the case the manifold is a Lie group. In the latter case, the notion of a configuration error is naturally defined by the group operation and facilitates a global analysis. However, such a notion is not intrinsic to a Riemannian manifold. In this paper, we define a configuration error followed by error dynamics on a Riemannian manifold, and then prove AGAT. The results are demonstrated for a spherical pendulum which is an SMS on $S^2$ and for a particle moving on a Lissajous curve in $\mathbb{R}^3$.
Neural Module Networks
Venue: arXiv cs.CV 2017
Year: 2017

Visual question answering is fundamentally compositional in nature---a question like "where is the dog?" shares substructure with questions like "what color is the dog?" and "where is the cat?" This paper seeks to simultaneously exploit the representational capacity of deep networks and the compositional linguistic structure of questions. We describe a procedure for constructing and learning *neural module networks*, which compose collections of jointly-trained neural "modules" into deep networks for question answering. Our approach decomposes questions into their linguistic substructures, and uses these structures to dynamically instantiate modular networks (with reusable components for recognizing dogs, classifying colors, etc.). The resulting compound networks are jointly trained. We evaluate our approach on two challenging datasets for visual question answering, achieving state-of-the-art results on both the VQA natural image dataset and a new dataset of complex questions about abstract shapes.
Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity
Venue: arXiv cs.CC 2017
Year: 2017

We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis #ETH introduced by Dell et al. (ACM Transactions on Algorithms, 2014). Our framework allows us to convert classical #P-hardness results for counting problems into tight lower bounds under #ETH, thus ruling out algorithms with running time $2^{o(n)}$ on graphs with $n$ vertices and $O(n)$ edges. As exemplary applications of this framework, we obtain tight lower bounds under #ETH for the evaluation of the zero-one permanent, the matching polynomial, and the Tutte polynomial on all non-easy points except for one line. This remaining line was settled very recently by Brand et al. (IPEC 2016).
Microblog Analysis as a Programme of Work
Venue: arXiv cs.HC 2017
Year: 2017

Inspired by a European project, PHEME, that requires the close analysis of Twitter-based conversations in order to look at the spread of rumors via social media, this paper has two objectives. The first of these is to take the analysis of microblogs back to first principles and lay out what microblog analysis should look like as a foundational programme of work. The other is to describe how this is of fundamental relevance to Human-Computer Interaction's interest in grasping the constitution of people's interactions with technology within the social order. Our critical finding is that, despite some surface similarities, Twitter-based conversations are a wholly distinct social phenomenon requiring an independent analysis that treats them as unique phenomena in their own right, rather than as another species of conversation that can be handled within the framework of existing Conversation Analysis. This motivates the argument that Microblog Analysis be established as a foundationally independent programme, examining the organizational characteristics of microblogging from the ground up. We articulate how aspects of this approach have already begun to shape our design activities within the PHEME project.
Revisiting Differentially Private Hypothesis Tests for Categorical Data
Venue: arXiv cs.CR 2017
Year: 2017

In this paper, we consider methods for performing hypothesis tests on data protected by a statistical disclosure control technology known as differential privacy. Previous approaches to differentially private hypothesis testing either perturbed the test statistic with random noise having large variance (and resulted in a significant loss of power) or added smaller amounts of noise directly to the data but failed to adjust the test in response to the added noise (resulting in biased, unreliable $p$-values). In this paper, we develop a variety of practical hypothesis tests that address these problems. Using a different asymptotic regime that is more suited to hypothesis testing with privacy, we show a modified equivalence between chi-squared tests and likelihood ratio tests. We then develop differentially private likelihood ratio and chi-squared tests for a variety of applications on tabular data (i.e., independence, sample proportions, and goodness-of-fit tests). Experimental evaluations on small and large datasets using a wide variety of privacy settings demonstrate the practicality and reliability of our methods.
Quantifying Inefficiency of Fair Cost-Sharing Mechanisms for Sharing Economy
Venue: arXiv cs.GT 2017
Year: 2017

Sharing economy is a distributed peer-to-peer economic paradigm, which gives rise to a variety of social interactions for economic purposes. One fundamental distributed decision-making process is coalition formation for sharing certain replaceable resources collaboratively, for example, sharing hotel rooms among travelers, sharing taxi-rides among passengers, and sharing regular passes among users. Motivated by the applications of sharing economy, this paper studies a coalition formation game subject to the capacity of $K$ participants per coalition. The participants in each coalition are supposed to split the associated cost according to a given cost-sharing mechanism. A stable coalition structure is established when no group of participants can opt out to form another coalition that leads to lower individual payments. We quantify the inefficiency of distributed decision-making processes under a cost-sharing mechanism by the strong price of anarchy (SPoA), comparing a worst-case stable coalition structure and a social optimum. In particular, we derive SPoA for common fair cost-sharing mechanisms (e.g., equal-split, proportional-split, egalitarian and Nash bargaining solutions of bargaining games, and usage based cost-sharing). We show that the SPoA for equal-split, proportional-split, and usage based cost-sharing (under certain conditions) is $Θ(\log K)$, whereas the one for egalitarian and Nash bargaining solutions is $O(\sqrt{K} \log K)$. Therefore, distributed decision-making processes under common fair cost-sharing mechanisms induce only moderate inefficiency.
Complexity and Approximability of Parameterized MAX-CSPs
Venue: arXiv cs.CC 2017
Year: 2017

We study the optimization version of constraint satisfaction problems (Max-CSPs) in the framework of parameterized complexity; the goal is to compute the maximum fraction of constraints that can be satisfied simultaneously. In standard CSPs, we want to decide whether this fraction equals one. The parameters we investigate are structural measures, such as the treewidth or the clique-width of the variable-constraint incidence graph of the CSP instance. We consider Max-CSPs with the constraint types AND, OR, PARITY, and MAJORITY, and with various parameters k, and we attempt to fully classify them into the following three cases: 1. The exact optimum can be computed in FPT time. 2. It is W[1]-hard to compute the exact optimum, but there is a randomized FPT approximation scheme (FPTAS), which computes a $(1-ε)$-approximation in time $f(k,ε)\cdot poly(n)$. 3. There is no FPTAS unless FPT=W[1]. For the corresponding standard CSPs, we establish FPT vs. W[1]-hardness results.
Malthusian Locks
Venue: arXiv cs.DC 2017
Year: 2017

Applications running in modern multithreaded environments are sometimes \emph{over-threaded}. The excess threads do not improve performance, and in fact may act to degrade performance via \emph{scalability collapse}. Often, such software also has highly contended locks. We opportunistically leverage the existence of such locks by modifying the lock admission policy so as to intentionally limit the number of threads circulating over the lock in a given period. Specifically, if there are more threads circulating than are necessary to keep the lock saturated, our approach will selectively cull and passivate some of those threads. We borrow the concept of \emph{swapping} from the field of memory management and intentionally impose \emph{concurrency restriction} (CR) if a lock is oversubscribed. In the worst case CR does no harm, but it often yields performance benefits. The resultant admission order is unfair over the short term but we explicitly provide long-term fairness by periodically shifting threads between the set of passivated threads and those actively circulating. Our approach is palliative, but often effective.
mplrs: A scalable parallel vertex/facet enumeration code
Venue: arXiv cs.MS 2017
Year: 2017

We describe a new parallel implementation, mplrs, of the vertex enumeration code lrs that uses the MPI parallel environment and can be run on a network of computers. The implementation makes use of a C wrapper that essentially uses the existing lrs code with only minor modifications. mplrs was derived from the earlier parallel implementation plrs, written by G. Roumanis in C++. plrs uses the Boost library and runs on a shared memory machine. In developing mplrs we discovered a method of balancing the parallel tree search, called budgeting, that greatly improves parallelization beyond the bottleneck encountered previously at around 32 cores. This method can be readily adapted for use in other reverse search enumeration codes. We also report some preliminary computational results comparing parallel and sequential codes for vertex/facet enumeration problems for convex polyhedra. The problems chosen span the range from simple to highly degenerate polytopes. For most problems tested, the results clearly show the advantage of using the parallel implementation mplrs of the reverse search based code lrs, even when as few as 8 cores are available. For some problems almost linear speedup was observed up to 1200 cores, the largest number of cores tested.
Calculating the Unrooted Subtree Prune-and-Regraft Distance
Venue: arXiv cs.DS 2017
Year: 2017

The subtree prune-and-regraft (SPR) distance metric is a fundamental way of comparing evolutionary trees. It has wide-ranging applications, such as to study lateral genetic transfer, viral recombination, and Markov chain Monte Carlo phylogenetic inference. Although the rooted version of SPR distance can be computed relatively efficiently between rooted trees using fixed-parameter-tractable maximum agreement forest (MAF) algorithms, no MAF formulation is known for the unrooted case. Correspondingly, previous algorithms are unable to compute unrooted SPR distances larger than 7. In this paper, we substantially advance understanding of and computational algorithms for the unrooted SPR distance. First we identify four properties of optimal SPR paths, each of which suggests that no MAF formulation exists in the unrooted case. Then we introduce the replug distance, a new lower bound on the unrooted SPR distance that is amenable to MAF methods, and give an efficient fixed-parameter algorithm for calculating it. Finally, we develop a "progressive A*" search algorithm using multiple heuristics, including the TBR and replug distances, to exactly compute the unrooted SPR distance. Our algorithm is nearly two orders of magnitude faster than previous methods on small trees, and allows computation of unrooted SPR distances as large as 14 on trees with 50 leaves.
Positioning via Direct Localization in C-RAN Systems
Venue: arXiv cs.IT 2017
Year: 2017

Cloud Radio Access Network (C-RAN) is a prominent architecture for 5G wireless cellular system that is based on the centralization of baseband processing for multiple distributed radio units (RUs) at a control unit (CU). In this work, it is proposed to leverage the C-RAN architecture to enable the implementation of direct localization of the position of mobile devices from the received signals at distributed RUs. With ideal connections between the CU and the RUs, direct localization is known to outperform traditional indirect localization, whereby the location of a source is estimated from intermediary parameters estimated at the RUs. However, in a C-RAN system with capacity limited fronthaul links, the advantage of direct localization may be offset by the distortion caused by the quantization of the received signal at the RUs. In this paper, the performance of direct localization is studied by accounting for the effect of fronthaul quantization with or without dithering. An approximate Maximum Likelihood (ML) localization is developed. Then, the Cramer-Rao Bound (CRB) on the squared position error (SPE) of direct localization with quantized observations is derived. Finally, the performance of indirect localization and direct localization with or without dithering is compared via numerical results.
$E_γ$-Resolvability
Venue: arXiv cs.IT 2017
Year: 2017

The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper we study $E_γ$-resolvability, in which total variation is replaced by the more general $E_γ$ distance. A general one-shot achievability bound for the precision of such an approximation is developed. Let $Q_{\sf X|U}$ be a random transformation, $n$ be an integer, and $E\in(0,+\infty)$. We show that in the asymptotic setting where $γ=\exp(nE)$, a (nonnegative) randomness rate above $\inf_{Q_{\sf U}: D(Q_{\sf X}\|{π}_{\sf X})\le E} \{D(Q_{\sf X}\|{π}_{\sf X})+I(Q_{\sf U},Q_{\sf X|U})-E\}$ is sufficient to approximate the output distribution ${π}_{\sf X}^{\otimes n}$ using the channel $Q_{\sf X|U}^{\otimes n}$, where $Q_{\sf U}\to Q_{\sf X|U}\to Q_{\sf X}$, and is also necessary in the case of finite $\mathcal{U}$ and $\mathcal{X}$. In particular, a randomness rate of $\inf_{Q_{\sf U}}I(Q_{\sf U},Q_{\sf X|U})-E$ is always sufficient. We also study the convergence of the approximation error under the high probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating $E_γ$ and other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d.~setting, 2) a one-shot version of the mutual covering lemma, and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.
A New Class of Combinatorial Markets with Covering Constraints: Algorithms and Applications
Venue: arXiv cs.GT 2017
Year: 2017

We introduce a new class of combinatorial markets in which agents have covering constraints over resources required and are interested in delay minimization. Our market model is applicable to several settings including scheduling, cloud computing, and communicating over a network. This model is quite different from the traditional models, to the extent that neither do the classical equilibrium existence results seem to apply to it nor do any of the efficient algorithmic techniques developed to compute equilibria seem to apply directly. We give a proof of existence of equilibrium and a polynomial time algorithm for finding one, drawing heavily on techniques from LP duality and submodular minimization. We observe that in our market model, the set of equilibrium prices could be a connected, non-convex set. To the best of our knowledge, this is the first natural example of the phenomenon where the set of solutions could have such complicated structure, yet there is a combinatorial polynomial time algorithm to find one. Finally, we show that our model inherits many of the fairness properties of traditional equilibrium models.
Coresets for Kinematic Data: From Theorems to Real-Time Systems
Venue: arXiv cs.RO 2017
Year: 2017

A coreset (or core-set) of a dataset is its semantic compression with respect to a set of queries, such that querying the (small) coreset provably yields an approximate answer to querying the original (full) dataset. In the last decade, coresets provided breakthroughs in theoretical computer science for approximation algorithms, and more recently, in the machine learning community for learning "Big data". However, we are not aware of real-time systems that compute coresets in a rate of dozens of frames per second. In this paper we suggest a framework to turn theorems to such systems using coresets. We begin with a proof of independent interest, that any set of $n$ matrices in $\mathbb{R}^{d\times d}$ whose sum is $S$, has a positively weighted subset whose sum has the same center of mass (mean) and orientation (left+right singular vectors) as $S$, and consists of $O(dr)$ matrices (independent of $n$), where $r\leq d$ is the rank of $S$. We provide an algorithm that computes this (core) set in one pass over possibly infinite stream of matrices in $d^{O(1)}$ time per matrix insertion. By maintaining such a coreset for kinematic (moving) set of $n$ points, we can run pose-estimation algorithms, such as Kabsch or PnP, on the small coresets, instead of the $n$ points, in real-time using weak devices, while obtaining the same results. This enabled us to implement a low-cost ($<\$100$) IoT wireless system that tracks a toy (and harmless) quadcopter which guides guests to a desired room (in a hospital, mall, hotel, museum, etc.) with no help of additional human or remote controller. We hope that our framework will encourage researchers outside the theoretical community to design and use coresets in future systems and papers. To this end, we provide extensive experimental results on both synthetic and real data, as well as a link to the open code of our system and algorithms.
VRFP: On-the-fly Video Retrieval using Web Images and Fast Fisher Vector Products
Venue: arXiv cs.CV 2017
Year: 2017

VRFP is a real-time video retrieval framework based on short text input queries, which obtains weakly labeled training images from the web after the query is known. The retrieved web images representing the query and each database video are treated as unordered collections of images, and each collection is represented using a single Fisher Vector built on CNN features. Our experiments show that a Fisher Vector is robust to noise present in web images and compares favorably in terms of accuracy to other standard representations. While a Fisher Vector can be constructed efficiently for a new query, matching against the test set is slow due to its high dimensionality. To perform matching in real-time, we present a lossless algorithm that accelerates the inner product computation between high dimensional Fisher Vectors. We prove that the expected number of multiplications required decreases quadratically with the sparsity of Fisher Vectors. We are not only able to construct and apply query models in real-time, but with the help of a simple re-ranking scheme, we also outperform state-of-the-art automatic retrieval methods by a significant margin on TRECVID MED13 (3.5%), MED14 (1.3%) and CCV datasets (5.2%). We also provide a direct comparison on standard datasets between two different paradigms for automatic video retrieval - zero-shot learning and on-the-fly retrieval.
Competitive Energy Trading Framework for Demand-side Management in Neighborhood Area Networks
Venue: arXiv cs.GT 2017
Year: 2017

This paper, by comparing three potential energy trading systems, studies the feasibility of integrating a community energy storage (CES) device with consumer-owned photovoltaic (PV) systems for demand-side management of a residential neighborhood area network. We consider a fully-competitive CES operator in a non-cooperative Stackelberg game, a benevolent CES operator that has socially favorable regulations with competitive users, and a centralized cooperative CES operator that minimizes the total community energy cost. The former two game-theoretic systems consider that the CES operator first maximizes their revenue by setting a price signal and trading energy with the grid. Then the users with PV panels play a non-cooperative repeated game following the actions of the CES operator to trade energy with the CES device and the grid to minimize energy costs. The centralized CES operator cooperates with the users to minimize the total community energy cost without appropriate incentives. The non-cooperative Stackelberg game with the fully-competitive CES operator has a unique Stackelberg equilibrium at which the CES operator maximizes revenue and users obtain unique Pareto-optimal Nash equilibrium CES energy trading strategies. Extensive simulations show that the fully-competitive CES model gives the best trade-off of operating environment between the CES operator and the users.
Mined Semantic Analysis: A New Concept Space Model for Semantic Representation of Textual Data
Venue: arXiv cs.CL 2017
Year: 2017

Mined Semantic Analysis (MSA) is a novel concept space model which employs unsupervised learning to generate semantic representations of text. MSA represents textual structures (terms, phrases, documents) as a Bag of Concepts (BoC) where concepts are derived from concept rich encyclopedic corpora. Traditional concept space models exploit only target corpus content to construct the concept space. MSA, alternatively, uncovers implicit relations between concepts by mining for their associations (e.g., mining Wikipedia's "See also" link graph). We evaluate MSA's performance on benchmark datasets for measuring semantic relatedness of words and sentences. Empirical results show competitive performance of MSA compared to prior state-of-the-art methods. Additionally, we introduce the first analytical study to examine statistical significance of results reported by different semantic relatedness methods. Our study shows that, the nuances of results across top performing methods could be statistically insignificant. The study positions MSA as one of state-of-the-art methods for measuring semantic relatedness, besides the inherent interpretability and simplicity of the generated semantic representation.