OpenRaiser/Intern-Atlas huggingface dataset:
P_3-Games
Venue: arXiv cs.DM 2016
Year: 2016

Without further ado, we present the P_3-game. The P_3-game is decidable for elementary classes of graphs such as paths and cycles. From an algorithmic point of view, the connected P_3-game is fascinating. We show that the connected P_3-game is polynomially decidable for classes such as trees, chordal graphs, ladders, cacti, outerplanar graphs and circular arc graphs.
Enhancing fault tolerance capabilities in quorum-based cycle routing
Venue: arXiv cs.NI 2016
Year: 2016

In this paper we propose a generalized R redundancy cycle technique that provides optical networks almost fault-tolerant communications. More importantly, when applied using only single cycles rather than the standard paired cycles, the generalized R redundancy technique is shown to almost halve the necessary light-trail resources in the network while maintaining the fault-tolerance and dependability expected from cycle-based routing. For efficiency and distributed control, it is common in distributed systems and algorithms to group nodes into intersecting sets referred to as quorum sets. Optimal communication quorum sets forming optical cycles based on light-trails have been shown to flexibly and efficiently route both point-to-point and multipoint-to-multipoint traffic requests. Commonly cycle routing techniques will use pairs of cycles to achieve both routing and fault-tolerance, which uses substantial resources and creates the potential for underutilization. Instead, we intentionally utilize R redundancy within the quorum cycles for fault-tolerance such that every point-to-point communication pairs occur in at least R cycles. The result is a set of R = 3 redundant cycles with 93.23-99.34% fault coverage even with two simultaneous faults all while using 38.85-42.39% fewer resources.
Multi-Operator Spectrum Sharing for Small Cell Networks : A Matching Game Perspective
Venue: arXiv cs.IT 2016
Year: 2016

One of the many problems faced by current cellular network technology is the under utilization of the dedicated, licensed spectrum of network operators. An emerging paradigm to solve this issue is to allow multiple operators to share some parts of each others' spectrum. Previous works on spectrum sharing have failed to integrate the theoretical insights provided by recent developments in stochastic geometrical approaches to cellular network analysis with the objectives of network resource allocation problems. In this paper, we study the non-orthogonal spectrum assignment with the goal of maximizing the social welfare of the network, defined as the expected weighted sum rate of the operators. We adopt the many-to-one stable matching game framework to tackle this problem. Moreover, using the stochastic geometrical approach, we show that its solution can be both stable as well as socially optimal. This allows for computation of the game theoretical solution using generic Markov Chain Monte Carlo method. We also investigate the role of power allocation schemes using Q-learning, and we numerically show that the effect of resource allocation scheme is much more significant than the effect of power allocation for the social welfare of the system.
Seeing with Humans: Gaze-Assisted Neural Image Captioning
Venue: arXiv cs.CV 2016
Year: 2016

Gaze reflects how humans process visual scenes and is therefore increasingly used in computer vision systems. Previous works demonstrated the potential of gaze for object-centric tasks, such as object localization and recognition, but it remains unclear if gaze can also be beneficial for scene-centric tasks, such as image captioning. We present a new perspective on gaze-assisted image captioning by studying the interplay between human gaze and the attention mechanism of deep neural networks. Using a public large-scale gaze dataset, we first assess the relationship between state-of-the-art object and scene recognition models, bottom-up visual saliency, and human gaze. We then propose a novel split attention model for image captioning. Our model integrates human gaze information into an attention-based long short-term memory architecture, and allows the algorithm to allocate attention selectively to both fixated and non-fixated image regions. Through evaluation on the COCO/SALICON datasets we show that our method improves image captioning performance and that gaze can complement machine attention for semantic scene understanding tasks.
Active Learning for Approximation of Expensive Functions with Normal Distributed Output Uncertainty
Venue: arXiv cs.LG 2016
Year: 2016

