OpenRaiser/Intern-Atlas huggingface dataset:
The Mysteries of Security Games: Equilibrium Computation Becomes Combinatorial Algorithm Design
Venue: arXiv cs.GT 2016
Year: 2016

The security game is a basic model for resource allocation in adversarial environments. Here there are two players, a defender and an attacker. The defender wants to allocate her limited resources to defend critical targets and the attacker seeks his most favorable target to attack. In the past decade, there has been a surge of research interest in analyzing and solving security games that are motivated by applications from various domains. This paper examines security games from a theoretical perspective and provides a unified view of various security game models. In particular, each security game can be characterized by a set system $E$ which consists of the defender's pure strategies, The defender's best response problem can be viewed as a combinatorial optimization problem over $E$. Our framework captures most of the basic security game models in the literature, including all the deployed systems, The set system $E$ arising from various domains encodes standard combinatorial problems like bipartite matching, maximum coverage, min-cost flow, packing problems, etc. Our main result shows that equilibrium computation in security games is essentially a combinatorial problem. In particular, we prove that, for any set system $E$, the following problems can be reduced to each other in polynomial time: (0) combinatorial optimization over $E$, (1) computing the minimax equilibrium for zero-sum security games over $E$, (2) computing the strong Stackelberg equilibrium for security games over $E$, (3) computing the best or worst (for the defender) Nash equilibrium for security games over $E$. Here, by "games over $E$" we mean the class of security games with arbitrary payoff structures, but a fixed set $E$ of defender pure strategies. This shows that the complexity of a security game is essentially determined by the set system $E$.
The Effect of Communication Topology on Scalar Field Estimation by Networked Robotic Swarms
Venue: arXiv cs.RO 2016
Year: 2016

This paper studies the problem of reconstructing a two-dimensional scalar field using a swarm of networked robots with local communication capabilities. We consider the communication network of the robots to form either a chain or a grid topology. We formulate the reconstruction problem as an optimization problem that is constrained by first-order linear dynamics on a large, interconnected system. To solve this problem, we employ an optimization-based scheme that uses a gradient-based method with an analytical computation of the gradient. In addition, we derive bounds on the trace of observability Gramian of the system, which helps us to quantify and compare the estimation capability of chain and grid networks. A comparison based on a performance measure related to the H2 norm of the system is also used to study robustness of the network topologies. Our resultsare validated using both simulated scalar fields and actual ocean salinity data.
An Evolvable Fuzzy Logic System for handoff management in heterogeneous Wireless Networks
Venue: arXiv cs.NI 2016
Year: 2016

One of the features of the Next Generation Wireless Networks (NGWNs) is its heterogeneous communication environment. Heterogeneous networks are ranging from wireless WAN, LAN, MAN and PAN. The most important parameters in this regard are different data rates and coverage of these networks. In this paper, we propose an evolvable fuzzy logic-based algorithm for managing handover process in heterogeneous wireless networks. We use fuzzy logic system to determine the right time of initiating the handoff procedure and utilize Genetic Algorithm (GA) to predict the best form of rules of the fuzzy module. We implement our proposed scheme on a special simulation model and discuss about the impact of evolution on the algorithm.
Fair Scheduling for Data Collection in Mobile Sensor Networks with Energy Harvesting
Venue: arXiv cs.NI 2016
Year: 2016

We consider the problem of data collection from a continental-scale network of energy harvesting sensors, applied to tracking mobile assets in rural environments. Our application constraints favour a highly asymmetric solution, with heavily duty-cycled sensor nodes communicating with powered base stations. We study a novel scheduling optimisation problem for energy harvesting mobile sensor network, that maximises the amount of collected data under the constraints of radio link quality and energy harvesting efficiency, while ensuring a fair data reception. We show that the problem is NP-complete and propose a heuristic algorithm to approximate the optimal scheduling solution in polynomial time. Moreover, our algorithm is flexible in handling progressive energy harvesting events, such as with solar panels, or opportunistic and bursty events, such as with Wireless Power Transfer. We use empirical link quality data, solar energy, and WPT efficiency to evaluate the proposed algorithm in extensive simulations and compare its performance to state-of-the-art. We show that our algorithm achieves high data reception rates, under different fairness and node lifetime constraints.
Extracting Arabic Relations from the Web
Venue: arXiv cs.CL 2016
Year: 2016

