OpenRaiser/Intern-Atlas huggingface dataset:
Desirability and the birth of incomplete preferences
Venue: arXiv cs.AI 2015
Year: 2015

We establish an equivalence between two seemingly different theories: one is the traditional axiomatisation of incomplete preferences on horse lotteries based on the mixture independence axiom; the other is the theory of desirable gambles developed in the context of imprecise probability. The equivalence allows us to revisit incomplete preferences from the viewpoint of desirability and through the derived notion of coherent lower previsions. On this basis, we obtain new results and insights: in particular, we show that the theory of incomplete preferences can be developed assuming only the existence of a worst act---no best act is needed---, and that a weakened Archimedean axiom suffices too; this axiom allows us also to address some controversy about the regularity assumption (that probabilities should be positive---they need not), which enables us also to deal with uncountable possibility spaces; we show that it is always possible to extend in a minimal way a preference relation to one with a worst act, and yet the resulting relation is never Archimedean, except in a trivial case; we show that the traditional notion of state independence coincides with the notion called strong independence in imprecise probability---this leads us to give much a weaker definition of state independence than the traditional one; we rework and uniform the notions of complete preferences, beliefs, values; we argue that Archimedeanity does not capture all the problems that can be modelled with sets of expected utilities and we provide a new notion that does precisely that. Perhaps most importantly, we argue throughout that desirability is a powerful and natural setting to model, and work with, incomplete preferences, even in case of non-Archimedean problems. This leads us to suggest that desirability, rather than preference, should be the primitive notion at the basis of decision-theoretic axiomatisations.
Writing and Publishing Scientific Articles in Computer Science
Venue: arXiv cs.GL 2015
Year: 2015

Over 15 years of teaching, advising students and coordinating scientific research activities and projects in computer science, we have observed the difficulties of students to write scientific papers to present the results of their research practices. In addition, they repeatedly have doubts about the publishing process. In this article we propose a conceptual framework to support the writing and publishing of scientific papers in computer science, providing a kind of guide for computer science students to effectively present the results of their research practices, particularly for experimental research.
Executing Bag of Distributed Tasks on Virtually Unlimited Cloud Resources
Venue: arXiv cs.DC 2015
Year: 2015

Bag-of-Distributed-Tasks (BoDT) application is the collection of identical and independent tasks each of which requires a piece of input data located around the world. As a result, Cloud computing offers an ef- fective way to execute BoT application as it not only consists of multiple geographically distributed data centres but also allows a user to pay for what she actually uses only. In this paper, BoDT on the Cloud using virtually unlimited cloud resources. A heuristic algorithm is proposed to find an execution plan that takes budget constraints into account. Compared with other approaches, with the same given budget, our algorithm is able to reduce the overall execution time up to 50%.
An Iterative On-Line Mechanism for Demand-Side Aggregation
Venue: arXiv cs.SY 2015
Year: 2015

This paper considers a demand-side aggregation scheme specifically for large numbers of small loads, such as households and small and medium-sized businesses. We introduce a novel auction format, called a staggered clock-proxy auction (SCPA), for on-line scheduling of these loads. This is a two phase format, consisting of: a sequence of overlapping iterative ascending-price clock auctions, one for each time-slot over a finite decision horizon, and; a set of proxy auctions that begin at the termination of each individual clock auction, and which determine the final price and allocation for each time-slot. The overlapping design of the clock phases grant bidders the ability to effectively bid on inter-temporal bundles of electricity use, thereby focusing on the most relevant parts of the price-quantity space. Since electricity is a divisible good, the proxy auction uses demand-schedule bids, which the aggregator uses to compute a uniform-price partial competitive equilibrium for each time slot. We show that, under mild assumptions on the bidders' utilities functions, the proxy phase implements the Vickrey-Clarke-Groves outcome, which makes straightforward bidding in the proxy phase a Bayes-Nash equilibrium. Furthermore, we demonstrate the SCPA in a scenario comprised of household agents with three different utility function types, and show how the mechanism enables efficient on-line energy use scheduling.
ZOS: A Fast Rendezvous Algorithm Based on Set of Available Channels for Cognitive Radios
Venue: arXiv cs.NI 2015
Year: 2015