When approximating a black-box function, sampling with active learning focussing on regions with non-linear responses tends to improve accuracy. We present the FLOLA-Voronoi method introduced previously for deterministic responses, and theoretically derive the impact of output uncertainty. The algorithm automatically puts more emphasis on exploration to provide more information to the models.
Multilingual Modal Sense Classification using a Convolutional Neural Network
Venue: arXiv cs.CL 2016
Year: 2016

Modal sense classification (MSC) is a special WSD task that depends on the meaning of the proposition in the modal's scope. We explore a CNN architecture for classifying modal sense in English and German. We show that CNNs are superior to manually designed feature-based classifiers and a standard NN classifier. We analyze the feature maps learned by the CNN and identify known and previously unattested linguistic features. We benchmark the CNN on a standard WSD task, where it compares favorably to models using sense-disambiguated target vectors.
How Image Degradations Affect Deep CNN-based Face Recognition?
Venue: arXiv cs.CV 2016
Year: 2016

Face recognition approaches that are based on deep convolutional neural networks (CNN) have been dominating the field. The performance improvements they have provided in the so called in-the-wild datasets are significant, however, their performance under image quality degradations have not been assessed, yet. This is particularly important, since in real-world face recognition applications, images may contain various kinds of degradations due to motion blur, noise, compression artifacts, color distortions, and occlusion. In this work, we have addressed this problem and analyzed the influence of these image degradations on the performance of deep CNN-based face recognition approaches using the standard LFW closed-set identification protocol. We have evaluated three popular deep CNN models, namely, the AlexNet, VGG-Face, and GoogLeNet. Results have indicated that blur, noise, and occlusion cause a significant decrease in performance, while deep CNN models are found to be robust to distortions, such as color distortions and change in color balance.
Acceptable Strategy Profiles in Stochastic Games
Venue: arXiv cs.GT 2016
Year: 2016

This paper presents a new solution concept for multiplayer stochastic games, namely, acceptable strategy profiles. For each player $i$ and state $s$ in a stochastic game, let $w_i(s)$ be a real number. A strategy profile is \emph{$w$-acceptable}, where $w=(w_i(s))$, if the discounted payoff to each player $i$ at every initial state $s$ is at least $w_i(s)$, provided the discount factor of the players is sufficiently close to 1. Our goal is to provide simple strategy profiles that are $w$-acceptable for payoff vectors $w$ in which all coordinates are high.
A Distributed Satisfactory Content Delivery Scheme for QoS Provisioning in Delay Tolerant Networks
Venue: arXiv cs.GT 2016
Year: 2016

We deal in this paper with the content forwarding problem in Delay Tolerant Networks (DTNs). We first formulate the content delivery interaction as a non-cooperative satisfaction game. On one hand, the source node seeks to ensure a delivery probability above some given threshold. On the other hand, the relay nodes seek to maximize their own payoffs. The source node offers a reward (virtual coins) to the relay which caches and forwards the file to the final destination. Each relay faces the dilemma of accepting/rejecting to cache the source's file. Cooperation incurs energy cost due to caching, carrying and forwarding the source's file. Yet, when a relay accepts to cooperate, it may receive some reward if it succeeds to be the first relay to forward the content to the destination. Otherwise, the relay may receive some penalty in the form of a constant regret; the latter parameter is introduced to make incentive for cooperation. Next, we introduce the concept of Satisfaction Equilibrium (SE) as a solution concept to the induced game. Now, the source node is solely interested in reaching a file delivery probability greater than some given threshold, while the relays behave rationally to maximize their respective payoffs. Full characterizations of the SEs for both pure and mixed strategies are derived. Furthermore, we propose two learning algorithms allowing the players (source/relays) to reach the SE strategies. Finally, extensive numerical investigations and some learning simulations are carried out to illustrate the behaviour of the interacting nodes.
A Multi-Dimensional Fairness Combinatorial Double-Sided Auction Model in Cloud Environment
Venue: arXiv cs.GT 2016
Year: 2016

