Integrating and approximating a function over the unit hyper-cube in dimension d, are a fundamental numerical tasks with many applications. Integration methods are widely used in valuation of financial derivatives. Approximation methods are used in the design of complex products like semiconductors and aircraft.
For small d, simple methods that evaluate the target function on a grid work very well. As the dimension d increases, such tensor product methods become computationally infeasible.
Sampling methods, such as Monte Carlo, are much less sensitive to the dimension effect, and are the practical methods of choice for large d. Better sampling methods, such as quasi-Monte Carlo sampling, use combinatorics to define the input points.
This talk surveys recent work in sampling methods for integration and approximation, and presents some challenges for combinatorial methods. One challenge is to develop point sets with some equidistribution properties of (t,m,s)-nets but for which the equidistribution is much better for relatively important dimensions. Another is to study performance bounds for equidistribution, analogous to the bounds on orthogonal array strength, for very high dimensions. A third challenge is to construct point sets in the unit cube that are better for quasi-regression approximation than are random points. A fourth challenge is to construct point sets that are better for integrating very smooth functions.