On the public citation graph

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs

0 signed · 84 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/rsa.10013.absopenalex-snapshot
Testing the diameter of graphs
inferredcites →https://doi.org/10.1002/rsa.10023openalex-snapshot
Testing properties of directed graphs: acyclicity and connectivity
inferredcites →https://doi.org/10.1007/978-1-4615-0005-6_5openalex-snapshot
Property Testing in Massive Graphs
inferredcites →https://doi.org/10.1007/978-3-642-22670-0_9openalex-snapshot
On Testing Expansion in Bounded-Degree Graphs
inferredcites →https://doi.org/10.1007/s00453-001-0078-7openalex-snapshot
Property Testing in Bounded Degree Graphs
inferredcites →https://doi.org/10.1007/s00493-008-2321-1openalex-snapshot
A separation theorem in property testing
inferredcites →https://doi.org/10.1007/s004930050060openalex-snapshot
A Sublinear Bipartiteness Tester for Bounded Degree Graphs
inferredcites →https://doi.org/10.1007/s004930070001openalex-snapshot
Efficient Testing of Large Graphs
inferredcites →https://doi.org/10.1016/0196-6774(84)90019-1openalex-snapshot
A separator theorem for graphs of bounded genus
inferredcites →https://doi.org/10.1016/s0167-5060(04)x8001-8openalex-snapshot
Algorithmic Graph Theory and Perfect Graphs
inferredcites →https://doi.org/10.1090/dimacs/043/04openalex-snapshot
Combinatorial property testing (a survey)
inferredcites →https://doi.org/10.1109/sfcs.2002.1181886openalex-snapshot
A lower bound for testing 3-colorability in bounded-degree graphs
inferredcites →https://doi.org/10.1109/sfcs.2005.5openalex-snapshot
A Characterization of the (natural) Graph Properties Testable with One-Sided Error
inferredcites →https://doi.org/10.1137/0136016openalex-snapshot
A Separator Theorem for Planar Graphs
inferredcites →https://doi.org/10.1137/100791075openalex-snapshot
Sublinear Time Algorithms
inferredcites →https://doi.org/10.1137/s0097539703436424openalex-snapshot
Tight Bounds for Testing Bipartiteness in General Graphs
inferredcites →https://doi.org/10.1137/s009753970444199xopenalex-snapshot
Abstract Combinatorial Programs and Efficient Property Testers
inferredcites →https://doi.org/10.1142/9789812562494_0014openalex-snapshot
THE ART OF UNINFORMED DECISIONS: A PRIMER TO PROPERTY TESTING
inferredcites →https://doi.org/10.1145/100216.100254openalex-snapshot
A separator theorem for graphs with an excluded minor and its applications
inferredcites →https://doi.org/10.1145/1060590.1060611openalex-snapshot
Every monotone graph property is testable
inferredcites →https://doi.org/10.1145/1132516.1132555openalex-snapshot
A combinatorial characterization of the testable graph properties
inferredcites →https://doi.org/10.1145/1132516.1132556openalex-snapshot
Graph limits and parameter testing
inferredcites →https://doi.org/10.1145/285055.285060openalex-snapshot
Property testing and its connection to learning and approximation
inferredcites →https://doi.org/10.1145/954092.954103openalex-snapshot
Algorithms column
inferredcites →https://doi.org/10.4230/dagsemproc.05291.3openalex-snapshot
Contemplations on Testing Graph Properties
inferredcites →https://doi.org/10.5555/1109557.1109589openalex-snapshot
Testing triangle-freeness in general graphs

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1002/rsa.20308openalex-snapshot
Parameter testing in bounded degree graphs of subexponential growth
inferred← citeshttps://doi.org/10.1002/rsa.20652openalex-snapshot
Constructing near spanning trees with few local inspections
inferred← citeshttps://doi.org/10.1002/rsa.20727openalex-snapshot
Decomposing a graph into expanding subgraphs
inferred← citeshttps://doi.org/10.1002/rsa.20826openalex-snapshot
Planar graphs: Random walks and bipartiteness testing
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_43openalex-snapshot
An Expansion Tester for Bounded Degree Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-14444-8_13openalex-snapshot
Extremal Problems for Sparse Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-15775-2_35openalex-snapshot
Local Graph Exploration and Fast Property Testing
inferred← citeshttps://doi.org/10.1007/978-3-642-15775-2_6openalex-snapshot
Testing Euclidean Spanners
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_17openalex-snapshot
Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_24openalex-snapshot
Testing Euclidean Spanners
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_5openalex-snapshot
Sublinear-time Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-16367-8_9openalex-snapshot
Sublinear Graph Approximation Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-642-22935-0_45openalex-snapshot
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
inferred← citeshttps://doi.org/10.1007/978-3-642-33090-2_52openalex-snapshot
Property Testing in Sparse Directed Graphs: Strong Connectivity and Subgraph-Freeness
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_60openalex-snapshot
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
inferred← citeshttps://doi.org/10.1007/978-3-662-44522-8_4openalex-snapshot
What Does the Local Structure of a Planar Graph Tell Us About Its Global Structure?
inferred← citeshttps://doi.org/10.1007/s00037-012-0048-2openalex-snapshot
Comparing the strength of query types in property testing: The case of k-colorability
inferred← citeshttps://doi.org/10.1007/s00037-019-00191-6openalex-snapshot
On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
inferred← citeshttps://doi.org/10.1016/j.aim.2009.10.018openalex-snapshot
Every minor-closed property of sparse graphs is testable
inferred← citeshttps://doi.org/10.1017/s096354831000012xopenalex-snapshot
Testing Expansion in Bounded-Degree Graphs
inferred← citeshttps://doi.org/10.1109/focs.2007.4389526openalex-snapshot
Testing Expansion in Bounded-Degree Graphs
inferred← citeshttps://doi.org/10.1109/focs.2007.69openalex-snapshot
Balloon Popping With Applications to Ascending Auctions
inferred← citeshttps://doi.org/10.1109/focs.2009.77openalex-snapshot
Local Graph Partitions for Approximation and Testing
inferred← citeshttps://doi.org/10.1109/focs.2011.69openalex-snapshot
Planar Graphs: Random Walks and Bipartiteness Testing
inferred← citeshttps://doi.org/10.1109/focs.2018.00055openalex-snapshot
Finding Forbidden Minors in Sublinear Time: A n^1/2+o(1)-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
inferred← citeshttps://doi.org/10.1109/focs.2019.00089openalex-snapshot
A Characterization of Graph Properties Testable for General Planar Graphs with one-Sided Error (It's all About Forbidden Subgraphs)
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00034openalex-snapshot
Random walks and forbidden minors III: $\text{poly}\left(d\varepsilon ^{-1}\right)$-time partition oracles for minor-free graph classes
inferred← citeshttps://doi.org/10.1109/lics.2017.8005080openalex-snapshot
Learning first-order definable concepts over structures of small degree
inferred← citeshttps://doi.org/10.1109/smart55829.2022.10046959openalex-snapshot
Graph Family Characterization using the Path Length Array
inferred← citeshttps://doi.org/10.1137/1.9781611973402.86openalex-snapshot
Hereditary properties of permutations are strongly testable
inferred← citeshttps://doi.org/10.1137/1.9781611975482.45openalex-snapshot
Every Testable (Infinite) Property of Bounded-Degree Graphs Contains an Infinite Hyperfinite Subproperty
inferred← citeshttps://doi.org/10.1137/1.9781611976465.29openalex-snapshot
Treewidth-Pliability and PTAS for Max-CSPs
inferred← citeshttps://doi.org/10.1137/100791075openalex-snapshot
Sublinear Time Algorithms
inferred← citeshttps://doi.org/10.1137/100802980openalex-snapshot
An Expansion Tester for Bounded Degree Graphs
inferred← citeshttps://doi.org/10.1137/110837863openalex-snapshot
Noise Tolerance of Expanders and Sublinear Expansion Reconstruction
inferred← citeshttps://doi.org/10.1137/120890946openalex-snapshot
Every Property of Hyperfinite Graphs Is Testable
inferred← citeshttps://doi.org/10.1137/19m1245463openalex-snapshot
Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
inferred← citeshttps://doi.org/10.1145/1993636.1993726openalex-snapshot
Every property of hyperfinite graphs is testable
inferred← citeshttps://doi.org/10.1145/2629508openalex-snapshot
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
inferred← citeshttps://doi.org/10.1145/2897518.2897575openalex-snapshot
Relating two property testing models for bounded degree directed graphs
inferred← citeshttps://doi.org/10.1145/3428675openalex-snapshot
The Subgraph Testing Model
inferred← citeshttps://doi.org/10.1145/3564246.3585218openalex-snapshot
Towards the Erdős-Gallai Cycle Decomposition Conjecture
inferred← citeshttps://doi.org/10.1145/3584948openalex-snapshot
Faster Property Testers in a Variation of the Bounded Degree Model
inferred← citeshttps://doi.org/10.1145/3626515openalex-snapshot
Pliability and Approximating Max-CSPs
inferred← citeshttps://doi.org/10.17877/de290r-13142openalex-snapshot
Property testing in gradbeschränkten gerichteten Graphen unter Nichtsichtbarkeit eingehender Kanten
inferred← citeshttps://doi.org/10.2139/ssrn.5244441openalex-snapshot
Property Testing in Bounded Degree Hypergraphs
inferred← citeshttps://doi.org/10.48550/arxiv.0906.5010openalex-snapshot
Testing cycle-freeness: Finding a certificate
inferred← citeshttps://doi.org/10.48550/arxiv.1106.4587openalex-snapshot
An Efficient Partitioning Oracle for Bounded-Treewidth Graphs
inferred← citeshttps://doi.org/10.48550/arxiv.1302.3417openalex-snapshot
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
inferred← citeshttps://doi.org/10.48550/arxiv.1312.0497openalex-snapshot
Property-Testing in Sparse Directed Graphs: 3-Star-Freeness and Connectivity
inferred← citeshttps://doi.org/10.48550/arxiv.1407.2109openalex-snapshot
Planar Graphs: Random Walks and Bipartiteness Testing
inferred← citeshttps://doi.org/10.48550/arxiv.1909.09984openalex-snapshot
On the Characterization of $1$-sided error Strongly-Testable Graph Properties for bounded-degree graphs, including an appendix
inferred← citeshttps://doi.org/10.48550/arxiv.1909.10647openalex-snapshot
A characterization of graph properties testable for general planar graphs with one-sided error (It is all about forbidden subgraphs)
inferred← citeshttps://doi.org/10.48550/arxiv.2102.00556openalex-snapshot
Random walks and forbidden minors III: poly(d/ε)-time partition oracles for minor-free graph classes
inferred← citeshttps://doi.org/10.48550/arxiv.2102.07587openalex-snapshot
Testing properties of signed graphs
inferred← citeshttps://doi.org/10.5555/2095116.2095204openalex-snapshot
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
inferred← citeshttps://doi.org/10.5555/2722129.2722214openalex-snapshot
Decomposing a graph into expanding subgraphs
inferred← citeshttps://doi.org/10.5555/3329995.3330015openalex-snapshot
Learning first-order definable concepts over structures of small degree
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.