The goal of this research is to extract a large list or table from named entities and relations in a specific domain. A small set of a handful of instance relations is required as input from the user. The system exploits summaries from Google search engine as a source text. These instances are used to extract patterns. The output is a set of new entities and their relations. The results from four experiments show that precision and recall varies according to relation type. Precision ranges from 0.61 to 0.75 while recall ranges from 0.71 to 0.83. The best result is obtained for (player, club) relationship, 0.72 and 0.83 for precision and recall respectively.
Robust multigrid for high-order discontinuous Galerkin methods: A fast Poisson solver suitable for high-aspect ratio Cartesian grids
Venue: arXiv cs.CE 2016
Year: 2016

We present a polynomial multigrid method for nodal interior penalty and local discontinuous Galerkin formulations of the Poisson equation on Cartesian grids. For smoothing we propose two classes of overlapping Schwarz methods. The first class comprises element-centered and the second face-centered methods. Within both classes we identify methods that achieve superior convergence rates, prove robust with respect to the mesh spacing and the polynomial order, at least up to ${P=32}$. Consequent structure exploitation yields a computational complexity of $O(PN)$, where $N$ is the number of unknowns. Further we demonstrate the suitability of the face-centered method for element aspect ratios up to 32.
A Jamming-resilient Algorithm for Self-triggered Network Coordination
Venue: arXiv cs.SY 2016
Year: 2016

The issue of cyber-security has become ever more prevalent in the analysis and design of cyber-physical systems. In this paper, we investigate self-triggered consensus networks in the presence of communication failures caused by Denialof- Service (DoS) attacks. A general framework is considered in which the network links can fail independent of each other. By introducing a notion of Persistency-of-Communication (PoC), we provide an explicit characterization of DoS frequency and duration under which consensus can be preserved by suitably designing time-varying control and communication policies. An explicit characterization of the effects of DoS on the consensus time is also provided. The considered notion of PoC is compared with classic average connectivity conditions that are found in pure continuous-time consensus networks. Finally, examples are given to substantiate the analysis.
Resilient Control under Denial-of-Service:Robust Design
Venue: arXiv cs.SY 2016
Year: 2016

In this paper, we study networked control systems in the presence of Denial-of-Service (DoS) attacks, namely attacks that prevent transmissions over the communication network. The control objective is to maximize frequency and duration of the DoS attacks under which closed-loop stability is not destroyed. Analog and digital predictor-based controllers with state resetting are proposed, which achieve the considered control objective for a general class of DoS signals. An example is given to illustrate the proposed solution approach.
Interactive Modeling of Concept Drift and Errors in Relevance Feedback
Venue: arXiv cs.HC 2016
Year: 2016

Users giving relevance feedback in exploratory search are often uncertain about the correctness of their feedback, which may result in noisy or even erroneous feedback. Additionally, the search intent of the user may be volatile as the user is constantly learning and reformulating her search hypotheses during the search. This may lead to a noticeable concept drift in the feedback. We formulate a Bayesian regression model for predicting the accuracy of each individual user feedback and thus find outliers in the feedback data set. Additionally, we introduce a timeline interface that visualizes the feedback history to the user and gives her suggestions on which past feedback is likely in need of adjustment. This interface also allows the user to adjust the feedback accuracy inferences made by the model. Simulation experiments demonstrate that the performance of the new user model outperforms a simpler baseline and that the performance approaches that of an oracle, given a small amount of additional user interaction. A user study shows that the proposed modelling technique, combined with the timeline interface, makes it easier for the users to notice and correct mistakes in their feedback, and to discover new items.
A regularization-based approach for unsupervised image segmentation
Venue: arXiv cs.CV 2016
Year: 2016