In cloud investment markets, consumers are looking for the lowest cost and a desirable fairness while providers are looking for strategies to achieve the highest possible profit and return. Most existing models for auction-based resource allocation in cloud environments only consider the overall profit increase and ignore the profit of each participant individually or the difference between the rich and the poor participants. This paper proposes a multi-dimensional fairness combinatorial double auction (MDFCDA) model which strikes a balance between the revenue and the fairness among participants. We solve a winner determination problem (WDP) through integer programming which incorporates the fairness attribute based on the history of participants which is stored in a repository. Our evaluation results show that the proposed model increases the willingness of participants to take part in the next auction rounds. Moreover, the average percentage of resource utilization is increased.
A Model of Navigation History
Venue: arXiv cs.SE 2016
Year: 2016

Navigation has been a core component of the web since its inception: users and scripts can follow hyperlinks, and can go back or forwards through the navigation history. In this paper, we present a formal model aligned with the WHATWG specification of navigation history, and investigate its properties. The fundamental property of navigation history is that traversing the history by delta then by delta' should be the same as traversing by delta+delta'. In particular, traversing by +1 (forward) then by -1 (back) is the same as traversing by 0 (doing nothing). We show that the specification-aligned model does not satisfy this property, by exhibiting a series of counter-examples, which motivate four patches to the model. We present a series of experiments, showing that browsers are inconsistent in their implementation of navigation history, but that their behaviour is closer to the patched model than to the specification-aligned model. We propose patches to the specification to align it with the patched model.
Revisiting enumerative two-part crude MDL for Bernoulli and multinomial distributions (Extended version)
Venue: arXiv cs.IT 2016
Year: 2016

We leverage the Minimum Description Length (MDL) principle as a model selection technique for Bernoulli distributions and compare several types of MDL codes. We first present a simplistic crude two-part MDL code and a Normalized Maximum Likelihood (NML) code. We then focus on the enumerative two-part crude MDL code, suggest a Bayesian interpretation for finite size data samples, and exhibit a strong connection with the NML approach. We obtain surprising impacts on the estimation of the model complexity together with superior compression performance. This is then generalized to the case of the multinomial distributions. Both the theoretical analysis and the experimental comparisons suggest that one might use the enumerative code rather than NML in practice, for Bernoulli and multinomial distributions.
Private and Truthful Aggregative Game for Large-Scale Spectrum Sharing
Venue: arXiv cs.GT 2016
Year: 2016

Thanks to the rapid development of information technology, the size of the wireless network becomes larger and larger, which makes spectrum resources more precious than ever before. To improve the efficiency of spectrum utilization, game theory has been applied to study the spectrum sharing in wireless networks for a long time. However, the scale of wireless network in existing studies is relatively small. In this paper, we introduce a novel game and model the spectrum sharing problem as an aggregative game for large-scale, heterogeneous, and dynamic networks. The massive usage of spectrum also leads to easier privacy divulgence of spectrum users' actions, which calls for privacy and truthfulness guarantees in wireless network. In a large decentralized scenario, each user has no priori about other users' decisions, which forms an incomplete information game. A "weak mediator", e.g., the base station or licensed spectrum regulator, is introduced and turns this game into a complete one, which is essential to reach a Nash equilibrium (NE). By utilizing past experience on the channel access, we propose an online learning algorithm to improve the utility of each user, achieving NE over time. Our learning algorithm also provides no regret guarantee to each user. Our mechanism admits an approximate ex-post NE. We also prove that it satisfies the joint differential privacy and is incentive-compatible. Efficiency of the approximate NE is evaluated, and the innovative scaling law results are disclosed. Finally, we provide simulation results to verify our analysis.
POLYPATH: Supporting Multiple Tradeoffs for Interaction Latency
Venue: arXiv cs.OS 2016
Year: 2016

