OpenRaiser/Intern-Atlas huggingface dataset:
Optimal error of query sets under the differentially-private matrix mechanism
Venue: arXiv cs.DB 2012
Year: 2012

A common goal of privacy research is to release synthetic data that satisfies a formal privacy guarantee and can be used by an analyst in place of the original data. To achieve reasonable accuracy, a synthetic data set must be tuned to support a specified set of queries accurately, sacrificing fidelity for other queries. This work considers methods for producing synthetic data under differential privacy and investigates what makes a set of queries "easy" or "hard" to answer. We consider answering sets of linear counting queries using the matrix mechanism, a recent differentially-private mechanism that can reduce error by adding complex correlated noise adapted to a specified workload. Our main result is a novel lower bound on the minimum total error required to simultaneously release answers to a set of workload queries. The bound reveals that the hardness of a query workload is related to the spectral properties of the workload when it is represented in matrix form. The bound is most informative for $(ε,δ)$-differential privacy but also applies to $ε$-differential privacy.
Pattern Matching in Multiple Streams
Venue: arXiv cs.DS 2012
Year: 2012

We investigate the problem of deterministic pattern matching in multiple streams. In this model, one symbol arrives at a time and is associated with one of s streaming texts. The task at each time step is to report if there is a new match between a fixed pattern of length m and a newly updated stream. As is usual in the streaming context, the goal is to use as little space as possible while still reporting matches quickly. We give almost matching upper and lower space bounds for three distinct pattern matching problems. For exact matching we show that the problem can be solved in constant time per arriving symbol and O(m+s) words of space. For the k-mismatch and k-difference problems we give O(k) time solutions that require O(m+ks) words of space. In all three cases we also give space lower bounds which show our methods are optimal up to a single logarithmic factor. Finally we set out a number of open problems related to this new model for pattern matching.
Are we there yet? When to stop a Markov chain while generating random graphs
Venue: arXiv cs.SI 2012
Year: 2012

Markov chains are a convenient means of generating realizations of networks, since they require little more than a procedure for rewiring edges. If a rewiring procedure exists for generating new graphs with specified statistical properties, then a Markov chain sampler can generate an ensemble of graphs with prescribed characteristics. However, successive graphs in a Markov chain cannot be used when one desires independent draws from the distribution of graphs; the realizations are correlated. Consequently, one runs a Markov chain for N iterations before accepting the realization as an independent sample. In this work, we devise two methods for calculating N. They are both based on the binary "time-series" denoting the occurrence/non-occurrence of edge (u, v) between vertices u and v in the Markov chain of graphs generated by the sampler. They differ in their underlying assumptions. We test them on the generation of graphs with a prescribed joint degree distribution. We find the N proportional |E|, where |E| is the number of edges in the graph. The two methods are compared by sampling on real, sparse graphs with 10^3 - 10^4 vertices.
Symbolic bisimulation for quantum processes
Venue: arXiv cs.LO 2012
Year: 2012

With the previous notions of bisimulation presented in literature, to check if two quantum processes are bisimilar, we have to instantiate the free quantum variables of them with arbitrary quantum states, and verify the bisimilarity of resultant configurations. This makes checking bisimilarity infeasible from an algorithmic point of view because quantum states constitute a continuum. In this paper, we introduce a symbolic operational semantics for quantum processes directly at the quantum operation level, which allows us to describe the bisimulation between quantum processes without resorting to quantum states. We show that the symbolic bisimulation defined here is equivalent to the open bisimulation for quantum processes in the previous work, when strong bisimulations are considered. An algorithm for checking symbolic ground bisimilarity is presented. We also give a modal logical characterisation for quantum bisimilarity based on an extension of Hennessy-Milner logic to quantum processes.
Characteristic Formulae for Relations with Nested Fixed Points
Venue: arXiv cs.LO 2012
Year: 2012

A general framework for the connection between characteristic formulae and behavioral semantics is described in [2]. This approach does not suitably cover semantics defined by nested fixed points, such as the n-nested simulation semantics for n greater than 2. In this study we address this deficiency and give a description of nested fixed points that extends the approach for single fixed points in an intuitive and comprehensive way.
IO vs OI in Higher-Order Recursion Schemes
Venue: arXiv cs.LO 2012
Year: 2012

We propose a study of the modes of derivation of higher-order recursion schemes, proving that value trees obtained from schemes using innermost-outermost derivations (IO) are the same as those obtained using unrestricted derivations. Given that higher-order recursion schemes can be used as a model of functional programs, innermost-outermost derivations policy represents a theoretical view point of call by value evaluation strategy.
Energy Efficiency Optimization for MIMO Broadcast Channels
Venue: arXiv cs.IT 2012
Year: 2012

