We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schulman (FOCS'96, SICOMP'00) gave a surprising randomized algorithm to verify associativity of an operation odot: S x S -> S in optimal time O(|S|^2), they left open the problem of finding any subcubic algorithm for verifying distributivity of given operations odot, oplus: S x S -> S.

Regular expression search is a key primitive in myriads of applications, from web scrapping to bioinformatics. A regular expression is a formalism for compactly describing a set of strings, built recursively from single characters using three operators: concatenation, union, and Kleene star. Two basic algorithmic problems concerning such expressions are membership and pattern matching. In the regular expression membership problem, we are given a regular expression R and a string T of length n, and must decide whether T matches R. In the regular expression pattern matching problem, the task to find the substrings of T that match R. By now we have a good understanding of the complexity of regular expression membership and pattern matching in the classical setting. However, only some special cases have been considered in the practically relevant streaming setting: dictionary matching and wildcard pattern matching. In the dictionary matching problem, we are given a dictionary of d strings of length at most m and a string T, and must find substrings of T that match one of the dictionary strings. In the wildcard pattern matching problem, we are given a string P of length m that contains d wildcards, where a wildcard is a special symbol that matches any character of the alphabet, and a string T, and must find all substrings of T that match P. Both problems can be solved in the streaming model by a randomised Monte Carlo algorithm that uses (d log m) space [Golan and Porat (ESA 2017), Golan, Kopelowitz and Porat (Algorithmica 2019)]. In the general case, we cannot hope for a streaming algorithm with space complexity smaller than the length of R for either variant of regular expression search. The main contribution of this paper is that we identify the number of unions and Kleene stars, denoted by d, as the parameter that allows for an efficient streaming algorithm. This parameter has been previously considered in the classical setting, and it has been observed that in practice it is significantly smaller than the length of R. We design general randomised Monte Carlo algorithms for both problems that use (d3 polylog n) space in the streaming setting. A crucial technical ingredient of our algorithms is an adaptation of the general framework for evaluating a circuit with addition and convolution gates in a space-efficient manner [Lokshtanov and Nederlof (STOC 2010), Bringmann (SODA 2017)], initially designed as a key component of a pseudopolynomial time algorithm for the subset sum problem. We show how to replace the Extended Generalised Riemann Hypothesis in [Bringmann (SODA 2017)] by an application of the Bombieri–Vinogradov theorem to achieve the same bounds (but unconditionally), which might be of independent interest.

Permutation $σ$ appears in permutation $π$ if there exists a subsequence of $π$ that is order-isomorphic to $σ$. The natural question is to check if $σ$ appears in $π$, and if so count the number of occurrences. We know that for any fixed length~k, we can check if a given pattern of length k appears in a permutation of length n in time linear in n, but being able to count all such occurrences in $f(k)\cdot n^{o(k/\log k)}$ time would refute the exponential time hypothesis (ETH). This motivates a systematic study of the complexity of counting occurrences for different patterns of fixed small length k. We investigate this question for k=4. Very recently, Even-Zohar and Leng [arXiv 2019] identified two types of 4-patterns. For the first type they designed an $Õ(n)$ time algorithm, while for the second they were able to provide an $Õ(n^{1.5})$ time algorithm. This brings up the question whether the permutations of the second type are inherently harder than the first type. We establish a connection between counting 4-patterns of the second type and counting 4-cycles in a sparse undirected graph. By designing two-way reductions we show that the complexities of both problems are the same, up to polylogarithmic factors. This allows us to provide a reasonable argument for why there is a difference in the complexities for counting 4-patterns of the two types. In particular, even for the simpler problem of detecting a 4-cycle in a graph on m edges, the best known algorithm works in $O(m^{4/3})$ time. Our reductions imply that an $O(n^{4/3-\varepsilon})$ time algorithm for counting occurrences would imply an exciting breakthrough for counting (and hence also detecting) 4-cycles. In the other direction, by plugging in the fastest known algorithm for counting 4-cycles, we obtain an algorithm for counting occurrences of any 4-pattern in $O(n^{1.48})$ time.

In the problem of Generalised Pattern Matching (GPM) [STOC'94, Muthukrishnan and Palem], we are given a text T of length n over an alphabet Σ_T, a pattern P of length m over an alphabet Σ_P, and a matching relationship ⊆ Σ_T × Σ_P, and must return all substrings of T that match P (reporting) or the number of mismatches between each substring of T of length m and P (counting). In this work, we improve over all previously known algorithms for this problem: - For ? being the maximum number of characters that match a fixed character, we show two new Monte Carlo algorithms, a reporting algorithm with time ?(? n log n log m) and a (1-ε)-approximation counting algorithm with time ?(ε^-1 ? n log n log m). We then derive a (1-ε)-approximation deterministic counting algorithm for GPM with ?(ε^-2 ? n log⁶ n) time. - For ? being the number of pairs of matching characters, we demonstrate Monte Carlo algorithms for reporting and (1-ε)-approximate counting with running time ?(√? n log m √{log n}) and ?(√{ε^-1 ?} n log m √{log n}), respectively, as well as a (1-ε)-approximation deterministic algorithm for the counting variant of GPM with ?(ε^-1 √{?} n log^{7/2} n) time. - Finally, for ℐ being the total number of disjoint intervals of characters that match the m characters of the pattern P, we show that both the reporting and the counting variants of GPM can be solved exactly and deterministically in ?(n√{ℐ log m} +n log n) time. At the heart of our new deterministic upper bounds for ? and ? lies a faster construction of superimposed codes, which solves an open problem posed in [FOCS'97, Indyk] and can be of independent interest. To conclude, we demonstrate first lower bounds for GPM. We start by showing that any deterministic or Monte Carlo algorithm for GPM must use Ω(?) time, and then proceed to show higher lower bounds for combinatorial algorithms. These bounds show that our algorithms are almost optimal, unless a radically new approach is developed.

