More Like this

1. A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs

   https://doi.org/10.4230/LIPICS.ISAAC.2024.54  

   Paul-Pena, Daniel; Seshadhri, C (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mestre, Julián; Wirth, Anthony (Ed.)

   Counting the number of homomorphisms of a pattern graph H in a large input graph G is a fundamental problem in computer science. In many applications in databases, bioinformatics, and network science, we need more than just the total count. We wish to compute, for each vertex v of G, the number of H-homomorphisms that v participates in. This problem is referred to as homomorphism orbit counting, as it relates to the orbits of vertices of H under its automorphisms. Given the need for fast algorithms for this problem, we study when near-linear time algorithms are possible. A natural restriction is to assume that the input graph G has bounded degeneracy, a commonly observed property in modern massive networks. Can we characterize the patterns H for which homomorphism orbit counting can be done in near-linear time? We discover a dichotomy theorem that resolves this problem. For pattern H, let 𝓁 be the length of the longest induced path between any two vertices of the same orbit (under the automorphisms of H). If 𝓁 ≤ 5, then H-homomorphism orbit counting can be done in near-linear time for bounded degeneracy graphs. If 𝓁 > 5, then (assuming fine-grained complexity conjectures) there is no near-linear time algorithm for this problem. We build on existing work on dichotomy theorems for counting the total H-homomorphism count. Surprisingly, there exist (and we characterize) patterns H for which the total homomorphism count can be computed in near-linear time, but the corresponding orbit counting problem cannot be done in near-linear time. 

   more » « less
2. Pseudodeterminism: promises and lowerbounds

   https://doi.org/10.1145/3519935.3520043  

   Dixon, Peter; Pavan, A.; Woude, Jason Vander; Vinodchandran, N. V. (July 2022, Symposium on Theory of Computing (STOC))

   Stefano Leonardi and Anupam Gupta (Ed.)

   A probabilistic algorithm A is pseudodeterministic if, on every input, there exists a canonical value that is output with high probability. If the algorithm outputs one of k canonical values with high probability, then it is called a k-pseudodeterministic algorithm. In the study of pseudodeterminism, the Acceptance Probability Estimation Problem (APEP), which is to additively approximate the acceptance probability of a Boolean circuit, is emerging as a central computational problem. This problem admits a 2-pseudodeterministic algorithm. Recently, it was shown that a pseudodeterministic algorithm for this problem would imply that any multi-valued function that admits a k-pseudodeterministic algorithm for a constant k (including approximation algorithms) also admits a pseudodeterministic algorithm (Dixon, Pavan, Vinodchandran; ITCS 2021). The contribution of the present work is two-fold. First, as our main conceptual contribution, we establish that the existence of a pseudodeterministic algorithm for APEP is fundamentally related to the gap between probabilistic promise classes and the corresponding standard complexity classes. In particular, we show the following equivalence: APEP has a pseudodeterministic approximation algorithm if and only if every promise problem in PromiseBPP has a solution in BPP. A conceptual interpretation of this equivalence is that the algorithmic gap between 2-pseudodeterminism and pseudodeterminism is equivalent to the gap between PromiseBPP and BPP. Based on this connection, we show that designing pseudodeterministic algorithms for APEP leads to the solution of some open problems in complexity theory, including new Boolean circuit lower bounds. This equivalence also explains how multi-pseudodeterminism is connected to problems in SearchBPP. In particular, we show that if APEP has a pseudodeterministic algorithm, then every problem that admits a k(n)-pseudodeterministic algorithm (for any polynomial k) is in SearchBPP and admits a pseudodeterministic algorithm. Motivated by this connection, we also explore its connection to probabilistic search problems and establish that APEP is complete for certain notions of search problems in the context of pseudodeterminism. Our second contribution is establishing query complexity lower bounds for multi-pseudodeterministic computations. We prove that for every k ≥ 1, there exists a problem whose (k+1)-pseudodeterministic query complexity, in the uniform query model, is O(1) but has a k-pseudodeterministic query complexity of Ω(n), even in the more general nonadaptive query model. A key contribution of this part of the work is the utilization of Sperner’s lemma in establishing query complexity lower bounds. 

   more » « less
3. Largest acylindrical actions and Stability in hierarchically hyperbolic groups

   https://doi.org/10.1090/btran/50  

   Abbott, Carolyn; Behrstock, Jason; Durham, Matthew (February 2021, Transactions of the American Mathematical Society, Series B)

   We consider two manifestations of non-positive curvature: acylindrical actions (on hyperbolic spaces) and quasigeodesic stability. We study these properties for the class of hierarchically hyperbolic groups, which is a general framework for simultaneously studying many important families of groups, including mapping class groups, right-angled Coxeter groups, most 3 3 –manifold groups, right-angled Artin groups, and many others. A group that admits an acylindrical action on a hyperbolic space may admit many such actions on different hyperbolic spaces. It is natural to try to develop an understanding of all such actions and to search for a “best” one. The set of all cobounded acylindrical actions on hyperbolic spaces admits a natural poset structure, and in this paper we prove that all hierarchically hyperbolic groups admit a unique action which is the largest in this poset. The action we construct is also universal in the sense that every element which acts loxodromically in some acylindrical action on a hyperbolic space does so in this one. Special cases of this result are themselves new and interesting. For instance, this is the first proof that right-angled Coxeter groups admit universal acylindrical actions. The notion of quasigeodesic stability of subgroups provides a natural analogue of quasiconvexity which can be considered outside the context of hyperbolic groups. In this paper, we provide a complete classification of stable subgroups of hierarchically hyperbolic groups, generalizing and extending results that are known in the context of mapping class groups and right-angled Artin groups. Along the way, we provide a characterization of contracting quasigeodesics; interestingly, in this generality the proof is much simpler than in the special cases where it was already known. In the appendix, it is verified that any space satisfying the a priori weaker property of being an “almost hierarchically hyperbolic space” is actually a hierarchically hyperbolic space. The results of the appendix are used to streamline the proofs in the main text. 

   more » « less
4. Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles

   Suman K. Bera, Noujan Pashanasangi (January 2021, Symposium on Discrete Algorithms (SODA))

   null (Ed.)

   Counting homomorphisms of a constant sized pattern graph H in an input graph G is a fundamental computational problem. There is a rich history of studying the complexity of this problem, under various constraints on the input G and the pattern H. Given the significance of this problem and the large sizes of modern inputs, we investigate when near-linear time algorithms are possible. We focus on the case when the input graph has bounded degeneracy, a commonly studied and practically relevant class for homomorphism counting. It is known from previous work that for certain classes of H, H-homomorphisms can be counted exactly in near-linear time in bounded degeneracy graphs. Can we precisely characterize the patterns H for which near-linear time algorithms are possible? We completely resolve this problem, discovering a clean dichotomy using fine-grained complexity. Let m denote the number of edges in G. We prove the following: if the largest induced cycle in H has length at most 5, then there is an O(mlogm) algorithm for counting H-homomorphisms in bounded degeneracy graphs. If the largest induced cycle in H has length at least 6, then (assuming standard fine-grained complexity conjectures) there is a constant γ>0, such that there is no o(m1+γ) time algorithm for counting H-homomorphisms. 

   more » « less
5. Near-Linear Time Homomorphism Counting in Bounded Degeneracy Graphs: The Barrier of Long Induced Cycles

   https://doi.org/10.1137/1.9781611976465.138  

   Bera, Suman K.; Pashanasangi, Noujan; Seshadhri, C. (January 2021, Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms)

   null (Ed.)

   Counting homomorphisms of a constant sized pattern graph H in an input graph G is a fundamental computational problem. There is a rich history of studying the complexity of this problem, under various constraints on the input G and the pattern H. Given the significance of this problem and the large sizes of modern inputs, we investigate when near-linear time algorithms are possible. We focus on the case when the input graph has bounded degeneracy, a commonly studied and practically relevant class for homomorphism counting. It is known from previous work that for certain classes of H, H-homomorphisms can be counted exactly in near-linear time in bounded degeneracy graphs. Can we precisely characterize the patterns H for which near-linear time algorithms are possible? We completely resolve this problem, discovering a clean dichotomy using fine-grained complexity. Let m denote the number of edges in G. We prove the following: if the largest induced cycle in H has length at most 5, then there is an O(m log m) algorithm for counting H-homomorphisms in bounded degeneracy graphs. If the largest induced cycle in H has length at least 6, then (assuming standard fine-grained complexity conjectures) there is a constant γ > 0, such that there is no o(m1+γ) time algorithm for counting H-homomorphisms. 

   more » « less