OpenRaiser/Intern-Atlas huggingface dataset:
On Manipulation in Prediction Markets When Participants Influence Outcomes Directly
Venue: arXiv cs.GT 2014
Year: 2014

Prediction markets are often used as mechanisms to aggregate information about a future event, for example, whether a candidate will win an election. The event is typically assumed to be exogenous. In reality, participants may influence the outcome, and therefore (1) running the prediction market could change the incentives of participants in the process that creates the outcome (for example, agents may want to change their vote in an election), and (2) simple results such as the myopic incentive compatibility of proper scoring rules no longer hold in the prediction market itself. We introduce a model of games of this kind, where agents first trade in a prediction market and then take an action that influences the market outcome. Our two-stage two-player model, despite its simplicity, captures two aspects of real-world prediction markets: (1) agents may directly influence the outcome, (2) some of the agents instrumental in deciding the outcome may not take part in the prediction market. We show that this game has two different types of perfect Bayesian equilibria, which we term LPP and HPP, depending on the values of the belief parameters: in the LPP domain, equilibrium prices reveal expected market outcomes conditional on the participants' private information, whereas HPP equilibria are collusive -- participants effectively coordinate in an uninformative and untruthful way.
Bar Recursion and Products of Selection Functions
Venue: arXiv cs.LO 2014
Year: 2014

We show how two iterated products of selection functions can both be used in conjunction with system T to interpret, via the dialectica interpretation and modified realizability, full classical analysis. We also show that one iterated product is equivalent over system T to Spector's bar recursion, whereas the other is T-equivalent to modified bar recursion. Modified bar recursion itself is shown to arise directly from the iteration of a different binary product of "skewed" selection functions. Iterations of the dependent binary products are also considered but in all cases are shown to be T-equivalent to the iteration of the simple products.
Towards Investigating Substructures and Role Recognition in Goal Oriented Online Communities
Venue: arXiv cs.SI 2014
Year: 2014

In this paper, we apply social network analytic methods to unveil the structural dynamics of a popular open source goal oriented IRC community, Ubuntu. The primary objective is to track the development of this ever growing community over time using a social network lens and examine the dynamically changing participation patterns of people. Specifically, our research seeks out to investigate answers to the following question: How can the communication dynamics help us in delineating important substructures in the IRC network? This gives an insight into how open source learning communities function internally and what drives the exhibited IRC behavior. By application of a consistent set of social network metrics, we discern factors that affect people's embeddedness in the overall IRC network, their structural influence and importance as discussion initiators or responders. Deciphering these informal connections are crucial for the development of novel strategies to improve communication and foster collaboration between people conversing in the IRC channel, there by stimulating knowledge flow in the network. Our approach reveals a novel network skeleton, that more closely resembles the behavior of participants interacting online. We highlight bottlenecks to effective knowledge dissemination in the IRC, so that focused attention could be provided to communities with peculiar behavioral patterns. Additionally, we explore interesting research directions in augmenting the study of communication dynamics in the IRC.
PTAS for Minimax Approval Voting
Venue: arXiv cs.DS 2014
Year: 2014

We consider Approval Voting systems where each voter decides on a subset to candidates he/she approves. We focus on the optimization problem of finding the committee of fixed size k minimizing the maximal Hamming distance from a vote. In this paper we give a PTAS for this problem and hence resolve the open question raised by Carragianis et al. [AAAI'10]. The result is obtained by adapting the techniques developed by Li et al. [JACM'02] originally used for the less constrained Closest String problem. The technique relies on extracting information and structural properties of constant size subsets of votes.
Service Level Agreement Complexity: Processing Concerns for Standalone and Aggregate SLAs
Venue: arXiv cs.SE 2014
Year: 2014

