Journal article:

    Samuel R. Buss.
    "The graph of multiplication is equivalent to counting."
    Information Processing Letters 41 (1992) 199-201.

Download conference article: postscript or PDF

    Abstract: Counting is AC0-reducible to the graph of multiplication. Hence the graph of multiplication is equivalent under AC0 reductions to majority and to the function form of multiplication.

Back to Sam Buss's publications page.