Basics for sublinear algorithms

In this chapter, we study the theoretical foundations of sublinear algorithms. We discuss the foundations of approximation and randomization and show the history of the development of sublinear algorithms in the theoretical research line. Intrinsically, sublinear algorithms can be considered as one branch of approximation algorithms with confidence guarantees. A sublinear algorithm says that the accuracy of the algorithm output will not deviate from an error bound and there is high confidence that the error bound will be satisfied. More rigidly, a sublinear algorithm is commonly written as (1 +ε, δ)-approximation in a mathematical form. Here ε is commonly called an accuracy parameter and δ is commonly called a confidence parameter. This accuracy parameter is the same to the approximate factor in approximation algorithms. This confidence parameter is the key trade-off where the complexity of the algorithm can reduce to sublinear. We will rigidly define these parameters in this chapter.