Algorithmic and analysis techniques in property testing
From MaRDI portal
Recommendations
Cited in
(66)- An adaptivity hierarchy theorem for property testing
- Testing shape restrictions of discrete distributions
- Dynamic graph stream algorithms in \(o(n)\) space
- Non-interactive proofs of proximity
- Testing piecewise functions
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- An optimal tester for \(k\)-linear
- Exponentially improved algorithms and lower bounds for testing signed majorities
- New techniques and tighter bounds for local computation algorithms
- An optimal tester for k-Linear
- Testing Lipschitz functions on hypergrid domains
- Testing properties of functions on finite groups
- Trigger detection for adaptive scientific workflows using percentile sampling
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Finding cycles and trees in sublinear time
- Lower Bounds for Testing Computability by Small Width OBDDs
- On the average-case complexity of property testing
- A Brief Introduction to Property Testing
- Introduction to testing graph properties
- Randomness and computation
- Contemplations on Testing Graph Properties
- Another motivation for reducing the randomness complexity of algorithms
- Property testing for bounded degree databases
- Homomorphisms in graph property testing
- Big data on the rise? Testing monotonicity of distributions
- Testing list H-homomorphisms
- Testing the \((s,t)\) connectivity of graphs and digraphs
- Hierarchy theorems for property testing
- Testable and untestable classes of first-order formulae
- A chasm between identity and equivalence testing with conditional queries
- scientific article; zbMATH DE number 1857651 (Why is no real title available?)
- scientific article; zbMATH DE number 1903351 (Why is no real title available?)
- Testing for forbidden posets in ordered rooted forests
- A brief introduction to property testing
- Introduction to testing graph properties
- Hierarchy theorems for property testing
- Algorithmic Aspects of Property Testing in the Dense Graphs Model
- An exponential separation between MA and AM proofs of proximity
- Property testing. Problems and techniques
- The subgraph testing model
- scientific article; zbMATH DE number 7559095 (Why is no real title available?)
- Almost optimal distribution-free junta testing
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Constant-query testability of assignments to constraint satisfaction problems
- Partially symmetric functions are efficiently isomorphism testable
- Testing probability distributions using conditional samples
- Sorting and selection on dynamic data
- Proximity Oblivious Testing and the Role of Invariances
- Proximity oblivious testing and the role of invariances
- Discrimination of quantum states under locality constraints in the many-copy setting
- On one-sided testing affine subspaces
- Erasures versus errors in local decoding and property testing
- Testing properties of graphs and functions
- Almost Optimal Testers for Concise Representations.
- Almost optimal proper learning and testing polynomials
- On one-sided testing affine subspaces
- The power and limitations of uniform samples in testing properties of figures
- Property testing of LP-type problems
- (Quantum) complexity of testing signed graph clusterability
- On testing group properties
- On the locally testable code of Dinur \textit{et al.} (2021)
- Property testing lower bounds via communication complexity
- Property testing of curve similarity
- Quantum property testing in sparse directed graphs
- Testing cluster structure of graphs
- Testing computability by width-two OBDDs
This page was built for publication: Algorithmic and analysis techniques in property testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5190073)
