Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Property testing is to quickly distinguish whether object satisfies a property or is epsilon-far from satisfying the property. We focus on objects which can be tested with "constant" query complexity, depending only on epsilon and the property, and not on the size of the object being tested. For general results in this area, the query complexity coming from the proof techniques are often enormous and impractical. It remains a major open problem if better bounds hold. We address this question for permutation hereditary property testing.Hoppen, Kohayakawa, Moreira, and Sampaio conjectured and Klimošová and Král' proved that hereditary permutation properties can be tested with respect to Kendall's tau distance. The query complexity bound coming from this proof is huge, even for testing a single forbidden subpermutation. We give a new proof which gives a polynomial bound in 1/epsilon in this case.Maybe surprisingly, for testing with respect to the cut metric, we prove there is a universal (not depending on the property), polynomial in 1/epsilon query complexity bound for two-sided testing hereditary properties. We further give a nearly linear bound with respect to a closely related metric which also depends on the smallest forbidden subpermutation for the property. Joint work with Jacob Fox.