OpenRaiser/Intern-Atlas huggingface dataset:
A Near-Optimal Mechanism for Impartial Selection
Venue: arXiv cs.GT 2014
Year: 2014

We examine strategy-proof elections to select a winner amongst a set of agents, each of whom cares only about winning. This impartial selection problem was introduced independently by Holzman and Moulin and Alon et al. Fisher and Klimm showed that the permutation mechanism is impartial and $1/2$-optimal, that is, it selects an agent who gains, in expectation, at least half the number of votes of most popular agent. Furthermore, they showed the mechanism is $7/12$-optimal if agents cannot abstain in the election. We show that a better guarantee is possible, provided the most popular agent receives at least a large enough, but constant, number of votes. Specifically, we prove that, for any $ε>0$, there is a constant $N_ε$ (independent of the number $n$ of voters) such that, if the maximum number of votes of the most popular agent is at least $N_ε$ then the permutation mechanism is $(\frac{3}{4}-ε)$-optimal. This result is tight. Furthermore, in our main result, we prove that near-optimal impartial mechanisms exist. In particular, there is an impartial mechanism that is $(1-ε)$-optimal, for any $ε>0$, provided that the maximum number of votes of the most popular agent is at least a constant $M_ε$.
Learning Nash Equilibria in Congestion Games
Venue: arXiv cs.LG 2014
Year: 2014

We study the repeated congestion game, in which multiple populations of players share resources, and make, at each iteration, a decentralized decision on which resources to utilize. We investigate the following question: given a model of how individual players update their strategies, does the resulting dynamics of strategy profiles converge to the set of Nash equilibria of the one-shot game? We consider in particular a model in which players update their strategies using algorithms with sublinear discounted regret. We show that the resulting sequence of strategy profiles converges to the set of Nash equilibria in the sense of Cesàro means. However, strong convergence is not guaranteed in general. We show that strong convergence can be guaranteed for a class of algorithms with a vanishing upper bound on discounted regret, and which satisfy an additional condition. We call such algorithms AREP algorithms, for Approximate REPlicator, as they can be interpreted as a discrete-time approximation of the replicator equation, which models the continuous-time evolution of population strategies, and which is known to converge for the class of congestion games. In particular, we show that the discounted Hedge algorithm belongs to the AREP class, which guarantees its strong convergence.
On-Line Monitoring for Temporal Logic Robustness
Venue: arXiv cs.SY 2014
Year: 2014

In this paper, we provide a Dynamic Programming algorithm for on-line monitoring of the state robustness of Metric Temporal Logic specifications with past time operators. We compute the robustness of MTL with unbounded past and bounded future temporal operators MTL over sampled traces of Cyber-Physical Systems. We implemented our tool in Matlab as a Simulink block that can be used in any Simulink model. We experimentally demonstrate that the overhead of the MTL robustness monitoring is acceptable for certain classes of practical specifications.
Categories of Quantum and Classical Channels (extended abstract)
Venue: arXiv cs.LO 2014
Year: 2014

We introduce the CP*-construction on a dagger compact closed category as a generalisation of Selinger's CPM-construction. While the latter takes a dagger compact closed category and forms its category of "abstract matrix algebras" and completely positive maps, the CP*-construction forms its category of "abstract C*-algebras" and completely positive maps. This analogy is justified by the case of finite-dimensional Hilbert spaces, where the CP*-construction yields the category of finite-dimensional C*-algebras and completely positive maps. The CP*-construction fully embeds Selinger's CPM-construction in such a way that the objects in the image of the embedding can be thought of as "purely quantum" state spaces. It also embeds the category of classical stochastic maps, whose image consists of "purely classical" state spaces. By allowing classical and quantum data to coexist, this provides elegant abstract notions of preparation, measurement, and more general quantum channels.
The expressive power of quantum walks in terms of language acceptance
Venue: arXiv cs.FL 2014
Year: 2014