In this paper, we examine the problem of a single provider offering multiple types of service level agreements, and the implications thereof. In doing so, we propose a simple model for machine-readable service level agreements (SLAs) and outline specifically how these machine-readable SLAs can be constructed and injected into cloud infrastructures - important for next-generation cloud systems as well as customers. We then computationally characterize the problem, establishing the importance of both verification and solution, showing that in the general case injecting policies into cloud infrastructure is NP-Complete, though the problem can be made more tractable by further constraining SLA representations and using approximation techniques.
Leveraging user profile attributes for improving pedagogical accuracy of learning pathways
Venue: arXiv cs.CY 2014
Year: 2014

In recent years, with the enormous explosion of web based learning resources, personalization has become a critical factor for the success of services that wish to leverage the power of Web 2.0. However, the relevance, significance and impact of tailored content delivery in the learning domain is still questionable. Apart from considering only interaction based features like ratings and inferring learner preferences from them, if these services were to incorporate innate user profile attributes which affect learning activities, the quality of recommendations produced could be vastly improved. Recognizing the crucial role of effective guidance in informal educational settings, we provide a principled way of utilizing multiple sources of information from the user profile itself for the recommendation task. We explore factors that affect the choice of learning resources and explain in what way are they helpful to improve the pedagogical accuracy of learning objects recommended. Through a systematical application of machine learning techniques, we further provide a technological solution to convert these indirectly mapped learner specific attributes into a direct mapping with the learning resources. This mapping has a distinct advantage of tagging learning resources to make their metadata more informative. The results of our empirical study depict the similarity of nominal learning attributes with respect to each other. We further succeed in capturing the learner subset, whose preferences are most likely to be an indication of learning resource usage. Our novel system filters learner profile attributes to discover a tag that links them with learning resources.
DMVP: Foremost Waypoint Coverage of Time-Varying Graphs
Venue: arXiv cs.CC 2014
Year: 2014

We consider the Dynamic Map Visitation Problem (DMVP), in which a team of agents must visit a collection of critical locations as quickly as possible, in an environment that may change rapidly and unpredictably during the agents' navigation. We apply recent formulations of time-varying graphs (TVGs) to DMVP, shedding new light on the computational hierarchy $\mathcal{R} \supset \mathcal{B} \supset \mathcal{P}$ of TVG classes by analyzing them in the context of graph navigation. We provide hardness results for all three classes, and for several restricted topologies, we show a separation between the classes by showing severe inapproximability in $\mathcal{R}$, limited approximability in $\mathcal{B}$, and tractability in $\mathcal{P}$. We also give topologies in which DMVP in $\mathcal{R}$ is fixed parameter tractable, which may serve as a first step toward fully characterizing the features that make DMVP difficult.
Parameterized Model-Checking for Timed-Systems with Conjunctive Guards (Extended Version)
Venue: arXiv cs.LO 2014
Year: 2014

In this work we extend the Emerson and Kahlon's cutoff theorems for process skeletons with conjunctive guards to Parameterized Networks of Timed Automata, i.e. systems obtained by an \emph{apriori} unknown number of Timed Automata instantiated from a finite set $U_1, \dots, U_n$ of Timed Automata templates. In this way we aim at giving a tool to universally verify software systems where an unknown number of software components (i.e. processes) interact with continuous time temporal constraints. It is often the case, indeed, that distributed algorithms show an heterogeneous nature, combining dynamic aspects with real-time aspects. In the paper we will also show how to model check a protocol that uses special variables storing identifiers of the participating processes (i.e. PIDs) in Timed Automata with conjunctive guards. This is non-trivial, since solutions to the parameterized verification problem often relies on the processes to be symmetric, i.e. indistinguishable. On the other side, many popular distributed algorithms make use of PIDs and thus cannot directly apply those solutions.
A Preliminary Survey of Knowledge Discovery on Smartphone Applications (apps): Principles, Techniques and Research Directions for E-health
Venue: arXiv cs.CY 2014
Year: 2014

