Testing for Forbidden Order Patterns in an Array

DOI10.1137/1.9781611974782.104zbMath1403.68338OpenAlexW4247687185MaRDI QIDQ4575847

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

Mathematics Subject Classification ID

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

Related Items (7)

Improved algorithm for permutation testing ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Smooth Heaps and a Dual View of Self-Adjusting Data Structures ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Finding and counting permutations via CSPs ⋮ Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity

This page was built for publication: Testing for Forbidden Order Patterns in an Array