Property Testing

Regular languages are testable with a constant number of queries, Alon, Krivelevich, Newman, Szegedy, SIAM J. Comput. 30 (2001), 1842-1862.

Testing satisfiability, Alon, Shapira, J. Algorithms 47 (2003), 87-103.

Batu, T., Fischer, E., Fortnow, L., Kumar, R., Rubinfeld, R., White, P.   Testing random variables for independence and identity, Proc. 42nd FOCS (2001), 442-451.

Bogdanov, A., Obata, K., Trevisan, L.   A linear lower bound on the query complexity of property testing algorithms for 3-coloring in bounded-degree graphs, Proc. 43rd FOCS (2002), 93-102.

Czumaj, A., Sohler, C.   Property testing with geometric queries, Proc. 9th ESA (2001), 266-277.

Czumaj, A., Sohler, C., Ziegler, M.   Property testing in computational geometry, Proc. 8th ESA (2000), 155-166.

Ergun, F., Kannan, S., Kumar, S.R., Rubinfeld, R., Vishwanthan, M.   Spot-checkers, JCSS 60 (2000), 717-751.

Fischer, E.   On the strength of comparisons in property testing, Electronic Colloquium on Computational Complexity (ECCC) 8 (2001).

Fischer, E., Newman, I.   Testing of matrix properties, Proc. 33rd STOC (2001), 286-295.

Halevy, S., Kushilevitz, E.   Distribution-free property testing, Proc. RANDOM-APPROX (2003), 302-317.

Newman, I.   Testing of functions that have small width branching programs, Proc. 41st FOCS (2000), 251-258.

Bellare, M., Coppersmith, D., Hastad, J., Kiwi, M., Sudan, M. Linearity Testing in Characteristic Two, IEEE Trans. on IT 42 (1996) 1781-1795

Alon, N. Shapira, A., Homomorphism in Graph Property Testing – A Survey

Alon, N. Fischer, E., Newman, I., Shapira, A., A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
Proc. of STOC 2006, 251-260.

Sublinear Algorithms

Achlioptas, D., McSherry, F.   Fast computation of low rank matrix, Proc. 33rd STOC (2001), 611-618.

Azar, Y., Fiat, A., Karlin, A., McSherry, F., Saia, J.   Spectral analysis of data, Proc. 33rd STOC (2001), 619-626.

Bradley, P.S., Mangasarian, O.L., Musicant D.R.   Optimization methods in massive data sets, Handbook of Massive Data Sets (2002), Kluwer, 439-471.

Chazelle, B., Liu, D., Magen, A.   Sublinear geometric algorithms, Proc. 35th STOC (2003), 531-540.

Czumaj, A., Sohler, C.   Sublinear-time approximation for clustering via random sampling, Proc. 31st ICALP, 2004.

Czumaj, A., Sohler, C.   Estimating the weight of metric minimum spanning trees in sublinear-time Proc. 36th STOC (2004).

Czumaj, A., Ergun, F., Fortnow, L., Magen, A., Newman, I., Rubinfeld, R., Sohler, C.   Sublinear-time approximation of Euclidean minimum spanning tree, Proc. 14th SODA (2003), 813-822.

Drineas, P., Kannan, R.   Pass efficient algorithm for approximating large matrices, Proc. 14th SODA (2003), 223-232.

Frieze, A., Kannan, R.   Quick approximation to matrices and applications, Combinatorica 19 (1999), 175-220.

Indyk, P.   Sublinear-time algorithms for metric space problems, Proc. 31st STOC (1999), 428-434.

Indyk, P.   A sublinear-time approximation scheme for clustering in metric spaces, Proc. 40th FOCS (1999), 154-159.

Mishra, N., Oblinger, D., Pitt, L.   Sublinear time approximate clustering, Proc. 12th SODA (2001), 439-447.

Streaming

Babcock, B., Babu, S., Datar, M., Motwani, R., Widom, J.   Models and issues in data stream systems, Proc. 21st PODS (2002), 1-16.

Babcock, B., Datar, M., Motwani, R.   Sampling from a moving window over streaming data, Proc. 13th SODA (2002), 633-634.

Charikar, M., Chen, K., Farach-Colton, M.   Finding frequent items in data streams, Theor. Comput. Sci. 312 (2004), 3-15.

Charikar, M., L. O'Callaghan and R. Panigrahy,   Better streaming algorithms for clustering problems, Proc. 35th STOC (2003), 30-39.

Datar, M., Gionis, A., Indyk, P., Motwani, R.   Maintaining stream statistics over sliding windows, SIAM J. Comput. 31 (2002), 1794-1813.

Gilbert, A., Guha, S., Indyk, P., Kotidis, Y., Muthukrishnan, S., Strauss, M.   Fast, small-space algorithms for approximate histogram maintenance, Proc. 34th STOC (2002), 389-398.

Indyk, P.   Stable distributions, pseudorandom generators, embeddings and data stream computation, Proc. 41st FOCS (2000), 189-197.

Muthukrishnan, S.   Data streams: algorithms and applications, http://www.cs.rutgers.edu/~muthu/

Ganguly, S. Estimating Frequency Moments of Data Streams using Random Linear Combinations, Proc 7^th Random (2004), 369-380

Bhuvangiri, L., Ganguly, S., Kesh, D., Saha, C., Simpler algorithm for estimating frequency moments of data streams, Proc 17^th SODA (2006) 708-713