OpenRaiser/Intern-Atlas huggingface dataset:
Team Performance with Test Scores
Venue: arXiv cs.DS 2018
Year: 2018

Team performance is a ubiquitous area of inquiry in the social sciences, and it motivates the problem of team selection -- choosing the members of a team for maximum performance. Influential work of Hong and Page has argued that testing individuals in isolation and then assembling the highest-scoring ones into a team is not an effective method for team selection. For a broad class of performance measures, based on the expected maximum of random variables representing individual candidates, we show that tests directly measuring individual performance are indeed ineffective, but that a more subtle family of tests used in isolation can provide a constant-factor approximation for team performance. These new tests measure the "potential" of individuals, in a precise sense, rather than performance, to our knowledge they represent the first time that individual tests have been shown to produce near-optimal teams for a non-trivial team performance measure. We also show families of subdmodular and supermodular team performance functions for which no test applied to individuals can produce near-optimal teams, and discuss implications for submodular maximization via hill-climbing.
Error Correction by Structural Simplicity: Correcting Samplable Additive Errors
Venue: arXiv cs.IT 2018
Year: 2018

This paper explores the possibilities and limitations of error correction by the structural simplicity of error mechanisms. Specifically, we consider channel models, called \emph{samplable additive channels}, in which (a) errors are efficiently sampled without the knowledge of the coding scheme or the transmitted codeword; (b) the entropy of the error distribution is bounded; and (c) the number of errors introduced by the channel is unbounded. For the channels, several negative and positive results are provided. Assuming the existence of one-way functions, there are samplable additive errors of entropy $n^ε$ for $ε\in (0,1)$ that are pseudorandom, and thus not correctable by efficient coding schemes. It is shown that there is an oracle algorithm that induces a samplable distribution over $\{0,1\}^n$ of entropy $m = ω( \log n)$ that is not pseudorandom, but is uncorrectable by efficient schemes of rate less than $1 - m/n - o(1)$. The results indicate that restricting error mechanisms to be efficiently samplable and not pseudorandom is insufficient for error correction. As positive results, some conditions are provided under which efficient error correction is possible.
A study of the classification of low-dimensional data with supervised manifold learning
Venue: arXiv cs.LG 2018
Year: 2018

Supervised manifold learning methods learn data representations by preserving the geometric structure of data while enhancing the separation between data samples from different classes. In this work, we propose a theoretical study of supervised manifold learning for classification. We consider nonlinear dimensionality reduction algorithms that yield linearly separable embeddings of training data and present generalization bounds for this type of algorithms. A necessary condition for satisfactory generalization performance is that the embedding allow the construction of a sufficiently regular interpolation function in relation with the separation margin of the embedding. We show that for supervised embeddings satisfying this condition, the classification error decays at an exponential rate with the number of training samples. Finally, we examine the separability of supervised nonlinear embeddings that aim to preserve the low-dimensional geometric structure of data based on graph representations. The proposed analysis is supported by experiments on several real data sets.
A Combinatorial Model of Interference in Frequency Hopping Schemes
Venue: arXiv cs.IT 2018
Year: 2018

In a frequency hopping (FH) scheme users communicate simultaneously using FH sequences defined on the same set of frequency channels. An FH sequence specifies the frequency channel to be used as communication progresses. Much of the research on the performance of FH schemes is based on either pairwise mutual interference or adversarial interference but not both. In this paper, we evaluate the performance of an FH scheme with respect to both group-wise mutual interference and adversarial interference (jamming), bearing in mind that more than two users may be transmitting simultaneously in the presence of a jammer. We establish a correspondence between a cover-free code and an FH scheme. This gives a lower bound on the transmission capacity. Furthermore, we specify a jammer model and consider what additional properties a cover-free code should have to resist the jammer. We demonstrate that a purely combinatorial approach is inadequate against such a jammer, but that with the use of pseudorandomness, we can have a system that has high throughput as well as security against jamming.
REBA: A Refinement-Based Architecture for Knowledge Representation and Reasoning in Robotics
Venue: arXiv cs.RO 2018
Year: 2018