Most of existing rendezvous algorithms generate channel-hopping sequences based on the whole channel set. They are inefficient when the set of available channels is a small subset of the whole channel set. We propose a new algorithm called ZOS which uses three types of elementary sequences (namely, Zero-type, One-type, and S-type) to generate channel-hopping sequences based on the set of available channels. ZOS provides guaranteed rendezvous without any additional requirements. The maximum time-to-rendezvous of ZOS is upper-bounded by O(m1*m2*log2M) where M is the number of all channels and m1 and m2 are the numbers of available channels of two users.
Comparing Victims of Phishing and Malware Attacks: Unraveling Risk Factors and Possibilities for Situational Crime Prevention
Venue: arXiv cs.CY 2015
Year: 2015

This paper compares the risk factors for becoming a victim of two types of phishing: high-tech phishing (using malicious software) and low-tech phishing (using e-mails and telephone calls). These risk factors are linked to possibilities for situational crime prevention. Data from a cybercrime victim survey in the Netherlands (n=10,316) is used. Based on routine activity theory, the multivariate analyses include thirty variables. The findings show situational crime prevention has to be aimed at groups other than just the users themselves. Criminals are primarily interested in popular online places and the onus is on the owners of these virtual places to protect their visitors from getting infected.
Exact Error Analysis and Energy-Efficiency Optimization of Regenerative Relay Systems with Spatial Correlation
Venue: arXiv cs.IT 2015
Year: 2015

Energy efficiency and its optimization constitute critical tasks in the design of low-power wireless networks. The present work is devoted to the error rate analysis and energy-efficiency optimization of regenerative cooperative networks in the presence of multipath fading under spatial correlation. To this end, exact and asymptotic analytic expressions are firstly derived for the symbol-error-rate of $M{-}$ary quadrature amplitude and $M{-}$ary phase shift keying modulations assuming a dual-hop decode-and-forward relay system, spatially correlated Nakagami${-}m$ multipath fading and maximum ratio combining. The derived expressions are subsequently employed in quantifying the energy consumption of the considered system, incorporating both transmit energy and the energy consumed by the transceiver circuits, as well as in deriving the optimal power allocation formulation for minimizing energy consumption under certain quality-of-service requirements. A relatively harsh path-loss model, that also accounts for realistic device-to-device communications, is adopted in numerical evaluations and various useful insights are provided for the design of future low-energy wireless networks deployments. Indicatively, it is shown that depending on the degree of spatial correlation, severity of fading, transmission distance, relay location and power allocation strategy, target performance can be achieved with large overall energy reduction compared to direct transmission reference.
Generalized Kirchhoff-Law-Johnson-Noise (KLJN) secure key exchange system using arbitrary resistors
Venue: arXiv cs.CR 2015
Year: 2015

The Kirchhoff-Law-Johnson-Noise (KLJN) secure key exchange system has been introduced as a simple, very low cost and efficient classical physical alternative to quantum key distribution systems. The ideal system uses only a few electronic components - identical resistor pairs, switches and interconnecting wires - to guarantee perfectly protected data transmission. We show that a generalized KLJN system can provide unconditional security even if it is used with significantly less limitations. The more universal conditions ease practical realizations considerably and support more robust protection against attacks. Our theoretical results are confirmed by numerical simulations.
An inequality for the Fourier spectrum of parity decision trees
Venue: arXiv cs.DM 2015
Year: 2015

We give a new bound on the sum of the linear Fourier coefficients of a Boolean function in terms of its parity decision tree complexity. This result generalizes an inequality of O'Donnell and Servedio for regular decision trees. We use this bound to obtain the first non-trivial lower bound on the parity decision tree complexity of the recursive majority function.
Utility Fair Rate Allocation in LTE/802.11 Networks
Venue: arXiv cs.NI 2015
Year: 2015

