Activists engage in highly public and collaborative work, and their social movement groups have long been targeted by the surveillance state. Many consider the adoption of secure and privacy-enhancing technologies to be the antidote. However, activists operate with limited resources and elevated risk, making the adoption of these technologies difficult and imperfect. We investigate how groups navigate organizing using digital communication, and specifically how groups make intentional (even if insecure) decisions around privacy protections in their organizing. We interviewed 40 activists belonging to 33 U.S.-based social movement groups ranging in size, structure, and tactics. Responses were analyzed qualitatively to uncover factors influencing digital security decisions for organizing work. We find that low-risk hierarchical groups with a lack of training and little concern for surveillance tended to not consider privacy as they navigate digital technologies and horizontally-organized groups engaging in risky activities took intentional strides to enhance their digital privacy within the context of their activism. The availability and influence of a technically-minded group member or advisor plays a strong role in the adoption of PETs. A groups\' lack of knowledge in PET use or concern with surveillance is a barrier to PET adoption and highlights the importance of education. Finally, we find that feature availability and learnability is still an important factor in PET adoption. This work illustrates the nuanced factors and responses that users aware of the threat of surveillance are taking into consideration, including but not restricted to, the adoption of E2EE communication technology and the digital security culture necessary to operationalize it.

Abstract Existing end-to-end-encrypted (E2EE) email systems, mainly PGP, have long been evaluated in controlled lab settings. While these studies have exposed usability obstacles for the average user and offer design improvements, there exist users with an immediate need for private communication, who must cope with existing software and its limitations. We seek to understand whether individuals motivated by concrete privacy threats, such as those vulnerable to state surveil-lance, can overcome usability issues to adopt complex E2EE tools for long-term use. We surveyed regional activists, as surveillance of social movements is well-documented. Our study group includes individuals from 9 social movement groups in the US who had elected to participate in a workshop on using Thunder-bird+Enigmail for email encryption. These workshops tool place prior to mid-2017, via a partnership with a non-profit which supports social movement groups. Six to 40 months after their PGP email encryption training, more than half of the study participants were continuing to use PGP email encryption despite intervening widespread deployment of simple E2EE messaging apps such as Signal. We study the interplay of usability with social factors such as motivation and the risks that individuals undertake through their activism. We find that while usability is an important factor, it is not enough to explain long term use. For example, we find that riskiness of one’s activism is negatively correlated with long-term PGP use. This study represents the first long-term study, and the first in-the-wild study, of PGP email encryption adoption.

We study two optimization problems on simplicial complexes with homology over ℤ₂, the minimum bounded chain problem: given a d-dimensional complex 𝒦 embedded in ℝ^(d+1) and a null-homologous (d-1)-cycle C in 𝒦, find the minimum d-chain with boundary C, and the minimum homologous chain problem: given a (d+1)-manifold ℳ and a d-chain D in ℳ, find the minimum d-chain homologous to D. We show strong hardness results for both problems even for small values of d; d = 2 for the former problem, and d=1 for the latter problem. We show that both problems are APX-hard, and hard to approximate within any constant factor assuming the unique games conjecture. On the positive side, we show that both problems are fixed-parameter tractable with respect to the size of the optimal solution. Moreover, we provide an O(√{log β_d})-approximation algorithm for the minimum bounded chain problem where β_d is the dth Betti number of 𝒦. Finally, we provide an O(√{log n_{d+1}})-approximation algorithm for the minimum homologous chain problem where n_{d+1} is the number of (d+1)-simplices in ℳ.

