Distributed Corruption Detection in Networks

by Noga Alon, Elchanan Mossel, and Robin Pemantle

Theory of Computing, Volume 16(1), pp. 1-23, 2020

Bibliography with links to cited articles

[1]   Noga Alon: Explicit expanders of every degree and size, 2020. [arXiv:2003.11673]

[2]   Noga Alon, Jehoshua Bruck, Joseph Seffi Naor, Moni Naor, and Ron M. Roth: Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inform. Theory, 38(2):509–516, 1992. [doi:10.1109/18.119713]

[3]   Noga Alon and Fan R. K. Chung: Explicit construction of linear sized tolerant networks. Discrete Math., 72(1–3):15–19, 1988. Preliminary version in Proc. First Japan Conf. on Graph Theory and Appl., 1986. [doi:10.1016/0012-365X(88)90189-6]

[4]   Noga Alon, Gil Kalai, Moty Ricklin, and Larry Stockmeyer: Lower bounds on the competitive ratio for mobile user tracking and distributed job scheduling. Theoret. Comput. Sci., 130(1):175–201, 1994. Preliminary version in FOCS’92. [doi:10.1016/0304-3975(94)90158-9]

[5]   Noga Alon, Paul Seymour, and Robin Thomas: A separator theorem for nonplanar graphs. J. Amer. Math. Soc., 3(4):801–808, 1990. [doi:10.2307/1990903]

[6]   Ryan Alweiss: Noisy corruption detection. Inform. Process. Lett., 155(105897), 2020. [doi:10.1016/j.ipl.2019.105897, arXiv:1908.07493]

[7]   Piotr Berman and Marek Karpinski: On some tighter inapproximability results (extended abstract). In Proc. 26th Internat. Colloq. on Automata, Languages and Programming (ICALP’99), volume 1644, pp. 200–209. Springer, 1999. [doi:10.1007/3-540-48523-6_17]

[8]   Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms. MIT Press, Cambridge, MA, third edition, 2009.

[9]   Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal: Fault tolerance in networks of bounded degree. SIAM J. Comput., 17(5):975–988, 1988. Preliminary version in STOC’86. [doi:10.1137/0217061]

[10]   Odd-Helge Fjeldstad: Fighting fiscal corruption: lessons from the Tanzania Revenue Authority. Public Administration and Development, 23(2):165–175, 2003. [doi:10.1002/pad.278]

[11]   Juan A. Garay and Rafail Ostrovsky: Almost-everywhere secure computation. In Advances in Cryptology—EUROCRYPT’08, volume 4965, pp. 307–323. Springer, 2008. [doi:10.1007/978-3-540-78967-3_18]

[12]   S. Louis Hakimi and Ashok T. Amin: Characterization of connection assignment of diagnosable systems. IEEE Trans. Computers, C-23(1):86–88, 1974. [doi:10.1109/t-c.1974.223782]

[13]   Shlomo Hoory, Nathan Linial, and Avi Wigderson: Expander graphs and their applications. Bull. Amer. Math. Soc., 43(4):439–561, 2006. [doi:10.1090/S0273-0979-06-01126-8]

[14]   Yan Jin, Elchanan Mossel, and Govind Ramnarayan: Being corrupt requires being clever, but detecting corruption doesn’t. In 10th Innovations in Theoretical Comp. Sci. Conf. (ITCS’19, volume 124, pp. 45:1–45:14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.ITCS.2019.45, arXiv:1809.10325]

[15]   Tiko Kameda, Shunichi Toida, and F. J. Allan: A diagnosing algorithm for networks. Information and Control, 29(2):141–148, 1975. [doi:10.1016/S0019-9958(75)90508-2]

[16]   Jon G. Kuhl and Sudhakar M. Reddy: Distributed fault-tolerance for large multiprocessor systems. In Proc. 7th Ann. Symp. on Computer Architecture (ISCA’80), pp. 23–30. ACM Press, 1980. [doi:10.1145/800053.801905]

[17]   Leslie Lamport, Robert Shostak, and Marshall Pease: The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982. [doi:10.1145/357172.357176]

[18]   Richard J. Lipton and Robert Endre Tarjan: A separator theorem for planar graphs. SIAM J. Appl. Math., 36(2):177–189, 1979. [doi:10.1137/0136016]

[19]   Alex Lubotzky, Ralph Phillips, and Peter Sarnak: Ramanujan graphs. Combinatorica, 8(3):261–277, 1988. [doi:10.1007/BF02126799]

[20]   Grigory A. Margulis: Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators (Russian). Problemy Peredachi Informatsii, 24(1):51–60, 1988. Link at Mathnet.ru. English translation: Problems Inform. Transmission 24 (1988/1) 39–46.

[21]   Biswanath Mukherjee, L. Todd Heberlein, and Karl N. Levitt: Network intrusion detection. IEEE Network, 8(3):26–41, 1994. [doi:10.1109/65.283931]

[22]   Richard P. Nielsen: Corruption networks and implications for ethical corruption reform. Journal of Business Ethics, 42(2):125–149, 2003. [doi:10.1023/A:1021969204875]

[23]   Franco P. Preparata, Gernot Metze, and Robert T. Chien: On the connection assignment problem of diagnosable systems. IEEE Trans. Electronic Computers, EC-16(6):848–854, 1967. [doi:10.1109/PGEC.1967.264748]

[24]   Prasad Raghavendra and David Steurer: Graph expansion and the unique games conjecture. In Proc. 42nd STOC, pp. 755–764. ACM Press, 2010. [doi:10.1145/1806689.1806792]

[25]   Michael T. Rock and Heidi Bonnett: The comparative politics of corruption: accounting for the East Asian paradox in empirical studies of corruption, growth and investment. World Development, 32(6):999–1017, 2004. [doi:10.1016/j.worlddev.2003.12.002]

[26]   Małgorzata Steinder and Adarshpal S. Sethi: A survey of fault localization techniques in computer networks. Sci. Comput. Programming, 53(2):165–194, 2004. [doi:10.1016/j.scico.2004.01.010]

[27]   R. Michael Tanner: Explicit construction of concentrators from generalized n-gons. SIAM J. on Algebraic Discrete Methods, 5(3):287–293, 1984. [doi:10.1137/0605030]