OpenRaiser/Intern-Atlas huggingface dataset:
Optimal Shape-Gain Quantization for Multiuser MIMO Systems with Linear Precoding
Venue: arXiv cs.IT 2011
Year: 2011

This paper studies the optimal bit allocation for shape-gain vector quantization of wireless channels in multiuser (MU) multiple-input multiple-output (MIMO) downlink systems based on linear precoding. Our design minimizes the mean squared-error between the original and quantized channels through optimal bit allocation across shape (direction) and gain (magnitude) for a fixed feedback overhead per user. This is shown to significantly reduce the quantization error, which in turn, decreases the MU interference. This paper makes three main contributions: first, we focus on channel gain quantization and derive the quantization distortion, based on a Euclidean distance measure, corresponding to singular values of a MIMO channel. Second, we show that the Euclidean distance-based distortion of a unit norm complex channel, due to shape quantization, is proportional to \frac{2^{-2Bs}}{2M-1}, where, Bs is the number of shape quantization bits and M is the number of transmit antennas. Finally, we show that for channels in complex space and allowing for a large feedback overhead, the number of direction quantization bits should be approximately (2M - 1) times the number of channel magnitude quantization bits.
Constraining the Size Growth of the Task Space with Socially Guided Intrinsic Motivation using Demonstrations
Venue: arXiv cs.AI 2011
Year: 2011

This paper presents an algorithm for learning a highly redundant inverse model in continuous and non-preset environments. Our Socially Guided Intrinsic Motivation by Demonstrations (SGIM-D) algorithm combines the advantages of both social learning and intrinsic motivation, to specialise in a wide range of skills, while lessening its dependence on the teacher. SGIM-D is evaluated on a fishing skill learning experiment.
Requirements for Automated Assessment of Spreadsheet Maintainability
Venue: arXiv cs.SE 2011
Year: 2011

The use of spreadsheets is widespread. Be it in business, finance, engineering or other areas, spreadsheets are created for their flexibility and ease to quickly model a problem. Very often they evolve from simple prototypes to implementations of crucial business logic. Spreadsheets that play a crucial role in an organization will naturally have a long lifespan and will be maintained and evolved by several people. Therefore, it is important not only to look at their reliability, i.e., how well is the intended functionality implemented, but also at their maintainability, i.e., how easy it is to diagnose a spreadsheet for deficiencies and modify it without degrading its quality. In this position paper we argue for the need to create a model to estimate the maintainability of a spreadsheet based on (automated) measurement. We propose to do so by applying a structured methodology that has already shown its value in the estimation of maintainability of software products. We also argue for the creation of a curated, community-contributed repository of spreadsheets.
Stability of Evolving Multi-Agent Systems
Venue: arXiv cs.MA 2011
Year: 2011

A Multi-Agent System is a distributed system where the agents or nodes perform complex functions that cannot be written down in analytic form. Multi-Agent Systems are highly connected, and the information they contain is mostly stored in the connections. When agents update their state, they take into account the state of the other agents, and they have access to those states via the connections. There is also external, user-generated input into the Multi-Agent System. As so much information is stored in the connections, agents are often memory-less. This memory-less property, together with the randomness of the external input, has allowed us to model Multi-Agent Systems using Markov chains. In this paper, we look at Multi-Agent Systems that evolve, i.e. the number of agents varies according to the fitness of the individual agents. We extend our Markov chain model, and define stability. This is the start of a methodology to control Multi-Agent Systems. We then build upon this to construct an entropy-based definition for the degree of instability (entropy of the limit probabilities), which we used to perform a stability analysis. We then investigated the stability of evolving agent populations through simulation, and show that the results are consistent with the original definition of stability in non-evolving Multi-Agent Systems, proposed by Chli and De Wilde. This paper forms the theoretical basis for the construction of Digital Business Ecosystems, and applications have been reported elsewhere.
Differential Modulation for Bi-directional Relaying with Analog Network Coding
Venue: arXiv cs.IT 2011
Year: 2011

In this paper, we propose an analog network coding scheme with differential modulation (ANC-DM) using amplify-and-forward protocol for bidirectional relay networks when neither the source nodes nor the relay knows the channel state information (CSI). The performance of the proposed ANC-DM scheme is analyzed and a simple asymptotic bit error rate (BER) expression is derived. The analytical results are verified through simulations. It is shown that the BER performance of the proposed differential scheme is about 3 dB away from that of the coherent detection scheme. To improve the system performance, the optimum power allocation between the sources and the relay is determined based on the simplified BER. Simulation results indicate that the proposed differential scheme with optimum power allocation yields 1-2 dB performance improvement over an equal power allocation scheme.
A Structural Approach to Reversible Computation
Venue: arXiv cs.LO 2011
Year: 2011

