More Like this

1. Streaming Algorithms via Local Algorithms for Maximum Directed Cut

   Saxena, Raghuvansh R; Singer, Noah G; Sudan, Madhu; Velusamy, Santhoshini (January 2025, Society for Industrial and Applied Mathematics)

   We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of (Buchbinder, Feldman, Seffi, and Schwartz [14] and Censor-Hillel, Levy, and Shachnai [16]), we develop streaming algorithms for both adversarially and randomly ordered streams that approximate the value of maximum directed cut in bounded-degree graphs. In n-vertex graphs, for adversarially ordered streams, our algorithm uses O (n1-Ω(1)) (sub-linear) space and for randomly ordered streams, our algorithm uses logarithmic space. Moreover, both algorithms require only one pass over the input stream. With a constant number of passes, we give a logarithmic-space algorithm which works even on graphs with unbounded degree on adversarially ordered streams. Our algorithms achieve any fixed constant approximation factor less than 1/2. In the single-pass setting, this is tight: known lower bounds show that obtaining any constant approximation factor greater than 1/2 is impossible without using linear space in adversarially ordered streams (Kapralov and Krachun [37]) and space in randomly ordered streams, even on bounded degree graphs (Kapralov, Khanna, and Sudan [35]). In terms of techniques, our algorithms partition the vertices into a small number of different types based on the structure of their local neighborhood, ensuring that each type carries enough information about the structure to approximately simulate the local algorithm on a vertex with that type. We then develop tools to accurately estimate the frequency of each type. This allows us to simulate an execution of the local algorithm on all vertices, and thereby approximate the value of the maximum directed cut. 

   more » « less
2. Streaming Algorithms via Local Algorithms for Maximum Directed Cut

   Saxena, Raghuvansh R; Singer, Noah G; Sudan, Madhu; Velusamy, Santhoshini (January 2025, Society for Industrial and Applied Mathematics)

   We explore the use of local algorithms in the design of streaming algorithms for the Maximum Directed Cut problem. Specifically, building on the local algorithm of (Buchbinder, Feldman, Seffi, and Schwartz [14] and Censor-Hillel, Levy, and Shachnai [16]), we develop streaming algorithms for both adversarially and randomly ordered streams that approximate the value of maximum directed cut in bounded-degree graphs. In n-vertex graphs, for adversarially ordered streams, our algorithm uses O (n1-Ω(1)) (sub-linear) space and for randomly ordered streams, our algorithm uses logarithmic space. Moreover, both algorithms require only one pass over the input stream. With a constant number of passes, we give a logarithmic-space algorithm which works even on graphs with unbounded degree on adversarially ordered streams. Our algorithms achieve any fixed constant approximation factor less than 1/2. In the single-pass setting, this is tight: known lower bounds show that obtaining any constant approximation factor greater than 1/2 is impossible without using linear space in adversarially ordered streams (Kapralov and Krachun [37]) and space in randomly ordered streams, even on bounded degree graphs (Kapralov, Khanna, and Sudan [35]). In terms of techniques, our algorithms partition the vertices into a small number of different types based on the structure of their local neighborhood, ensuring that each type carries enough information about the structure to approximately simulate the local algorithm on a vertex with that type. We then develop tools to accurately estimate the frequency of each type. This allows us to simulate an execution of the local algorithm on all vertices, and thereby approximate the value of the maximum directed cut. 

   more » « less
3. Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms

   https://doi.org/10.4230/LIPIcs.ICALP.2018.7  

   Arar, Moab; Chechik, Shiri; Cohen, Sarel; Stein, Clifford; Wajc, David (July 2018, Automata, languages and programming)
4. Designing Ethical Algorithms

   https://doi.org/10.17705/2msqe.00012  

   Martin, Kirsten (January 2019, MIS Quarterly Executive)
5. Statecraft by Algorithms

   https://doi.org/10.1086/725134  

   Steingart, Alma (July 2023, Osiris)

   Throughout the 1920s Congress failed to pass an apportionment bill. Among the various reasons for the failure was Congress’s inability to decide which method, or algorithm, should govern apportionment. Two competing methods, major fractions and equal proportions, rose to the top and the supporter of each claimed that his method offered the only “fair” and “unbiased” solution to the problem. Following this early debate, this chapter argues that contemporary concerns about algorithm fairness and equality do not emerge out of the nature of their complexity. Rather, they inhere in the incommensurability between mathematical and social rationales and the wide room for interpretation yawning between the two. Not only are definitions of “fairness” multiple but how algorithms are described, either through method or through principle, can lead to completely different results. 

   more » « less