Robustly self-ordered graphs: constructions and applications to property testing

DOI10.46298/THEORETICS.22.1MaRDI QIDQ6562699zbMATH OpenFDO

Authors Oded Goldreich, A. Wigderson

Publication date 27 June 2024

Published in TheoretiCS (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/THEORETICS.22.1

zbMATH Keywords

random graphsexpanderscoding theoryasymmetric graphstwo-source extractorstolerant testingnon-malleable extractorstesting graph properties

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• Robustly self-ordered graphs: constructions and applications to property testing
• Property testing in bounded degree graphs
• scientific article; zbMATH DE number 1559556
• Testing Graph Isomorphism
• scientific article; zbMATH DE number 1241385

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

(4)

• Sample-based distance-approximation for subsequence-freeness
• Robustly self-ordered graphs: constructions and applications to property testing
• Seed-protecting extractors
• On testing isomorphism to a fixed graph in the bounded-degree graph model

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)