We consider proportional fair rate allocation in a heterogeneous network with a mix of LTE and 802.11 cells which supports multipath and multihomed operation (simultaneous connection of a user device to multiple LTE BSs and 802.11 APs). We show that the utility fair optimisation problem is non-convex but that a global optimum can be found by solving a sequence of convex optimisations in a distributed fashion. The result is a principled approach to offload from LTE to 802.11 and for exploiting LTE/802.11 path diversity to meet user traffic demands.
Dependent Random Graphs and Multiparty Pointer Jumping
Venue: arXiv cs.CC 2015
Year: 2015

We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs "dependent random graphs". Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. We also obtain bounds for the chromatic number. Surprisingly, many of the standard properties of random graphs also hold in this relaxed setting. We show that with high probability, a dependent random graph will contain a clique of size $\frac{(1-o(1))\log n}{\log(1/p)}$, and the chromatic number will be at most $\frac{n \log(1/1-p)}{\log n}$. As an application and second main result, we give a new communication protocol for the k-player Multiparty Pointer Jumping (MPJ_k) problem in the number-on-the-forehead (NOF) model. Multiparty Pointer Jumping is one of the canonical NOF communication problems, yet even for three players, its communication complexity is not well understood. Our protocol for MPJ_3 costs $O(\frac{n\log\log n}{\log n})$ communication, improving on a bound of Brody and Chakrabarti [BC08]. We extend our protocol to the non-Boolean pointer jumping problem $\widehat{MPJ}_k$, achieving an upper bound which is o(n) for any $k >= 4$ players. This is the first o(n) bound for $\widehat{MPJ}_k$ and improves on a bound of Damm, Jukna, and Sgall [DJS98] which has stood for almost twenty years.
A Convex Optimization Approach to Smooth Trajectories for Motion Planning with Car-Like Robots
Venue: arXiv cs.RO 2015
Year: 2015

In the recent past, several sampling-based algorithms have been proposed to compute trajectories that are collision-free and dynamically-feasible. However, the outputs of such algorithms are notoriously jagged. In this paper, by focusing on robots with car-like dynamics, we present a fast and simple heuristic algorithm, named Convex Elastic Smoothing (CES) algorithm, for trajectory smoothing and speed optimization. The CES algorithm is inspired by earlier work on elastic band planning and iteratively performs shape and speed optimization. The key feature of the algorithm is that both optimization problems can be solved via convex programming, making CES particularly fast. A range of numerical experiments show that the CES algorithm returns high-quality solutions in a matter of a few hundreds of milliseconds and hence appears amenable to a real-time implementation.
Hyperspectral Image Classification and Clutter Detection via Multiple Structural Embeddings and Dimension Reductions
Venue: arXiv cs.CV 2015
Year: 2015

We present a new and effective approach for Hyperspectral Image (HSI) classification and clutter detection, overcoming a few long-standing challenges presented by HSI data characteristics. Residing in a high-dimensional spectral attribute space, HSI data samples are known to be strongly correlated in their spectral signatures, exhibit nonlinear structure due to several physical laws, and contain uncertainty and noise from multiple sources. In the presented approach, we generate an adaptive, structurally enriched representation environment, and employ the locally linear embedding (LLE) in it. There are two structure layers external to LLE. One is feature space embedding: the HSI data attributes are embedded into a discriminatory feature space where spatio-spectral coherence and distinctive structures are distilled and exploited to mitigate various difficulties encountered in the native hyperspectral attribute space. The other structure layer encloses the ranges of algorithmic parameters for LLE and feature embedding, and supports a multiplexing and integrating scheme for contending with multi-source uncertainty. Experiments on two commonly used HSI datasets with a small number of learning samples have rendered remarkably high-accuracy classification results, as well as distinctive maps of detected clutter regions.
A Game-Theoretic Model and Best-Response Learning Method for Ad Hoc Coordination in Multiagent Systems
Venue: arXiv cs.GT 2015
Year: 2015

