OpenRaiser/Intern-Atlas huggingface dataset:
On the impossibility of non-static quantum bit commitment between two parties
Venue: arXiv cs.CR 2011
Year: 2011

Recently, Choi \emph{et al}. proposed an assumption on Mayers-Lo-Chau (MLC) no-go theorem that the state of the entire quantum system is invariable to both participants before the unveiling phase. This means that the theorem is only applicable to static quantum bit commitment (QBC). This paper find that the assumption is unnecessary and the MLC no-go theorem can be applied to not only static QBC, but also non-static one. A non-static QBC protocol proposed by Choi \emph{et al.} is briefly reviewed and analyzed to work as a supporting example. In addition, a novel way to prove the impossibility of the two kinds of QBC is given.
A New Semantic Web Approach for Constructing, Searching and Modifying Ontology Dynamically
Venue: arXiv cs.IR 2011
Year: 2011

Semantic web is the next generation web, which concerns the meaning of web documents It has the immense power to pull out the most relevant information from the web pages, which is also meaningful to any user, using software agents. In today's world, agent communication is not possible if concerned ontology is changed a little. We have pointed out this very problem and developed an Ontology Purification System to help agent communication. In our system you can send queries and view the search results. If it can't meet the criteria then it finds out the mismatched elements. Modification is done within a second and you can see the difference. That's why we emphasis on the word dynamic. When Administrator is updating the system, at the same time that updation is visible to the user.
Statistical Compressed Sensing of Gaussian Mixture Models
Venue: arXiv cs.CV 2011
Year: 2011

A novel framework of compressed sensing, namely statistical compressed sensing (SCS), that aims at efficiently sampling a collection of signals that follow a statistical distribution, and achieving accurate reconstruction on average, is introduced. SCS based on Gaussian models is investigated in depth. For signals that follow a single Gaussian model, with Gaussian or Bernoulli sensing matrices of O(k) measurements, considerably smaller than the O(k log(N/k)) required by conventional CS based on sparse models, where N is the signal dimension, and with an optimal decoder implemented via linear filtering, significantly faster than the pursuit decoders applied in conventional CS, the error of SCS is shown tightly upper bounded by a constant times the best k-term approximation error, with overwhelming probability. The failure probability is also significantly smaller than that of conventional sparsity-oriented CS. Stronger yet simpler results further show that for any sensing matrix, the error of Gaussian SCS is upper bounded by a constant times the best k-term approximation with probability one, and the bound constant can be efficiently calculated. For Gaussian mixture models (GMMs), that assume multiple Gaussian distributions and that each signal follows one of them with an unknown index, a piecewise linear estimator is introduced to decode SCS. The accuracy of model selection, at the heart of the piecewise linear decoder, is analyzed in terms of the properties of the Gaussian distributions and the number of sensing measurements. A maximum a posteriori expectation-maximization algorithm that iteratively estimates the Gaussian models parameters, the signals model selection, and decodes the signals, is presented for GMM-based SCS. In real image sensing applications, GMM-based SCS is shown to lead to improved results compared to conventional CS, at a considerably lower computational cost.
Synthesis of Memory-Efficient Real-Time Controllers for Safety Objectives (Full Version)
Venue: arXiv cs.LO 2011
Year: 2011

We study synthesis of controllers for real-time systems, where the objective is to stay in a given safe set. The problem is solved by obtaining winning strategies in concurrent two-player \emph{timed automaton games} with safety objectives. To prevent a player from winning by blocking time, we restrict each player to strategies that ensure that the player cannot be responsible for causing a zeno run. We construct winning strategies for the controller which require access only to (1) the system clocks (thus, controllers which require their own internal infinitely precise clocks are not necessary), and (2) a linear (in the number of clocks) number of memory bits. Precisely, we show that a memory of size $\big(3\cdot|C|+1 + \lg(|C|+1)\big)$ bits suffices for winning controller strategies for safety objectives, where $C$ is the set of clocks of the timed automaton game, significantly improving the previous known exponential bound. We also settle the open question of whether \emph{region} strategies for controllers require memory for safety objectives by showing with an example that region strategies do require memory for safety objectives.
Optimality of Binning for Distributed Hypothesis Testing
Venue: arXiv cs.IT 2011
Year: 2011

We study a hypothesis testing problem in which data is compressed distributively and sent to a detector that seeks to decide between two possible distributions for the data. The aim is to characterize all achievable encoding rates and exponents of the type 2 error probability when the type 1 error probability is at most a fixed value. For related problems in distributed source coding, schemes based on random binning perform well and often optimal. For distributed hypothesis testing, however, the use of binning is hindered by the fact that the overall error probability may be dominated by errors in binning process. We show that despite this complication, binning is optimal for a class of problems in which the goal is to "test against conditional independence." We then use this optimality result to give an outer bound for a more general class of instances of the problem.
Solving the Satisfiability Problem Through Boolean Networks
Venue: arXiv cs.AI 2011
Year: 2011

