Property testing and its connection to learning and approximation
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- Functions that have read-once branching programs of quadratic size are not necessarily testable
- A sublinear-time approximation scheme for bin packing
- A large lower bound on the query complexity of a simple Boolean function
- Testing algebraic geometric codes
- Approximate testing and its relationship to learning
- Approximate testing with error relative to input size.
- Spot-checkers
- Additive combinatorics and graph theory
- An adaptivity hierarchy theorem for property testing
- Proofs of proximity for context-free languages and read-once branching programs
- Estimating the distance to a hereditary graph property
- The Bradley-Terry condition is \(L_1\)-testable
- Dynamic graph stream algorithms in \(o(n)\) space
- Non-interactive proofs of proximity
- Testing hypergraph colorability
- Testing piecewise functions
- Algebraic testing and weight distributions of codes.
- Testing metric properties
- Fast approximate probabilistically checkable proofs
- Random sampling and approximation of MAX-CSPs
- On the strength of comparisons in property testing
- A quantitative Arrow theorem
- Bounds for graph regularity and removal lemmas
- Comparing the strength of query types in property testing: the case of \(k\)-colorability
- 2-transitivity is insufficient for local testability
- An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity
- Quantum algorithms on Walsh transform and Hamming distance for Boolean functions
- 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
- Local minimax rates for closeness testing of discrete distributions
- Induced arithmetic removal: complexity 1 patterns over finite fields
- An optimal tester for \(k\)-linear
- Estimating the number of connected components in a graph via subgraph sampling
- Efficient removal lemmas for matrices
- Hierarchy theorems for testing properties in size-oblivious query complexity
- On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
- Testing the supermodular-cut condition
- Lower bounds for testing triangle-freeness in Boolean functions
- Exponentially improved algorithms and lower bounds for testing signed majorities
- Moments of two-variable functions and the uniqueness of graph limits
- A lower bound for testing juntas
- Property testing on \(k\)-vertex-connectivity of graphs
- Locality and checkability in wait-free computing
- Testing consistency of quartet topologies: a parameterized approach
- Testing of matrix-poset properties
- Property testing of regular tree languages
- Quantum algorithms for learning and testing juntas
- Tolerant property testing and distance approximation
- Approximate consistency for transformations on words and trees
- Quantum and classical query complexities for generalized Deutsch-Jozsa problems
- An optimal tester for k-Linear
- Testing Lipschitz functions on hypergrid domains
- scientific article; zbMATH DE number 1670655 (Why is no real title available?)
- Two-sided error proximity oblivious testing
- Optimal bounds on approximation of submodular and XOS functions by juntas
- Additive combinatorics: with a view towards computer science and cryptography -- an exposition
- Robust characterizations of k-wise independence over product spaces and related testing results
- On the efficiency of polynomial time approximation schemes
- Finding cycles and trees in sublinear time
- Testing cluster structure of graphs
- Recognizing coverage functions
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- Parameterized testability
- Lower Bounds for Testing Computability by Small Width OBDDs
- Testability and repair of hereditary hypergraph properties
- Dependent random choice
- 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
- Locality and checkability in wait-free computing
- A Nearly-Quadratic Gap between Adaptive and Non-adaptive Property Testers
- A self-tester for linear functions over the integers with an elementary proof of correctness
- Testing Odd-Cycle-Freeness in Boolean Functions
- Fast property testing and metrics for permutations
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Densities in large permutations and parameter testing
- Homomorphisms in graph property testing
- Every Monotone 3-Graph Property is Testable
- Proofs of proximity for context-free languages and read-once branching programs
- Quantum locally testable codes
- Arguments of proximity (extended abstract)
- Testing list H-homomorphisms
- Indistinguishability and First-Order Logic
- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting
- On the Query Complexity of Testing Orientations for Being Eulerian
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- Property testing. A learning theory perspective
- Relational Properties Expressible with One Universal Quantifier Are Testable
- Reoptimization of constraint satisfaction problems with approximation resistant predicates
- Approximate membership for regular languages modulo the edit distance
- scientific article; zbMATH DE number 1241385 (Why is no real title available?)
This page was built for publication: Property testing and its connection to learning and approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3158518)
