Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

Hereditary properties of permutations are strongly testable

Tools
- Tools
+ Tools

Klimošová , Tereza and Králʼ, Daniel (2014) Hereditary properties of permutations are strongly testable. In: 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14), Portland, USA, 5-7 Jan 2014. Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms pp. 1164-1173. ISBN 9781611973389.

[img]
Preview
HTML (Conference paper)
WRAP_Kral_permtest.pdf - Accepted Version

Download (400Kb) | Preview
[img] Other (Copyright permission email from publisher)
RE Copyright information.msg - Other
Embargoed item. Restricted access to Repository staff only

Download (76Kb)
Official URL: http://dx.doi.org/10.1137/1.9781611973402.86

Request Changes to record.

Abstract

We show that for every hereditary permutation property and every ∊0 > 0, there exists an integer M such that if a permutation π is ∊o-far from in the Kendall's tau distance, then a random subpermutation of π of order M has the property P with probability at most ∊0. This settles an open problem whether hereditary permutation properties are strongly testable, i.e., testable with respect to the Kendall's tau distance, which is considered to be the edit distance for permutations. Our method also yields a proof of a conjecture of Hoppen, Kohayakawa, Moreira and Sampaio on the relation of the rectangular distance and the Kendall's tau distance of a permutation from a hereditary property.

Item Type: Conference Item (Paper)
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions: Faculty of Science > Mathematics
Library of Congress Subject Headings (LCSH): Permutations, Computer algorithms
Series Name: Proceedings
Journal or Publication Title: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher: SIAM
ISBN: 9781611973389
Editor: Chekuri, Chandra
Official Date: January 2014
Dates:
DateEvent
January 2014Published
Page Range: pp. 1164-1173
Status: Peer Reviewed
Publication Status: Published
Funder: Seventh Framework Programme (European Commission) (FP7), European Research Council (ERC)
Grant number: 259385 (ERC)
Conference Paper Type: Paper
Title of Event: 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14)
Type of Event: Conference
Location of Event: Portland, USA
Date(s) of Event: 5-7 Jan 2014

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us