We propose a novel unsupervised image segmentation algorithm, which aims to segment an image into several coherent parts. It requires no user input, no supervised learning phase and assumes an unknown number of segments. It achieves this by first over-segmenting the image into several hundred superpixels. These are iteratively joined on the basis of a discriminative classifier trained on color and texture information obtained from each superpixel. The output of the classifier is regularized by a Markov random field that lends more influence to neighbouring superpixels that are more similar. In each iteration, similar superpixels fall under the same label, until only a few coherent regions remain in the image. The algorithm was tested on a standard evaluation data set, where it performs on par with state-of-the-art algorithms in term of precision and greatly outperforms the state of the art by reducing the oversegmentation of the object of interest.
Resource Sharing in 5G mmWave Cellular Networks
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, we discuss resource sharing, a key dimension in mmWave network design in which spectrum, access and/or network infrastructure resources can be shared by multiple operators. It is argued that this sharing paradigm will be essential to fully exploit the tremendous amounts of bandwidth and the large number of antenna degrees of freedom available in these bands, and to provide statistical multiplexing to accommodate the highly variable nature of the traffic. In this paper, we investigate and compare various sharing configurations in order to capture the enhanced potential of mmWave communications. Our results reflect both the technical and the economical aspects of the various sharing paradigms. We deliver a number of key insights, corroborated by detailed simulations, which include an analysis of the effects of the distinctive propagation characteristics of the mmWave channel, along with a rigorous multi-antenna characterization. Key findings of this study include (i) the strong dependence of the comparative results on channel propagation and antenna characteristics, and therefore the need to accurately model them, and (ii) the desirability of a full spectrum and infrastructure sharing configuration, which may result in increased user rate as well as in economical advantages for both service provider.
Multi-prover Proof-of-Retrievability
Venue: arXiv cs.CR 2016
Year: 2016

There has been considerable recent interest in "cloud storage" wherein a user asks a server to store a large file. One issue is whether the user can verify that the server is actually storing the file, and typically a challenge-response protocol is employed to convince the user that the file is indeed being stored correctly. The security of these schemes is phrased in terms of an extractor which will recover the file given any "proving algorithm" that has a sufficiently high success probability. This forms the basis of \emph{proof-of-retrievability} ($\mathsf{PoR}$) systems. In this paper, we study multiple server $\mathsf{PoR}$ systems. We formalize security definitions for two possible scenarios: (i) when a threshold of servers succeed with high enough probability (worst-case) and (ii) when the average of the success probability of all the servers is above a threshold (average-case). We also motivate the study of confidentiality of the outsourced message. We give $\mathsf{M}\mbox{-}\mathsf{PoR}$ schemes which are secure under both these security definitions and provide reasonable confidentiality guarantees even when there is no restriction on the computational power of the servers. We also show how classical statistical techniques used by Paterson, Stinson and Upadhyay (Journal of Mathematical Cryptology: 7(3)) can be extended to evaluate whether the responses of the provers are accurate enough to permit successful extraction. We also look at one specific instantiation of our construction when instantiated with the unconditionally secure version of the Shacham-Waters scheme (Asiacrypt, 2008). This scheme gives reasonable security and privacy guarantee. We show that, in the multi-server setting with computationally unbounded provers, one can overcome the limitation that the verifier needs to store as much secret information as the provers.
Efficient Authentication of Outsourced String Similarity Search
Venue: arXiv cs.CR 2016
Year: 2016