People usually seek out varied information to deal with their health problems. However, the large volume of information available may present challenges for the public to distinguish good from suboptimal advice. How to ensure the right information for the right person at the right time and place has always been a challenge. For example, smart phone application vendor markets provide a varied selection of health applications for users. However, there is a lack of substantive reference information for consumers to base well-informed decisions about whether or not to adopt the applications they review and to ascertain the validity of the information provided by these e-health solutions. Thus, this study aims to review the existing relevant research about smart phone applications and identify pertinent research questions in the field of knowledge discovery for health applications that can be addressed in future research. Therefore, this study can be seen as an important step for researchers to explore this domain and extend our work for the well-being of public.
A unified framework for thermal face recognition
Venue: arXiv cs.CV 2014
Year: 2014

The reduction of the cost of infrared (IR) cameras in recent years has made IR imaging a highly viable modality for face recognition in practice. A particularly attractive advantage of IR-based over conventional, visible spectrum-based face recognition stems from its invariance to visible illumination. In this paper we argue that the main limitation of previous work on face recognition using IR lies in its ad hoc approach to treating different nuisance factors which affect appearance, prohibiting a unified approach that is capable of handling concurrent changes in multiple (or indeed all) major extrinsic sources of variability, which is needed in practice. We describe the first approach that attempts to achieve this - the framework we propose achieves outstanding recognition performance in the presence of variable (i) pose, (ii) facial expression, (iii) physiological state, (iv) partial occlusion due to eye-wear, and (v) quasi-occlusion due to facial hair growth.
Critical Independent Sets of a Graph
Venue: arXiv cs.DM 2014
Year: 2014

Let $G$ be a simple graph with vertex set $V\left( G\right) $. A set $S\subseteq V\left( G\right) $ is independent if no two vertices from $S$ are adjacent, and by $\mathrm{Ind}(G)$ we mean the family of all independent sets of $G$. The number $d\left( X\right) =$ $\left\vert X\right\vert -\left\vert N(X)\right\vert $ is the difference of $X\subseteq V\left( G\right) $, and a set $A\in\mathrm{Ind}(G)$ is critical if $d(A)=\max \{d\left( I\right) :I\in\mathrm{Ind}(G)\}$ (Zhang, 1990). Let us recall the following definitions: $\mathrm{core}\left( G\right) $ = $\bigcap$ {S : S is a maximum independent set}. $\mathrm{corona}\left( G\right)$ = $\bigcup$ {S :S is a maximum independent set}. $\mathrm{\ker}(G)$ = $\bigcap$ {S : S is a critical independent set}. $\mathrm{diadem}(G)$ = $\bigcup$ {S : S is a critical independent set}. In this paper we present various structural properties of $\mathrm{\ker}(G)$, in relation with $\mathrm{core}\left( G\right) $, $\mathrm{corona}\left( G\right) $, and $\mathrm{diadem}(G)$.
'Almost Sure' Chaotic Properties of Machine Learning Methods
Venue: arXiv cs.LG 2014
Year: 2014

It has been demonstrated earlier that universal computation is 'almost surely' chaotic. Machine learning is a form of computational fixed point iteration, iterating over the computable function space. We showcase some properties of this iteration, and establish in general that the iteration is 'almost surely' of chaotic nature. This theory explains the observation in the counter intuitive properties of deep learning methods. This paper demonstrates that these properties are going to be universal to any learning method.
Parallelism-Aware Memory Interference Delay Analysis for COTS Multicore Systems
Venue: arXiv cs.DC 2014
Year: 2014

In modern Commercial Off-The-Shelf (COTS) multicore systems, each core can generate many parallel memory requests at a time. The processing of these parallel requests in the DRAM controller greatly affects the memory interference delay experienced by running tasks on the platform. In this paper, we model a modern COTS multicore system which has a nonblocking last-level cache (LLC) and a DRAM controller that prioritizes reads over writes. To minimize interference, we focus on LLC and DRAM bank partitioned systems. Based on the model, we propose an analysis that computes a safe upper bound for the worst-case memory interference delay. We validated our analysis on a real COTS multicore platform with a set of carefully designed synthetic benchmarks as well as SPEC2006 benchmarks. Evaluation results show that our analysis is more accurately capture the worst-case memory interference delay and provides safer upper bounds compared to a recently proposed analysis which significantly under-estimate the delay.
A Fast Synchronization Clustering Algorithm
Venue: arXiv cs.LG 2014
Year: 2014

