Average Case and Probabilistic Setting of Information-Based Complexity

This project will continue research on the average and probabilistic settings of information-based complexity. The goal is to investigate when intractability or noncomputability in the deterministic worst case setting can be avoided by using randomness or by using average and probabilistic settings. In addition, two new research directions will be pursued. The first is probabilistic complexity for piece-wise smooth functions. The second is the relation between complexity and stability.