OpenRaiser/Intern-Atlas huggingface dataset:
A Note On Estimating the Spectral Norm of A Matrix Efficiently
Venue: arXiv cs.DS 2011
Year: 2011

We give an efficient algorithm which can obtain a relative error approximation to the spectral norm of a matrix, combining the power iteration method with some techniques from matrix reconstruction which use random sampling.
PAC learnability versus VC dimension: a footnote to a basic result of statistical learning
Venue: arXiv cs.LG 2011
Year: 2011

A fundamental result of statistical learnig theory states that a concept class is PAC learnable if and only if it is a uniform Glivenko-Cantelli class if and only if the VC dimension of the class is finite. However, the theorem is only valid under special assumptions of measurability of the class, in which case the PAC learnability even becomes consistent. Otherwise, there is a classical example, constructed under the Continuum Hypothesis by Dudley and Durst and further adapted by Blumer, Ehrenfeucht, Haussler, and Warmuth, of a concept class of VC dimension one which is neither uniform Glivenko-Cantelli nor consistently PAC learnable. We show that, rather surprisingly, under an additional set-theoretic hypothesis which is much milder than the Continuum Hypothesis (Martin's Axiom), PAC learnability is equivalent to finite VC dimension for every concept class.
On the Recognition of Fuzzy Circular Interval Graphs
Venue: arXiv cs.DM 2011
Year: 2011

Fuzzy circular interval graphs are a generalization of proper circular arc graphs and have been recently introduced by Chudnovsky and Seymour as a fundamental subclass of claw-free graphs. In this paper, we provide a polynomial-time algorithm for recognizing such graphs, and more importantly for building a suitable representation.
Responsibility Modeling for the Sociotechnical Risk Analysis of Coalitions of Systems
Venue: arXiv cs.SE 2011
Year: 2011

Society is challenging systems engineers by demanding ever more complex and integrated systems. With the rise of cloud computing and systems-of-systems (including cyber-physical systems) we are entering an era where mission critical services and applications will be dependent upon 'coalitions-of-systems'. Coalitions-of-systems (CoS) are a class of system similar to systems-of-systems but they differ in that they interact to further overlapping self-interests rather than an overarching mission. Assessing the sociotechnical risks associated with CoS is an open research question of societal importance as existing risk analysis techniques typically focus on the technical aspects of systems and ignore risks associated with coalition partners reneging on responsibilities or leaving the coalition. We demonstrate that a responsibility modeling based risk analysis approach enables the identification of sociotechnical risks associated with CoS. The approach identifies hazards and associated risks that may arise when relying upon a coalition of human/organizational/technical agents to provision a service or application. Through a case study of a proposed cloud IT infrastructure migration we show how the technique identifies vulnerabilities that may arise because of human, organizational or technical agents failing to discharge responsibilities.
Cooperative Spectrum Sensing for Amplify-and-Forward Cognitive Networks
Venue: arXiv cs.IT 2011
Year: 2011

We develop a framework for spectrum sensing in cooperative amplify-and-forward cognitive radio networks. We consider a stochastic model where relays are assigned in cognitive radio networks to transmit the primary user's signal to a cognitive Secondary Base Station (SBS). We develop the Bayesian optimal decision rule under various scenarios of Channel State Information (CSI) varying from perfect to imperfect CSI. In order to obtain the optimal decision rule based on a Likelihood Ratio Test (LRT), the marginal likelihood under each hypothesis relating to presence or absence of transmission needs to be evaluated pointwise. However, in some cases the evaluation of the LRT can not be performed analytically due to the intractability of the multi-dimensional integrals involved. In other cases, the distribution of the test statistic can not be obtained exactly. To circumvent these difficulties we design two algorithms to approximate the marginal likelihood, and obtain the decision rule. The first is based on Gaussian Approximation where we quantify the accuracy of the approximation via a multivariate version of the Berry-Esseen bound. The second algorithm is based on Laplace approximation for the marginal likelihood, which results in a non-convex optimisation problem which is solved efficiently via Bayesian Expectation-Maximisation method. We also utilise a Laguerre series expansion to approximate the distribution of the test statistic in cases where its distribution can not be derived exactly. Performance is evaluated via analytic bounds and compared to numerical simulations.
Key Management in Mobile Sensor Networks
Venue: arXiv cs.CR 2011
Year: 2011

Wireless sensor networks consist of sensor nodes with limited computational and communication capabilities. This paper deals with mobile sensors which are divided into clusters based on their physical locations. Efficient ways of key distribution among the sensors and inter and intra cluster communications are examined. The security of the entire network is considered through efficient key management by taking into consideration the network's power capabilities.
Optimal Cell Towers Distribution by using Spatial Mining and Geographic Information System
Venue: arXiv cs.DB 2011
Year: 2011

The appearance of wireless communication is dramatically changing our life. Mobile telecommunications emerged as a technological marvel allowing for access to personal and other services, devices, computation and communication, in any place and at any time through effortless plug and play. Setting up wireless mobile networks often requires: Frequency Assignment, Communication Protocol selection, Routing schemes selection, and cells towers distributions. This research aims to optimize the cells towers distribution by using spatial mining with Geographic Information System (GIS) as a tool. The distribution optimization could be done by applying the Digital Elevation Model (DEM) on the image of the area which must be covered with two levels of hierarchy. The research will apply the spatial association rules technique on the second level to select the best square in the cell for placing the antenna. From that the proposal will try to minimize the number of installed towers, makes tower's location feasible, and provides full area coverage.
Privacy Preserving Moving KNN Queries
Venue: arXiv cs.DB 2011
Year: 2011

We present a novel approach that protects trajectory privacy of users who access location-based services through a moving k nearest neighbor (MkNN) query. An MkNN query continuously returns the k nearest data objects for a moving user (query point). Simply updating a user's imprecise location such as a region instead of the exact position to a location-based service provider (LSP) cannot ensure privacy of the user for an MkNN query: continuous disclosure of regions enables the LSP to follow a user's trajectory. We identify the problem of trajectory privacy that arises from the overlap of consecutive regions while requesting an MkNN query and provide the first solution to this problem. Our approach allows a user to specify the confidence level that represents a bound of how much more the user may need to travel than the actual kth nearest data object. By hiding a user's required confidence level and the required number of nearest data objects from an LSP, we develop a technique to prevent the LSP from tracking the user's trajectory for MkNN queries. We propose an efficient algorithm for the LSP to find k nearest data objects for a region with a user's specified confidence level, which is an essential component to evaluate an MkNN query in a privacy preserving manner; this algorithm is at least two times faster than the state-of-the-art algorithm. Extensive experimental studies validate the effectiveness of our trajectory privacy protection technique and the efficiency of our algorithm.
Self-Assembly with Geometric Tiles
Venue: arXiv cs.CG 2011
Year: 2011

In this work we propose a generalization of Winfree's abstract Tile Assembly Model (aTAM) in which tile types are assigned rigid shapes, or geometries, along each tile face. We examine the number of distinct tile types needed to assemble shapes within this model, the temperature required for efficient assembly, and the problem of designing compact geometric faces to meet given compatibility specifications. Our results show a dramatic decrease in the number of tile types needed to assemble $n \times n$ squares to $Θ(\sqrt{\log n})$ at temperature 1 for the most simple model which meets a lower bound from Kolmogorov complexity, and $O(\log\log n)$ in a model in which tile aggregates must move together through obstacle free paths within the plane. This stands in contrast to the $Θ(\log n / \log\log n)$ tile types at temperature 2 needed in the basic aTAM. We also provide a general method for simulating a large and computationally universal class of temperature 2 aTAM systems with geometric tiles at temperature 1. Finally, we consider the problem of computing a set of compact geometric faces for a tile system to implement a given set of compatibility specifications. We show a number of bounds on the complexity of geometry size needed for various classes of compatibility specifications, many of which we directly apply to our tile assembly results to achieve non-trivial reductions in geometry size.
On the optimal compression of sets in PSPACE
Venue: arXiv cs.CC 2011
Year: 2011

We show that if DTIME[2^{O(n)}] is not included in DSPACE[2^{o(n)}], then, for every set B in PSPACE, all strings x in B of length n can be represented by a string compressed(x) of length at most log (|B^{=n}|) + O(log n), such that a polynomial-time algorithm, given compressed(x), can distinguish x from all the other strings in B^{=n}. Modulo the O(log n) additive trem, this achieves the information-theoretical optimum for string compression.
Mechanism Design without Money via Stable Matching
Venue: arXiv cs.GT 2011
Year: 2011

Mechanism design without money has a rich history in social choice literature. Due to the strong impossibility theorem by Gibbard and Satterthwaite, exploring domains in which there exist dominant strategy mechanisms is one of the central questions in the field. We propose a general framework, called the generalized packing problem (\gpp), to study the mechanism design questions without payment. The \gpp\ possesses a rich structure and comprises a number of well-studied models as special cases, including, e.g., matroid, matching, knapsack, independent set, and the generalized assignment problem. We adopt the agenda of approximate mechanism design where the objective is to design a truthful (or strategyproof) mechanism without money that can be implemented in polynomial time and yields a good approximation to the socially optimal solution. We study several special cases of \gpp, and give constant approximation mechanisms for matroid, matching, knapsack, and the generalized assignment problem. Our result for generalized assignment problem solves an open problem proposed in \cite{DG10}. Our main technical contribution is in exploitation of the approaches from stable matching, which is a fundamental solution concept in the context of matching marketplaces, in application to mechanism design. Stable matching, while conceptually simple, provides a set of powerful tools to manage and analyze self-interested behaviors of participating agents. Our mechanism uses a stable matching algorithm as a critical component and adopts other approaches like random sampling and online mechanisms. Our work also enriches the stable matching theory with a new knapsack constrained matching model.
Energy and Mean-Payoff Parity Markov Decision Processes
Venue: arXiv cs.GT 2011
Year: 2011

We consider Markov Decision Processes (MDPs) with mean-payoff parity and energy parity objectives. In system design, the parity objective is used to encode ω-regular specifications, and the mean-payoff and energy objectives can be used to model quantitative resource constraints. The energy condition requires that the resource level never drops below 0, and the mean-payoff condition requires that the limit-average value of the resource consumption is within a threshold. While these two (energy and mean-payoff) classical conditions are equivalent for two-player games, we show that they differ for MDPs. We show that the problem of deciding whether a state is almost-sure winning (i.e., winning with probability 1) in energy parity MDPs is in NP \cap coNP, while for mean-payoff parity MDPs, the problem is solvable in polynomial time, improving a recent PSPACE bound.
Numbers as Data Structures: The Prime Successor Function as Primitive
Venue: arXiv cs.CC 2011
Year: 2011

The symbolic representation of a number should be considered as a data structure, and the choice of data structure depends on the arithmetic operations that are to be performed. Numbers are almost universally represented using position based notations based on exponential powers of a base number - usually 10. This representations is computationally efficient for the standard arithmetic operations, but it is not efficient for factorisation. This has led to a common confusion that factorisation is inherently computationally hard. We propose a new representation of the natural numbers based on bags and using the prime successor function as a primitive - prime bags (PBs). This data structure is more efficient for most arithmetic operations, and enables numbers can be efficiently factored. However, it also has the interesting feature that addition appears to be computationally hard. PBs have an interesting alternative interpretation as partitions of numbers represented in the standard way, and this reveals a novel relationship between prime numbers and the partition function. The PB representation can be extended to rational and irrational numbers, and this provides the most direct proof of the irrationality of the square root of 2. I argue that what needs to be ultimately understood is not the peculiar computation complexity properties of the decimal system (e.g. factorisation), but rather what arithmetical operator trade-offs are generally possible.
On Stabilization in Herman's Algorithm
Venue: arXiv cs.DS 2011
Year: 2011

Herman's algorithm is a synchronous randomized protocol for achieving self-stabilization in a token ring consisting of N processes. The interaction of tokens makes the dynamics of the protocol very difficult to analyze. In this paper we study the expected time to stabilization in terms of the initial configuration. It is straightforward that the algorithm achieves stabilization almost surely from any initial configuration, and it is known that the worst-case expected time to stabilization (with respect to the initial configuration) is Theta(N^2). Our first contribution is to give an upper bound of 0.64 N^2 on the expected stabilization time, improving on previous upper bounds and reducing the gap with the best existing lower bound. We also introduce an asynchronous version of the protocol, showing a similar O(N^2) convergence bound in this case. Assuming that errors arise from the corruption of some number k of bits, where k is fixed independently of the size of the ring, we show that the expected time to stabilization is O(N). This reveals a hitherto unknown and highly desirable property of Herman's algorithm: it recovers quickly from bounded errors. We also show that if the initial configuration arises by resetting each bit independently and uniformly at random, then stabilization is significantly faster than in the worst case.
Similarity Join Size Estimation using Locality Sensitive Hashing
Venue: arXiv cs.DB 2011
Year: 2011

Similarity joins are important operations with a broad range of applications. In this paper, we study the problem of vector similarity join size estimation (VSJ). It is a generalization of the previously studied set similarity join size estimation (SSJ) problem and can handle more interesting cases such as TF-IDF vectors. One of the key challenges in similarity join size estimation is that the join size can change dramatically depending on the input similarity threshold. We propose a sampling based algorithm that uses the Locality-Sensitive-Hashing (LSH) scheme. The proposed algorithm LSH-SS uses an LSH index to enable effective sampling even at high thresholds. We compare the proposed technique with random sampling and the state-of-the-art technique for SSJ (adapted to VSJ) and demonstrate LSH-SS offers more accurate estimates at both high and low similarity thresholds and small variance using real-world data sets.
On Social-Temporal Group Query with Acquaintance Constraint
Venue: arXiv cs.SI 2011
Year: 2011

Three essential criteria are important for activity planning, including: (1) finding a group of attendees familiar with the initiator, (2) ensuring each attendee in the group to have tight social relations with most of the members in the group, and (3) selecting an activity period available for all attendees. Therefore, this paper proposes Social-Temporal Group Query to find the activity time and attendees with the minimum total social distance to the initiator. Moreover, this query incorporates an acquaintance constraint to avoid finding a group with mutually unfamiliar attendees. Efficient processing of the social-temporal group query is very challenging. We show that the problem is NP-hard via a proof and formulate the problem with Integer Programming. We then propose two efficient algorithms, SGSelect and STGSelect, which include effective pruning techniques and employ the idea of pivot time slots to substantially reduce the running time, for finding the optimal solutions. Experimental results indicate that the proposed algorithms are much more efficient and scalable. In the comparison of solution quality, we show that STGSelect outperforms the algorithm that represents manual coordination by the initiator.
Adding noise to the input of a model trained with a regularized objective
Venue: arXiv cs.AI 2011
Year: 2011

Regularization is a well studied problem in the context of neural networks. It is usually used to improve the generalization performance when the number of input samples is relatively small or heavily contaminated with noise. The regularization of a parametric model can be achieved in different manners some of which are early stopping (Morgan and Bourlard, 1990), weight decay, output smoothing that are used to avoid overfitting during the training of the considered model. From a Bayesian point of view, many regularization techniques correspond to imposing certain prior distributions on model parameters (Krogh and Hertz, 1991). Using Bishop's approximation (Bishop, 1995) of the objective function when a restricted type of noise is added to the input of a parametric function, we derive the higher order terms of the Taylor expansion and analyze the coefficients of the regularization terms induced by the noisy input. In particular we study the effect of penalizing the Hessian of the mapping function with respect to the input in terms of generalization performance. We also show how we can control independently this coefficient by explicitly penalizing the Jacobian of the mapping function on corrupted inputs.
Computer Arithmetic Preserving Hamming Distance of Operands in Operation Result
Venue: arXiv cs.AR 2011
Year: 2011

The traditional approach to fault tolerant computing involves replicating computation units and applying a majority vote operation on individual result bits. This approach, however, has several limitations; the most severe is the resource requirement. This paper presents a new method for fault tolerant computing where for a given error rate, the hamming distance between correct inputs and faulty inputs as well as the hamming distance between a correct result and a faulty result is preserved throughout processing thereby enabling correction of up to transient faults per computation cycle. The new method is compared and contrasted with current protection methods and its cost / performance is analyzed.
Hiding Information in a Stream Control Transmission Protocol
Venue: arXiv cs.CR 2011
Year: 2011

The STCP (Stream Control Transmission Protocol) is a candidate for a new transport layer protocol that may replace the TCP (Transmission Control Protocol) and the UDP (User Datagram Protocol) protocols in future IP networks. Currently, the SCTP is implemented in, or can be added to, many popular operating systems (Windows, BSD, Linux, HPUX or Sun Solaris). This paper identifies and presents all possible "places" where hidden information can be exchanged using an SCTP. The paper focuses mostly on proposing new steganographic methods that can be applied to an SCTP and that can utilise new, characteristic SCTP features, such as multi-homing and multi-streaming. Moreover, for each method, the countermeasure is covered. When used with malicious intent, a method may pose a threat to network security. Knowledge about potential SCTP steganographic methods may be used as a supplement to RFC5062, which describes security attacks in an SCTP protocol. Presented in this paper is a complete analysis of information hiding in an SCTP, and this analysis can be treated as a "guide" when developing steganalysis (detection) tools.
Characterization of Random Linear Network Coding with Application to Broadcast Optimization in Intermittently Connected Networks
Venue: arXiv cs.IT 2011
Year: 2011

We address the problem of optimizing the throughput of network coded traffic in mobile networks operating in challenging environments where connectivity is intermittent and locally available memory space is limited. Random linear network coding (RLNC) is shown to be equivalent (across all possible initial conditions) to a random message selection strategy where nodes are able to exchange buffer occupancy information during contacts. This result creates the premises for a tractable analysis of RLNC packet spread, which is in turn used for enhancing its throughput under broadcast. By exploiting the similarity between channel coding and RLNC in intermittently connected networks, we show that quite surprisingly, network coding, when not used properly, is still significantly underutilizing network resources. We propose an enhanced forwarding protocol that increases considerably the throughput for practical cases, with negligible additional delay.
Fife's Theorem for (7/3)-Powers
Venue: arXiv cs.FL 2011
Year: 2011

We prove a Fife-like characterization of the infinite binary (7/3)-power-free words, by giving a finite automaton of 15 states that encodes all such words. As a consequence, we characterize all such words that are 2-automatic.
Evolutionary Foundations of Mathematics
Venue: arXiv cs.OH 2011
Year: 2011

We propose a simple cognitive model where qualitative and quantitative com- parisons enable animals to identify objects, associate them with their properties held in memory and make naive inference. Simple notions like equivalence re- lations, order relations are used. We then show that such processes are at the root of human mathematical reasoning by showing that the elements of totally ordered sets satisfy the Peano axioms. The process through which children learn counting is then formalized. Finally association is modeled as a Markov process leading to a stationary distribution.
On a conjecture by Belfiore and Solé on some lattices
Venue: arXiv cs.IT 2011
Year: 2011

The point of this note is to prove that the secrecy function attains its maximum at y=1 on all known extremal even unimodular lattices. This is a special case of a conjecture by Belfiore and Solé. Further, we will give a very simple method to verify or disprove the conjecture on any given unimodular lattice.