Discrete time quantum walks are known to be universal for quantum computation. This has been proven by showing that they can simulate a universal quantum gate set. In this paper, we examine computation by quantum walks in terms of language acceptance, and present two ways in which discrete time quantum walks can accept some languages with certainty. These walks can take quantum as well as classical inputs, and we show that when the input is quantum, the walks can also be interpreted as performing the task of quantum state discrimination.
Genesis of Altmetrics or Article-level Metrics for Measuring Efficacy of Scholarly Communications: Current Perspectives
Venue: arXiv cs.DL 2014
Year: 2014

The article-level metrics (ALMs) or altmetrics becomes a new trendsetter in recent times for measuring the impact of scientific publications and their social outreach to intended audiences. The popular social networks such as Facebook, Twitter, and Linkedin and social bookmarks such as Mendeley and CiteULike are nowadays widely used for communicating research to larger transnational audiences. In 2012, the San Francisco Declaration on Research Assessment got signed by the scientific and researchers communities across the world. This declaration has given preference to the ALM or altmetrics over traditional but faulty journal impact factor (JIF)-based assessment of career scientists. JIF does not consider impact or influence beyond citations count as this count reflected only through Thomson Reuters' Web of Science database. Furthermore, JIF provides indicator related to the journal, but not related to a published paper. Thus, altmetrics now becomes an alternative metrics for performance assessment of individual scientists and their contributed scholarly publications. This paper provides a glimpse of genesis of altmetrics in measuring efficacy of scholarly communications and highlights available altmetric tools and social platforms linking altmetric tools, which are widely used in deriving altmetric scores of scholarly publications. The paper thus argues for institutions and policy makers to pay more attention to altmetrics based indicators for evaluation purpose but cautions that proper safeguards and validations are needed before their adoption.
Permutation Trellis Coded Multi-level FSK Signaling to Mitigate Primary User Interference in Cognitive Radio Networks
Venue: arXiv cs.IT 2014
Year: 2014

We employ Permutation Trellis Code (PTC) based multi-level Frequency Shift Keying signaling to mitigate the impact of Primary Users (PUs) on the performance of Secondary Users (SUs) in Cognitive Radio Networks (CRNs). The PUs are assumed to be dynamic in that they appear intermittently and stay active for an unknown duration. Our approach is based on the use of PTC combined with multi-level FSK modulation so that an SU can improve its data rate by increasing its transmission bandwidth while operating at low power and not creating destructive interference for PUs. We evaluate system performance by obtaining an approximation for the actual Bit Error Rate (BER) using properties of the Viterbi decoder and carry out a thorough performance analysis in terms of BER and throughput. The results show that the proposed coded system achieves i) robustness by ensuring that SUs have stable throughput in the presence of heavy PU interference and ii) improved resiliency of SU links to interference in the presence of multiple dynamic PUs.
Parameterized TSP: Beating the Average
Venue: arXiv cs.DS 2014
Year: 2014

In the Travelling Salesman Problem (TSP), we are given a complete graph $K_n$ together with an integer weighting $w$ on the edges of $K_n$, and we are asked to find a Hamilton cycle of $K_n$ of minimum weight. Let $h(w)$ denote the average weight of a Hamilton cycle of $K_n$ for the weighting $w$. Vizing (1973) asked whether there is a polynomial-time algorithm which always finds a Hamilton cycle of weight at most $h(w)$. He answered this question in the affirmative and subsequently Rublineckii (1973) and others described several other TSP heuristics satisfying this property. In this paper, we prove a considerable generalisation of Vizing's result: for each fixed $k$, we give an algorithm that decides whether, for any input edge weighting $w$ of $K_n$, there is a Hamilton cycle of $K_n$ of weight at most $h(w)-k$ (and constructs such a cycle if it exists). For $k$ fixed, the running time of the algorithm is polynomial in $n$, where the degree of the polynomial does not depend on $k$ (i.e., the generalised Vizing problem is fixed-parameter tractable with respect to the parameter $k$).
Agreement in Partitioned Dynamic Networks
Venue: arXiv cs.DC 2014
Year: 2014

