There are many interesting papers, many of which do not assume too much background, and others which are more difficult but perhaps we can decide
on a subset of the paper which is reasonable present.
Here are some examples, but there are many others that would
be good candidates.
Some papers are "classics", but most
point to interesting and active research directions.
I have also included a few papers on the related topics of
streaming algorithms.
In addition to the papers below, I would be happy to suggest others according
to your specific interests. I will also add a few more in the
first days of the semester, according to discussions with students.
Dana Ron, Rocco A. Servedio:
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities. Algorithmica 72(2): 400-429 (2015)
Dana Ron, Gilad Tsur:
On Approximating the Number of Relevant Variables in a Function. TOCT 5(2): 7 (2013)
Property testing of graphs
Artur Czumaj, Pan Peng, Christian Sohler:
Testing Cluster Structure of Graphs. STOC 2015: 723-732
Artur Czumaj, Pan Peng, Christian Sohler:
Testing Cluster Structure of Graphs. CoRR abs/1504.03294 (2015)
Reid Andersen, Christian Borgs, Jennifer T. Chayes, John E. Hopcroft, Vahab S. Mirrokni, Shang-Hua Teng:
Local Computation of PageRank Contributions. Internet Mathematics 5(1): 23-45 (2008)
Christian Borgs, Jennifer T. Chayes, Laszlo Lovasz, Vera T. Sos, Balazs Szegedy, Katalin Vesztergombi:
Graph limits and parameter testing. STOC 2006: 261-270
Christian Borgs, Jennifer T. Chayes, Adam Smith:
Private Graphon Estimation for Sparse Graphs. CoRR abs/1506.06162 (2015)
Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Shang-Hua Teng:
Multiscale Matrix Sampling and Sublinear-Time PageRank Computation. Internet Mathematics 10(1-2): 20-48 (2014)
Christian Borgs, Michael Brautbar, Jennifer T. Chayes, Shang-Hua Teng:
A Sublinear Time Algorithm for PageRank Computations. WAW 2012: 41-53
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler:
Finding cycles and trees in sublinear time. Random Struct. Algorithms 45(2): 139-184 (2014)
Learning and Testing distributions
Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin:
Testing Identity of Structured Distributions. SODA 2015: 1841-1854
Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Nearly Optimal Learning and Sparse Covers for Sums of Independent Integer Random Variables. CoRR abs/1505.00662 (2015)
Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin:
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions. CoRR abs/1508.05538 (2015)
Constantinos Daskalakis, Ilias Diakonikolas, Rocco A. Servedio:
Learning k-Modal Distributions via Testing. Theory of Computing 10: 535-570 (2014)
Siu-on Chan, Ilias Diakonikolas, Paul Valiant, Gregory Valiant:
Optimal Algorithms for Testing Closeness of Discrete Distributions. SODA 2014: 1193-1203
Edith Cohen:-
Estimation for monotone sampling: competitiveness and customization. PODC 2014: 124-133
Edith Cohen:
All-distances sketches, revisited: HIP estimators for massive graphs analysis. PODS 2014: 88-99
Edith Cohen, Haim Kaplan:
What You Can Do with Coordinated Samples. APPROX-RANDOM 2013: 452-467
Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup:
Stream sampling for variance-optimal estimation of subset sums. SODA 2009: 1255-1264
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
Verifiable Stream Computation and Arthur-Merlin Communication. Conference on Computational Complexity 2015: 217-243
paper
Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler:
Annotations for Sparse Data Streams. SODA 2014: 687-706
paper
Tom Gur and Ron Rothblum:
Non-Interactive Proofs of Proximity.