Introduction to Property Testing
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Collision-based Testers are Optimal for Uniformity and Closeness
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
- Robustly self-ordered graphs: constructions and applications to property testing
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- scientific article; zbMATH DE number 7559054 (Why is no real title available?)
- Algorithms that access the input via queries
- Two Party Distribution Testing: Communication and Security
- Optimal unateness testers for real-valued functions: adaptivity helps
- Efficient testing without efficient regularity
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Learning-augmented query policies for minimum spanning tree with uncertainty
- Testing distributions of huge objects
- Testing piecewise functions
- scientific article; zbMATH DE number 7559095 (Why is no real title available?)
- Global information from local observations of the noisy voter model on a graph
- A Note on Tolerant Testing with One-Sided Error
- On the Effect of the Proximity Parameter on Property Testers
- On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)
- On the Optimal Analysis of the Collision Probability Tester (an Exposition)
- The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
- Hypothesis testing for high-dimensional multinomials: a selective review
- Quasi-random words and limits of word sequences
- Property testing lower bounds via a generalization of randomized parity decision trees
- A PCP of proximity for real algebraic polynomials
- On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
- Zero-knowledge proofs of proximity
- Locally verifiable signature and key aggregation
- An adaptivity hierarchy theorem for property testing
- On the power of relaxed local decoding algorithms
- scientific article; zbMATH DE number 7758308 (Why is no real title available?)
- A lower bound on the complexity of testing grained distributions
- A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Stability of homomorphisms, coverings and cocycles. I: Equivalence
- Software testing in computable analysis
- A characterization of easily testable induced digraphs and \(k\)-colored graphs
- A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
- A two-sided error distributed property tester for conductance
- Testing linear inequalities of subgraph statistics
- A hierarchy theorem for interactive proofs of proximity
- Erasures versus errors in local decoding and property testing
- On one-sided testing affine subspaces
- Testing for dense subsets in a graph via the partition function
- Complexity of high-dimensional identity testing with coordinate conditional sampling
- Erasure-resilient sublinear-time graph algorithms
- Concentration of the collision estimator
- Smooth and strong PCPs
- An explicit construction of graphs of bounded degree that are far from being Hamiltonian
- Quantum Chebyshev's Inequality and Applications
- Pliability and approximating Max-CSPs
- The subgraph testing model
- On one-sided testing affine subspaces
- Testing intersectingness of uniform families
- Random walks and forbidden minors. I: An \(n^{1/2+o(1)}\)-query one-sided tester for minor closed properties on bounded degree graphs
- On the tree-width of even-hole-free graphs
- Sample efficient identity testing and independence testing of quantum states
- Comparison graphs: a unified method for uniformity testing
- Sampling and optimal preference elicitation in simple mechanisms
- An optimal tester for \(k\)-linear
- Testing versus estimation of graph properties, revisited
- Proofs of proximity for distribution testing
- An exponential separation between MA and AM proofs of proximity
- Relaxed locally correctable codes
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- Testability in group theory
- Property testing of LP-type problems
- Graph coloring via degeneracy in streaming and other space-conscious models
- Property testing and expansion in cubical complexes
- Local-vs-global combinatorics
- Random Walks and Forbidden Minors I: An $n^{1/2+o(1)}$-Query One-Sided Tester for Minor Closed Properties on Bounded Degree Graphs
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- Hierarchy theorems for testing properties in size-oblivious query complexity
- No-signaling linear PCPs
- Testing support size more efficiently than learning histograms
- Distribution-free proofs of proximity
- Statistical difference beyond the polarizing regime
- \(k\)-hop graph neural networks
- On testing group properties
- One-sided error testing of monomials and affine subspaces
- On properties that are non-trivial to test
- Testing in the bounded-degree graph model with degree bound two
- On the query complexity of testing local graph properties in the bounded-degree graph model
- On testing asymmetry in the bounded degree graph model
- On testing isomorphism to a fixed graph in the bounded-degree graph model
- Testing isomorphism in the bounded-degree graph model
- On testing Hamiltonicity in the bounded degree graph model
- Robust self-ordering versus local self-ordering
- On the complexity of estimating the effective support size
- On the lower bound on the length of relaxed locally decodable codes
- On the locally testable code of Dinur \textit{et al.} (2021)
- On locally-characterized expander graphs (a survey)
- On counting t-cliques mod 2
- Testing graph properties with the container method
- Stability of approximate group actions: uniform and probabilistic
- Polynomial removal lemmas for ordered graphs
- scientific article; zbMATH DE number 7758318 (Why is no real title available?)
- Parameterized inapproximability hypothesis under ETH
- Topics and Techniques in Distribution Testing: A Biased but Representative Sample
- Improved sublinear-time moment estimation using weighted sampling
This page was built for publication: Introduction to Property Testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5371343)