Reversibility is a key issue in the interface between computation and physics, and of growing importance as miniaturization progresses towards its physical limits. Most foundational work on reversible computing to date has focussed on simulations of low-level machine models. By contrast, we develop a more structural approach. We show how high-level functional programs can be mapped compositionally (i.e. in a syntax-directed fashion) into a simple kind of automata which are immediately seen to be reversible. The size of the automaton is linear in the size of the functional term. In mathematical terms, we are building a concrete model of functional computation. This construction stems directly from ideas arising in Geometry of Interaction and Linear Logic---but can be understood without any knowledge of these topics. In fact, it serves as an excellent introduction to them. At the same time, an interesting logical delineation between reversible and irreversible forms of computation emerges from our analysis.
Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions
Venue: arXiv cs.DB 2011
Year: 2011

In this paper, we formulate a top-k query that compares objects in a database to a user-provided query object on a novel scoring function. The proposed scoring function combines the idea of attractive and repulsive dimensions into a general framework to overcome the weakness of traditional distance or similarity measures. We study the properties of the proposed class of scoring functions and develop efficient and scalable index structures that index the isolines of the function. We demonstrate various scenarios where the query finds application. Empirical evaluation demonstrates a performance gain of one to two orders of magnitude on querying time over existing state-of-the-art top-k techniques. Further, a qualitative analysis is performed on a real dataset to highlight the potential of the proposed query in discovering hidden data characteristics.
PIQL: Success-Tolerant Query Processing in the Cloud
Venue: arXiv cs.DB 2011
Year: 2011

Newly-released web applications often succumb to a "Success Disaster," where overloaded database machines and resulting high response times destroy a previously good user experience. Unfortunately, the data independence provided by a traditional relational database system, while useful for agile development, only exacerbates the problem by hiding potentially expensive queries under simple declarative expressions. As a result, developers of these applications are increasingly abandoning relational databases in favor of imperative code written against distributed key/value stores, losing the many benefits of data independence in the process. Instead, we propose PIQL, a declarative language that also provides scale independence by calculating an upper bound on the number of key/value store operations that will be performed for any query. Coupled with a service level objective (SLO) compliance prediction model and PIQL's scalable database architecture, these bounds make it easy for developers to write success-tolerant applications that support an arbitrarily large number of users while still providing acceptable performance. In this paper, we present the PIQL query processing system and evaluate its scale independence on hundreds of machines using two benchmarks, TPC-W and SCADr.
gSketch: On Query Estimation in Graph Streams
Venue: arXiv cs.DB 2011
Year: 2011

Many dynamic applications are built upon large network infrastructures, such as social networks, communication networks, biological networks and the Web. Such applications create data that can be naturally modeled as graph streams, in which edges of the underlying graph are received and updated sequentially in a form of a stream. It is often necessary and important to summarize the behavior of graph streams in order to enable effective query processing. However, the sheer size and dynamic nature of graph streams present an enormous challenge to existing graph management techniques. In this paper, we propose a new graph sketch method, gSketch, which combines well studied synopses for traditional data streams with a sketch partitioning technique, to estimate and optimize the responses to basic queries on graph streams. We consider two different scenarios for query estimation: (1) A graph stream sample is available; (2) Both a graph stream sample and a query workload sample are available. Algorithms for different scenarios are designed respectively by partitioning a global sketch to a group of localized sketches in order to optimize the query estimation accuracy. We perform extensive experimental studies on both real and synthetic data sets and demonstrate the power and robustness of gSketch in comparison with the state-of-the-art global sketch method.
A secure solution on hierarchical access control
Venue: arXiv cs.CR 2011
Year: 2011

Hierarchical access control is an important and traditional problem in information security. In 2001, Wu et.al. proposed an elegant solution for hierarchical access control by the secure-filter. Jeng and Wang presented an improvement of Wu et. al.'s method by the ECC cryptosystem. However, secure-filter method is insecure in dynaminc access control. Lie, Hsu and Tripathy, Paul pointed out some secure leaks on the secure-filter and presented some improvements to eliminate these secure flaws. In this paper, we revise the secure-filter in Jeng-Wang method and propose another secure solutions in hierarchical access control problem. CA is a super security class (user) in our proposed method and the secure-filter of $u_i$ in our solutions is a polynomial of degree $n_i+1$ in $\mathbb{Z}_p^*$, $f_i(x)=(x-h_i)(x-a_1)...(x-a_{n_i})+L_{l_i}(K_i)$. Although the degree of our secure-filter is larger than others solutions, our solution is secure and efficient in dynamics access control.
Matroids and Integrality Gaps for Hypergraphic Steiner Tree Relaxations
Venue: arXiv cs.DM 2011
Year: 2011

