Academic
Publications
On the Shrinkage Exponent for Read-Once Formulae

On the Shrinkage Exponent for Read-Once Formulae,10.1016/0304-3975(94)00081-S,Theoretical Computer Science,Johan Håstad,Alexander A. Razborov,Andrew C

On the Shrinkage Exponent for Read-Once Formulae   (Citations: 2)
BibTex | RIS | RefWorks Download
Abstract: We prove that the size of any read-once de Morgan formula reduces in averageby a factor of at least p o(1)when all but a fraction p of the input variables arerandomly assigned to f0; 1g (here * ) 1= log 2 (5 1)  3:27). This resolves in thearmative a conjecture of Paterson and Zwick. The bound is shown to be tight upto a polylogarithmic factor for all p  n.
Journal: Theoretical Computer Science - TCS , vol. 141, no. 1&2, pp. 269-282, 1995
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Other works relevant to the subjects considered in this paper are [8], [9], [10], and [17]...

    Moshe Dubineret al. Amplification by Read-Once Formulas

    • ...Other works relevant to the subjects considered in this paper are [7],[8],[9] and [16]...
    • ...Definition 2.3 (Formulae) A formula of n variables is defined recursively as follows: (i) for 1 5 i 5 n, the variables z; and their negations are formulae; (ii) iff and g are formulae then so are (1 f), (f A g), (f V g) and (f @ 9). A formula in which no XOR gates are used is called unale or de Morgan...
    • ...Theorem 2.9 (Boppana’s inequality) Let H(z) = -xlogzz - (1 - z)log,(l - x) be the usual...
    • ...encounter a similar relation in Section 9 that presents constructions of small amplifying networks...
    • ...Using Corollary 4.3 and a simple change of variables we get 5.2. Had we used H(x)9 we logn) lower that...
    • ...U <{[SECTION]}>9 Amplifying networks Valiant’s construction of O(na) size monotone formulae that amplify($-:,$++) to (a, j) uses arepeated composition of the basic series-parallel unit A shown in Fig. 1. Better amplification can be obtained using other units (e.g., units B, C, D of Fig. 1)...
    • ...Theorem 9.1 Let f(t1 , .. ., tk) be the amplification function of a monotone read-once coniact network with k edges...
    • ...As 3u3 N 2.64 < 9 it seems that we could do a bit better using 3-dimensional grids...

    Moshe Dubineret al. Amplification and percolation [probabilistic Boolean functions]

Sort by: