scientific article; zbMATH DE number 3566175

zbMath0363.68070MaRDI QIDQ4138141

Lawrence H. Harper, John E. Savage

Publication date: 1976

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Tautologies with a unique Craig interpolant, uniform vs. nonuniform complexity, More on the complexity of slice functions, Analog computation via neural networks, Probabilistic parallel prefix computation, Polynomial division and its computational complexity, Algebraic complexity of computing polynomial zeros, Sequential and parallel complexity of approximate evaluation of polynomial zeros, Complexity of Boolean functions over bases with unbounded fan-in gates, Complexity of parallel matrix computations, Models of lower-bounds proofs, A lower bound for read-once-only branching programs, A logarithmic Boolean time algorithm for parallel polynomial division, Entropy of contact circuits and lower bounds on their complexity, Efficient parallel circuits and algorithms for division, Meanders and their applications in lower bounds arguments, Functions computed by monotone Boolean formulas with no repeated variables, Optimal and nearly optimal algorithms for approximating polynomial zeros, Switching functions whose monotone complexity is nearly quadratic, Displacement ranks of matrices and linear equations, Negation can be exponentially powerful, On the complexity of 2-output Boolean networks, Nonlinear lower bounds on the number of processors of circuits with sublinear separators, Nonuniform complexity and the randomness of certain complete languages, A nonlinear lower bound on the practical combinational complexity, Lower bounds on the area complexity of Boolean circuits, Prediction-preserving reducibility, Threshold circuits of small majority-depth, Relating monotone formula size and monotone depth of Boolean functions, Randomised algorithms, Size-space tradeoffs for oblivious computations, A consideration of a practical implementation for a new convergence division, Data subset selection by Boolean calculation, An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution, On the complexity of slice functions, Linear lower bounds on unbounded fan-in Boolean circuits, The performance of multilective VLSI algorithms