Cloud computing enables the outsourcing of big data analytics, where a third party server is responsible for data storage and processing. In this paper, we consider the outsourcing model that provides string similarity search as the service. In particular, given a similarity search query, the service provider returns all strings from the outsourced dataset that are similar to the query string. A major security concern of the outsourcing paradigm is to authenticate whether the service provider returns sound and complete search results. In this paper, we design AutoS3, an authentication mechanism of outsourced string similarity search. The key idea of AutoS3 is that the server returns a verification object VO to prove the result correctness. First, we design an authenticated string indexing structure named MBtree for VO construction. Second, we design two lightweight authentication methods named VS2 and EVS2 that can catch the service provider various cheating behaviors with cheap verification cost. Moreover, we generalize our solution for top k string similarity search. We perform an extensive set of experiment results on real world datasets to demonstrate the efficiency of our approach.
LDA Lattices Without Dithering Achieve Capacity on the Gaussian Channel
Venue: arXiv cs.IT 2016
Year: 2016

This paper deals with Low-Density Construction-A (LDA) lattices, which are obtained via Construction A from non-binary Low-Density Parity-Check codes. More precisely, a proof is provided that Voronoi constellations of LDA lattices achieve the capacity of the AWGN channel under lattice encoding and decoding. This is obtained after showing the same result for more general Construction-A lattice constellations. The theoretical analysis is carried out in a way that allows to describe how the prime number underlying Construction A behaves as a function of the lattice dimension. Moreover, no dithering is required in the transmission scheme, simplifying some previous solutions of the problem. Remarkably, capacity is achievable with LDA lattice codes whose parity-check matrices have constant row and column Hamming weights. Some expansion properties of random bipartite graphs constitute an extremely important tool for dealing with sparse matrices and allow to find a lower bound of the minimum Euclidean distance of LDA lattices in our ensemble.
Notes on Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
Venue: arXiv cs.CG 2016
Year: 2016

This write-up contains some minor results and notes related to our work [HQ15] (some of them already known in the literature). In particular, it shows the following: - We show that a graph with polynomial expansion have sublinear separators. - We show that hereditary sublinear separators imply that a graph have small divisions. - We show a natural condition on a set of segments, such that they have low density. This might be of independent interest in trying to define a realistic input model for a set of segments. Unlike the previous two results, this is new. For context and more details, see the main paper.
Robust Design of Spectrum-Sharing Networks
Venue: arXiv cs.NI 2016
Year: 2016

In spectrum-sharing networks, primary users have the right to preempt secondary users, which significantly degrades the performance of underlying secondary users. In this paper, we use backup channels to provide reliability guarantees for secondary users. In particular, we study the optimal white channel assignment that minimizes the amount of recovery capacity (i.e., bandwidth of backup channels) needed to meet a given reliability guarantee. This problem is shown to be coupled by two NP-hard objectives. We characterize the structure of the optimal assignment and develop bi-criteria approximation algorithms. Moreover, we investigate the scaling of the recovery capacity as the network size becomes large. It is shown that the recovery capacity is negligible as compared to the total traffic demands in a large-scale network.
Daala: A Perceptually-Driven Next Generation Video Codec
Venue: arXiv cs.MM 2016
Year: 2016

The Daala project is a royalty-free video codec that attempts to compete with the best patent-encumbered codecs. Part of our strategy is to replace core tools of traditional video codecs with alternative approaches, many of them designed to take perceptual aspects into account, rather than optimizing for simple metrics like PSNR. This paper documents some of our experiences with these tools, which ones worked and which did not, and what we've learned from them. The result is a codec which compares favorably with HEVC on still images, and is on a path to do so for video as well.
Noisy Index Coding with PSK and QAM
Venue: arXiv cs.IT 2016
Year: 2016