Modern mobile systems use a single input-to-display path to serve all applications. In meeting the visual goals of all applications, the path has a latency inadequate for many important interactions. To accommodate the different latency requirements and visual constraints by different interactions, we present POLYPATH, a system design in which application developers (and users) can choose from multiple path designs for their application at any time. Because a POLYPATH system asks for two or more path designs, we present a novel fast path design, called Presto. Presto reduces latency by judiciously allowing frame drops and tearing. We report an Android 5-based prototype of POLYPATH with two path designs: Android legacy and Presto. Using this prototype, we quantify the effectiveness, overhead, and user experience of POLYPATH, especially Presto, through both objective measurements and subjective user assessment. We show that Presto reduces the latency of legacy touchscreen drawing applications by almost half; and more importantly, this reduction is orthogonal to that of other popular approaches and is achieved without any user-noticeable negative visual effect. When combined with touch prediction, Presto is able to reduce the touch latency below 10 ms, a remarkable achievement without any hardware support.
Assessing the Use of Social Media in Massive Open Online Courses
Venue: arXiv cs.CY 2016
Year: 2016

The study explores whether the use of Twitter in Massive Open Online Courses (MOOCs) promotes the interaction among learners. The social network analysis shows that instructors still play a very central role in the social media communication and the communication network between students shrinking over time. The mere use of social media fails to promote learner-learner interaction. More research is needed for understanding learner motivation and how instructional design can help increase their engagement and participation.
Revisiting Reuse in Main Memory Database Systems
Venue: arXiv cs.DB 2016
Year: 2016

Reusing intermediates in databases to speed-up analytical query processing has been studied in the past. Existing solutions typically require intermediate results of individual operators to be materialized into temporary tables to be considered for reuse in subsequent queries. However, these approaches are fundamentally ill-suited for use in modern main memory databases. The reason is that modern main memory DBMSs are typically limited by the bandwidth of the memory bus, thus query execution is heavily optimized to keep tuples in the CPU caches and registers. To that end, adding additional materialization operations into a query plan not only add additional traffic to the memory bus but more importantly prevent the important cache- and register-locality opportunities resulting in high performance penalties. In this paper we study a novel reuse model for intermediates, which caches internal physical data structures materialized during query processing (due to pipeline breakers) and externalizes them so that they become reusable for upcoming operations. We focus on hash tables, the most commonly used internal data structure in main memory databases to perform join and aggregation operations. As queries arrive, our reuse-aware optimizer reasons about the reuse opportunities for hash tables, employing cost models that take into account hash table statistics together with the CPU and data movement costs within the cache hierarchy. Experimental results, based on our HashStash prototype demonstrate performance gains of $2\times$ for typical analytical workloads with no additional overhead for materializing intermediates.
Automata Theory Approach to Predicate Intuitionistic Logic
Venue: arXiv cs.LO 2016
Year: 2016

Predicate intuitionistic logic is a well established fragment of dependent types. According to the Curry-Howard isomorphism proof construction in the logic corresponds well to synthesis of a program the type of which is a given formula. We present a model of automata that can handle proof construction in full intuitionistic first-order logic. The automata are constructed in such a way that any successful run corresponds directly to a normal proof in the logic. This makes it possible to discuss formal languages of proofs or programs, the closure properties of the automata and their connections with the traditional logical connectives.
Pilot Testing an Artificial Intelligence Algorithm That Selects Homeless Youth Peer Leaders Who Promote HIV Testing
Venue: arXiv cs.AI 2016
Year: 2016

Objective. To pilot test an artificial intelligence (AI) algorithm that selects peer change agents (PCA) to disseminate HIV testing messaging in a population of homeless youth. Methods. We recruited and assessed 62 youth at baseline, 1 month (n = 48), and 3 months (n = 38). A Facebook app collected preliminary social network data. Eleven PCAs selected by AI attended a 1-day training and 7 weekly booster sessions. Mixed-effects models with random effects were used to assess change over time. Results. Significant change over time was observed in past 6-month HIV testing (57.9%, 82.4%, 76.3%; p < .05) but not condom use (63.9%, 65.7%, 65.8%). Most youth reported speaking to a PCA about HIV prevention (72.0% at 1 month, 61.5% at 3 months). Conclusions. AI is a promising avenue for implementing PCA models for homeless youth. Increasing rates of regular HIV testing is critical to HIV prevention and linking homeless youth to treatment.
On Optimal Fronthaul Compression and Decoding Strategies for Uplink Cloud Radio Access Networks
Venue: arXiv cs.IT 2016
Year: 2016