This paper describes an architecture for robots that combines the complementary strengths of probabilistic graphical models and declarative programming to represent and reason with logic-based and probabilistic descriptions of uncertainty and domain knowledge. An action language is extended to support non-boolean fluents and non-deterministic causal laws. This action language is used to describe tightly-coupled transition diagrams at two levels of granularity, with a fine-resolution transition diagram defined as a refinement of a coarse-resolution transition diagram of the domain. The coarse-resolution system description, and a history that includes (prioritized) defaults, are translated into an Answer Set Prolog (ASP) program. For any given goal, inference in the ASP program provides a plan of abstract actions. To implement each such abstract action, the robot automatically zooms to the part of the fine-resolution transition diagram relevant to this action. A probabilistic representation of the uncertainty in sensing and actuation is then included in this zoomed fine-resolution system description, and used to construct a partially observable Markov decision process (POMDP). The policy obtained by solving the POMDP is invoked repeatedly to implement the abstract action as a sequence of concrete actions, with the corresponding observations being recorded in the coarse-resolution history and used for subsequent reasoning. The architecture is evaluated in simulation and on a mobile robot moving objects in an indoor domain, to show that it supports reasoning with violation of defaults, noisy observations and unreliable actions, in complex domains.
Social Influence in the Concurrent Diffusion of Information and Behaviors in Online Social Networks
Venue: arXiv cs.SI 2018
Year: 2018

The emergence of online social networks has greatly facilitated the diffusion of information and behaviors. While the two diffusion processes are often intertwined, "talking the talk" does not necessarily mean "walking the talk"--those who share information about an action may not actually participate in it. We do not know if the diffusion of information and behaviors are similar, or if social influence plays an equally important role in these processes. Integrating text mining, social network analyses, and survival analysis, this research examines the concurrent spread of information and behaviors related to the Ice Bucket Challenge on Twitter. We show that the two processes follow different patterns. Unilateral social influence contributes to the diffusion of information, but not to the diffusion of behaviors; bilateral influence conveyed via the communication process is a significant and positive predictor of the diffusion of behaviors, but not of information. These results have implications for theories of social influence, social networks, and contagion.
Variable-mixing parameter quantized kernel robust mixed-norm algorithms for combating impulsive interference
Venue: arXiv cs.SY 2018
Year: 2018

Although the kernel robust mixed-norm (KRMN) algorithm outperforms the kernel least mean square (KLMS) algorithm in impulsive noise, it still has two major problems as follows: (1) The choice of the mixing parameter in the KRMN is crucial to obtain satisfactory performance. (2) The structure of the KRMN algorithm grows linearly as the iteration goes on, thus it has high computational complexity and memory requirements. To solve the parameter selection problem, two variable-mixing parameter KRMN (VPKRMN) algorithms are developed in this paper. Moreover, a sparsification algorithm, quantized VPKRMN (QVPKRMN) algorithm is introduced for nonlinear system identification with impulsive interferences. The energy conservation relation (ECR) and convergence property of the QVPKRMN algorithm are analyzed. Simulation results in the context of nonlinear system identification under impulsive interference demonstrate the superior performance of the proposed VPKRMN and QVPKRMN algorithms as compared with the existing algorithms.
An Impossibility Result for Housing Markets with Fractional Endowments
Venue: arXiv cs.GT 2018
Year: 2018

The housing market setting constitutes a fundamental model of exchange economies of goods. Most of the work concerning housing markets does not cater for randomized assignments or allocation of time-shares. House allocation with fractional endowments of houses was considered by Athanassoglou and Sethuraman (2011) who posed the open problem whether individual rationality, weak strategyproofness, and efficiency are compatible for the setting. We show that the three axioms are incompatible.
Supervisor Localization of Discrete-Event Systems under Partial Observation
Venue: arXiv cs.SY 2018
Year: 2018

Recently we developed supervisor localization, a top-down approach to distributed control of discrete-event systems. Its essence is the allocation of monolithic (global) control action among the local control strategies of individual agents. In this paper, we extend supervisor localization by considering partial observation; namely not all events are observable. Specifically, we employ the recently proposed concept of relative observability to compute a partial-observation monolithic supervisor, and then design a suitable localization procedure to decompose the supervisor into a set of local controllers. In the resulting local controllers, only observable events can cause state change. Further, to deal with large-scale systems, we combine the partial-observation supervisor localization with an efficient architectural synthesis approach: first compute a heterarchical array of partial-observation decentralized supervisors and coordinators, and then localize each of these supervisors/coordinators into local controllers.
A (1+epsilon)-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies
Venue: arXiv cs.DS 2018
Year: 2018

In a classical problem in scheduling, one has $n$ unit size jobs with a precedence order and the goal is to find a schedule of those jobs on $m$ identical machines as to minimize the makespan. It is one of the remaining four open problems from the book of Garey & Johnson whether or not this problem is $\mathbf{NP}$-hard for $m=3$. We prove that for any fixed $\varepsilon$ and $m$, an LP-hierarchy lift of the time-indexed LP with a slightly super poly-logarithmic number of $r = (\log(n))^{Θ(\log \log n)}$ rounds provides a $(1 + \varepsilon)$-approximation. For example Sherali-Adams suffices as hierarchy. This implies an algorithm that yields a $(1+\varepsilon)$-approximation in time $n^{O(r)}$. The previously best approximation algorithms guarantee a $2 - \frac{7}{3m+1}$-approximation in polynomial time for $m \geq 4$ and $\frac{4}{3}$ for $m=3$. Our algorithm is based on a recursive scheduling approach where in each step we reduce the correlation in form of long chains. Our method adds to the rather short list of examples where hierarchies are actually useful to obtain better approximation algorithms.
Discriminative Learning of the Prototype Set for Nearest Neighbor Classification
Venue: arXiv cs.LG 2018
Year: 2018