In this paper we present a new approach to solve the satisfiability problem (SAT), based on boolean networks (BN). We define a mapping between a SAT instance and a BN, and we solve SAT problem by simulating the BN dynamics. We prove that BN fixed points correspond to the SAT solutions. The mapping presented allows to develop a new class of algorithms to solve SAT. Moreover, this new approach suggests new ways to combine symbolic and connectionist computation and provides a general framework for local search algorithms.
Boolean Networks Design by Genetic Algorithms
Venue: arXiv cs.NE 2011
Year: 2011

We present and discuss the results of an experimental analysis in the design of Boolean networks by means of genetic algorithms. A population of networks is evolved with the aim of finding a network such that the attractor it reaches is of required length $l$. In general, any target can be defined, provided that it is possible to model the task as an optimisation problem over the space of networks. We experiment with different initial conditions for the networks, namely in ordered, chaotic and critical regions, and also with different target length values. Results show that all kinds of initial networks can attain the desired goal, but with different success ratios: initial populations composed of critical or chaotic networks are more likely to reach the target. Moreover, the evolution starting from critical networks achieves the best overall performance. This study is the first step toward the use of search algorithms as tools for automatically design Boolean networks with required properties.
Hidden-Markov Program Algebra with iteration
Venue: arXiv cs.CR 2011
Year: 2011

We use Hidden Markov Models to motivate a quantitative compositional semantics for noninterference-based security with iteration, including a refinement- or "implements" relation that compares two programs with respect to their information leakage; and we propose a program algebra for source-level reasoning about such programs, in particular as a means of establishing that an "implementation" program leaks no more than its "specification" program. <p>This joins two themes: we extend our earlier work, having iteration but only qualitative, by making it quantitative; and we extend our earlier quantitative work by including iteration. <p>We advocate stepwise refinement and source-level program algebra, both as conceptual reasoning tools and as targets for automated assistance. A selection of algebraic laws is given to support this view in the case of quantitative noninterference; and it is demonstrated on a simple iterated password-guessing attack.
Synthese des Controleurs Optimaux pour les Systemes a Evenements Discrets
Venue: arXiv cs.FL 2011
Year: 2011

In this paper, we introduce the problem of synthesizing optimal controllers for discrete event systems and we propose a procedure for solving this problem, where the method and specifications are represented by finite state automata and with increasing complexity. We will subscribe to the synthetic methodology by the control theory initiated by supervision by Ramadge and Wonham. For an illustration on a simple example, then a model with a complexity high. In this spirit, languages, methods and tools development used to specify and development must reach a level of quality to meet the requirements expressed. Face this situation, we are helping in this work the systematic use of formal methods in systems development cycles in the equipping and adapting the UML (Unified Modeling Language) which is the most exploited in industrial projects.
XWeB: the XML Warehouse Benchmark
Venue: arXiv cs.DB 2011
Year: 2011

With the emergence of XML as a standard for representing business data, new decision support applications are being developed. These XML data warehouses aim at supporting On-Line Analytical Processing (OLAP) operations that manipulate irregular XML data. To ensure feasibility of these new tools, important performance issues must be addressed. Performance is customarily assessed with the help of benchmarks. However, decision support benchmarks do not currently support XML features. In this paper, we introduce the XML Warehouse Benchmark (XWeB), which aims at filling this gap. XWeB derives from the relational decision support benchmark TPC-H. It is mainly composed of a test data warehouse that is based on a unified reference model for XML warehouses and that features XML-specific structures, and its associate XQuery decision support workload. XWeB's usage is illustrated by experiments on several XML database management systems.
An Improvement on Ranks of Explicit Tensors
Venue: arXiv cs.DM 2011
Year: 2011

We give constructions of n^k x n^k x n tensors of rank at least 2n^k - O(n^(k-1)). As a corollary we obtain an [n]^r shaped tensor with rank at least 2n^(r/2) - O(n^(r/2)-1) when r is odd. The tensors are constructed from a simple recursive pattern, and the lower bounds are proven using a partitioning theorem developed by Brockett and Dobkin. These two bounds are improvements over the previous best-known explicit tensors that had ranks n^k and n^(r/2) respectively
Towards an axiomatic system for Kolmogorov complexity
Venue: arXiv cs.IT 2011
Year: 2011

