Derandomizing Isolation in Space-Bounded Settings (Q5232318): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
+Normal rank
@@ Property / cites work @@
+Depth reduction for circuits of unbounded fan-in
@@ Property / cites work: Depth reduction for circuits of unbounded fan-in / rank @@
+Normal rank
@@ Property / cites work @@
+Isolation, matching, and counting uniform and nonuniform upper bounds
+Normal rank
@@ Property / cites work @@
+Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs
+Normal rank
@@ Property / cites work @@
+Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
+Normal rank
@@ Property / cites work @@
+New results on noncommutative and commutative polynomial identity testing
+Normal rank
@@ Property / cites work @@
+A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity
+Normal rank
@@ Property / cites work @@
+On the theory of average case complexity
@@ Property / cites work: On the theory of average case complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Determinant Sums for Undirected Hamiltonicity
@@ Property / cites work: Determinant Sums for Undirected Hamiltonicity / rank @@
+Normal rank
@@ Property / cites work @@
+Shortest Two Disjoint Paths in Polynomial Time
@@ Property / cites work: Shortest Two Disjoint Paths in Polynomial Time / rank @@
+Normal rank
@@ Property / cites work @@
+Directed Planar Reachability Is in Unambiguous Log-Space
+Normal rank
@@ Property / cites work @@
+Smoothed Analysis of Belief Propagation for Minimum-Cost Flow and Matching
+Normal rank
@@ Property / cites work @@
+Time-space tradeoff in derandomizing probabilistic logspace
+Normal rank
@@ Property / cites work @@
+The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
+Normal rank
@@ Property / cites work @@
+Universal classes of hash functions
@@ Property / cites work: Universal classes of hash functions / rank @@
+Normal rank
@@ Property / cites work @@
+Randomness-Optimal Unique Element Isolation with Applications to Perfect Matching and Related Problems
+Normal rank
@@ Property / cites work @@
+Fast Hamiltonicity Checking Via Bases of Perfect Matchings
+Normal rank
@@ Property / cites work @@
+Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
+Normal rank
@@ Property / cites work @@
+Q3549731
@@ Property / cites work: Q3549731 / rank @@
+Normal rank
@@ Property / cites work @@
+Dynamic Complexity of Directed Reachability and Other Problems
+Normal rank
@@ Property / cites work @@
+Reachability is in DynFO
@@ Property / cites work: Reachability is in DynFO / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministically isolating a perfect matching in bipartite planar graphs
+Normal rank
@@ Property / cites work @@
+Space complexity of perfect matching in bounded genus bipartite graphs
+Normal rank
@@ Property / cites work @@
+Is Valiant-Vazirani's isolation probability improvable?
+Normal rank
@@ Property / cites work @@
+Computing the shortest essential cycle
@@ Property / cites work: Computing the shortest essential cycle / rank @@
+Normal rank
@@ Property / cites work @@
+Bipartite perfect matching is in quasi-NC
@@ Property / cites work: Bipartite perfect matching is in quasi-NC / rank @@
+Normal rank
@@ Property / cites work @@
+Boolean complexity classes vs. their arithmetic analogs
+Normal rank
@@ Property / cites work @@
+Belief Propagation for Min-Cost Network Flow: Convergence and Correctness
+Normal rank
@@ Property / cites work @@
+On the Lattice Isomorphism Problem
@@ Property / cites work: On the Lattice Isomorphism Problem / rank @@
+Normal rank
@@ Property / cites work @@
+Shortest \((A+B)\)-path packing via hafnian
@@ Property / cites work: Shortest \((A+B)\)-path packing via hafnian / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic Space is Closed under Complementation
+Normal rank
@@ Property / cites work @@
+Q4608568
@@ Property / cites work: Q4608568 / rank @@
+Normal rank
@@ Property / cites work @@
+A circuit-based proof of Toda's theorem
@@ Property / cites work: A circuit-based proof of Toda's theorem / rank @@
+Normal rank
@@ Property / cites work @@
+Q5365136
@@ Property / cites work: Q5365136 / rank @@
+Normal rank
@@ Property / cites work @@
+Constructing a perfect matching is in random NC
@@ Property / cites work: Constructing a perfect matching is in random NC / rank @@
+Normal rank
@@ Property / cites work @@
+On the Complexity of Equivalence and Minimisation for Q-weighted Automata
+Normal rank
@@ Property / cites work @@
+Randomness efficient identity testing of multivariate polynomials
+Normal rank
@@ Property / cites work @@
+Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
+Normal rank
@@ Property / cites work @@
+On self-reducibility and weak P-selectivity
@@ Property / cites work: On self-reducibility and weak P-selectivity / rank @@
+Normal rank
@@ Property / cites work @@
+Logspace Reduction of Directed Reachability for Bounded Genus Graphs to the Planar Case
+Normal rank
@@ Property / cites work @@
+Subtree isomorphism is NC reducible to bipartite perfect matching
+Normal rank
@@ Property / cites work @@
+A fast parallel algorithm for minimum-cost small integral flows
+Normal rank
@@ Property / cites work @@
+Matching is as easy as matrix inversion
@@ Property / cites work: Matching is as easy as matrix inversion / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators for space-bounded computation
+Normal rank
@@ Property / cites work @@
+Parallel algorithms for the assignment and minimum-cost flow problems
+Normal rank
@@ Property / cites work @@
+Making Nondeterminism Unambiguous
@@ Property / cites work: Making Nondeterminism Unambiguous / rank @@
+Normal rank
@@ Property / cites work @@
+\(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
+Normal rank
@@ Property / cites work @@
+Relationships between nondeterministic and deterministic tape complexities
+Normal rank
@@ Property / cites work @@
+On enumerating monomials and other combinatorial structures by polynomial interpolation
+Normal rank
@@ Property / cites work @@
+On the Tape Complexity of Deterministic Context-Free Languages
+Normal rank
@@ Property / cites work @@
+The method of forced enumeration for nondeterministic automata
+Normal rank
@@ Property / cites work @@
+Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Q3191145
@@ Property / cites work: Q3191145 / rank @@
+Normal rank
@@ Property / cites work @@
+PP is as Hard as the Polynomial-Time Hierarchy
@@ Property / cites work: PP is as Hard as the Polynomial-Time Hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+The Time Complexity of Constraint Satisfaction
@@ Property / cites work: The Time Complexity of Constraint Satisfaction / rank @@
+Normal rank
@@ Property / cites work @@
+NP is as easy as detecting unique solutions
@@ Property / cites work: NP is as easy as detecting unique solutions / rank @@
+Normal rank
@@ Property / cites work @@
+Q5111135
@@ Property / cites work: Q5111135 / rank @@
+Normal rank
@@ Property / cites work @@
+Properties that characterize LOGCFL
@@ Property / cites work: Properties that characterize LOGCFL / rank @@
+Normal rank
@@ Property / cites work @@
+Structural analysis of the complexity of inverse functions
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/17m1130538
+Normal rank
@@ Property / OpenAlex ID @@
+W2944729076
@@ Property / OpenAlex ID: W2944729076 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q127903949
@@ Property / Wikidata QID: Q127903949 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:5232318