Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials

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.