Characterizing the fundamental energy efficiency (EE) limits of MIMO broadcast channels (BC) is significant for the development of green wireless communications. We address the EE optimization problem for MIMO-BC in this paper and consider a practical power model, i.e., taking into account a transmit independent power which is related to the number of active transmit antennas. Under this setup, we propose a new optimization approach, in which the transmit covariance is optimized under fixed active transmit antenna sets, and then active transmit antenna selection (ATAS) is utilized. During the transmit covariance optimization, we propose a globally optimal energy efficient iterative water-filling scheme through solving a series of concave fractional programs based on the block-coordinate ascent algorithm. After that, ATAS is employed to determine the active transmit antenna set. Since activating more transmit antennas can achieve higher sum-rate but at the cost of larger transmit independent power consumption, there exists a tradeoff between the sum-rate gain and the power consumption. Here ATAS can exploit the best tradeoff and thus further improve the EE. Optimal exhaustive search and low-complexity norm based ATAS schemes are developed. Through simulations, we discuss the effect of different parameters on the EE of the MIMO-BC.
Excluding 4-wheels
Venue: arXiv cs.DM 2012
Year: 2012

A 4-wheel is a graph formed by a cycle C and a vertex not in C that has at least four neighbors in C. We prove that a graph G that does not contain a 4-wheel as a subgraph is 4-colorable and we describe some structural properties of such a graph.
Optimal bandwidth-aware VM allocation for Infrastructure-as-a-Service
Venue: arXiv cs.NI 2012
Year: 2012

Infrastructure-as-a-Service (IaaS) providers need to offer richer services to be competitive while optimizing their resource usage to keep costs down. Richer service offerings include new resource request models involving bandwidth guarantees between virtual machines (VMs). Thus we consider the following problem: given a VM request graph (where nodes are VMs and edges represent virtual network connectivity between the VMs) and a real data center topology, find an allocation of VMs to servers that satisfies the bandwidth guarantees for every virtual network edge---which maps to a path in the physical network---and minimizes congestion of the network. Previous work has shown that for arbitrary networks and requests, finding the optimal embedding satisfying bandwidth requests is $\mathcal{NP}$-hard. However, in most data center architectures, the routing protocols employed are based on a spanning tree of the physical network. In this paper, we prove that the problem remains $\mathcal{NP}$-hard even when the physical network topology is restricted to be a tree, and the request graph topology is also restricted. We also present a dynamic programming algorithm for computing the optimal embedding in a tree network which runs in time $O(3^kn)$, where $n$ is the number of nodes in the physical topology and $k$ is the size of the request graph, which is well suited for practical requests which have small $k$. Such requests form a large class of web-service and enterprise workloads. Also, if we restrict the requests topology to a clique (all VMs connected to a virtual switch with uniform bandwidth requirements), we show that the dynamic programming algorithm can be modified to output the minimum congestion embedding in time $O(k^2n)$.
Inferential or Differential: Privacy Laws Dictate
Venue: arXiv cs.DB 2012
Year: 2012

So far, privacy models follow two paradigms. The first paradigm, termed inferential privacy in this paper, focuses on the risk due to statistical inference of sensitive information about a target record from other records in the database. The second paradigm, known as differential privacy, focuses on the risk to an individual when included in, versus when not included in, the database. The contribution of this paper consists of two parts. The first part presents a critical analysis on differential privacy with two results: (i) the differential privacy mechanism does not provide inferential privacy, (ii) the impossibility result about achieving Dalenius's privacy goal [5] is based on an adversary simulated by a Turing machine, but a human adversary may behave differently; consequently, the practical implication of the impossibility result remains unclear. The second part of this work is devoted to a solution addressing three major drawbacks in previous approaches to inferential privacy: lack of flexibility for handling variable sensitivity, poor utility, and vulnerability to auxiliary information.
Approximation by Quantization
Venue: arXiv cs.AI 2012
Year: 2012

Inference in graphical models consists of repeatedly multiplying and summing out potentials. It is generally intractable because the derived potentials obtained in this way can be exponentially large. Approximate inference techniques such as belief propagation and variational methods combat this by simplifying the derived potentials, typically by dropping variables from them. We propose an alternate method for simplifying potentials: quantizing their values. Quantization causes different states of a potential to have the same value, and therefore introduces context-specific independencies that can be exploited to represent the potential more compactly. We use algebraic decision diagrams (ADDs) to do this efficiently. We apply quantization and ADD reduction to variable elimination and junction tree propagation, yielding a family of bounded approximate inference schemes. Our experimental tests show that our new schemes significantly outperform state-of-the-art approaches on many benchmark instances.
An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information
Venue: arXiv cs.AI 2012
Year: 2012