This paper investigates the compress-and-forward scheme for an uplink cloud radio access network (C-RAN) model, where multi-antenna base-stations (BSs) are connected to a cloud-computing based central processor (CP) via capacity-limited fronthaul links. The BSs compress the received signals with Wyner-Ziv coding and send the representation bits to the CP; the CP performs the decoding of all the users' messages. Under this setup, this paper makes progress toward the optimal structure of the fronthaul compression and CP decoding strategies for the compress-and-forward scheme in C-RAN. On the CP decoding strategy design, this paper shows that under a sum fronthaul capacity constraint, a generalized successive decoding strategy of the quantization and user message codewords that allows arbitrary interleaved order at the CP achieves the same rate region as the optimal joint decoding. Further, it is shown that a practical strategy of successively decoding the quantization codewords first, then the user messages, achieves the same maximum sum rate as joint decoding under individual fronthaul constraints. On the joint optimization of user transmission and BS quantization strategies, this paper shows that if the input distributions are assumed to be Gaussian, then under joint decoding, the optimal quantization scheme for maximizing the achievable rate region is Gaussian. Moreover, Gaussian input and Gaussian quantization with joint decoding achieve to within a constant gap of the capacity region of the Gaussian multiple-input multiple-output (MIMO) uplink C-RAN model. Finally, this paper addresses the computational aspect of optimizing uplink MIMO C-RAN by showing that under fixed Gaussian input, the sum rate maximization problem over the Gaussian quantization noise covariance matrices can be formulated as convex optimization problems, thereby facilitating its efficient solution.
A Virtual Network PaaS for 3GPP 4G and Beyond Core Network Services
Venue: arXiv cs.NI 2016
Year: 2016

Cloud computing and Network Function Virtualization (NFV) are emerging as key technologies to overcome the challenges facing 4G and beyond mobile systems. Over the last few years, Platform-as-a-Service (PaaS) has gained momentum and has become more widely adopted throughout IT enterprises. It simplifies the applications provisioning and accelerates time-to-market while lowering costs. Telco can leverage the same model to provision the 4G and beyond core network services using NFV technology. However, many challenges have to be addressed, mainly due to the specificities of network services. This paper proposes an architecture for a Virtual Network Platform-as-a-Service (VNPaaS) to provision 3GPP 4G and beyond core network services in a distributed environment. As an illustrative use case, the proposed architecture is employed to provision the 3GPP Home Subscriber Server (HSS) as-a-Service (HSSaaS). The HSSaaS is built from Virtualized Network Functions (VNFs) resulting from a novel decomposition of HSS. A prototype is implemented and early measurements are made.
Bridging Ecology and Cloud: Transposing Ecological Prespective to Enable Better Cloud Autoscaling
Venue: arXiv cs.SE 2016
Year: 2016

Elastic autoscaling is the fundamental mechanism that enables the cloud-based services to continually evolve themselves - through changing the related software configurations and hardware resource provisions - under time-varying workloads. However, given the increasingly complex dynamic, uncertainty and trade-offs related to the runtime QoS and cost/energy of services, cloud autoscaling system is becoming one of the most complex artifacts constructed by human and thus its effectiveness is difficult to be preserved. In this article, we present novel ideas for facilitating cloud autoscaling. Our hypothesis that cloud ecosystem, represented by a collection of cloud-based services, bears many similarities with the natural ecosystem. As such, we in- tend to investigate how ecological view can be adopted to better explain how the cloud-based services evolve, and to explore what are the key factors that drive stable and sustainable cloud-based services in the cloud. To achieve this goal, we aim to transpose ecological principles, theories and models into cloud autoscaling analogues and spontaneously improve long-term stability and sustainability of cloud ecosystem.