E. Novak, Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials, J COMPLEX, 15(3), 1999, pp. 299-316
Lower bounds for the error of quadrature formulas with positive weights are
proved. We get intractability results for quasi-Monte Carlo methods and, m
ore generally, for positive formulas. We consider general classes of functi
ons but concentrate on lower bounds for relatively small classes of trigono
metric polynomials. We also conjecture that similar lower bounds hold for a
rbitrary quadrature formulas and state different equivalent conjectures con
cerning positive definiteness of certain matrices and certain extremal prob
lems for trigonometric polynomials. We also study classes of functions with
weighted norms where some Variables are "more important" than others. Posi
tive quadrature formulas are then tractable iff the sum of the wrights is b
ounded. (C) 1999 Academic Press.