Compressed Decision Problems in Hyperbolic Groups.
From MaRDI portal
Publication:5090484
DOI10.4230/LIPIcs.STACS.2019.34OpenAlexW2962736578MaRDI QIDQ5090484
Chetan Gupta, Raghunath Tewari, Vimal Raj Sharma
Publication date: 18 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.STACS.2019.37
Related Items (3)
Space-efficient algorithms for reachability in directed geometric graphs ⋮ Unnamed Item ⋮ Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space complexity of perfect matching in bounded genus bipartite graphs
- Green's theorem and isolation in planar graphs
- Planar and grid graph reachability problems
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- A very hard log-space counting class
- On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
- Counting quantifiers, successor relations, and logarithmic space
- On the power of unambiguity in log-space
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Directed Planar Reachability Is in Unambiguous Log-Space
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
- The graph genus problem is NP-complete
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- Undirected connectivity in log-space
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs
- Boolean complexity classes vs. their arithmetic analogs
- Making Nondeterminism Unambiguous
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Bipartite perfect matching is in quasi-NC
This page was built for publication: Compressed Decision Problems in Hyperbolic Groups.