Noisy index coding problems over AWGN channel are considered. For a given index coding problem and a chosen scalar linear index code of length $N$, we propose to transmit the $N$ index coded bits as a single signal from a $2^N$- PSK constellation. By transmitting the index coded bits in this way, there is an $N/2$ - fold reduction in the bandwidth consumed. Also, receivers with side information satisfying certain conditions get coding gain relative to a receiver with no side information. This coding gain is due to proper utilization of their side information and hence is called "PSK side information coding gain (PSK-SICG)". A necessary and sufficient condition for a receiver to get PSK-SICG is presented. An algorithm to map the index coded bits to PSK signal set such that the PSK-SICG obtained is maximized for the receiver with maximum side information is given. We go on to show that instead of transmitting the $N$ index coded bits as a signal from $2^N$- PSK, we can as well transmit them as a signal from $2^N$- QAM and all the results including the necessary and sufficient condition to get coding gain holds. We prove that sending the index coded bits as a QAM signal is better than sending them as a PSK signal when the receivers see an effective signal set of eight points or more.
Scalable Linear Causal Inference for Irregularly Sampled Time Series with Long Range Dependencies
Venue: arXiv cs.LG 2016
Year: 2016

Linear causal analysis is central to a wide range of important application spanning finance, the physical sciences, and engineering. Much of the existing literature in linear causal analysis operates in the time domain. Unfortunately, the direct application of time domain linear causal analysis to many real-world time series presents three critical challenges: irregular temporal sampling, long range dependencies, and scale. Moreover, real-world data is often collected at irregular time intervals across vast arrays of decentralized sensors and with long range dependencies which make naive time domain correlation estimators spurious. In this paper we present a frequency domain based estimation framework which naturally handles irregularly sampled data and long range dependencies while enabled memory and communication efficient distributed processing of time series data. By operating in the frequency domain we eliminate the need to interpolate and help mitigate the effects of long range dependencies. We implement and evaluate our new work-flow in the distributed setting using Apache Spark and demonstrate on both Monte Carlo simulations and high-frequency financial trading that we can accurately recover causal structure at scale.
On the Effects of Battery Imperfections in an Energy Harvesting Device
Venue: arXiv cs.IT 2016
Year: 2016

Energy Harvesting allows the devices in a Wireless Sensor Network to recharge their batteries through environmental energy sources. While in the literature the main focus is on devices with ideal batteries, in reality several inefficiencies have to be considered to correctly design the operating regimes of an Energy Harvesting Device (EHD). In this work we describe how the throughput optimization problem changes under \emph{real battery} constraints in an EHD. In particular, we consider imperfect knowledge of the state of charge of the battery and storage inefficiencies, \emph{i.e.}, part of the harvested energy is wasted in the battery recharging process. We formulate the problem as a Markov Decision Process, basing our model on some realistic observations about transmission, consumption and harvesting power. We find the performance upper bound with a real battery and numerically discuss the novelty introduced by the real battery effects. We show that using the \emph{old} policies obtained without considering the real battery effects is strongly sub-optimal and may even result in zero throughput.
Generalizing The Morley Trisector and Various Theorems with Realizability Computations
Venue: arXiv cs.CG 2016
Year: 2016

An approach is shown that proves various theorems of plane geometry in an algorithmic manner. The approach affords transparent proofs of a generalization of the Theorem of Morley and other well known results by casting them in terms of constraint satisfaction.
Recovery of signals under the condition on RIC and ROC via prior support information
Venue: arXiv cs.IT 2016
Year: 2016

In this paper, the sufficient condition in terms of the RIC and ROC for the stable and robust recovery of signals in both noiseless and noisy settings was established via weighted $l_{1}$ minimization when there is partial prior information on support of signals. An improved performance guarantee has been derived. We can obtain a less restricted sufficient condition for signal reconstruction and a tighter recovery error bound under some conditions via weighted $l_{1}$ minimization. When prior support estimate is at least $50\%$ accurate, the sufficient condition is weaker than the analogous condition by standard $l_{1}$ minimization method, meanwhile the reconstruction error upper bound is provably to be smaller under additional conditions. Furthermore, the sufficient condition is also proved sharp.