Until recently, LP relaxations have played a limited role in the design of approximation algorithms for the Steiner tree problem. In 2010, Byrka et al. presented a ln(4)+epsilon approximation based on a hypergraphic LP relaxation, but surprisingly, their analysis does not provide a matching bound on the integrality gap. We take a fresh look at hypergraphic LP relaxations for the Steiner tree problem - one that heavily exploits methods and results from the theory of matroids and submodular functions - which leads to stronger integrality gaps, faster algorithms, and a variety of structural insights of independent interest. More precisely, we present a deterministic ln(4)+epsilon approximation that compares against the LP value and therefore proves a matching ln(4) upper bound on the integrality gap. Similarly to Byrka et al., we iteratively fix one component and update the LP solution. However, whereas they solve an LP at every iteration after contracting a component, we show how feasibility can be maintained by a greedy procedure on a well-chosen matroid. Apart from avoiding the expensive step of solving a hypergraphic LP at each iteration, our algorithm can be analyzed using a simple potential function. This gives an easy means to determine stronger approximation guarantees and integrality gaps when considering restricted graph topologies. In particular, this readily leads to a 73/60 bound on the integrality gap for quasi-bipartite graphs. For the case of quasi-bipartite graphs, we present a simple algorithm to transform an optimal solution to the bidirected cut relaxation to an optimal solution of the hypergraphic relaxation, leading to a fast 73/60 approximation for quasi-bipartite graphs. Furthermore, we show how the separation problem of the hypergraphic relaxation can be solved by computing maximum flows, providing a fast independence oracle for our matroids.
A Framework for Automated and Certified Refinement Steps
Venue: arXiv cs.SE 2011
Year: 2011

The refinement calculus provides a methodology for transforming an abstract specification into a concrete implementation, by following a succession of refinement rules. These rules have been mechanized in theorem-provers, thus providing a formal and rigorous way to prove that a given program refines another one. In a previous work, we have extended this mechanization for object-oriented programs, where the memory is represented as a graph, and we have integrated our approach within the rCOS tool, a model-driven software development tool providing a refinement language. Hence, for any refinement step, the tool automatically generates the corresponding proof obligations and the user can manually discharge them, using a provided library of refinement lemmas. In this work, we propose an approach to automate the search of possible refinement rules from a program to another, using the rewriting tool Maude. Each refinement rule in Maude is associated with the corresponding lemma in Isabelle, thus allowing the tool to automatically generate the Isabelle proof when a refinement rule can be automatically found. The user can add a new refinement rule by providing the corresponding Maude rule and Isabelle lemma.
Domain Theory and the Logic of Observable Properties
Venue: arXiv cs.LO 2011
Year: 2011

The mathematical framework of Stone duality is used to synthesize a number of hitherto separate developments in Theoretical Computer Science: - Domain Theory, the mathematical theory of computation introduced by Scott as a foundation for denotational semantics. - The theory of concurrency and systems behaviour developed by Milner, Hennessy et al. based on operational semantics. - Logics of programs. Stone duality provides a junction between semantics (spaces of points = denotations of computational processes) and logics (lattices of properties of processes). Moreover, the underlying logic is geometric, which can be computationally interpreted as the logic of observable properties---i.e. properties which can be determined to hold of a process on the basis of a finite amount of information about its execution. These ideas lead to the following programme: 1. A metalanguage is introduced, comprising - types = universes of discourse for various computational situations. - terms = programs = syntactic intensions for models or points. 2. A standard denotational interpretation of the metalanguage is given, assigning domains to types and domain elements to terms. 3. The metalanguage is also given a {\em logical} interpretation, in which types are interpreted as propositional theories and terms are interpreted via a program logic, which axiomatizes the properties they satisfy. 4. The two interpretations are related by showing that they are Stone duals of each other. Hence, semantics and logic are guaranteed to be in harmony with each other, and in fact each determines the other up to isomorphism. This opens the way to a whole range of applications. Given a denotational description of a computational situation in our meta-language, we can turn the handle to obtain a logic for that situation.
Zigzag Codes: MDS Array Codes with Optimal Rebuilding
Venue: arXiv cs.IT 2011
Year: 2011

MDS array codes are widely used in storage systems to protect data against erasures. We address the \emph{rebuilding ratio} problem, namely, in the case of erasures, what is the fraction of the remaining information that needs to be accessed in order to rebuild \emph{exactly} the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct then the rebuilding ratio is 1 (access all the remaining information). However, the interesting and more practical case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between 1/2 and 3/4, however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a 2-erasure correcting code, the rebuilding ratio is 1/2. In general, we construct a new family of $r$-erasure correcting MDS array codes that has optimal rebuilding ratio of $\frac{e}{r}$ in the case of $e$ erasures, $1 \le e \le r$. Our array codes have efficient encoding and decoding algorithms (for the case $r=2$ they use a finite field of size 3) and an optimal update property.
The interval ordering problem
Venue: arXiv cs.DS 2011
Year: 2011

