Introduction to Property Testing
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Hypothesis testing for high-dimensional multinomials: a selective review
- An adaptivity hierarchy theorem for property testing
- The Bradley-Terry condition is \(L_1\)-testable
- Testing piecewise functions
- On the tree-width of even-hole-free graphs
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Property testing lower bounds via a generalization of randomized parity decision trees
- Smooth and strong PCPs
- \(k\)-hop graph neural networks
- A PCP of proximity for real algebraic polynomials
- A characterization of easily testable induced digraphs and \(k\)-colored graphs
- Concentration of the collision estimator
- An optimal tester for \(k\)-linear
- Estimating the number of connected components in a graph via subgraph sampling
- Statistical difference beyond the polarizing regime
- Hierarchy theorems for testing properties in size-oblivious query complexity
- Improved bounds for quantified derandomization of constant-depth circuits and polynomials
- Property testing and expansion in cubical complexes
- An optimal tester for k-Linear
- 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 hierarchy theorem for interactive proofs of proximity
- scientific article; zbMATH DE number 1857651 (Why is no real title available?)
- On the power of relaxed local decoding algorithms
- On the Query Complexity of Estimating the Distance to Hereditary Graph Properties
- Zero-knowledge proofs of proximity
- Proofs of proximity for distribution testing
- Efficient testing without efficient regularity
- A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error
- An exponential separation between MA and AM proofs of proximity
- A two-sided error distributed property tester for conductance
- Polynomial removal lemmas for ordered graphs
- scientific article; zbMATH DE number 7625202 (Why is no real title available?)
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
- Testing local properties of arrays
- Every Set in P Is Strongly Testable Under a Suitable Encoding
- The subgraph testing model
- scientific article; zbMATH DE number 7559095 (Why is no real title available?)
- Parameterized query complexity of hitting set using stability of sunflowers
- Two Party Distribution Testing: Communication and Security
- Quantum Chebyshev's Inequality and Applications
- On the Effect of the Proximity Parameter on Property Testers
- On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing
- On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)
- The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution
- A Note on Tolerant Testing with One-Sided Error
- Reducing Testing Affine Spaces to Testing Linearity of Functions
- On the Optimal Analysis of the Collision Probability Tester (an Exposition)
- Flexible Models for Testing Graph Properties
- On approximating the number of k-cliques in sublinear time
- Optimal unateness testers for real-valued functions: adaptivity helps
- Testing for dense subsets in a graph via the partition function
- Collision-based Testers are Optimal for Uniformity and Closeness
- Relaxed locally correctable codes
- An explicit construction of graphs of bounded degree that are far from being Hamiltonian
- Topics and Techniques in Distribution Testing: A Biased but Representative Sample
- scientific article; zbMATH DE number 7650132 (Why is no real title available?)
- Random Walks and Forbidden Minors II: A $\mathrm{poly}(d\varepsilon^{-1})$-Query Tester for Minor-Closed Properties of Bounded-Degree Graphs
- Quasi-random words and limits of word sequences
- No-signaling linear PCPs
- Testing linear inequalities of subgraph statistics
- On one-sided testing affine subspaces
- Stability of approximate group actions: uniform and probabilistic
- Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
- A lower bound on the complexity of testing grained distributions
- Erasures versus errors in local decoding and property testing
- Testability in group theory
- Almost Optimal Testers for Concise Representations.
- scientific article; zbMATH DE number 7758308 (Why is no real title available?)
- scientific article; zbMATH DE number 7758318 (Why is no real title available?)
- Locally verifiable signature and key aggregation
- Almost optimal proper learning and testing polynomials
- Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
- Almost optimal query algorithm for hitting set using a subset query
- 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 Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification
- Global information from local observations of the noisy voter model on a graph
- Local-vs-global combinatorics
- Robustly self-ordered graphs: constructions and applications to property testing
- Testing distributions of huge objects
- On testability of first-order properties in bounded-degree graphs and connections to proximity-oblivious testing
- On one-sided testing affine subspaces
- Testing versus estimation of graph properties, revisited
- The power and limitations of uniform samples in testing properties of figures
- Property testing of LP-type problems
- Graph coloring via degeneracy in streaming and other space-conscious models
- Distribution-free proofs of proximity
- 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)
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)