This paper presents a Fast Synchronization Clustering algorithm (FSynC), which is an improved version of SynC algorithm. In order to decrease the time complexity of the original SynC algorithm, we combine grid cell partitioning method and Red-Black tree to construct the near neighbor point set of every point. By simulated experiments of some artificial data sets and several real data sets, we observe that FSynC algorithm can often get less time than SynC algorithm for many kinds of data sets. At last, it gives some research expectations to popularize this algorithm.
Using Flow Specifications of Parameterized Cache Coherence Protocols for Verifying Deadlock Freedom
Venue: arXiv cs.DC 2014
Year: 2014

We consider the problem of verifying deadlock freedom for symmetric cache coherence protocols. In particular, we focus on a specific form of deadlock which is useful for the cache coherence protocol domain and consistent with the internal definition of deadlock in the Murphi model checker: we refer to this deadlock as a system- wide deadlock (s-deadlock). In s-deadlock, the entire system gets blocked and is unable to make any transition. Cache coherence protocols consist of N symmetric cache agents, where N is an unbounded parameter; thus the verification of s-deadlock freedom is naturally a parameterized verification problem. Parametrized verification techniques work by using sound abstractions to reduce the unbounded model to a bounded model. Efficient abstractions which work well for industrial scale protocols typically bound the model by replacing the state of most of the agents by an abstract environment, while keeping just one or two agents as is. However, leveraging such efficient abstractions becomes a challenge for s-deadlock: a violation of s-deadlock is a state in which the transitions of all of the unbounded number of agents cannot occur and so a simple abstraction like the one above will not preserve this violation. In this work we address this challenge by presenting a technique which leverages high-level information about the protocols, in the form of message sequence dia- grams referred to as flows, for constructing invariants that are collectively stronger than s-deadlock. Efficient abstractions can be constructed to verify these invariants. We successfully verify the German and Flash protocols using our technique.
Directed Multicut with linearly ordered terminals
Venue: arXiv cs.DS 2014
Year: 2014

Motivated by an application in network security, we investigate the following "linear" case of Directed Mutlicut. Let $G$ be a directed graph which includes some distinguished vertices $t_1, \ldots, t_k$. What is the size of the smallest edge cut which eliminates all paths from $t_i$ to $t_j$ for all $i < j$? We show that this problem is fixed-parameter tractable when parametrized in the cutset size $p$ via an algorithm running in $O(4^p p n^4)$ time.
Feedback through Overhearing
Venue: arXiv cs.IT 2014
Year: 2014

In this paper we examine the value of feedback that comes from overhearing, without dedicated feedback resources. We focus on a simple model for this purpose: a deterministic two-hop interference channel, where feedback comes from overhearing the forward-links. A new aspect brought by this setup is the dual-role of the relay signal. While the relay signal needs to convey the source message to its corresponding destination, it can also provide a feedback signal which can potentially increase the capacity of the first hop. We derive inner and outer bounds on the sum capacity which match for a large range of the parameter values. Our results identify the parameter ranges where overhearing can provide non-negative capacity gain and can even achieve the performance with dedicated-feedback resources. The results also provide insights into which transmissions are most useful to overhear.
Fast Adaptive Algorithm for Robust Evaluation of Quality of Experience
Venue: arXiv cs.MM 2014
Year: 2014

