The Library
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.
|
HTML (Conference paper)
WRAP_Kral_permtest.pdf - Accepted Version Download (400Kb) | Preview |
|
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/other.png) |
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
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: |
|
||||
| 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 |