We study the problem of agent-based negotiation in combinatorial domains. It is difficult to reach optimal agreements in bilateral or multi-lateral negotiations when the agents' preferences for the possible alternatives are not common knowledge. Self-interested agents often end up negotiating inefficient agreements in such situations. In this paper, we present a protocol for negotiation in combinatorial domains which can lead rational agents to reach optimal agreements under incomplete information setting. Our proposed protocol enables the negotiating agents to identify efficient solutions using distributed search that visits only a small subspace of the whole outcome space. Moreover, the proposed protocol is sufficiently general that it is applicable to most preference representation models in combinatorial domains. We also present results of experiments that demonstrate the feasibility and computational efficiency of our approach.
Fractional Moments on Bandit Problems
Venue: arXiv cs.LG 2012
Year: 2012

Reinforcement learning addresses the dilemma between exploration to find profitable actions and exploitation to act according to the best observations already made. Bandit problems are one such class of problems in stateless environments that represent this explore/exploit situation. We propose a learning algorithm for bandit problems based on fractional expectation of rewards acquired. The algorithm is theoretically shown to converge on an eta-optimal arm and achieve O(n) sample complexity. Experimental results show the algorithm incurs substantially lower regrets than parameter-optimized eta-greedy and SoftMax approaches and other low sample complexity state-of-the-art techniques.
Price Updating in Combinatorial Prediction Markets with Bayesian Networks
Venue: arXiv cs.GT 2012
Year: 2012

To overcome the #P-hardness of computing/updating prices in logarithm market scoring rule-based (LMSR-based) combinatorial prediction markets, Chen et al. [5] recently used a simple Bayesian network to represent the prices of securities in combinatorial predictionmarkets for tournaments, and showed that two types of popular securities are structure preserving. In this paper, we significantly extend this idea by employing Bayesian networks in general combinatorial prediction markets. We reveal a very natural connection between LMSR-based combinatorial prediction markets and probabilistic belief aggregation,which leads to a complete characterization of all structure preserving securities for decomposable network structures. Notably, the main results by Chen et al. [5] are corollaries of our characterization. We then prove that in order for a very basic set of securities to be structure preserving, the graph of the Bayesian network must be decomposable. We also discuss some approximation techniques for securities that are not structure preserving.
Symbolic Dynamic Programming for Discrete and Continuous State MDPs
Venue: arXiv cs.AI 2012
Year: 2012

Many real-world decision-theoretic planning problems can be naturally modeled with discrete and continuous state Markov decision processes (DC-MDPs). While previous work has addressed automated decision-theoretic planning for DCMDPs, optimal solutions have only been defined so far for limited settings, e.g., DC-MDPs having hyper-rectangular piecewise linear value functions. In this work, we extend symbolic dynamic programming (SDP) techniques to provide optimal solutions for a vastly expanded class of DCMDPs. To address the inherent combinatorial aspects of SDP, we introduce the XADD - a continuous variable extension of the algebraic decision diagram (ADD) - that maintains compact representations of the exact value function. Empirically, we demonstrate an implementation of SDP with XADDs on various DC-MDPs, showing the first optimal automated solutions to DCMDPs with linear and nonlinear piecewise partitioned value functions and showing the advantages of constraint-based pruning for XADDs.
Kernel-based Conditional Independence Test and Application in Causal Discovery
Venue: arXiv cs.LG 2012
Year: 2012

Conditional independence testing is an important problem, especially in Bayesian network learning and causal discovery. Due to the curse of dimensionality, testing for conditional independence of continuous variables is particularly challenging. We propose a Kernel-based Conditional Independence test (KCI-test), by constructing an appropriate test statistic and deriving its asymptotic distribution under the null hypothesis of conditional independence. The proposed method is computationally efficient and easy to implement. Experimental results show that it outperforms other methods, especially when the conditioning set is large or the sample size is not very large, in which case other methods encounter difficulties.
Testing whether linear equations are causal: A free probability theory approach
Venue: arXiv cs.LG 2012
Year: 2012

We propose a method that infers whether linear relations between two high-dimensional variables X and Y are due to a causal influence from X to Y or from Y to X. The earlier proposed so-called Trace Method is extended to the regime where the dimension of the observed variables exceeds the sample size. Based on previous work, we postulate conditions that characterize a causal relation between X and Y. Moreover, we describe a statistical test and argue that both causal directions are typically rejected if there is a common cause. A full theoretical analysis is presented for the deterministic case but our approach seems to be valid for the noisy case, too, for which we additionally present an approach based on a sparsity constraint. The discussed method yields promising results for both simulated and real world data.
Technical Report on Hypergraph-Partitioning-Based Models and Methods for Exploiting Cache Locality in Sparse-Matrix Vector Multiplication
Venue: arXiv cs.NA 2012
Year: 2012