In the dynamic network model, the communication graph is assumed to be connected in every round but is otherwise arbitrary. We consider the related setting of $p$-partitioned dynamic networks, in which the communication graph in each round consists of at most $p$ connected components. We explore the problem of $k$-agreement in this model for $k\geq p$. We show that if the number of processes is unknown then it is impossible to achieve $k$-agreement for any $k$ and any $p\geq 2$. Given an upper bound $n$ on the number of processes, we provide algorithms achieving $k$-agreement in $p(n-p)$ rounds for $k=p$ and in $O(n/ε)$ rounds for $k=\lceil (1+ε)p \rceil$.
Boundary properties of the inconsistency of pairwise comparisons in group decisions
Venue: arXiv cs.AI 2014
Year: 2014

This paper proposes an analysis of the effects of consensus and preference aggregation on the consistency of pairwise comparisons. We define some boundary properties for the inconsistency of group preferences and investigate their relation with different inconsistency indices. Some results are presented on more general dependencies between properties of inconsistency indices and the satisfaction of boundary properties. In the end, given three boundary properties and nine indices among the most relevant ones, we will be able to present a complete analysis of what indices satisfy what properties and offer a reflection on the interpretation of the inconsistency of group preferences.
A Moving Least Squares Based Approach for Contour Visualization of Multi-Dimensional Data
Venue: arXiv cs.GR 2014
Year: 2014

Analysis of high dimensional data is a common task. Often, small multiples are used to visualize 1 or 2 dimensions at a time, such as in a scatterplot matrix. Associating data points between different views can be difficult though, as the points are not fixed. Other times, dimensional reduction techniques are employed to summarize the whole dataset in one image, but individual dimensions are lost in this view. In this paper, we present a means of augmenting a dimensional reduction plot with isocontours to reintroduce the original dimensions. By applying this to each dimension in the original data, we create multiple views where the points are consistent, which facilitates their comparison. Our approach employs a combination of a novel, graph-based projection technique with a GPU accelerated implementation of moving least squares to interpolate space between the points. We also present evaluations of this approach both with a case study and with a user study.
Context-Free Grammars with Storage
Venue: arXiv cs.FL 2014
Year: 2014

Context-free S grammars are introduced, for arbitrary (storage) type S, as a uniform framework for recursion-based grammars, automata, and transducers, viewed as programs. To each occurrence of a nonterminal of a context-free S grammar an object of type S is associated, that can be acted upon by tests and operations, as indicated in the rules of the grammar. Taking particular storage types gives particular formalisms, such as indexed grammars, top-down tree transducers, attribute grammars, etc. Context-free S grammars are equivalent to pushdown S automata. The context-free S languages can be obtained from the deterministic one-way S automaton languages by way of the delta operations on languages, introduced in this paper.
Apuntes relevantes sobre la evaluación en la alfabetización informacional
Venue: arXiv cs.CY 2014
Year: 2014

The purpose of this study is to reflect on some questions concerning the evaluation in information literacy. It is discussed some elements such as scenarios, objects and methods in the evaluation of information literacy programs. It is highlighted the need to influence in the context of such programs as the result of student learning. Some notions emerged from the educational field are taken into account to solidify the ideas presented here. It is argued the implications of this type of assessment practices for information professionals, who serve as trainers of information skills.
Targetable Named Entity Recognition in Social Media
Venue: arXiv cs.CL 2014
Year: 2014

We present a novel approach for recognizing what we call targetable named entities; that is, named entities in a targeted set (e.g, movies, books, TV shows). Unlike many other NER systems that need to retrain their statistical models as new entities arrive, our approach does not require such retraining, which makes it more adaptable for types of entities that are frequently updated. For this preliminary study, we focus on one entity type, movie title, using data collected from Twitter. Our system is tested on two evaluation sets, one including only entities corresponding to movies in our training set, and the other excluding any of those entities. Our final model shows F1-scores of 76.19% and 78.70% on these evaluation sets, which gives strong evidence that our approach is completely unbiased to any par- ticular set of entities found during training.
Lower Bounds for Structuring Unreliable Radio Networks
Venue: arXiv cs.DC 2014
Year: 2014