In [She82], it is shown that four basic functional properties are enough to characterize plain Kolmogorov complexity, hence obtaining an axiomatic characterization of this notion. In this paper, we try to extend this work, both by looking at alternative axiomatic systems for plain complexity and by considering potential axiomatic systems for other types of complexity. First we show that the axiomatic system given by Shen cannot be weakened (at least in any natural way). We then give an analogue of Shen's axiomatic system for conditional complexity. In a the second part of the paper, we look at prefix-free complexity and try to construct an axiomatic system for it. We show however that the natural analogues of Shen's axiomatic systems fails to characterize prefix-free complexity.
An architecture for the evaluation of intelligent systems
Venue: arXiv cs.AI 2011
Year: 2011

One of the main research areas in Artificial Intelligence is the coding of agents (programs) which are able to learn by themselves in any situation. This means that agents must be useful for purposes other than those they were created for, as, for example, playing chess. In this way we try to get closer to the pristine goal of Artificial Intelligence. One of the problems to decide whether an agent is really intelligent or not is the measurement of its intelligence, since there is currently no way to measure it in a reliable way. The purpose of this project is to create an interpreter that allows for the execution of several environments, including those which are generated randomly, so that an agent (a person or a program) can interact with them. Once the interaction between the agent and the environment is over, the interpreter will measure the intelligence of the agent according to the actions, states and rewards the agent has undergone inside the environment during the test. As a result we will be able to measure agents' intelligence in any possible environment, and to make comparisons between several agents, in order to determine which of them is the most intelligent. In order to perform the tests, the interpreter must be able to randomly generate environments that are really useful to measure agents' intelligence, since not any randomly generated environment will serve that purpose.
Message and State Cooperation in a Relay Channel When the Relay Has Strictly Causal State Information
Venue: arXiv cs.IT 2011
Year: 2011

A state-dependent relay channel is studied in which strictly causal channel state information is available at the relay and no state information is available at the source and destination. Source and relay are connected via two unidirectional out-of-band orthogonal links of finite capacity, and a state-dependent memoryless channel connects source and relay, on one side, and the destination, on the other. Via the orthogonal links, the source can convey information about the message to be delivered to the destination to the relay while the relay can forward state information to the source. This exchange enables cooperation between source and relay on both transmission of message and state information to the destination. First, an achievable scheme, inspired by noisy network coding, is proposed that exploits both message and state cooperation. Next, based on the given achievable rate and appropriate upper bounds, capacity results are identified for some special cases. Finally, a Gaussian model is studied, along with corresponding numerical results that illuminate the relative merits of state and message cooperation.
A Simulation Experiment on a Built-In Self Test Equipped with Pseudorandom Test Pattern Generator and Multi-Input Shift Register (MISR)
Venue: arXiv cs.AR 2011
Year: 2011

This paper investigates the impact of the changes of the characteristic polynomials and initial loadings, on behaviour of aliasing errors of parallel signature analyzer (Multi-Input Shift Register), used in an LFSR based digital circuit testing technique. The investigation is carried-out through an extensive simulation study of the effectiveness of the LFSR based digital circuit testing technique. The results of the study show that when the identical characteristic polynomials of order n are used in both pseudo-random test-pattern generator, as well as in Multi-Input Shift Register (MISR) signature analyzer (parallel type) then the probability of aliasing errors remains unchanged due to the changes in the initial loadings of the pseudo-random test-pattern generator.
Linear-Time Algorithms for Graphs of Bounded Rankwidth: A Fresh Look Using Game Theory
Venue: arXiv cs.DS 2011
Year: 2011

We present an alternative proof of a theorem by Courcelle, Makowski and Rotics which states that problems expressible in MSO are solvable in linear time for graphs of bounded rankwidth. Our proof uses a game-theoretic approach and has the advantage of being self-contained, intuitive, and fairly easy to follow. In particular, our presentation does not assume any background in logic or automata theory. We believe that it is good to have alternative proofs of this important result. Moreover our approach can be generalized to prove other results of a similar flavor, for example, that of Courcelle's Theorem for treewidth.
Pattern tree-based XOLAP rollup operator for XML complex hierarchies
Venue: arXiv cs.DB 2011
Year: 2011

With the rise of XML as a standard for representing business data, XML data warehousing appears as a suitable solution for decision-support applications. In this context, it is necessary to allow OLAP analyses on XML data cubes. Thus, XQuery extensions are needed. To define a formal framework and allow much-needed performance optimizations on analytical queries expressed in XQuery, defining an algebra is desirable. However, XML-OLAP (XOLAP) algebras from the literature still largely rely on the relational model. Hence, we propose in this paper a rollup operator based on a pattern tree in order to handle multidimensional XML data expressed within complex hierarchies.
Prisoner's Dilemma on Graphs with Large Girth
Venue: arXiv cs.SI 2011
Year: 2011