The ad hoc coordination problem is to design an autonomous agent which is able to achieve optimal flexibility and efficiency in a multiagent system with no mechanisms for prior coordination. We conceptualise this problem formally using a game-theoretic model, called the stochastic Bayesian game, in which the behaviour of a player is determined by its private information, or type. Based on this model, we derive a solution, called Harsanyi-Bellman Ad Hoc Coordination (HBA), which utilises the concept of Bayesian Nash equilibrium in a planning procedure to find optimal actions in the sense of Bellman optimal control. We evaluate HBA in a multiagent logistics domain called level-based foraging, showing that it achieves higher flexibility and efficiency than several alternative algorithms. We also report on a human-machine experiment at a public science exhibition in which the human participants played repeated Prisoner's Dilemma and Rock-Paper-Scissors against HBA and alternative algorithms, showing that HBA achieves equal efficiency and a significantly higher welfare and winning rate.
Distributed Optimal Quantization and Power Allocation for Sensor Detection Via Consensus
Venue: arXiv cs.SY 2015
Year: 2015

We address the optimal transmit power allocation problem (from the sensor nodes (SNs) to the fusion center (FC)) for the decentralized detection of an unknown deterministic spatially uncorrelated signal which is being observed by a distributed wireless sensor network. We propose a novel fully distributed algorithm, in order to calculate the optimal transmit power allocation for each sensor node (SN) and the optimal number of quantization bits for the test statistic in order to match the channel capacity. The SNs send their quantized information over orthogonal uncorrelated channels to the FC which linearly combines them and makes a final decision. What makes this scheme attractive is that the SNs share with their neighbours just their individual transmit powers at the current states. As a result, the SN processing complexity is further reduced.
PDF Steganography based on Chinese Remainder Theorem
Venue: arXiv cs.CR 2015
Year: 2015

We propose different approaches of PDF files based steganography, essentially based on the Chinese Remainder Theorem. Here, after a cover PDF document has been released from unnecessary A0, a secret message is hidden in it using one of the proposed approaches, making it invisible to common PDF readers, and the file is then transmitted through a non-secure communication channel. Where each of our methods, ensure the condition that the number of inserted A0 is less than the number of characters of the secret message s.
Network investigation methodology for BitTorrent Sync: A Peer-to-Peer based file synchronisation service
Venue: arXiv cs.CR 2015
Year: 2015

High availability is no longer just a business continuity concern. Users are increasingly dependant on devices that consume and produce data in ever increasing volumes. A popular solution is to have a central repository which each device accesses after centrally managed authentication. This model of use is facilitated by cloud based file synchronisation services such as Dropbox, OneDrive, Google Drive and Apple iCloud. Cloud architecture allows the provisioning of storage space with "always-on" access. Recent concerns over unauthorised access to third party systems and large scale exposure of private data have made an alternative solution desirable. These events have caused users to assess their own security practices and the level of trust placed in third party storage services. One option is BitTorrent Sync, a cloudless synchronisation utility provides data availability and redundancy. This utility replicates files stored in shares to remote peers with access controlled by keys and permissions. While lacking the economies brought about by scale, complete control over data access has made this a popular solution. The ability to replicate data without oversight introduces risk of abuse by users as well as difficulties for forensic investigators. This paper suggests a methodology for investigation and analysis of the protocol to assist in the control of data flow across security perimeters.
Encoding Markov Logic Networks in Possibilistic Logic
Venue: arXiv cs.AI 2015
Year: 2015

Markov logic uses weighted formulas to compactly encode a probability distribution over possible worlds. Despite the use of logical formulas, Markov logic networks (MLNs) can be difficult to interpret, due to the often counter-intuitive meaning of their weights. To address this issue, we propose a method to construct a possibilistic logic theory that exactly captures what can be derived from a given MLN using maximum a posteriori (MAP) inference. Unfortunately, the size of this theory is exponential in general. We therefore also propose two methods which can derive compact theories that still capture MAP inference, but only for specific types of evidence. These theories can be used, among others, to make explicit the hidden assumptions underlying an MLN or to explain the predictions it makes.
Virtual Machine Placement Literature Review
Venue: arXiv cs.DC 2015
Year: 2015