In this paper, we study lower bounds for randomized solutions to the maximal independent set (MIS) and connected dominating set (CDS) problems in the dual graph model of radio networks---a generalization of the standard graph-based model that now includes unreliable links controlled by an adversary. We begin by proving that a natural geographic constraint on the network topology is required to solve these problems efficiently (i.e., in time polylogarthmic in the network size). We then prove the importance of the assumption that nodes are provided advance knowledge of their reliable neighbors (i.e, neighbors connected by reliable links). Combined, these results answer an open question by proving that the efficient MIS and CDS algorithms from [Censor-Hillel, PODC 2011] are optimal with respect to their dual graph model assumptions. They also provide insight into what properties of an unreliable network enable efficient local computation.
Estimating Maximally Probable Constrained Relations by Mathematical Programming
Venue: arXiv cs.LG 2014
Year: 2014

Estimating a constrained relation is a fundamental problem in machine learning. Special cases are classification (the problem of estimating a map from a set of to-be-classified elements to a set of labels), clustering (the problem of estimating an equivalence relation on a set) and ranking (the problem of estimating a linear order on a set). We contribute a family of probability measures on the set of all relations between two finite, non-empty sets, which offers a joint abstraction of multi-label classification, correlation clustering and ranking by linear ordering. Estimating (learning) a maximally probable measure, given (a training set of) related and unrelated pairs, is a convex optimization problem. Estimating (inferring) a maximally probable relation, given a measure, is a 01-linear program. It is solved in linear time for maps. It is NP-hard for equivalence relations and linear orders. Practical solutions for all three cases are shown in experiments with real data. Finally, estimating a maximally probable measure and relation jointly is posed as a mixed-integer nonlinear program. This formulation suggests a mathematical programming approach to semi-supervised learning.
Adaptive Learning in Cartesian Product of Reproducing Kernel Hilbert Spaces
Venue: arXiv cs.LG 2014
Year: 2014

We propose a novel adaptive learning algorithm based on iterative orthogonal projections in the Cartesian product of multiple reproducing kernel Hilbert spaces (RKHSs). The task is estimating/tracking nonlinear functions which are supposed to contain multiple components such as (i) linear and nonlinear components, (ii) high- and low- frequency components etc. In this case, the use of multiple RKHSs permits a compact representation of multicomponent functions. The proposed algorithm is where two different methods of the author meet: multikernel adaptive filtering and the algorithm of hyperplane projection along affine subspace (HYPASS). In a certain particular case, the sum space of the RKHSs is isomorphic to the product space and hence the proposed algorithm can also be regarded as an iterative projection method in the sum space. The efficacy of the proposed algorithm is shown by numerical examples.
Open-set Person Re-identification
Venue: arXiv cs.CV 2014
Year: 2014

Person re-identification is becoming a hot research for developing both machine learning algorithms and video surveillance applications. The task of person re-identification is to determine which person in a gallery has the same identity to a probe image. This task basically assumes that the subject of the probe image belongs to the gallery, that is, the gallery contains this person. However, in practical applications such as searching a suspect in a video, this assumption is usually not true. In this paper, we consider the open-set person re-identification problem, which includes two sub-tasks, detection and identification. The detection sub-task is to determine the presence of the probe subject in the gallery, and the identification sub-task is to determine which person in the gallery has the same identity as the accepted probe. We present a database collected from a video surveillance setting of 6 cameras, with 200 persons and 7,413 images segmented. Based on this database, we develop a benchmark protocol for evaluating the performance under the open-set person re-identification scenario. Several popular metric learning algorithms for person re-identification have been evaluated as baselines. From the baseline performance, we observe that the open-set person re-identification problem is still largely unresolved, thus further attention and effort is needed.
Assessment of Response Time for New Multi Level Feedback Queue Scheduler
Venue: arXiv cs.OS 2014
Year: 2014

