Search results for "Computation theory"
showing 10 items of 336 documents
Quadratically Tight Relations for Randomized Query Complexity
2020
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional…
Distributed construction of quantum fingerprints
2003
Quantum fingerprints are useful quantum encodings introduced by Buhrman, Cleve, Watrous, and de Wolf (Physical Review Letters, Volume 87, Number 16, Article 167902, 2001; quant-ph/0102001) in obtaining an efficient quantum communication protocol. We design a protocol for constructing the fingerprint in a distributed scenario. As an application, this protocol gives rise to a communication protocol more efficient than the best known classical protocol for a communication problem.
Recent Developments in Quantum Algorithms and Complexity
2014
We survey several recent developments in quantum algorithms and complexity: Reichardt’s characterization of quantum query algorithms via span programs [15]; New bounds on the number of queries that are necessary for simulating a quantum algorithm that makes a very small number of queries [2]; Exact quantum algorithms with superlinear advantage over the best classical algorithm [4].
Left-star order structure of Rickart *-rings
2015
Janowitz proved in 1983 that the initial segments of a Rickart *-ring with the star order are orthomodular posets. In this paper, the same result is proved for the left-star order , which was introduced by Marovtet al., by finding an orthogonality which corresponds to in a certain way and then applying a result proved by Cīrulis which states that the initial segments of any quasi-orthomodular set are orthomodular.
A Framework to Improve the Disaster Response Through a Knowledge-Based Multi-Agent System
2017
The disaster response still faces problems of collaboration due to lack of policies concerning the information exchange during the response. Moreover, plans are prepared to respond to a disaster, but drills to apply them are limited and do not allow to determine their efficiency and conflicts with other organizations. This paper presents a framework allowing for different organizations involving in the disaster response to assess their collaboration through its simulation using an explicit representation of their knowledge. This framework is based on a multi-agent system composed of three generic agent models to represent the organizational structure of disaster response. The decision-makin…
Assignment of Roles and Channels for a Multichannel MAC in Wireless Mesh Networks
2009
International audience; A multichannel MAC improves throughput in wireless mesh networks by multiplexing transmissions over orthogonal channels. In this paper, we propose an efficient way for constructing the wireless mesh structure associated with Molecular MAC, a multichannel MAC layer designed for efficient packet forwarding. Molecular MAC outperforms other classical approaches, but requires a specific structure for efficient operation. First, we propose a centralized protocol that provides an upper bound for constructing such a molecular structure through a MILP (Mixed Integer Linear Programming) formulation that maximizes network capacity. Then, we present two distributed self-stabiliz…
A Learning Automata Based Solution to Service Selection in Stochastic Environments
2010
Published version of a paper published in the book: Trends in Applied Intelligent Systems. Also available on SpringerLink: http://dx.doi.org/10.1007/978-3-642-13033-5_22 With the abundance of services available in today’s world, identifying those of high quality is becoming increasingly difficult. Reputation systems can offer generic recommendations by aggregating user provided opinions about service quality, however, are prone to ballot stuffing and badmouthing . In general, unfair ratings may degrade the trustworthiness of reputation systems, and changes in service quality over time render previous ratings unreliable. In this paper, we provide a novel solution to the above problems based …
“Anti-Bayesian” flat and hierarchical clustering using symmetric quantiloids
2017
A myriad of works has been published for achieving data clustering based on the Bayesian paradigm, where the clustering sometimes resorts to Naive-Bayes decisions. Within the domain of clustering, the Bayesian principle corresponds to assigning the unlabelled samples to the cluster whose mean (or centroid) is the closest. Recently, Oommen and his co-authors have proposed a novel, counter-intuitive and pioneering PR scheme that is radically opposed to the Bayesian principle. The rational for this paradigm, referred to as the “Anti-Bayesian” (AB) paradigm, involves classification based on the non-central quantiles of the distributions. The first-reported work to achieve clustering using the A…
EV-planning: Electric vehicle itinerary planning
2014
International audience; In the latest few years, lot of efforts have been done to pave the way to sustainable mobility, in order to solve pollution problems and fuel shortage. The use of electric vehicles (EV) is considered as one of the best ecologic and economic solution. However, autonomy barriers and limitations slow the progress and the deployment of this technology. In this paper, we propose an advanced electric vehicles' fleet management architecture. This architecture considers the most important factors that can affect the traveling mode of electric vehicles, in order to offer different services to fleet management companies for an efficient monitoring and management of their fleet…