Compressed Decision Problems in Hyperbolic Groups.
From MaRDI portal
Publication:5090484
DOI10.4230/LIPICS.STACS.2019.34OpenAlexW2962736578MaRDI QIDQ5090484FDOQ5090484
Authors: Chetan Gupta, Vimal Raj Sharma, Raghunath Tewari 
Publication date: 18 July 2022
Full work available at URL: https://doi.org/10.4230/LIPIcs.STACS.2019.37
Cites Work
- Undirected connectivity in log-space
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- The graph genus problem is NP-complete
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Boolean complexity classes vs. their arithmetic analogs
- Making Nondeterminism Unambiguous
- A very hard log-space counting class
- Counting quantifiers, successor relations, and logarithmic space
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- Planar and grid graph reachability problems
- Title not available (Why is that?)
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- 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
- Space complexity of perfect matching in bounded genus bipartite graphs
- Green's theorem and isolation in planar graphs
- On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- On the power of unambiguity in log-space
- Identity testing for constant-width, and commutative, read-once oblivious ABPs
- Trading determinism for time in space bounded computations
- Bipartite perfect matching is in quasi-NC
- Derandomizing isolation lemma for \(K_{3,3}\)-free and \(K_5\)-free bipartite graphs
- Deterministically isolating a perfect matching in bipartite planar graphs
- Derandomizing isolation in space-bounded settings
Cited In (5)
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Title not available (Why is that?)
- Space-efficient algorithms for reachability in directed geometric graphs
- Title not available (Why is that?)
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
This page was built for publication: Compressed Decision Problems in Hyperbolic Groups.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090484)
