Previous Chapter
10. Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms (2/3)
Something for (Almost) Nothing 165
6. M. Blum, M. Luby, and R. Rubinfeld. Self-testing/correcting with applications to
numerical problems. Journal of Computer and System Sciences, 47:549–595, 1993.
(Earlier version in STOC’90.)
7. A. Campagna, A. Guo, and R. Rubinfeld. Local reconstructors and tolerant testers for
connectivity and diameter. In APPROX-RANDOM, pp. 411–424, Springer, Berkeley,
CA, 2013.
8. D. Chakrabarty and C. Seshadhri. A o(n) monotonicity tester for boolean functions
over the hypercube. In STOC, pp. 411–418, ACM, Palo Alto, CA, 2013.
9. S. Chakraborty, D. Garc´ıa-Soriano, and A. Matsliah. Efficient sample extractors for
juntas with applications. In Automata, Languages and Programming: 38th International
Colloquium, pp. 545–556, Springer, Zurich, Switzerland, 2011.
10. X. Chen, R. A. Servedio, and L. Tan. New algorithms and lower bounds for monotonicity
testing. In 55th IEEE Annual Symposium on Foundations of Computer Science,
pp. 286–295. Philadelphia, PA, October 18–21, 2014,
11. A. Czumaj and C. Sohler. Abstract combinatorial programs and efficient property
testers. SIAM Journal on Computing, 34(3):580–615, 2005.
12. A. Czumaj and C. Sohler. Sublinear-time algorithms. Bulletin of the EATCS, 89:23–47,
2006.
13. I. de Sola Pool and M. Kochen. Contacts and influence. Social Networks, 1(1):5–51,
1979.
14. I. Diakonikolas, H. Lee, K. Matulef, K. Onak, R. Rubinfeld, R. Servedio, and A. Wan.
Testing for concise representations. In Proceedings of the 48th Annual IEEE Symposium
on Foundations of Computer Science, pp. 549–558, IEEE, Providence, RI, 2007.
15. Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova, D. Ron, and A. Samorodnitsky.
Improved testing algorithms for monotonocity. In Proceedings of RANDOM, pp. 97–108,
Springer, Berkeley, CA, 1999.
16. D. A. Easley and J. M. Kleinberg. Networks, Crowds, and Markets – Reasoning About
a Highly Connected World. Cambridge University Press, New York, 2010.
17. F. Erg¨un, S. Kannan, S. R. Kumar, R. Rubinfeld, and M. Viswanathan. Spot-checkers.
JCSS, 60(3):717–751, 2000.
18. G. Even, M. Medina, and D. Ron. Best of two local models: Local centralized and local
distributed algorithms. arXiv preprint arXiv:1402.3796, 2014.
19. G. Even, M. Medina, and D. Ron. Distributed maximum matching in bounded degree
graphs. arXiv preprint arXiv:1407.7882, 2014.
20. T. Feder and D. H. Greene. Optimal algorithms for approximate clustering. In
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2–4,
1988, Chicago, IL, pp. 434–444, 1988.
21. E. Fischer, G. Kindler, D. Ron, S. Safra, and A. Samorodnitsky. Testing juntas. Journal
of Computer and System Sciences, 68(4):753–787, 2004.
22. E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and
A. Samrodnitsky. Monotonicity testing over general poset domains. In Proceedings of
166 Handbook of Big Data
the 34th Annual ACM Symposium on the Theory of Computing, pp. 474–483, ACM,
Montreal, Canada, 2002.
23. R. J. Fowler, M. S. Paterson, and S. L. Tanimoto. Optimal packing and covering in the
plane are np-complete. IPL, pp. 434–444, 1981.
24. O. Goldreich. Combinatorial property testing – A survey. In Randomization Methods
in Algorithm Design, pp. 45–60, AMS, Princeton, NJ, 1998.
25. O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samordinsky. Testing
monotonicity. Combinatorica, 20(3):301–337, 2000.
26. O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning
and approximation. Journal of the ACM, 45:653–750, 1998.
27. O. Goldreich and D. Ron. On sample-based testers. In Proceedings of the 6th Innovations
in Theoretical Computer Science, pp. 337–345, ACM, Rehovot, Israel, 2015.
28. A. Hassidim, Y. Mansour, and S. Vardi. Local computation mechanism design. In
Proceedings of the 15th ACM Conference on Economics and Computation, pp. 601–616.
ACM, Palo Alto, CA, 2014.
29. M. Jha and S. Raskhodnikova. Testing and reconstruction of lipschitz functions with
applications to data privacy. Journal on Computing, 42(2):700–731, 2013.
30. R. M. Karp. Reducibility among combinatorial problems. In Proceedings of a Symposium
on the Complexity of Computer Computations, pp. 85–103. March 20–22, 1972, IBM
Thomas J. Watson Research Center, Yorktown Heights, NY, 1972.
31. M. J. Kearns and D. Ron. Testing problems with sublearning sample complexity. Journal
of Computer and System Sciences, 61(3):428–456, 2000.
32. P. Kothari, A. Nayyeri, R. O’Donnell, and C. Wu. Testing surface area. In Proceedings
of the 25th ACM-SIAM Symposium on Discrete Algorithms, pp. 1204–1214, SIAM,
Portland, OR, 2014.
33. F. Kuhn, T. Moscibroda, and R. Wattenhofer. Local computation: Lower and upper
bounds. CoRR, http://arxiv.org/abs/1011.5470, 2010.
34. R. Kumar and R. Rubinfeld. Algorithms column: Sublinear-time algorithms. SIGACT
News, 34:57–67, 2003.
35. R. Kumar and R. Rubinfeld. Sublinear time algorithms. SIGACT News, 34:57–67, 2003.
36. R. Levi, R. Rubinfeld, and A. Yodpinyanee. Local computation algorithms for graphs
of non-constant degrees. arXiv preprint arXiv:1502.04022, 2015.
37. Y. Mansour, A. Rubinstein, S. Vardi, and N. Xie. Converting online algorithms to
local computation algorithms. In Automata, Languages, and Programming, pp. 653–664.
Springer, Warwick, 2012.
38. Y. Mansour and S. Vardi. A local computation approximation scheme to maximum
matching. In Approximation, Randomization, and Combinatorial Optimization: Algo-
rithms and Techniques, pp. 260–273. Springer, Berkeley, CA, 2013.
39. K. Matulef, R. O’Donnell, R. Rubinfeld, and R. A. Servedio. Testing halfspaces. SIAM
Journal on Computing, 39(5):2004–2047, 2010.
Something for (Almost) Nothing 167
40. N. Megiddo and E. Zemel. An O(n log n) randomizing algorithm for the weighted
euclidean 1-center problem. Journal of Algorithms, 7(3):358–368, 1986.
41. N. Mishra, D. Oblinger, and L. Pitt. Sublinear time approximate clustering. In
Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms,
pp. 439–447. Society for Industrial and Applied Mathematics Philadelphia, PA, 2001.
42. J. Neeman. Testing surface area with arbitrary accuracy. In Proceedings of the 46th
Annual ACM Symposium on the Theory of Computing, pp. 393–397, ACM, New York,
2014.
43. H. N. Nguyen and K. Onak. Constant-time approximation algorithms via local
improvements. In Proceedings of the 49th Annual IEEE Symposium on Foundations
of Computer Science, pp. 327–336, IEEE, Philadelphia, PA, 2008.
44. K. Onak, D. Ron, M. Rosen, and R. Rubinfeld. A near-optimal sublinear-time algorithm
for approximating the minimum vertex cover size. In Proceedings of the 23rd Annual
ACM-SIAM Symposium on Discrete Algorithms, pp. 1123–1131. SIAM, Kyoto, Japan,
2012.
45. C. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Com-
plexity. Dover Publications, Mineola, NY, 1998.
46. M. Parnas and D. Ron. Testing the diameter of graphs. Random Structures and
Algorithms, 20(2):165–183, 2002.
47. M. Parnas and D. Ron. Approximating the minimum vertex cover in sublinear time
and a connection to distributed algorithms. Theoretical Computer Science, 381(1–3):
183–196, 2007.
48. M. Parnas, D. Ron, and R. Rubinfeld. Tolerant property testing and distance
approximation. Journal of Computer and System Sciences, 72(6):1012–1042, 2006.
49. O. Reingold and S. Vardi. New techniques and tighter bounds for local computation
algorithms. arXiv preprint arXiv:1404.5398, 2014.
50. D. Ron. Property testing. In S. Rajasekaran, P. M. Pardalos, J. H. Reif, and J. Rolim
(eds.), Handbook on Randomization, Vol. II, pp. 597–649, Springer, 2001.
51. D. Ron. Property testing: A learning theory perspective. Foundations and Trends in
Machine Learning, 3:307–402, 2008.
52. R. Rubinfeld. Sublinear time algorithms. In Proceedings of the International Congress
of Mathematicians, Vol. 3, pp. 1095–1111, AMS, Madrid, Spain, 2006.
53. R. Rubinfeld. Taming big probability distributions. ACM Crossroads, 19(1):24–28, 2012.
54. R. Rubinfeld and A. Shapira. Sublinear time algorithms. SIAM Journal of Discrete
Mathematics, 25(4):1562–1588, 2011.
55. R. Rubinfeld and M. Sudan. Robust characterizations of polynomials with applications
to program testing. SIAM Journal on Computing, 25:252–271, 1996.
56. Y. Yoshida, Y. Yamamoto, and H. Ito. An improved constant-time approximation
algorithm for maximum matchings. In Proceedings of the 41st Annual ACM Symposium
on the Theory of Computing, pp. 225–234, ACM, Bethesda, MD, 2009.
This page intentionally left blankThis page intentionally left blank
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.