Response time is one of the characteristics of scheduler, happens to be a prominent attribute of any CPU scheduling algorithm. The proposed New Multi Level Feedback Queue [NMLFQ] Scheduler is compared with dynamic, real time, Dependent Activity Scheduling Algorithm (DASA) and Lockes Best Effort Scheduling Algorithm (LBESA). We abbreviated beneficial result of NMLFQ scheduler in comparison with dynamic best effort schedulers with respect to response time.
Modeling Basic Aspects of Cyber-Physical Systems, Part II
Venue: arXiv cs.RO 2014
Year: 2014

We continue to consider the question of what language features are needed to effectively model cyber-physical systems (CPS). In previous work, we proposed using a core language as a way to study this question, and showed how several basic aspects of CPS can be modeled clearly in a language with a small set of constructs. This paper reports on the result of our analysis of two, more complex, case studies from the domain of rigid body dynamics. The first one, a quadcopter, illustrates that previously proposed core language can support larger, more interesting systems than previously shown. The second one, a serial robot, provides a concrete example of why we should add language support for static partial derivatives, namely that it would significantly improve the way models of rigid body dynamics can be expressed.
Amortized $\tilde{O}(|V|)$-Delay Algorithm for Listing Chordless Cycles in Undirected Graphs
Venue: arXiv cs.DS 2014
Year: 2014

Chordless cycles are very natural structures in undirected graphs, with an important history and distinguished role in graph theory. Motivated also by previous work on the classical problem of listing cycles, we study how to list chordless cycles. The best known solution to list all the $C$ chordless cycles contained in an undirected graph $G = (V,E)$ takes $O(|E|^2 +|E|\cdot C)$ time. In this paper we provide an algorithm taking $\tilde{O}(|E| + |V |\cdot C)$ time. We also show how to obtain the same complexity for listing all the $P$ chordless $st$-paths in $G$ (where $C$ is replaced by $P$ ).
An Automated Social Graph De-anonymization Technique
Venue: arXiv cs.CR 2014
Year: 2014

We present a generic and automated approach to re-identifying nodes in anonymized social networks which enables novel anonymization techniques to be quickly evaluated. It uses machine learning (decision forests) to matching pairs of nodes in disparate anonymized sub-graphs. The technique uncovers artefacts and invariants of any black-box anonymization scheme from a small set of examples. Despite a high degree of automation, classification succeeds with significant true positive rates even when small false positive rates are sought. Our evaluation uses publicly available real world datasets to study the performance of our approach against real-world anonymization strategies, namely the schemes used to protect datasets of The Data for Development (D4D) Challenge. We show that the technique is effective even when only small numbers of samples are used for training. Further, since it detects weaknesses in the black-box anonymization scheme it can re-identify nodes in one social network when trained on another.
e-Installation: Synesthetic Documentation of Media Art via Telepresence Technologies
Venue: arXiv cs.OH 2014
Year: 2014

In this paper, a new synesthetic documentation method that contributes to media art conservation is presented. This new method is called e-Installation in analogy to the idea of the e-Book as the electronic version of a real book. An e-Installation is a virtualized media artwork that reproduces all synesthesia, interaction, and meaning levels of the artwork. Advanced 3D modeling and telepresence technologies with a very high level of immersion allow the virtual re-enactment of works of media art that are no longer performable or rarely exhibited. The virtual re-enactment of a media artwork can be designed with a scalable level of complexity depending on whether it addresses professionals such as curators, art restorers, and art theorists or the general public. An e-Installation is independent from the artwork's physical location and can be accessed via head-mounted display or similar data goggles, computer browser, or even mobile devices. In combination with informational and preventive conservation measures, the e-Installation offers an intermediate and long-term solution to archive, disseminate, and pass down the milestones of media art history as a synesthetic documentation when the original work can no longer be repaired or exhibited in its full function.