The popular 3-SUM conjecture states that there is no strongly subquadratic time algorithm for checking if a given set of integers contains three distinct elements that sum up to zero. A closely related problem is to check if a given set of integers contains distinct x 1, x 2, x 3 such that x 1+x 2=2x 3. This can be reduced to 3-SUM in almost-linear time, but surprisingly a reverse reduction establishing 3-SUM hardness was not known.

The quartet distance is a measure of similarity used to compare two unrooted phylogenetic trees on the same set of n leaves, defined as the number of subsets of four leaves related by a different topology in both trees. After a series of previous results, Brodal et al. [SODA 2013] presented an algorithm that computes this number in O(ndlogn) time, where d is the maximum degree of a node. For the related triplet distance between rooted phylogenetic trees, the same authors were able to design an O(nlogn) time algorithm, that is, with running time independent of d. This raises the question of achieving such complexity for computing the quartet distance, or at least improving the dependency on d.

We consider the top tree compression scheme introduced by Bille et al. [ICALP 2013] and construct an infinite family of trees on n nodes labeled from an alphabet of size sigma, for which the size of the top DAG is Theta(n/log_sigma n log log_sigma n). Our construction matches a previously known upper bound and exhibits a weakness of this scheme, as the information-theoretic lower bound is Omega(n/log_sigma n}). This settles an open problem stated by Lohrey et al. [arXiv 2017], who designed a more involved version achieving the lower bound. We show that this can be also guaranteed by a very minor modification of the original scheme: informally, one only needs to ensure that different parts of the tree are not compressed too quickly. Arguably, our version is more uniform, and in particular, the compression procedure is oblivious to the value of sigma.

Edit distance between trees is a natural generalization of the classical edit distance between strings, in which the allowed elementary operations are contraction, uncontraction and relabeling of an edge. Demaine et al. [ACM Trans. on Algorithms, 6(1), 2009] showed how to compute the edit distance between rooted trees on $n$ nodes in $\mathcal{O}(n^{3})$ time. However, generalizing their method to unrooted trees seems quite problematic, and the most efficient known solution remains to be the previous $\mathcal{O}(n^{3}\log n)$ time algorithm by Klein [ESA 1998]. Given the lack of progress on improving this complexity, it might appear that unrooted trees are simply more difficult than rooted trees. We show that this is, in fact, not the case, and edit distance between unrooted trees on $n$ nodes can be computed in $\mathcal{O}(n^{3})$ time. A significantly faster solution is unlikely to exist, as Bringmann et al. [SODA 2018] proved that the complexity of computing the edit distance between rooted trees cannot be decreased to $\mathcal{O}(n^{3-ε})$ unless some popular conjecture fails, and the lower bound easily extends to unrooted trees. We also show that for two unrooted trees of size $m$ and $n$, where $m\le n$, our algorithm can be modified to run in $\mathcal{O}(nm^2(1+\log\frac nm))$. This, again, matches the complexity achieved by Demaine et al. for rooted trees, who also showed that this is optimal if we restrict ourselves to the so-called decomposition algorithms.

We consider a population of n agents which communicate with each other in a decentralized manner, through random pairwise interactions. One or more agents in the population may act as authoritative sources of information, and the objective of the remaining agents is to obtain information from or about these source agents. We study two basic tasks: broadcasting, in which the agents are to learn the bit-state of an authoritative source which is present in the population, and source detection, in which the agents are required to decide if at least one source agent is present in the population or not.

In the Maximum Duo-Preservation String Mapping problem we are given two strings and wish to map the letters of the former to the letters of the latter as to maximise the number of duos. A duo is a pair of consecutive letters that is mapped to a pair of consecutive letters in the same order. This is complementary to the well-studied Minimum Common String Partition problem, where the goal is to partition the former string into blocks that can be permuted and concatenated to obtain the latter string. Maximum Duo-Preservation String Mapping is APX-hard. After a series of improvements, Brubach [WABI 2016] showed a polynomial-time 3.25-approximation algorithm. Our main contribution is that, for any eps>0, there exists a polynomial-time (2+eps)-approximation algorithm. Similarly to a previous solution by Boria et al. [CPM 2016], our algorithm uses the local search technique. However, this is used only after a certain preliminary greedy procedure, which gives us more structure and makes a more general local search possible. We complement this with a specialised version of the algorithm that achieves 2.67-approximation in quadratic time.