Property testing and its connection to learning and approximation

DOI10.1145/285055.285060zbMath1065.68575OpenAlexW1970630090WikidataQ105584189 ScholiaQ105584189MaRDI QIDQ3158518

Shafi Goldwasser, Dana Ron, Oded Goldreich

Publication date: 25 January 2005

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/285055.285060

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Combinatorial probability (60C05) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

An Algebraic Characterization of Testable Boolean CSPs, Testing Linear-Invariant Properties, 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, The Uniform Distribution Is Complete with Respect to Testing Identity to a Fixed Distribution, On the Optimal Analysis of the Collision Probability Tester (an Exposition), Flexible Models for Testing Graph Properties, Tropicalization of graph profiles, Testing linear inequalities of subgraph statistics, Discrimination of quantum states under locality constraints in the many-copy setting, A lower bound on the complexity of testing grained distributions, Erasures versus errors in local decoding and property testing, Approximating the distance to monotonicity of Boolean functions, Hypergraph regularity and random sampling, Testing membership for timed automata, Half-Spaces with Influential Variable, A Structural Theorem for Local Algorithms with Applications to Coding, Testing, and Verification, Unnamed Item, Unnamed Item, Local-vs-global combinatorics, Easily Testable Graph Properties, On Active and Passive Testing, Unnamed Item, Unnamed Item, Amplification and Derandomization without Slowdown, Testing convexity of figures under the uniform distribution, Non-Deterministic Graph Property Testing, Testing Data Binnings, Almost Optimal Testers for Concise Representations., Distributed Testing of Graph Isomorphism in the CONGEST Model., Estimating the Longest Increasing Sequence in Polylogarithmic Time, Lazy regular sensing, Fast distributed algorithms for testing graph properties, Unnamed Item, Earthmover Resilience and Testing in Ordered Structures, Testing subgraphs in directed graphs, Limitations of Local Filters of Lipschitz and Monotone Functions, Quasi-random words and limits of word sequences, Finding a Dense-Core in Jellyfish Graphs, On Approximating the Number of Relevant Variables in a Function, Testing Graph Blow-Up, Testing Graph Blow-Up, Proximity Oblivious Testing and the Role of Invariances, Proximity Oblivious Testing and the Role of Invariances, Unnamed Item, A characterization of constant‐sample testable properties, Planar graphs: Random walks and bipartiteness testing, Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing, Unnamed Item, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses, Separating Sublinear Time Computations by Approximate Diameter, Partially Symmetric Functions Are Efficiently Isomorphism Testable, Testing Probability Distributions using Conditional Samples, Unnamed Item, Unnamed Item, 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, Testing Odd-Cycle-Freeness in Boolean Functions, Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs, On the optimality of the random hyperplane rounding technique for MAX CUT, Quantum Locally Testable Codes, Parameterized property testing of functions, Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models, A Hierarchy Theorem for Interactive Proofs of Proximity, Testing the diameter of graphs, Testing properties of directed graphs: acyclicity and connectivity*, Fast Property Testing and Metrics for Permutations, Arguments of Proximity, Finding cycles and trees in sublinear time, Efficient Removal Lemmas for Matrices, Recognizing Coverage Functions, Quantum and classical query complexities for generalized Deutsch-Jozsa problems, Unnamed Item, Indistinguishability and First-Order Logic, A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, An optimal tester for \(k\)-Linear, Unnamed Item, Unnamed Item, Unnamed Item, Learning and Verifying Graphs Using Queries with a Focus on Edge Counting, Erasure-Resilient Property Testing, Algorithmic Aspects of Property Testing in the Dense Graphs Model, A Brief Introduction to Property Testing, Introduction to Testing Graph Properties, On the power of conditional samples in distribution testing, On the Query Complexity of Testing Orientations for Being Eulerian, Breaking the ε-Soundness Bound of the Linearity Test over GF(2), Efficient Testing without Efficient Regularity, Zero-Knowledge Proofs of Proximity, Proofs of Proximity for Distribution Testing, Embedding Graphs into Larger Graphs: Results, Methods, and Problems, Helly-Type Theorems in Property Testing, Testing Euclidean Spanners, An Exponential Separation Between MA and AM Proofs of Proximity, Hierarchy Theorems for Property Testing, Sublinear Algorithms for MAXCUT and Correlation Clustering, Sample-Based High-Dimensional Convexity Testing., Property testing of regular tree languages, Quantum algorithms for learning and testing juntas, Adaptive Lower Bound for Testing Monotonicity on the Line, Lower Bounds for Testing Computability by Small Width OBDDs, TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS, Limitation on the Rate of Families of Locally Testable Codes, Testing Juntas: A Brief Survey, Sublinear-time Algorithms, Short Locally Testable Codes and Proofs: A Survey in Two Parts, Property Testing of Massively Parametrized Problems – A Survey, Transitive-Closure Spanners: A Survey, Testing by Implicit Learning: A Brief Survey, Invariance in Property Testing, Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability, Testing Linear-Invariant Non-linear Properties: A Short Report, Optimal Testing of Reed-Muller Codes, Some Recent Results on Local Testing of Sparse Linear Codes, Testing (Subclasses of) Halfspaces, Local Property Reconstruction and Monotonicity, Green’s Conjecture and Testing Linear Invariant Properties, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Testability and repair of hereditary hypergraph properties, Tolerant property testing and distance approximation, Two-sided error proximity oblivious testing, Dependent random choice, Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas, Quantum Property Testing for Bounded-Degree Graphs, On Sums of Locally Testable Affine Invariant Properties, Limits on the Rate of Locally Testable Affine-Invariant Codes, Inflatable Graph Properties and Natural Property Tests, On the Average-Case Complexity of Property Testing, Short Locally Testable Codes and Proofs, On the Complexity of Computational Problems Regarding Distributions, 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, Every Set in P Is Strongly Testable Under a Suitable Encoding, Almost optimal distribution-free junta testing, Locality and Checkability in Wait-Free Computing, A unified framework for testing linear‐invariant properties, Relational Properties Expressible with One Universal Quantifier Are Testable, On the Query Complexity of Estimating the Distance to Hereditary Graph Properties, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, Estimating parameters associated with monotone properties, Constant-Round Interactive Proofs for Delegating Computation, Robust characterizations of k -wise independence over product spaces and related testing results, Improved Dynamic Graph Coloring, Unnamed Item, Every Monotone 3-Graph Property is Testable, Approximate consistency for transformations on words and trees, Algebraic testing and weight distributions of codes., Testing Lipschitz functions on hypergrid domains, Testing metric properties, Property testing of the Boolean and binary rank, Additive combinatorics and graph theory, Fast approximate probabilistically checkable proofs, Testing graphs against an unknown distribution, On the efficiency of polynomial time approximation schemes, Random sampling and approximation of MAX-CSPs, An adaptivity hierarchy theorem for property testing, On the strength of comparisons in property testing, Local minimax rates for closeness testing of discrete distributions, Induced arithmetic removal: complexity 1 patterns over finite fields, Lower bounds for testing Euclidean minimum spanning trees, Moments of two-variable functions and the uniqueness of graph limits, A self-tester for linear functions over the integers with an elementary proof of correctness, Proofs of proximity for context-free languages and read-once branching programs, Separating sublinear time computations by approximate diameter, An optimal tester for \(k\)-linear, Densities in large permutations and parameter testing, A lower bound for testing juntas, Information theory in property testing and monotonicity testing in higher dimension, Testing list \(H\)-homomorphisms, Testing juntas, Estimating the number of connected components in a graph via subgraph sampling, On the benefits of adaptivity in property testing of dense graphs, Reoptimization of constraint satisfaction problems with approximation resistant predicates, Testing properties of graphs and functions, Sunflowers and testing triangle-freeness of functions, Approximate membership for regular languages modulo the edit distance, Improved algorithms for quantum identification of Boolean oracles, Efficient removal lemmas for matrices, A quantitative Arrow theorem, Bounds for graph regularity and removal lemmas, When distributed computation is communication expensive, Estimating the distance to a hereditary graph property, Approximate testing with error relative to input size., Property testing on \(k\)-vertex-connectivity of graphs, Testability of minimum balanced multiway cut densities, The Bradley-Terry condition is \(L_1\)-testable, Testing the \((s,t)\) connectivity of graphs and digraphs, Comparing the strength of query types in property testing: the case of \(k\)-colorability, 2-transitivity is insufficient for local testability, Hierarchy theorems for property testing, Testable and untestable classes of first-order formulae, A new proof of the graph removal lemma, Efficiently testing sparse \(\text{GF}(2)\) polynomials, Locality and checkability in wait-free computing, A property tester for tree-likeness of quartet topologies, Testing consistency of quartet topologies: a parameterized approach, Testing Eulerianity and connectivity in directed sparse graphs, On the approximation ratio threshold for the reoptimization of the maximum number of satisfied equations in linear systems over a finite field, Distribution-free connectivity testing for sparse graphs, On testing Hamiltonicity of graphs, Testing \(k\)-edge-connectivity of digraphs, Is submodularity testable?, Property-preserving data reconstruction, Distributed discovery of large near-cliques, Deterministic vs non-deterministic graph property testing, The power and limitations of uniform samples in testing properties of figures, Testing of matrix-poset properties, Testing outerplanarity of bounded degree graphs, Decomposition of complete bipartite digraphs and complete digraphs into directed paths and directed cycles of fixed even length, Dynamic graph stream algorithms in \(o(n)\) space, An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity, Non-interactive proofs of proximity, A separation theorem in property testing, Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing, Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs, Quantum algorithms on Walsh transform and Hamming distance for Boolean functions, Every minor-closed property of sparse graphs is testable, Property testing lower bounds via communication complexity, Testing periodicity, Small space representations for metric min-sum \(k\)-clustering and their applications, Testing convexity properties of tree colorings, \(\omega\)-regular languages are testable with a constant number of queries, Testing hypergraph colorability, Attribute estimation and testing quasi-symmetry, Min sum clustering with penalties, An analytic approach to stability, Sublinear time algorithms in the theory of groups and semigroups., Generalizations of the removal lemma, Testing piecewise functions, Hierarchy theorems for testing properties in size-oblivious query complexity, Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms, Arithmetic progressions, different regularity lemmas and removal lemmas, Functions that have read-once branching programs of quadratic size are not necessarily testable, On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs, Characterizations of locally testable linear- and affine-invariant families, Testing computability by width-two OBDDs, A sublinear-time approximation scheme for bin packing, A large lower bound on the query complexity of a simple Boolean function, Spot-checkers, Testing algebraic geometric codes, Quantum algorithms for learning Walsh spectra of multi-output Boolean functions, Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials, Testing the supermodular-cut condition, Lower bounds for testing triangle-freeness in Boolean functions, Exponentially improved algorithms and lower bounds for testing signed majorities