Outlier detection is an integral part of robust evaluation for crowdsourceable Quality of Experience (QoE) and has attracted much attention in recent years. In QoE for multimedia, outliers happen because of different test conditions, human errors, abnormal variations in context, {etc}. In this paper, we propose a simple yet effective algorithm for outlier detection and robust QoE evaluation named iterative Least Trimmed Squares (iLTS). The algorithm assigns binary weights to samples, i.e., 0 or 1 indicating if a sample is an outlier, then the outlier-trimmed subset least squares solutions give robust ranking scores. An iterative optimization is carried alternatively between updating weights and ranking scores which converges to a local optimizer in finite steps. In our test setting, iLTS is up to 190 times faster than LASSO-based methods with a comparable performance. Moreover, a varied version of this method shows adaptation in outlier detection, which provides an automatic detection to determine whether a data sample is an outlier without \emph{a priori} knowledge about the amount of the outliers. The effectiveness and efficiency of iLTS are demonstrated on both simulated examples and real-world applications. A Matlab package is provided to researchers exploiting crowdsourcing paired comparison data for robust ranking.
Intrusions Detection System Based on Ubiquitous Network Nodes
Venue: arXiv cs.CR 2014
Year: 2014

Ubiquitous computing allows to make data and services within the reach of users anytime and anywhere. This makes ubiquitous networks vulnerable to attacks coming from either inside or outside the network. To ensure and enhance networks security, several solutions have been implemented. These solutions are inefficient and or incomplete. Solving these challenges in security with new requirement of Ubicomp, could provide a potential future for such systems towards better mobility and higher confidence level of end user services. We investigate the possibility to detect network intrusions, based on security nodes abilities. Specifically, we show how authentication can help build user profiles in each network node. Authentication is based on permissions and restrictions to access to information and services on ubiquitous network. As a result, our idea realizes a protection of nodes and assures security of network.
A Network Model characterized by a Latent Attribute Structure with Competition
Venue: arXiv cs.SI 2014
Year: 2014

The quest for a model that is able to explain, describe, analyze and simulate real-world complex networks is of uttermost practical as well as theoretical interest. In this paper we introduce and study a network model that is based on a latent attribute structure: each node is characterized by a number of features and the probability of the existence of an edge between two nodes depends on the features they share. Features are chosen according to a process of Indian-Buffet type but with an additional random "fitness" parameter attached to each node, that determines its ability to transmit its own features to other nodes. As a consequence, a node's connectivity does not depend on its age alone, so also "young" nodes are able to compete and succeed in acquiring links. One of the advantages of our model for the latent bipartite "node-attribute" network is that it depends on few parameters with a straightforward interpretation. We provide some theoretical, as well experimental, results regarding the power-law behaviour of the model and the estimation of the parameters. By experimental data, we also show how the proposed model for the attribute structure naturally captures most local and global properties (e.g., degree distributions, connectivity and distance distributions) real networks exhibit. keyword: Complex network, social network, attribute matrix, Indian Buffet process
Simultaneous Approximation of Constraint Satisfaction Problems
Venue: arXiv cs.DS 2014
Year: 2014

Given $k$ collections of 2SAT clauses on the same set of variables $V$, can we find one assignment that satisfies a large fraction of clauses from each collection? We consider such simultaneous constraint satisfaction problems, and design the first nontrivial approximation algorithms in this context. Our main result is that for every CSP $F$, for $k < \tilde{O}(\log^{1/4} n)$, there is a polynomial time constant factor Pareto approximation algorithm for $k$ simultaneous Max-$F$-CSP instances. Our methods are quite general, and we also use them to give an improved approximation factor for simultaneous Max-w-SAT (for $k <\tilde{O}(\log^{1/3} n)$). In contrast, for $k = ω(\log n)$, no nonzero approximation factor for $k$ simultaneous Max-$F$-CSP instances can be achieved in polynomial time (assuming the Exponential Time Hypothesis). These problems are a natural meeting point for the theory of constraint satisfaction problems and multiobjective optimization. We also suggest a number of interesting directions for future research.