Strongly sublinear algorithms for testing pattern freeness
From MaRDI portal
Publication:6566461
DOI10.46298/THEORETICS.24.1MaRDI QIDQ6566461FDOQ6566461
Authors: Ilan Newman, Nithin M. Varma 
Publication date: 3 July 2024
Published in: TheoretiCS (Search for Journal in Brave)
Cites Work
- Property testing and its connection to learning and approximation
- Spot-checkers
- Robust Characterizations of Polynomials with Applications to Program Testing
- Transitive-closure spanners
- Title not available (Why is that?)
- Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- Title not available (Why is that?)
- Excluded permutation matrices and the Stanley-Wilf conjecture
- On Complexity of the Subpattern Problem
- Title not available (Why is that?)
- Finding small patterns in permutations in linear time
- On the number of permutations avoiding a given pattern
- Regular languages are testable with a constant number of queries
- On the strength of comparisons in property testing
- The solution of a conjecture of Stanley and Wilf for all layered patterns
- Estimating the longest increasing sequence in polylogarithmic time
- Finding and counting permutations via CSPs
- Improved bounds for testing forbidden order patterns
- Fast property testing and metrics for permutations
- Parameterized property testing of functions
- Erasure-Resilient Property Testing
- Testing for forbidden order patterns in an array
- Title not available (Why is that?)
- Finding monotone patterns in sublinear time, adaptively
This page was built for publication: Strongly sublinear algorithms for testing pattern freeness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6566461)
