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

DOI10.46298/THEORETICS.22.1zbMATH Open1540.68179MaRDI QIDQ6562699FDOQ6562699

Authors: Oded Goldreich, A. Wigderson 

Publication date: 27 June 2024

Published in: TheoretiCS (Search for Journal in Brave)

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

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)

Cites Work

• Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
• Property testing and its connection to learning and approximation
• Expander graphs and their applications
• Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
• Assignment Testers: Towards a Combinatorial Proof of the PCP Theorem
• Property testing in bounded degree graphs
• Ramanujan graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).
• Asymmetric graphs
• Isomorphism of graphs of bounded valence can be tested in polynomial time
• Permutation Pseudographs and Contiguity
• Hierarchy theorems for property testing
• Non-malleable extractors and symmetric key cryptography from weak secrets
• Non-malleable extractors and codes, with their many tampered extensions
• Graph isomorphism in quasipolynomial time (extended abstract)
• Tolerant property testing and distance approximation
• The Asymptotic Number of Unlabelled Regular Graphs
• Introduction to Property Testing
• On the asymmetry of random regular graphs and random graphs
• Tolerant versus intolerant testing for Boolean properties
• Distinguishing Vertices of Random Graphs
• Every Set in P Is Strongly Testable Under a Suitable Encoding

Cited In (2)

• Sample-based distance-approximation for subsequence-freeness
• Robustly self-ordered graphs: constructions and applications to property testing

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)