The sparse matrix-vector multiplication (SpMxV) is a kernel operation widely used in iterative linear solvers. The same sparse matrix is multiplied by a dense vector repeatedly in these solvers. Matrices with irregular sparsity patterns make it difficult to utilize cache locality effectively in SpMxV computations. In this work, we investigate single- and multiple-SpMxV frameworks for exploiting cache locality in SpMxV computations. For the single-SpMxV framework, we propose two cache-size-aware top-down row/column-reordering methods based on 1D and 2D sparse matrix partitioning by utilizing the column-net and enhancing the row-column-net hypergraph models of sparse matrices. The multiple-SpMxV framework depends on splitting a given matrix into a sum of multiple nonzero-disjoint matrices so that the SpMxV operation is performed as a sequence of multiple input- and output- dependent SpMxV operations. For an effective matrix splitting required in this framework, we propose a cache- size-aware top-down approach based on 2D sparse matrix partitioning by utilizing the row-column-net hypergraph model. For this framework, we also propose two methods for effective ordering of individual SpMxV operations. The primary objective in all of the three methods is to maximize the exploitation of temporal locality. We evaluate the validity of our models and methods on a wide range of sparse matrices using both cache-miss simulations and actual runs by using OSKI. Experimental results show that proposed methods and models outperform state-of-the-art schemes.
Creating Usable Pin Array Tactons for Non-Visual Information
Venue: arXiv cs.HC 2012
Year: 2012

Spatial information can be difficult to present to a visually impaired computer user. In this paper we examine a new kind of tactile cueing for non-visual interaction as a potential solution, building on earlier work on vibrotactile Tactons. However, unlike vibrotactile Tactons, we use a pin array to stimulate the finger tip. Here, we describe how to design static and dynamic Tactons by defining their basic components. We then present user tests examining how easy it is to distinguish between different forms of pin array Tactons demonstrating accurate Tacton sets to represent directions. These experiments demonstrate usable patterns for static, wave and blinking pin array Tacton sets for guiding a user in one of eight directions. A study is then described that shows the benefits of structuring Tactons to convey information through multiple parameters of the signal. By using multiple independent parameters for a Tacton, this study demonstrates participants perceive more information through a single Tacton. Two applications using these Tactons are then presented: a maze exploration application and an electric circuit exploration application designed for use by and tested with visually impaired users.
PAC Bounds for Discounted MDPs
Venue: arXiv cs.LG 2012
Year: 2012

We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (MDPs). For the upper bound we make the assumption that each action leads to at most two possible next-states and prove a new bound for a UCRL-style algorithm on the number of time-steps when it is not Probably Approximately Correct (PAC). The new lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors.
Modeling Internet-Scale Policies for Cleaning up Malware
Venue: arXiv cs.NI 2012
Year: 2012

An emerging consensus among policy makers is that interventions undertaken by Internet Service Providers are the best way to counter the rising incidence of malware. However, assessing the suitability of countermeasures at this scale is hard. In this paper, we use an agent-based model, called ASIM, to investigate the impact of policy interventions at the Autonomous System level of the Internet. For instance, we find that coordinated intervention by the 0.2%-biggest ASes is more effective than uncoordinated efforts adopted by 30% of all ASes. Furthermore, countermeasures that block malicious transit traffic appear more effective than ones that block outgoing traffic. The model allows us to quantify and compare positive externalities created by different countermeasures. Our results give an initial indication of the types and levels of intervention that are most cost-effective at large scale.
Unsupervised Threshold for Automatic Extraction of Dolphin Dorsal Fin Outlines from Digital Photographs in DARWIN (Digital Analysis and Recognition of Whale Images on a Network)
Venue: arXiv cs.CV 2012
Year: 2012

At least two software packages---DARWIN, Eckerd College, and FinScan, Texas A&M---exist to facilitate the identification of cetaceans---whales, dolphins, porpoises---based upon the naturally occurring features along the edges of their dorsal fins. Such identification is useful for biological studies of population, social interaction, migration, etc. The process whereby fin outlines are extracted in current fin-recognition software packages is manually intensive and represents a major user input bottleneck: it is both time consuming and visually fatiguing. This research aims to develop automated methods (employing unsupervised thresholding and morphological processing techniques) to extract cetacean dorsal fin outlines from digital photographs thereby reducing manual user input. Ideally, automatic outline generation will improve the overall user experience and improve the ability of the software to correctly identify cetaceans. Various transformations from color to gray space were examined to determine which produced a grayscale image in which a suitable threshold could be easily identified. To assist with unsupervised thresholding, a new metric was developed to evaluate the jaggedness of figures ("pixelarity") in an image after thresholding. The metric indicates how cleanly a threshold segments background and foreground elements and hence provides a good measure of the quality of a given threshold. This research results in successful extractions in roughly 93% of images, and significantly reduces user-input time.