We study the evolution of cooperation in populations where individuals play prisoner's dilemma on a network. Every node of the network corresponds on an individual choosing whether to cooperate or defect in a repeated game. The players revise their actions by imitating those neighbors who have higher payoffs. We show that when the interactions take place on graphs with large girth, cooperation is more likely to emerge. On the flip side, in graphs with many cycles of length 3 and 4, defection spreads more rapidly. One of the key ideas of our analysis is that our dynamics can be seen as a perturbation of the voter model. We write the transition kernel of the corresponding Markov chain in terms of the pairwise correlations in the voter model. We analyze the pairwise correlation and show that in graphs with relatively large girth, cooperators cluster and help each other.
An Algorithm Computing the Core of a Konig-Egervary Graph
Venue: arXiv cs.DM 2011
Year: 2011

A set S of vertices is independent in a graph G if no two vertices from S are adjacent, and alpha(G) is the cardinality of a maximum independent set of G. G is called a Konig-Egervary graph if its order equals alpha(G)+mu(G), where mu(G) denotes the size of a maximum matching. By core(G) we mean the intersection of all maximum independent sets of G. To decide whether core(G) is empty is known to be NP-hard. In this paper, we present some polynomial time algorithms finding core(G) of a Konig-Egervary graph G.
The complexity of approximate Nash equilibrium in congestion games with negative delays
Venue: arXiv cs.GT 2011
Year: 2011

We extend the study of the complexity of finding an $\eps$-approximate Nash equilibrium in congestion games from the case of positive delay functions to delays of arbitrary sign. We first prove that in symmetric games with $α$-bounded jump the $\eps$-Nash dynamic converges in polynomial time when all delay functions are negative, similarly to the case of positive delays. We then establish a hardness result for symmetric games with $α$-bounded jump and with arbitrary delay functions: in that case finding an $\eps$-Nash equilibrium becomes $\PLS$-complete.
Pi01 sets and tilings
Venue: arXiv cs.DM 2011
Year: 2011

In this paper, we prove that given any Π^0_1 subset $P$ of $\{0,1\}^\NN$ there is a tileset $τ$ with a set of configurations $C$ such that $P\times\ZZ^2$ is recursively homeomorphic to $C\setminus U$ where $U$ is a computable set of configurations. As a consequence, if $P$ is countable, this tileset has the exact same set of Turing degrees.
On Rate-Splitting by a Secondary Link in Multiple Access Primary Network
Venue: arXiv cs.IT 2011
Year: 2011

An achievable rate region is obtained for a primary multiple access network coexisting with a secondary link of one transmitter and a corresponding receiver. The rate region depicts the sum primary rate versus the secondary rate and is established assuming that the secondary link performs rate-splitting. The achievable rate region is the union of two types of achievable rate regions. The first type is a rate region established assuming that the secondary receiver cannot decode any primary signal, whereas the second is established assuming that the secondary receiver can decode the signal of one primary receiver. The achievable rate region is determined first assuming discrete memoryless channel (DMC) then the results are applied to a Gaussian channel. In the Gaussian channel, the performance of rate-splitting is characterized for the two types of rate regions. Moreover, a necessary and sufficient condition to determine which primary signal that the secondary receiver can decode without degrading the range of primary achievable sum rates is provided. When this condition is satisfied by a certain primary user, the secondary receiver can decode its signal and achieve larger rates without reducing the primary achievable sum rates from the case in which it does not decode any primary signal. It is also shown that, the probability of having at least one primary user satisfying this condition grows with the primary signal to noise ratio.
Reversible Data Hiding Based on Two-level HDWT Coefficient Histograms
Venue: arXiv cs.CR 2011
Year: 2011

In recent years, reversible data hiding has attracted much more attention than before. Reversibility signifies that the original media can be recovered without any loss from the marked media after extracting the embedded message. This paper presents a new method that adopts two-level wavelet transform and exploits the feature of large wavelet coefficient variance to achieve the goal of high capacity with imperceptibility. Our method differs from those of previous ones in which the wavelet coefficients histogram not gray-level histogram is manipulated. Besides, clever shifting rules are introduced into histogram to avoid the decimal problem in pixel values after recovery to achieve reversibility. With small alteration of the wavelet coefficients in the embedding process, and therefore low visual distortion is obtained in the marked image. In addition, an important feature of our design is that the use of threshold is much different from previous studies. The results indicate that our design is superior to many other state-of-the-art reversible data hiding schemes.
Algorithms for Jumbled Pattern Matching in Strings
Venue: arXiv cs.DS 2011
Year: 2011

The Parikh vector p(s) of a string s is defined as the vector of multiplicities of the characters. Parikh vector q occurs in s if s has a substring t with p(t)=q. We present two novel algorithms for searching for a query q in a text s. One solves the decision problem over a binary text in constant time, using a linear size index of the text. The second algorithm, for a general finite alphabet, finds all occurrences of a given Parikh vector q and has sub-linear expected time complexity; we present two variants, which both use a linear size index of the text.