Efficient Testing without Efficient Regularity

DOI10.4230/LIPICS.ITCS.2018.54zbMath1462.68139OpenAlexW2783034206MaRDI QIDQ4993324

Lior Gishboliner, Asaf Shapira

Publication date: 15 June 2021

Full work available at URL: https://dblp.uni-trier.de/db/conf/innovations/innovations2018.html#GishbolinerS18

zbMATH Keywords

property testinginduced \(C_4\)-freeness

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new proof of the graph removal lemma
• A short proof of Gowers' lower bound for the regularity lemma
• Large cliques in \(C_4\)-free graphs
• On graphs with small subgraphs of large chromatic number
• Lower bounds of tower type for Szemerédi's uniformity lemma
• Bounds for graph regularity and removal lemmas
• On extremal problems of graphs and generalized graphs
• Graph removal lemmas
• On Proximity-Oblivious Testing
• Property testing and its connection to learning and approximation
• Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
• A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
• Testing subgraphs in large graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Removal lemmas with polynomial bounds
• A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
• Easily Testable Graph Properties
• Introduction to Property Testing
• Testing Graph Blow-Up
• Efficient testing of large graphs

This page was built for publication: Efficient Testing without Efficient Regularity