Testing for forbidden order patterns in an array

DOI10.1137/1.9781611974782.104zbMATH Open1403.68338OpenAlexW4247687185MaRDI QIDQ4575847FDOQ4575847

Authors: Ilan Newman, Yuri Rabinovich, Deepak Rajendraprasad, Christian Sohler 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.104

Recommendations

• Testing for forbidden order patterns in an array
• Improved bounds for testing forbidden order patterns
• On the strength of comparisons in property testing
• scientific article; zbMATH DE number 1418269
• Flipping out with many flips: hardness of testing \(k\)-monotonicity

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (12)

• Improved algorithm for permutation testing
• Testing for forbidden order patterns in an array
• Testing for forbidden posets in ordered rooted forests
• Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays
• Improved bounds for testing forbidden order patterns
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• Finding and counting permutations via CSPs
• On the strength of comparisons in property testing
• Testing hereditary properties of sequences
• Flipping out with many flips: hardness of testing \(k\)-monotonicity
• The power and limitations of uniform samples in testing properties of figures
• Smooth heaps and a dual view of self-adjusting data structures

This page was built for publication: Testing for forbidden order patterns in an array

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575847)