Sublinear algorithms for graph parameters
https://www.youtube.com/watch?v=_kos3_LVpJI
These are roughtly in inverse order of detailed/complete:
http://www.wisdom.weizmann.ac.il/~oded/PS/aver-gr2.ps
http://www.wisdom.weizmann.ac.il/~oded/p_aver-graph.html
http://www.eng.tau.ac.il/~danar/Public-pdf/avg.pdf
http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/GoldreichR-aveDegree.pdf
http://www.wisdom.weizmann.ac.il/~oded/PTW/sublin.pdf
http://tce.technion.ac.il/wp-content/uploads/sites/8/2015/04/DanaRonSlides.pdf
https://github.com/ice109/clrs/blob/master/ch22/sublinear.pdf