A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on ...
详细信息
A program correctness checker is an algorithm for checking the output of a computation. That is, given a program and an instance on which the program is run, the checker certifies whether the output of the program on that instance is correct. This paper defines the concept of a program checker. It designs program checkers for a few specific and carefully chosen problems in the class FP of functions computable in polynomial time. Problems in FP for which checkers are presented in this paper include Sorting, Matrix Rank and GCD. It also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. Two structural theorems are proven here. One is a characterization of problems that can be checked. The other theorem establishes equivalence classes of problems such that whenever one problem in a class is checkable, all problems in the class are checkable.
In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching by Mulmuley, Vazirani, and Vazirani [Combinatorica, ...
详细信息
In this paper, we precisely characterize the randomness complexity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching by Mulmuley, Vazirani, and Vazirani [Combinatorica, 7 (1987), pp. 105-113] and in several other applications. Given a set S and an unknown family F subset of or equal to 2(S) with \F\ less than or equal to Z, we present a scheme for assigning polynomially bounded wrights to the elements of S using only O(log Z + log \S\) random bits, such that the minimum weight set in F is unique with high probability. This generalizes the solution of Mulmuley, Vazirani, and Vazirani, who use O(S log S) bits, independent of Z. We also provide a matching lower bound for the randomness complexity of this problem. The new weight assignment scheme yields a randomness-efficient RNC(2) algorithm for perfect matching which uses O(log Z + log n) random bits, where Z is any given upper bound on the number of perfect matchings in the input graph. This generalizes the result of Grigoriev and Karpinski [Proc. IEEE Symposium on Foundations of Computer Science, 1987, pp. 166-172], who present an NC3 algorithm when Z is polynomial and improves the running time in this case. The worst-case randomness complexity of our algorithm is O(n log(m/n)) random bits improving on the previous bound of O(m log n). Our scheme also gives randomness-efficient solutions for several problems where unique element isolation is used, such as RNC algorithms for variants of matching and basic problems on linear matroids. We obtain a randomness-efficient random reduction from SAT to USAT, the language of uniquely satisfiable formulas, which can be derandomized in the case of languages in Few P to yield new proofs of the results Few P subset of or equal to + P and Few P subset of or equal to C = P.
We improve on the communication complexity of zero-knowledge proof systems. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega(kn) bit comm...
详细信息
We improve on the communication complexity of zero-knowledge proof systems. Let C be a Boolean circuit of size n. Previous zero-knowledge proof systems for the satisfiability of C require the use of Omega(kn) bit commitments in order to achieve a probability of undetected cheating below 2(-k). In the case k = n, the communication complexity of these protocols is therefore Omega(n(2)) bit commitments. In this paper, we present a zero-knowledge proof system for achieving the same goal with only O(n(1+epsilon n) + k root n(1+epsilon n)) bit commitments, where epsilon(n) goes to zero as n goes to infinity. In the case k = n, this is O(n root n(1+epsilon n)). Moreover, only O(k) commitments need ever be opened, which is interesting if it is substantially less expensive to commit to a bit than to open a commitment.
We propose a probabilistic algorithm to solve the problem of distributed broadcast. A simple diffusion algorithm is introduced, and its reliability is evaluated. The cost and reliability of the probabilistic algorithm...
详细信息
We propose a probabilistic algorithm to solve the problem of distributed broadcast. A simple diffusion algorithm is introduced, and its reliability is evaluated. The cost and reliability of the probabilistic algorithm are compared with the corresponding deterministic algorithm.
This paper shows that a minimization version of satisfiability is strongly NP-hard, even if each clause contains no more than two literals and/or each clause contains at most one unnegated variable. The worst-case and...
详细信息
This paper shows that a minimization version of satisfiability is strongly NP-hard, even if each clause contains no more than two literals and/or each clause contains at most one unnegated variable. The worst-case and average-case performances of greedy and probabilistic greedy heuristics for the problem are examined, and tight upper bounds on the performance ratio in each case are developed.
The use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. This gain in simplicity, efficienc...
详细信息
The use of randomization in the design and analysis of algorithms promises simple and efficient algorithms to difficult problems, some of which may not have a deterministic solution. This gain in simplicity, efficiency, and solvability results in a trade-off of the traditional notion of absolute correctness of algorithms for a more quantitative notion: correctness with a probability between 0 and 1. The addition of the notion of parallelism to the already unintuitive idea of randomization makes reasoning about probabilistic parallel programs all the more tortuous and difficult. In this paper we address the problem of specifying and deriving properties of probabilistic parallel programs that either hold deterministically or with probability 1. We present a proof methodology based on existing proof systems for probabilistic algorithms, the theory of the predicate transformer, and the theory of UNITY. Although the proofs of probabilistic programs are slippery at best, we show that such programs can be derived with the same rigor and elegance that we have seen in the derivation of sequential and parallel programs. By applying this methodology to derive probabilistic programs, we hope to develop tools and techniques that would make randomization a useful paradigm in algorithm design.
This paper analyses how the symmetry of a processor network influences the existence of a solution for the network orientation problem. The orientation of hypercubes and tori is the problem of assigning labels to each...
详细信息
This paper analyses how the symmetry of a processor network influences the existence of a solution for the network orientation problem. The orientation of hypercubes and tori is the problem of assigning labels to each link of each processor, in such a way that a sense of direction is given to the network. In this paper the problem of network orientation for these two topologies is studied under the assumption that the network contains a single leader, under the assumption that the processors possess unique identities, and under the assumption that the network is anonymous. The distinction between these three models is considered fundamental in distributed computing. It is shown that orientations can be computed by deterministic algorithms only when either a leader or unique identities are available. Orientations can be computed for anonymous networks by randomized algorithms, but only when the number of processors is known. When the number of processors is not known, even randomized algorithms cannot comp...
We show that the size of any sample space that could be used in Freivalds' probabilistic matrix product verification algorithm for n x n matrices is at least (n - 1)/epsilon if the probability of error is at most ...
详细信息
We show that the size of any sample space that could be used in Freivalds' probabilistic matrix product verification algorithm for n x n matrices is at least (n - 1)/epsilon if the probability of error is at most epsilon, matching the upper bound of Kimbrel and Sinha. We also provide a characterization of any sample space for which Freivalds' algorithm has probability of error at most epsilon. We then provide a generalization of Freivalds' algorithm and give a tight lower bound on the time-randomness tradeoff for this class of algorithms.
This paper explores the use of randomization as a primitive action in the solution of robot tasks. An example of randomization is the strategy of shaking a bin containing a part in order to orient the part in a desire...
详细信息
This paper explores the use of randomization as a primitive action in the solution of robot tasks. An example of randomization is the strategy of shaking a bin containing a part in order to orient the part in a desired stable state with some high probability. Further examples include tapping, vibrating, twirling, and random search. For instance, it is sometimes beneficial for a system to execute random motions purposefully when the precise motions required to perform an operation are unknown, as when they lie below the available sensor resolution. The purpose of this paper is to provide a theoretical framework for the planning and execution of randomized strategies for robot tasks. This framework is built on the standard backchaining approach of dynamic programming. Specifically, a randomizing planner backchains from the goal in a state space whose states describe the knowledge available to the system at run-time. By choosing random actions in a principled manner at run-time, a system can sometimes obtain a probabilistic strategy for accomplishing a task even when no guaranteed strategy exists for accomplishing that task. In other cases, the system may be able to obtain a speedup over an existing guaranteed strategy. The main result of this paper consists of two examples. One example shows that randomization can sometimes speed up task completion from exponential time to polynomial time. The other example shows that such a speedup is not always possible.
Probability and algorithms enjoy an almost boisterous interaction that has led to an active, extensive literature that touches fields as diverse as number theory and the design of computer hardware. This article offer...
详细信息
Probability and algorithms enjoy an almost boisterous interaction that has led to an active, extensive literature that touches fields as diverse as number theory and the design of computer hardware. This article offers a gentle introduction to the simplest, most basic ideas that underlie this development.
暂无评论