We examine a parameterized complexity class for randomized computation where only the error bound and not the full runtime is allowed to depend more than polynomially on the parameter, based on a proposal by Kwisthout...
详细信息
ISBN:
(数字)9783030108014
ISBN:
(纸本)9783030108014;9783030108007
We examine a parameterized complexity class for randomized computation where only the error bound and not the full runtime is allowed to depend more than polynomially on the parameter, based on a proposal by Kwisthout in [15,16]. We prove that this class, for which we propose the shorthand name PPPT, has a robust definition and is in fact equal to the intersection of the classes paraBPP and PP. this result is accompanied by a Cook-style proof of completeness for the corresponding promise class (under a suitable notion of reduction) for parameterized approximation versions of the inference problem in Bayesian networks, which is known to be PP-complete. Withthese definitions and results in place, we proceed by showing how it follows from this that derandomization is equivalent to efficient deterministic approximation methods for the inference problem. Furthermore, we observe as a straightforward application of a result due to Drucker in [8] that these problems cannot have polynomial size randomized kernels unless the polynomial hierarchy collapses to the third level. We conclude by indicating potential avenues for further exploration and application of this framework.
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressi...
详细信息
ISBN:
(纸本)9783031521126;9783031521133
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressions, called COVER BY ARIthMETIC PROGRESSIONS (CAP) and EXACT COVER BY ARIthMETIC PROGRESSIONS (XCAP). In both problems, we are given a set X consisting of n integers along with an integer k, and our goal is to find k arithmetic progressions whose union is X. In XCAP we additionally require the arithmetic progressions to be disjoint. Both problems were shown to be NP-complete by Heath [IPL'90]. We present a 2(O(k2)) poly(n) time algorithm for CAP and a 2(O(k3)) poly(n) time algorithm for XCAP. We also give a fixed parameter tractable algorithm for CAP parameterized below some guaranteed solution size. We complement these findings by proving that CAP is Strongly NP-complete in the field Z(p), if p is a prime number part of the input.
Trust and reputation systems are decision support tools used to drive parties' interactions on the basis of parties' reputation. In such systems, parties rate with each other after each interaction. Reputation...
详细信息
ISBN:
(纸本)9783642358432
Trust and reputation systems are decision support tools used to drive parties' interactions on the basis of parties' reputation. In such systems, parties rate with each other after each interaction. Reputation scores for each ratee are computed via reputation functions on the basis of collected ratings. We propose a general framework based on Bayesian decision theory for the assessment of such systems, with respect to the number of available ratings. Given a reputation function g and n independent ratings, one is interested in the value of the loss a user may incur by relying on the ratee's reputation as computed by the system. To this purpose, we study the behaviour of both Bayes and frequentist risk of reputation functions with respect to the number of available observations. We provide results that characterise the asymptotic behaviour of these two risks, describing their limits values and the exact exponential rate of convergence. One result of this analysis is that decision functions based on Maximum-Likelihood are asymptotically optimal. We also illustrate these results through a set of numerical simulations.
the well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
the well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. this problem is known to NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP subset of coNP/poly. We prove that Disjoint Paths remains NP-complete on split graphs, and show that the problem admits a kernel with O(k(2)) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k(3)) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.
We study properties characterized by applying successively a "destructive" rule expressed in first-order logic. the rule says that Points, a(1),...,a(k) of a structure can be removed if they satisfy a certai...
详细信息
ISBN:
(纸本)9783642112652
We study properties characterized by applying successively a "destructive" rule expressed in first-order logic. the rule says that Points, a(1),...,a(k) of a structure can be removed if they satisfy a certain first-order formula. phi(a(1),...,a(k)). the property defined this way by the formula is the set of finite structures such that we are able to obtain the empty structure when applying the rule repeatedly. Many classical properties can be formulated by means of a. "destructive" rule. We do a systematic study of the computational complexity of these properties according to the fragment of first-order logic in which the rule is expressed. We give the list of minimal fragments able to define NP-complete properties and maximal fragments that define only PTIME properties (unless PTIME = NP), depending on the number k of free variables and the quantifier symbols used in the formula. We also study more specifically the case where the formula has one free variable and is universal.
In this paper the notion of quantum finite one-counter automata (QF1CA) is introduced. Introduction of the notion is similar to that of the 2-way quantum finite state automata in [1]. the well-formedness conditions fo...
详细信息
ISBN:
(纸本)354066694X
In this paper the notion of quantum finite one-counter automata (QF1CA) is introduced. Introduction of the notion is similar to that of the 2-way quantum finite state automata in [1]. the well-formedness conditions for the automata are specified ensuring unitarity of evolution. A special kind of QF1CA, called simple, that satisfies the well-formedness conditions is introduced. that allows specify rules for constructing such automata more naturally and simpler than in general case. Possible models of language recognition by QF1CA are considered. the recognition of some languages by QF1CA is shown and compared with recognition by probabilistic counterparts.
Traditional verbatim browsers give back information linearly according to a ranking performed by a search engine that may not be optimal for the surfer. the latter may need to assess the pertinence of the information ...
详细信息
ISBN:
(纸本)9783030389192;9783030389185
Traditional verbatim browsers give back information linearly according to a ranking performed by a search engine that may not be optimal for the surfer. the latter may need to assess the pertinence of the information retrieved, particularly when s center dot he wants to explore other facets of a multi-facetted information space. Simultaneous facet visualisation can help to gain insights into the information retrieved and call for further refined searches. Facets are potentially heterogeneous co-occurrence networks, built choosing at least one reference type, and modeled by HyperBag-Graphs-families of multisets on a given universe. References allow to navigate inside the dataset and perform visual queries. the approach is illustrated on Arxiv scientific pre-prints searches.
ECN is a powerful tool that can achieve low latency and high throughput simultaneously. Support ECN for multi-queue scenarios is an industry trend in datacenter networks. However, ECN schemes developed for per-port ma...
详细信息
ISBN:
(纸本)9781538668719
ECN is a powerful tool that can achieve low latency and high throughput simultaneously. Support ECN for multi-queue scenarios is an industry trend in datacenter networks. However, ECN schemes developed for per-port marking cannot be applied directly to the multi-queue scenarios. It hurts at least one metric among latency, throughput, and the scheduling policy. State-of-the-art multi-queue ECN marking schemes each has its own limitations. In this paper, we present per-Port Marking with Selective Blindness (PMSB). the intuition is that: if a flow is found to be a victim of per-port marking, we can either revoke the marking or cancel the flow back-off even if its packets qualify the per-port threshold (i.e., selective blindness). By breaking the fixed causal relationship between ECN marking and flow back-off, flows from un-congested queues can be protected. We evaluate PMSB with large-scale NS-3 simulations. Our results demonstrate that PMSB can preserve a given scheduling policy. Compared withthe currentpractice, PMSB can reduce the average/99% completion time for small flows by 64.49%172.89% respectively while delivering a slightly better performance for large flows.
Mirror neurons are specialized neurons recently discovered in the brains of primates. In experiments mirror neurons showed activity both when a subject performed an action and when it observed the same action performe...
详细信息
ISBN:
(纸本)3540207791
Mirror neurons are specialized neurons recently discovered in the brains of primates. In experiments mirror neurons showed activity both when a subject performed an action and when it observed the same action performed by self or another (possibly conspecific) subject. We formulate and study possible computational consequences of the hypothesis in which the experimentally observed properties of mirror neurons are generalized to other perceptive modalities and the underlying mechanism for coupling sensory and motor information is extended by an associative mechanism serving for completion of cross-modal information composed of perception and motor information. Depending on of what kind of information is completed, the hypothesis opens the door for understanding the mechanisms for sensorimotor coordination, imitation learning, and thinking and is inspiring for the design of such mechanisms in the case of artificial agents. Our results justify the hopes generally related to the discovery of mirror neurons.
this book constitutes the refereed proceedings of the 35thconference on currenttrends in theory and practice of computerscience, SOFSEM 2009, held in pindleruv Mln, Czech Republic, in January 2009. the 49 revised f...
ISBN:
(数字)9783540958918
ISBN:
(纸本)9783540958901
this book constitutes the refereed proceedings of the 35thconference on currenttrends in theory and practice of computerscience, SOFSEM 2009, held in pindleruv Mln, Czech Republic, in January 2009. the 49 revised full papers, presented together with 9 invited contributions, were carefully reviewed and selected from 132 submissions. SOFSEM 2009 was organized around the following four tracks: Foundations of computerscience; theory and practice of Software Services; Game theoretic Aspects of E-commerce; and Techniques and Tools for Formal Verification.
暂无评论