Robustly self-ordered graphs: constructions and applications to property testing
From MaRDI portal
Recommendations
Cites work
- Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
- Asymmetric graphs
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Distinguishing Vertices of Random Graphs
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- Expander graphs and their applications
- Graph isomorphism in quasipolynomial time (extended abstract)
- Hierarchy theorems for property testing
- Introduction to Property Testing
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Non-malleable extractors and codes, with their many tampered extensions
- Non-malleable extractors and symmetric key cryptography from weak secrets
- On the asymmetry of random regular graphs and random graphs
- Permutation Pseudographs and Contiguity
- Property testing and its connection to learning and approximation
- Property testing in bounded degree graphs
- Ramanujan graphs
- Robust Characterizations of Polynomials with Applications to Program Testing
- Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
- The Asymptotic Number of Unlabelled Regular Graphs
- Tolerant property testing and distance approximation
- Tolerant versus intolerant testing for Boolean properties
- Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
Cited in
(5)- Robustly self-ordered graphs: constructions and applications to property testing
- Sample-based distance-approximation for subsequence-freeness
- Seed-protecting extractors
- On testing isomorphism to a fixed graph in the bounded-degree graph model
- Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)
This page was built for publication: Robustly self-ordered graphs: constructions and applications to property testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6562699)
