Browsing by Author "Cleve, Richard"
Now showing 1 - 4 of 4
Results Per Page
Sort Options
- ItemOpen AccessEFFICIENT COMPUTATIONS OF ENCODINGS FOR QUANTUM ERROR CORRECTION(1996-08-01) Cleve, Richard; Gottesman, DanielWe show how, given any set of generators of the stabilizer of a quantum code, an efficient gate array that computes the codewords can be constructed. For an In-qubit code whose stabilizer has Id generators, the resulting gate array consists of IO(nd) operations, and converts Ik-qubit data (where Ik = n - d) into In-qubit codewords
- ItemOpen AccessINTERPOLATING ARITHMETIC READ-ONCE FORMULAS IN PARALLEL(1995-05-01) Bshouty, Nader H.; Cleve, RichardA formula is read-once if each variable appears at most once in it. An artithmetic read-once formula is one in which the operations are addition, subtraction, multiplication, and division (and constants are allowed). We present a randomized (Las Vegas) parallel algorithm for the exact interpolation of arithmetic read-once formulas over sufficiently large fields. More specifically, for n-variable read-once formulas, and fields of size at least $3(n sup 2 + 3n - 2)$, our algorithm runs in $O(log sup 2 n)$ parallel steps using $O(n sup 4)$ processors (where the field operations are charged unit cost). This complements other results which imply that other classes of read-once formulas cannot be interpolated-or even learned with membership and equivalence queries-in poly-logarithmic-time with polynomially many processors (even though they can be learned sequentially in polynomial-time). These classes include boolean read-once formulas and arithmetic read-once formulas over fields of size o(n/log n) (for n variable read-once formulas).
- ItemOpen AccessORACLES AND QUERIES THAT ARE SUFFICIENT FOR EXACT LEARNING(1994-04-01) Bshouty, Nader H.; Cleve, Richard; Tamon, Christino; Kannan, SampathWe show that the class of all circuits is exactly learnable in (randomized) expected polynomial-time using subset and superset queries. Subset and superset queries are a generalization of equivalence queries, where an instance of a negative counterexample is requested (for subset queries) or a positive counterexample is requested (for superset queries). Our result is a consequence of the following result which we consider to be of independent interest: the class of all circuits is exactly learnable in (randomized) expected polynomial-time with equivalence queries and the aid of an NP-oracle. This improves the previous result of Gavald\o'a\(ga' [G93] where a $SIGMA~pile {p above 3 }$-oracle and equivalence queries are required in place of the NP-oracle and equvalence queries, and the learning algorithm is deterministic. The hypothesis class for both of the above learning algorithms is the class of circuits of slightly larger (polynomially related) size. Also, the algorithms can be adapted to learn the class of DNF formulas with hypothesis class consisting of depth-3 $andsign - orsign - andsign$ formulas (by the work of Angluin [A90], this is optimal in the sense that the hypothesis class cannot be reduced to depth-2 DNF formulas). We also found deterministic learning algorithms that use \fImembership\fR queries and the NP-oracle for learning monotone boolean functions and the class 0(log $n$)-DNF $cap$ 0(log $n$)-CNF. The running time of these algorithms are polynomial in $n$, DNF size and CNF size of the target formula. Finally with an NP-oracle and membership queries, there is a randomized polynomial-time algorithm that learns any class that is learnable from membership queries with unlimited computational power.
- ItemOpen AccessSIZE-DEPTH TRADEOFFS FOR ALGEBRAIC FORMULAE(1992-05-01) Eberly, Wayne; Cleve, Richard; Bshouty, Nader H.We prove some tradeoffs between the size and depth of algebraic formulae. In particular, we show that, for any fixed $ epsilon~>~O$, any algebraic formula of size \s+1Ss-1 can be converted into an equivalent formula of depth $\s+1O\s-1 (log \s+1S\s-1)$ and size $O(S sup {1+ epsilon})$. This result is an improvement over previously-known results where, to obtain the same depth bound, the formula-size is $ OMEGA (S sup alpha )$, with $ alpha~>=~2$.