Lightness and sparsity are two natural parameters for Euclidean $(1+\varepsilon)$-spanners. Classical results show that, when the dimension $d\in \mathbb{N}$ and $\varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits a $(1+\varepsilon)$-spanner with $O(n)$ edges and weight proportional to that of the Euclidean minimum spanning tree of $S$. In a recent breakthrough, Le and Solomon [Proceedings of FOCS, 2019, pp. 1078--1100] established the precise dependencies on $\varepsilon>0$, for constant $d\in \mathbb{N}$, of the minimum lightness and sparsity of $(1+\varepsilon)$-spanners, and observed that Steiner points can substantially improve the lightness and sparsity of a $(1+\varepsilon)$-spanner. They gave upper bounds of $\tilde{O}(\varepsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $d\geq 3$ and $\tilde{O}(\varepsilon^{-(d-1)/2})$ for the minimum sparsity in $d$-space for all $d\geq 1$. Subsequently, Le and Solomon [LIPIcs Leibniz Int. Proc. Inform. 173, Schloss Dagstuhl, Wadern, 2020, pp. 67:1--67:22] constructed Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\log\Delta)$ in the plane, where $\Delta\in \Omega(\sqrt{n})$ is the spread of $S$, defined as the ratio between the maximum and the minimum distance between a pair of points. In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner $(1+\varepsilon)$-spanners. We establish lower bounds of $\Omega(\varepsilon^{-d/2})$ for the lightness and $\Omega(\varepsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all constant $d\geq 2$. Our lower bound constructions generalize previous constructions by Le and Solomon, but the analysis substantially simplifies previous work, using new geometric insight, focusing on the directions of edges. Next, we show that for every finite set of points in the plane and every $\varepsilon\in (0,1]$, there exists a Euclidean Steiner $(1+\varepsilon)$-spanner of lightness $O(\varepsilon^{-1})$; this matches the lower bound for $d=2$. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis.

We consider the problem of finding the minimum-weight subgraph that satisfies given connectivity requirements. Specifically, given a requirement $r \in \{0,1,2,3\}$ for every vertex, we seek the minimum-weight subgraph that contains, for every pair of vertices $u$ and $v$, at least $\min\{ r(v), r(u)\}$ edge-disjoint $u$-to-$v$ paths. We give a polynomial-time approximation scheme (PTAS) for this problem when the input graph is planar and the subgraph may use multiple copies of any given edge. This generalizes an earlier result for $r \in \{0,1,2\}$. In order to achieve this PTAS, we prove some properties of triconnected planar graphs that may be of independent interest.

We show that every H-minor-free graph has a light (1+≥ilon)-spanner, resolving an open problem of Grigni and Sissokho and proving a conjecture of Grigni and Hung \cite{GH12}. Our lightness bound is \[O\left(\frac{\sigma_H}{≥ilon^3}\log \frac{1}{≥ilon}\right)\] where \sigma_H = |V(H)|√{\log |V(H)|} is the sparsity coefficient of H-minor-free graphs. That is, it has a practical dependency on the size of the minor H. Our result also implies that the polynomial time approximation scheme (PTAS) for the Travelling Salesperson Problem (TSP) in H-minor-free graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose running time is 2^{O_H\left(\frac{1}{≥ilon^4}\log \frac{1}{≥ilon}\right)}n^{O(1)} where O_H ignores dependencies on the size of H. Our techniques significantly deviate from existing lines of research on spanners for H-minor-free graphs, but build upon the work of Chechik and Wulff-Nilsen for spanners of general graphs[6].

We give an $O(n \log^3 n)$ algorithm that, given an $n$-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

We study the problems of finding a minimum cycle basis (a minimum weight set of cycles that form a basis for the cycle space) and a minimum homology basis (a minimum weight set of cycles that generates the 1-dimensional (Z_2)-homology classes) of an undirected graph embedded on an orientable surface of genus g. The problems are closely related, because the minimum cycle basis of a graph contains its minimum homology basis, and the minimum homology basis of the 1-skeleton of any graph is exactly its minimum cycle basis. For the minimum cycle basis problem, we give a deterministic O(n^omega + 2^2g n^2)-time algorithm. The best known existing algorithms for surface embedded graphs are those for general sparse graphs: an O(n^omega) time Monte Carlo algorithm [Amaldi et. al., ESA'09] and a deterministic O(n^3) time algorithm [Mehlhorn and Michail, TALG'09]. For the minimum homology basis problem, we give an O(g^3 n log n)-time algorithm, improving on existing algorithms for many values of g and n.

For an undirected $n$-vertex graph $G$ with non-negative edge-weights, we consider the following type of query: given two vertices $s$ and $t$ in $G$, what is the weight of a minimum $st$-cut in $G$? We solve this problem in preprocessing time $O(n\log^3 n)$ for graphs of bounded genus, giving the first sub-quadratic time algorithm for this class of graphs. Our result also improves by a logarithmic factor a previous algorithm by Borradaile, Sankowski and Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm constructs a Gomory-Hu tree for the given graph, providing a data structure with space $O(n)$ that can answer minimum-cut queries in constant time. The dependence on the genus of the input graph in our preprocessing time is $2^{O(g^2)}$.

There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems is optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to r-domination problems. In r-dominating set, one wishes to find a minimum subset S of vertices such that every vertex of G is within r hops of some vertex in S. In connected r-dominating set, one additionally requires that the set induces a connected subgraph of G. We give a O((2r+1)^tw n) time algorithm for r-dominating set and a randomized O((2r+2)^tw n^{O(1)}) time algorithm for connected r-dominating set in n-vertex graphs of treewidth tw. We show that the running time dependence on r and tw is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints.

Consider the following problem: given a graph with edge costs and a subset Q of vertices, find a minimum-cost subgraph in which there are two edge-disjoint paths connecting every pair of vertices in Q . The problem is a failure-resilient analog of the Steiner tree problem arising, for example, in telecommunications applications. We study a more general mixed-connectivity formulation, also employed in telecommunications optimization. Given a number (or requirement ) r ( v ) ∈ {0, 1, 2} for each vertex v in the graph, find a minimum-cost subgraph in which there are min { r ( u ), r ( v )} edge-disjoint u -to- v paths for every pair u , v of vertices. We address the problem in planar graphs, considering a popular relaxation in which the solution is allowed to use multiple copies of the input-graph edges (paying separately for each copy). The problem is max SNP-hard in general graphs and strongly NP-hard in planar graphs. We give the first polynomial-time approximation scheme in planar graphs. The running time is O ( n log n ). Under the additional restriction that the requirements are only non-zero for vertices on the boundary of a single face of a planar graph, we give a polynomial-time algorithm to find the optimal solution.

We give a randomized O ( n polylog n )-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed ϵ > 0 and given n terminals in the plane with connection requests between some pairs of terminals, our scheme finds a (1 + ϵ) approximation to the minimum-length forest that connects every requested pair of terminals.

For an undirected n -vertex planar graph G with nonnegative edge weights, we consider the following type of query: given two vertices s and t in G , what is the weight of a min st -cut in G ? We show how to answer such queries in constant time with O ( n log 4 n ) preprocessing time and O ( n log n ) space. We use a Gomory-Hu tree to represent all the pairwise min cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Since all-pairs min cut and the minimum-cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum-cycle basis in O ( n log 4 n ) time and O ( n log n ) space. Additionally, an explicit representation can be obtained in O ( C ) time and space where C is the size of the basis. These results require that shortest paths are unique. This can be guaranteed either by using randomization without overhead or deterministically with an additional log 2 n factor in the preprocessing times.

Users often need to test, debug or reuse spreadsheets. We present a new algorithm that can identify differences between two spreadsheets, providing a basis for future tools to help users compare two versions of a spreadsheet (thereby seeing what is new and needs testing) or two different spreadsheets (thereby seeing which is more appropriate for reuse in a situation). This algorithm, RowColAlign, is a two-dimensional generalization of the classic dynamic programming algorithm for solving the one-dimensional longest common subsequence problem. In addition, we present a new planted model for generating test cases to evaluate this algorithm and others like it, including the greedy SheetDiff algorithm presented in prior work. In our evaluation, our new RowColAlign algorithm made no errors at all on test cases, including test cases comparable to relatively large spreadsheets. Moreover, further analysis revealed that it is unexpected for our new algorithm to make errors except when spreadsheets contain an unrealistically small number of distinct values. These results are extremely encouraging, revealing our algorithm's potential as the basis for future spreadsheet tools.

We give an O(n log3n) algorithm that, given an n-node directed planar graph with arc capacities, a set of source nodes, and a set of sink nodes, finds a maximum flow from the sources to the sinks. Previously, the fastest algorithms known for this problem were those for general graphs.

For an undirected n-vertex planar graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We show how to answer such queries in constant time with O(n log5n) preprocessing time and O(n log n) space. We use a Gomory-Hu tree to represent all the pairwise min st-cuts implicitly. Previously, no subquadratic time algorithm was known for this problem. Our oracle can be extended to report the min st-cuts in time proportional to their size. Since all-pairs min si-cut and the minimum cycle basis are dual problems in planar graphs, we also obtain an implicit representation of a minimum cycle basis in O(n log5n) time and O(n log n) space and an explicit representation with additional O(C) time and space where G is the size of the basis. To obtain our results, we require that shortest paths be unique; this assumption can be removed deterministically with an additional O(log2n) running-time factor.

It was shown in [Indyk-Sidiropoulos 07] that any orientable graph of genus g can be probabilistically embedded into a graph of genus g-1 with constant distortion. Removing handles one by one gives an embedding into a distribution over planar graphs with distortion 2O(g). By removing all $g$ handles at once, we present a probabilistic embedding with distortion O(g2) for both orientable and non-orientable graphs. Our result is obtained by showing that the minimum-cut graph of [Erickson-HarPeled 04] has low dilation, and then randomly cutting this graph out of the surface using the Peeling Lemma from [Lee-Sidiropoulos 08].

We present the first polynomial-time approximation schemes (PTASes) for the following subset-connectivity problems in edge-weighted graphs of bounded genus: Steiner tree, low-connectivity survivable-network design, and subset TSP. The schemes run in $O(n \log n)$ time for graphs embedded on both orientable and non-orientable surfaces. This work generalizes the PTAS frameworks of Borradaile, Klein, and Mathieu (2007 and 2006) from planar graphs to bounded-genus graphs: any future problems shown to admit the required structure theorem for planar graphs will similarly extend to bounded-genus graphs.

We give the first correct O ( n log n ) algorithm for finding a maximum st -flow in a directed planar graph. After a preprocessing step that consists in finding single-source shortest-path distances in the dual, the algorithm consists of repeatedly saturating the leftmost residual s -to- t path.

We give a Polynomial-Time Approximation Scheme (PTAS) for the Steiner tree problem in planar graphs. The running time is O ( n log n ).

We give a randomized O(n2log n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed epsi > 0 and given any n pairs of terminals in the plane, our scheme finds a (1 + epsi)- approximation to the minimum-length forest that connects every pair of terminals.