On the public citation graph
Isolation, Matching, and Counting Uniform and Nonuniform Upper Bounds
0 signed · 107 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/jcss.2000.1730openalex-snapshot
Pseudorandom Generators without the XOR Lemma
inferredcites →https://doi.org/10.1007/3-540-54458-5_61openalex-snapshot
Unambiguity and fewness for logarithmic space
inferredcites →https://doi.org/10.1007/bf00299636openalex-snapshot
The method of forced enumeration for nondeterministic automata
inferredcites →https://doi.org/10.1007/bf01374526openalex-snapshot
Structure and importance of logspace-MOD class
inferredcites →https://doi.org/10.1007/bf02090768openalex-snapshot
On the power of parity polynomial time
inferredcites →https://doi.org/10.1007/bf02579206openalex-snapshot
Matching is as easy as matrix inversion
inferredcites →https://doi.org/10.1007/bf02579407openalex-snapshot
Constructing a perfect matching is in random NC
inferredcites →https://doi.org/10.1007/pl00001596openalex-snapshot
Verifying the determinant in parallel
inferredcites →https://doi.org/10.1007/s000370050023openalex-snapshot
The complexity of matrix rank and feasible systems of linear equations
inferredcites →https://doi.org/10.1007/s004930050058openalex-snapshot
Superpolynomial Lower Bounds for Monotone Span Programs
inferredcites →https://doi.org/10.1016/0016-0032(58)90688-4openalex-snapshot
An introduction to probability theory and its applications
inferredcites →https://doi.org/10.1016/0022-0000(84)90066-7openalex-snapshot
Space-bounded hierarchies and probabilistic computations
inferredcites →https://doi.org/10.1016/0022-0000(91)90020-6openalex-snapshot
Properties that characterize LOGCFL
inferredcites →https://doi.org/10.1016/0022-0000(92)90022-bopenalex-snapshot
Turing machines with few accepting computations and low sets for PP
inferredcites →https://doi.org/10.1016/0304-3975(93)90252-oopenalex-snapshot
A very hard log-space counting class
inferredcites →https://doi.org/10.1016/s0019-9958(83)80060-6openalex-snapshot
Parallel computation for well-endowed rings and space-bounded probabilistic machines
inferredcites →https://doi.org/10.1016/s0022-0000(05)80024-8openalex-snapshot
Gap-definable counting classes
inferredcites →https://doi.org/10.1051/ita/1996300100011openalex-snapshot
Relationships among $PL$, $\#L$, and the determinant
inferredcites →https://doi.org/10.1109/ccc.1999.766253openalex-snapshot
Pseudorandom generators without the XOR lemma
inferredcites →https://doi.org/10.1109/sfcs.1982.39openalex-snapshot
Storing a sparse table with O(1) worst case access time
inferredcites →https://doi.org/10.1109/sfcs.1982.80openalex-snapshot
On the program size of perfect and universal hash functions
inferredcites →https://doi.org/10.1109/sfcs.1997.646113openalex-snapshot
Making nondeterminism unambiguous
inferredcites →https://doi.org/10.1137/0206049openalex-snapshot
Computational Complexity of Probabilistic Turing Machines
inferredcites →https://doi.org/10.1137/0215070openalex-snapshot
Log Depth Circuits for Division and Related Problems
inferredcites →https://doi.org/10.1137/0217015openalex-snapshot
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
inferredcites →https://doi.org/10.1137/0217058openalex-snapshot
Nondeterministic Space is Closed under Complementation
inferredcites →https://doi.org/10.1137/s0097539700389652openalex-snapshot
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
inferredcites →https://doi.org/10.1137/s0097539798339041openalex-snapshot
Making Nondeterminism Unambiguous
inferredcites →https://doi.org/10.1145/237814.237856openalex-snapshot
The complexity of matrix rank and feasible systems of linear equations (extended abstract)
inferredcites →https://doi.org/10.1145/258533.258590openalex-snapshot
P = BPP if E requires exponential circuits
inferredcites →https://doi.org/10.1145/28395.383347openalex-snapshot
Matching is as easy as matrix inversion
inferredcites →https://doi.org/10.2307/2980979openalex-snapshot
An Introduction to Probability Theory and its Applications.
inferredcites →https://doi.org/10.6028/jres.069b.013openalex-snapshot
Maximum matching and a polyhedron with 0,1-vertices
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.2139/ssrn.4112141openalex-extracted
A Combinatorial Property of ♯L Assuming Nl = Ul and its Implications for Modl
inferred← citeshttps://doi.org/10.1006/inco.2001.3056openalex-snapshot
Sparse Sets and Collapse of Complexity Classes
inferred← citeshttps://doi.org/10.1007/11590156_19openalex-snapshot
The Directed Planar Reachability Problem
inferred← citeshttps://doi.org/10.1007/11786986_40openalex-snapshot
On the Bipartite Unique Perfect Matching Problem
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_50openalex-snapshot
The Complexity of Membership Problems for Circuits over Sets of Natural Numbers
inferred← citeshttps://doi.org/10.1007/978-3-032-27732-9_14openalex-snapshot
Reachability in Graphs with Polynomially Many Surface Non-separating Cycles is in UL
inferred← citeshttps://doi.org/10.1007/978-3-319-05446-9_3openalex-snapshot
Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs
inferred← citeshttps://doi.org/10.1007/978-3-540-31856-9_39openalex-snapshot
The Complexity of Solving Linear Equations over a Finite Ring
inferred← citeshttps://doi.org/10.1007/978-3-540-70918-3_42openalex-snapshot
The Polynomially Bounded Perfect Matching Problem Is in NC 2
inferred← citeshttps://doi.org/10.1007/978-3-540-73001-9_3openalex-snapshot
Reachability Problems: An Update
inferred← citeshttps://doi.org/10.1007/978-3-540-74510-5_14openalex-snapshot
Planarity, Determinants, Permanents, and (Unique) Matchings
inferred← citeshttps://doi.org/10.1007/978-3-540-85363-3_23openalex-snapshot
Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size
inferred← citeshttps://doi.org/10.1007/978-3-540-95891-8_42openalex-snapshot
The Simple Reachability Problem in Switch Graphs
inferred← citeshttps://doi.org/10.1007/978-3-662-43948-7_30openalex-snapshot
Dynamic Complexity of Directed Reachability and Other Problems
inferred← citeshttps://doi.org/10.1007/978-3-662-47666-6_13openalex-snapshot
Reachability is in DynFO
inferred← citeshttps://doi.org/10.1007/s00037-009-0280-6openalex-snapshot
Classifying Problems on Linear Congruences and Abelian Permutation Groups Using Logspace Counting Classes
inferred← citeshttps://doi.org/10.1007/s00037-012-0047-3openalex-snapshot
On the power of unambiguity in log-space
inferred← citeshttps://doi.org/10.1007/s00224-009-9172-zopenalex-snapshot
Planar and Grid Graph Reachability Problems
inferred← citeshttps://doi.org/10.1007/s00224-009-9204-8openalex-snapshot
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
inferred← citeshttps://doi.org/10.1007/s00236-022-00425-1openalex-snapshot
Depth-first search in directed planar graphs, revisited
inferred← citeshttps://doi.org/10.1016/j.dam.2003.12.001openalex-snapshot
The combinatorial approach yields an NC algorithm for computing Pfaffians
inferred← citeshttps://doi.org/10.1016/j.ic.2012.03.002openalex-snapshot
Greenʼs theorem and isolation in planar graphs
inferred← citeshttps://doi.org/10.1016/j.jcss.2011.11.002openalex-snapshot
Space complexity of perfect matching in bounded genus bipartite graphs
inferred← citeshttps://doi.org/10.1016/j.procs.2025.10.277openalex-snapshot
Trading Determinism for Time: The k-Reach Problem
inferred← citeshttps://doi.org/10.1016/j.tcs.2006.01.005openalex-snapshot
NL-printable sets and nondeterministic Kolmogorov complexity
inferred← citeshttps://doi.org/10.1016/s0022-0000(02)00025-9openalex-snapshot
Uniform constant-depth threshold circuits for division and iterated multiplication
inferred← citeshttps://doi.org/10.1016/s1571-0661(04)80838-7openalex-snapshot
NL-printable sets and Nondeterministic Kolmogorov Complexity
inferred← citeshttps://doi.org/10.1109/ccc.2004.1openalex-snapshot
Abelian permutation group problems and logspace counting classes
inferred← citeshttps://doi.org/10.1109/ccc.2004.1313844openalex-snapshot
Abelian permutation group problems and logspace counting classes
inferred← citeshttps://doi.org/10.1109/ccc.2005.28openalex-snapshot
The Complexity of the Inertia and Some Closure Properties of GapL
inferred← citeshttps://doi.org/10.1109/ccc.2005.7openalex-snapshot
Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy
inferred← citeshttps://doi.org/10.1109/ccc.2007.9openalex-snapshot
Directed Planar Reachability is in Unambiguous Log-Space
inferred← citeshttps://doi.org/10.1109/ccc.2010.21openalex-snapshot
On the Matching Problem for Special Graph Classes
inferred← citeshttps://doi.org/10.1109/ccc.2010.24openalex-snapshot
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00095openalex-snapshot
Distinguishing, Predicting, and Certifying: On the Long Reach of Partial Notions of Pseudorandomness
inferred← citeshttps://doi.org/10.1109/sfcs.2000.892080openalex-snapshot
On the hardness of graph isomorphism
inferred← citeshttps://doi.org/10.1137/17m1130538openalex-snapshot
Derandomizing Isolation in Space-Bounded Settings
inferred← citeshttps://doi.org/10.1137/s0097539700389652openalex-snapshot
Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
inferred← citeshttps://doi.org/10.1137/s009753970241096xopenalex-snapshot
On the Hardness of Graph Isomorphism
inferred← citeshttps://doi.org/10.1137/s0097539798339041openalex-snapshot
Making Nondeterminism Unambiguous
inferred← citeshttps://doi.org/10.1145/1490270.1490274openalex-snapshot
Directed Planar Reachability Is in Unambiguous Log-Space
inferred← citeshttps://doi.org/10.1145/1714450.1714453openalex-snapshot
Planarity, Determinants, Permanents, and (Unique) Matchings
inferred← citeshttps://doi.org/10.1145/2003685.2003687openalex-snapshot
On the Power of Isolation in Planar Graphs
inferred← citeshttps://doi.org/10.1145/3708508openalex-snapshot
Robustness for Space-Bounded Statistical Zero Knowledge
inferred← citeshttps://doi.org/10.1145/3717823.3718303openalex-snapshot
When Connectivity Is Hard, Random Walks Are Easy with Non-determinism
inferred← citeshttps://doi.org/10.1145/3774644openalex-snapshot
Unambiguous, Randomized, and Symmetric Catalytic Computation
inferred← citeshttps://doi.org/10.22331/q-2023-08-09-1079openalex-snapshot
Code-routing: a new attack on position verification
inferred← citeshttps://doi.org/10.3233/fi-2012-621openalex-snapshot
Unambiguous Functions in Logarithmic Space
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2009.2304openalex-snapshot
Arithmetic Circuits and the Hadamard Product of Polynomials
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2021.16openalex-snapshot
Reachability and Matching in Single Crossing Minor Free Graphs
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2016.10openalex-snapshot
Trading Determinism for Time in Space Bounded Computations
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2008.1346openalex-snapshot
Deterministically Isolating a Perfect Matching in Bipartite Planar Graphs
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2012.254openalex-snapshot
Improved Bounds for Bipartite Matching on Surfaces
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2016.10openalex-snapshot
Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.0802.1699openalex-snapshot
Longest paths in Planar DAGs in Unambiguous Logspace
inferred← citeshttps://doi.org/10.48550/arxiv.1411.7614openalex-snapshot
Derandomizing Isolation Lemma for $K_{3,3}$-free and $K_5$-free Bipartite Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1502.02135openalex-snapshot
Simultaneous Time-Space Upper Bounds for Certain Problems in Planar Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1711.00565openalex-snapshot
Typically-Correct Derandomization for Small Time and Space
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.