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.

Preview	HTML (Conference paper) WRAP_Kral_permtest.pdf - Accepted Version Download (400Kb) | Preview
	Other (Copyright permission email from publisher) RE Copyright information.msg - Other Embargoed item. Restricted access to Repository staff only Download (76Kb)

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, Engineering and Medicine > 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:	Date Event January 2014 Published
Page Range:	pp. 1164-1173
Status:	Peer Reviewed
Publication Status:	Published
Date of first compliant deposit:	4 March 2016
Date of first compliant Open Access:	4 March 2016
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

Downloads