Cloud Computing Datacenters host millions of virtual machines (VMs) on real world scenarios. In this context, Virtual Machine Placement (VMP) is one of the most challenging problems in cloud infrastructure management, considering also the large number of possible optimization criteria and different formulations that could be studied. VMP literature include relevant topics such as energy-efficiency, Service Level Agreements (SLA), cloud service markets, Quality of Service (QoS) and carbon dioxide emissions, all of them with high economical and ecological impact. This work presents an extensive up-to-date review of the most relevant VMP literature in order to identify research opportunities.
Backlog and Delay Reasoning in HARQ Systems
Venue: arXiv cs.IT 2015
Year: 2015

Recently, hybrid-automatic-repeat-request (HARQ) systems have been favored in particular state-of-the-art communications systems since they provide the practicality of error detections and corrections aligned with repeat-requests when needed at receivers. The queueing characteristics of these systems have taken considerable focus since the current technology demands data transmissions with a minimum delay provisioning. In this paper, we investigate the effects of physical layer characteristics on data link layer performance in a general class of HARQ systems. Constructing a state transition model that combines queue activity at a transmitter and decoding efficiency at a receiver, we identify the probability of clearing the queue at the transmitter and the packet-loss probability at the receiver. We determine the effective capacity that yields the maximum feasible data arrival rate at the queue under quality-of-service constraints. In addition, we put forward non-asymptotic backlog and delay bounds. Finally, regarding three different HARQ protocols, namely Type-I HARQ, HARQ-chase combining (HARQ-CC) and HARQ-incremental redundancy (HARQ-IR), we show the superiority of HARQ-IR in delay robustness over the others. However, we further observe that the performance gap between HARQ-CC and HARQ-IR is quite negligible in certain cases. The novelty of our paper is a general cross-layer analysis of these systems, considering encoding/decoding in the physical layer and delay aspects in the data-link layer.
A Concurrency Problem with Exponential DPLL(T) Proofs
Venue: arXiv cs.LO 2015
Year: 2015

Many satisfiability modulo theories solvers implement a variant of the DPLL(T ) framework which separates theory-specific reasoning from reasoning on the propositional abstraction of the formula. Such solvers conclude that a formula is unsatisfiable once they have learned enough theory conflicts to derive a propositional contradiction. However some problems, such as the diamonds problem, require learning exponentially many conflicts. We give a general criterion for establishing lower bounds on the number of theory conflicts in any DPLL(T ) proof for a given problem. We apply our criterion to two different state-of-the-art symbolic partial-order encodings of a simple, yet representative concurrency problem. Even though one of the encodings is asymptotically smaller than the other, we establish the same exponential lower bound proof complexity for both. Our experiments confirm this theoretical lower bound across multiple solvers and theory combinations.
CloRoFor: Cloud Robust Forensics
Venue: arXiv cs.DC 2015
Year: 2015

The malicious alteration of machine time is a big challenge in computer forensics. Detecting such changes and reconstructing the actual timeline of events is of paramount importance. However, this can be difficult since the attacker has many opportunities and means to hide such changes. In particular, cloud computing, host and guest machine time can be manipulated in various ways by an attacker. Guest virtual machines are especially vulnerable to attacks coming from their (more privileged) host. As such, it is important to guarantee the timeline integrity of both hosts and guests in a cloud, or at least to ensure that the alteration of such timeline does not go undetected. In this paper we survey the issues related to host and guest machine time integrity in the cloud. Further, we describe a novel architecture for host and guest time alteration detection and correction/resilience with respect to compromised hosts and guests. The proposed framework has been implemented on an especially built simulator. Collected results are evaluated and discussed. Performance figures show the feasibility of our proposal.