For a given set of intervals on the real line, we consider the problem of ordering the intervals with the goal of minimizing an objective function that depends on the exposed interval pieces (that is, the pieces that are not covered by earlier intervals in the ordering). This problem is motivated by an application in molecular biology that concerns the determination of the structure of the backbone of a protein. We present polynomial-time algorithms for several natural special cases of the problem that cover the situation where the interval boundaries are agreeably ordered and the situation where the interval set is laminar. Also the bottleneck variant of the problem is shown to be solvable in polynomial time. Finally we prove that the general problem is NP-hard, and that the existence of a constant-factor-approximation algorithm is unlikely.
Analysis of Kak's Quantum Cryptography Protocol from the Perspective of Source Strength
Venue: arXiv cs.CR 2011
Year: 2011

This paper analyzes the performance of Kak's quantum cryptography protocol when intensity monitoring is used to detect the presence of Eve during transmission. Some difficulties related to interception to obtain useful data from the transmission are discussed. The analysis shows the resilience of the protocol towards the man-in-the-middle attack.
Analysis and improvement of a strongly secure certificateless key exchange protocol without pairing
Venue: arXiv cs.CR 2011
Year: 2011

Recently, Yang and Tan proposed a certificateless key exchange protocol without pairing, and claimed their scheme satisfies forward secrecy, which means no adversary could derive an already-established session key unless the full user secret keys (including a private key and an ephemeral secret key) of both communication parties are compromised. However, in this paper, we point out their protocol is actually not secure as claimed by presenting an attack launched by an adversary who has learned the private key of one party and the ephemeral secret key of the other, but not the full user secret keys of both parties. Furthermore, to make up this flaw, we also provide an improved protocol in which the private key and the ephemeral secret key are closely intertwined with each other for generating the session key, thus above attack can be efficiently resisted.
A Biomimetic Model of the Outer Plexiform Layer by Incorporating Memristive Devices
Venue: arXiv cs.CV 2011
Year: 2011

In this paper we present a biorealistic model for the first part of the early vision processing by incorporating memristive nanodevices. The architecture of the proposed network is based on the organisation and functioning of the outer plexiform layer (OPL) in the vertebrate retina. We demonstrate that memristive devices are indeed a valuable building block for neuromorphic architectures, as their highly non-linear and adaptive response could be exploited for establishing ultra-dense networks with similar dynamics to their biological counterparts. We particularly show that hexagonal memristive grids can be employed for faithfully emulating the smoothing-effect occurring at the OPL for enhancing the dynamic range of the system. In addition, we employ a memristor-based thresholding scheme for detecting the edges of grayscale images, while the proposed system is also evaluated for its adaptation and fault tolerance capacity against different light or noise conditions as well as distinct device yields.
Instance-based XML data binding for mobile devices
Venue: arXiv cs.NI 2011
Year: 2011

XML and XML Schema are widely used in different domains for the definition of standards that enhance the interoperability between parts exchanging information through the Internet. The size and complexity of some standards, and their associated schemas, have been growing with time as new use case scenarios and data models are added to them. The common approach to deal with the complexity of producing XML processing code based on these schemas is the use of XML data binding generators. Unfortunately, these tools do not always produce code that ?ts the limitations of resource-constrained devices, such as mobile phones, in the presence of large schemas. In this paper we present Instance-based XML data binding, an approach to produce compact application-specific XML processing code for mobile devices. The approach utilises information extracted from a set of XML documents about how the application make use of the schemas.
On the Expected Complexity of Voronoi Diagrams on Terrains
Venue: arXiv cs.CG 2011
Year: 2011

We investigate the combinatorial complexity of geodesic Voronoi diagrams on polyhedral terrains using a probabilistic analysis. Aronov etal [ABT08] prove that, if one makes certain realistic input assumptions on the terrain, this complexity is Θ(n + m \sqrt n) in the worst case, where n denotes the number of triangles that define the terrain and m denotes the number of Voronoi sites. We prove that under a relaxed set of assumptions the Voronoi diagram has expected complexity O(n+m), given that the sites have a uniform distribution on the domain of the terrain(or the surface of the terrain). Furthermore, we present a worst-case construction of a terrain which implies a lower bound of Vmega(n m2/3) on the expected worst-case complexity if these assumptions on the terrain are dropped. As an additional result, we can show that the expected fatness of a cell in a random planar Voronoi diagram is bounded by a constant.