The nearest neighbor rule is a classic yet essential classification model, particularly in problems where the supervising information is given by pairwise dissimilarities and the embedding function are not easily obtained. Prototype selection provides means of generalization and improving efficiency of the nearest neighbor model, but many existing methods assume and rely on the analyses of the input vector space. In this paper, we explore a dissimilarity-based, parametrized model of the nearest neighbor rule. In the proposed model, the selection of the nearest prototypes is influenced by the parameters of the respective prototypes. It provides a formulation for minimizing the violation of the extended nearest neighbor rule over the training set in a tractable form to exploit numerical techniques. We show that the minimization problem reduces to a large-margin principle learning and demonstrate its advantage by empirical comparisons with other prototype selection methods.
UB-ANC Drone: A Flexible Airborne Networking and Communications Testbed
Venue: arXiv cs.NI 2018
Year: 2018

We present the University at Buffalo's Airborne Networking and Communications Testbed (UB-ANC Drone). UB-ANC Drone is an open software/hardware platform that aims to facilitate rapid testing and repeatable comparative evaluation of airborne networking and communications protocols at different layers of the protocol stack. It combines quadcopters capable of autonomous flight with sophisticated command and control capabilities and embedded software-defined radios (SDRs), which enable flexible deployment of novel communications and networking protocols. This is in contrast to existing airborne network testbeds, which rely on standard inflexible wireless technologies, e.g., Wi-Fi or Zigbee. UB-ANC Drone is designed with emphasis on modularity and extensibility, and is built around popular open-source projects and standards developed by the research and hobby communities. This makes UB-ANC Drone highly customizable, while also simplifying its adoption. In this paper, we describe UB-ANC Drone's hardware and software architecture.
The "handedness" of language: Directional symmetry breaking of sign usage in words
Venue: arXiv cs.CL 2018
Year: 2018

Language, which allows complex ideas to be communicated through symbolic sequences, is a characteristic feature of our species and manifested in a multitude of forms. Using large written corpora for many different languages and scripts, we show that the occurrence probability distributions of signs at the left and right ends of words have a distinct heterogeneous nature. Characterizing this asymmetry using quantitative inequality measures, viz. information entropy and the Gini index, we show that the beginning of a word is less restrictive in sign usage than the end. This property is not simply attributable to the use of common affixes as it is seen even when only word roots are considered. We use the existence of this asymmetry to infer the direction of writing in undeciphered inscriptions that agrees with the archaeological evidence. Unlike traditional investigations of phonotactic constraints which focus on language-specific patterns, our study reveals a property valid across languages and writing systems. As both language and writing are unique aspects of our species, this universal signature may reflect an innate feature of the human cognitive phenomenon.
Coding Theorem and Converse for Abstract Channels with Time Structure and Memory
Venue: arXiv cs.IT 2018
Year: 2018

A coding theorem and converse are proved for a large class of abstract stationary channels with time structure including the result by Kadota and Wyner (1972) on continuous-time real-valued channels as special cases. As main contribution the coding theorem is proved for a significantly weaker condition on the channel output memory - called total ergodicity w.r.t. finite alphabet block-memoryless input sources - and under a crucial relaxation of the measurability requirement for the channel. These improvements are achieved by introducing a suitable characterization of information rate capacity. It is shown that the $ψ$-mixing output memory condition used by Kadota and Wyner is quite restrictive and excludes important channel models, in particular for the class of Gaussian channels. In fact, it is proved that for Gaussian (e.g., fading or additive noise) channels the $ψ$-mixing condition is equivalent to finite output memory. Further, it is demonstrated that the measurability requirement of Kadota and Wyner is not satisfied for relevant continuous-time channel models such as linear filters, whereas the condition used in this paper is satisfied for these models. Moreover, a weak converse is derived for all stationary channels with time structure. Intersymbol interference as well as input constraints are taken into account in a general and flexible way, including amplitude and average power constraints as special case. Formulated in rigorous mathematical terms complete, explicit, and transparent proofs are presented. As a side product a gap in the proof of Kadota and Wyner - illustrated by a counterexample - is closed by providing a corrected proof of a lemma on the monotonicity of some sequence of normalized mutual information quantities. An abstract framework is established to treat discrete- and continuous-time channels with memory and arbitrary alphabets in a unified way.
Balanced Islands in Two Colored Point Sets in the Plane
Venue: arXiv cs.CG 2018
Year: 2018

