Compressed Decision Problems in Hyperbolic Groups.
From MaRDI portal
Publication:5090484
Recommendations
- On the power of unambiguity in log-space
- Directed planar reachability is in unambiguous log-space
- Polynomial min/max-weighted reachability is in unambiguous log-space
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- Min/max-poly weighting schemes and the NL versus UL problem
Cites work
- scientific article; zbMATH DE number 1346519 (Why is no real title available?)
- A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract)
- A very hard log-space counting class
- Bipartite perfect matching is in quasi-NC
- Boolean complexity classes vs. their arithmetic analogs
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Counting quantifiers, successor relations, and logarithmic space
- Derandomizing isolation in space-bounded settings
- Derandomizing isolation lemma for \(K_{3,3}\)-free and \(K_5\)-free bipartite graphs
- Deterministic identity testing for sum of read-once oblivious arithmetic branching programs
- Deterministically isolating a perfect matching in bipartite planar graphs
- Directed planar reachability is in unambiguous log-space
- Finding shortest non-separating and non-contractible cycles for topologically embedded graphs
- Green's theorem and isolation in planar graphs
- Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
- Identity testing for constant-width, and commutative, read-once oblivious ABPs
- Isolation, matching, and counting uniform and nonuniform upper bounds
- Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
- Making Nondeterminism Unambiguous
- On the power of unambiguity in log-space
- On the theory of Pfaffian orientations. II: \(T\)-joins, \(k\)-cuts, and duality of enumeration
- Planar and grid graph reachability problems
- Reachability in K 3,3-Free Graphs and K 5-Free Graphs Is in Unambiguous Log-Space
- Space complexity of perfect matching in bounded genus bipartite graphs
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- The graph genus problem is NP-complete
- Trading determinism for time in space bounded computations
- Undirected connectivity in log-space
Cited in
(5)- scientific article; zbMATH DE number 4001498 (Why is no real title available?)
- Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
- Space-efficient algorithms for reachability in directed geometric graphs
- scientific article; zbMATH DE number 7561603 (Why is no real title available?)
- 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)
