Robust Characterizations of Polynomials with Applications to Program Testing
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 large lower bound on the query complexity of a simple Boolean function
- Testing algebraic geometric codes
- 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
- The Bradley-Terry condition is \(L_1\)-testable
- Non-interactive proofs of proximity
- Testing hypergraph colorability
- Algebraic testing and weight distributions of codes.
- Testing metric properties
- Fast approximate probabilistically checkable proofs
- 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
- Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP
- 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
- Time- and space-efficient arguments from groups of unknown order
- Induced arithmetic removal: complexity 1 patterns over finite fields
- An optimal tester for \(k\)-linear
- Efficient removal lemmas for matrices
- Hierarchy theorems for testing properties in size-oblivious query complexity
- Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time
- Lower bounds for testing triangle-freeness in Boolean functions
- A lower bound for testing juntas
- Low-degree test with polynomially small error
- Property testing on \(k\)-vertex-connectivity of graphs
- 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
- Hermitian-lifted codes
- An optimal tester for k-Linear
- Efficient multivariate low-degree tests via interactive oracle proofs of proximity for polynomial codes
- Complexity theory. Abstracts from the workshop held November 14--20, 2021 (hybrid meeting)
- Testing Lipschitz functions on hypergrid domains
- Two-sided error proximity oblivious testing
- Three-player entangled XOR games are NP-hard to approximate
- Approximate testing with relative error
- A combinatorial characterization of smooth LTCs and applications
- Testing properties of functions on finite groups
- Trigger detection for adaptive scientific workflows using percentile sampling
- Robust characterizations of k-wise independence over product spaces and related testing results
- A polynomial regularity lemma for semialgebraic hypergraphs and its applications in geometry and property testing
- Testing low-degree polynomials over prime fields
- Testability and repair of hereditary hypergraph properties
- On Sums of Locally Testable Affine Invariant Properties
- Limits on the Rate of Locally Testable Affine-Invariant Codes
- 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
- Self-correctors for cryptographic modules
- 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
- Every Monotone 3-Graph Property is Testable
- Proofs of proximity for context-free languages and read-once branching programs
- Quantum locally testable codes
- Indistinguishability and First-Order Logic
- On the Query Complexity of Testing Orientations for Being Eulerian
- Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
- Relational Properties Expressible with One Universal Quantifier Are Testable
- Approximate membership for regular languages modulo the edit distance
- On the Robustness of Functional Equations
- Hierarchy theorems for property testing
- Testable and untestable classes of first-order formulae
- scientific article; zbMATH DE number 1559564 (Why is no real title available?)
- Local testing of lattices
- Checking properties of polynomials
- Erasure-Resilient Property Testing
- Parameterized property testing of functions
- Testing submodularity and other properties of valuation functions
- A hierarchy theorem for interactive proofs of proximity
- Cube vs. Cube Low Degree Test.
- Is submodularity testable?
- scientific article; zbMATH DE number 2086425 (Why is no real title available?)
- scientific article; zbMATH DE number 742944 (Why is no real title available?)
- Testing for forbidden posets in ordered rooted forests
- A brief introduction to property testing
- Short locally testable codes and proofs: a survey in two parts
- Introduction to testing graph properties
- Transitive-closure spanners: a 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
- Hierarchy theorems for property testing
- Algorithmic Aspects of Property Testing in the Dense Graphs Model
This page was built for publication: Robust Characterizations of Polynomials with Applications to Program Testing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4877517)
