Sbornik Mathematics · 2012 · 17 citations · 34 references
ComputingComputer ScienceMathematicsAlgebraCircuit TheoryTheory Of ComputationAlgorithm AnalysisAlgorithmic ComplexityCircuit ComplexityComputational ComplexityArithmetic Circuit ComplexityArithmetic CircuitsCircuit Lower BoundsCircuit Upper BoundsLower BoundsMonotone CircuitsPolynomial Time ComplexityPositive Real Functions
This work suggests a method for deriving lower bounds for the complexity of polynomials with positive real coefficients implemented by circuits of functional elements over the monotone arithmetic basis {l_brace}x+y, x {center_dot} y{r_brace} Union {l_brace}a {center_dot} x | a Element-Of R{sub +}{r_brace}. Using this method, several new results are obtained. In particular, we construct examples of polynomials of degree m-1 in each of the n variables with coefficients 0 and 1 having additive monotone complexity m{sup (1-o(1))n} and multiplicative monotone complexity m{sup (1/2-o(1))n} as m{sup n}{yields}{infinity}. In this form, the lower bounds derived here are sharp. Bibliography: 72 titles.
34
The complexity of computing the permanent
Leslie G. Valiant · Theoretical Computer Science · 1979 · 2.8K citations
Complexity and real computation
Choice Reviews Online · 1998 · 1.3K citations
The Art of Computer Programming, Vol. 2
Donald E. Knuth · Medical Entomology and Zoology · 1981 · 863 citations