Let $S$ be a set of $n$ points in general position in the plane, $r$ of which are red and $b$ of which are blue. In this paper we prove that there exist: for every $α\in \left [ 0,\frac{1}{2} \right ]$, a convex set containing exactly $\lceil αr\rceil$ red points and exactly $\lceil αb \rceil$ blue points of $S$; a convex set containing exactly $\left \lceil \frac{r+1}{2}\right \rceil$ red points and exactly $\left \lceil \frac{b+1}{2}\right \rceil$ blue points of $S$. Furthermore, we present polynomial time algorithms to find these convex sets. In the first case we provide an $O(n^4)$ time algorithm and an $O(n^2\log n)$ time algorithm in the second case. Finally, if $\lceil αr\rceil+\lceil αb\rceil$ is small, that is, not much larger than $\frac{1}{3}n$, we improve the running time to $O(n \log n)$.
Old Bands, New Tracks---Revisiting the Band Model for Robust Hypothesis Testing
Venue: arXiv cs.IT 2018
Year: 2018

The density band model proposed by Kassam for robust hypothesis testing is revisited in this paper. First, a novel criterion for the general characterization of least favorable distributions is proposed, which unifies existing results. This criterion is then used to derive an implicit definition of the least favorable distributions under band uncertainties. In contrast to the existing solution, it only requires two scalar values to be determined and eliminates the need for case-by-case statements. Based on this definition, a generic fixed-point algorithm is proposed that iteratively calculates the least favorable distributions for arbitrary band specifications. Finally, three different types of robust tests that emerge from band models are discussed and a numerical example is presented to illustrate their potential use in practice.
A Graph Traversal Based Approach to Answer Non-Aggregation Questions Over DBpedia
Venue: arXiv cs.CL 2018
Year: 2018

We present a question answering system over DBpedia, filling the gap between user information needs expressed in natural language and a structured query interface expressed in SPARQL over the underlying knowledge base (KB). Given the KB, our goal is to comprehend a natural language query and provide corresponding accurate answers. Focusing on solving the non-aggregation questions, in this paper, we construct a subgraph of the knowledge base from the detected entities and propose a graph traversal method to solve both the semantic item mapping problem and the disambiguation problem in a joint way. Compared with existing work, we simplify the process of query intention understanding and pay more attention to the answer path ranking. We evaluate our method on a non-aggregation question dataset and further on a complete dataset. Experimental results show that our method achieves best performance compared with several state-of-the-art systems.
Monotonicity and Competitive Equilibrium in Cake-cutting
Venue: arXiv cs.GT 2018
Year: 2018

We study the monotonicity properties of solutions in the classic problem of fair cake-cutting --- dividing a heterogeneous resource among agents with different preferences. Resource- and population-monotonicity relate to scenarios where the cake, or the number of participants who divide the cake, changes. It is required that the utility of all participants change in the same direction: either all of them are better-off (if there is more to share or fewer to share among) or all are worse-off (if there is less to share or more to share among). We formally introduce these concepts to the cake-cutting problem and examine whether they are satisfied by various common division rules. We prove that the Nash-optimal rule, which maximizes the product of utilities, is resource-monotonic and population-monotonic, in addition to being Pareto-optimal, envy-free and satisfying a strong competitive-equilibrium condition. Moreover, we prove that it is the only rule among a natural family of welfare-maximizing rules that is both proportional and resource-monotonic.
Dynamic Gossip
Venue: arXiv cs.DM 2018
Year: 2018

A gossip protocol is a procedure for spreading secrets among a group of agents, using a connection graph. The goal is for all agents to get to know all secrets, in which case we call the execution of the protocol successful. We consider distributed and dynamic gossip protocols. In distributed gossip the agents themselves instead of a global scheduler determine whom to call. In dynamic gossip not only secrets are exchanged but also telephone numbers (agent identities). This results in increased graph connectivity. We define six such distributed dynamic gossip protocols, and we characterize them in terms of the topology of the graphs on which they are successful, wherein we distinguish strong success (the protocol always terminates, possibly assuming fair scheduling) from weak success (the protocol sometimes terminates). For five of these protocols strong (fair) and weak success are characterized by weakly connected graphs. This result is surprising because the protocols are fairly different. In the sixth protocol an agent may only call another agent if it does not know the other agent's secret. Strong success for this protocol is characterized by graphs for which the set of non-terminal nodes is strongly connected. Weak success for this protocol is characterized by weakly connected graphs satisfying further topological constraints that we define in the paper. One direction of this characterization is surprisingly harder to prove than the other results in this contribution.