Robust Characterizations of Polynomials with Applications to Program Testing
From MaRDI portal
Publication:4877517
DOI10.1137/S0097539793255151zbMath0844.68062OpenAlexW2018925011WikidataQ105584156 ScholiaQ105584156MaRDI QIDQ4877517
Publication date: 18 August 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793255151
Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Specification and verification (program logics, model checking, etc.) (68Q60) Theory of software (68N99)
Related Items (only showing first 100 items - show all)
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 ⋮ Testing Odd-Cycle-Freeness in Boolean Functions ⋮ Quantum information and the PCP theorem ⋮ An adaptivity hierarchy theorem for property testing ⋮ On the strength of comparisons in property testing ⋮ 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 ⋮ Lower bounds for testing Euclidean minimum spanning trees ⋮ 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 ⋮ An optimal tester for \(k\)-linear ⋮ A lower bound for testing juntas ⋮ Hermitian-lifted codes ⋮ Testing juntas ⋮ Sunflowers and testing triangle-freeness of functions ⋮ Low-degree test with polynomially small error ⋮ Approximate membership for regular languages modulo the edit distance ⋮ Efficient removal lemmas for matrices ⋮ A quantitative Arrow theorem ⋮ Bounds for graph regularity and removal lemmas ⋮ Fault detection tests for stuck-at faults on parity counter inputs ⋮ A Polynomial Regularity Lemma for Semialgebraic Hypergraphs and Its Applications in Geometry and Property Testing ⋮ Approximate testing with error relative to input size. ⋮ Property testing on \(k\)-vertex-connectivity of graphs ⋮ The Bradley-Terry condition is \(L_1\)-testable ⋮ An optimal tester for \(k\)-Linear ⋮ 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 ⋮ 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) ⋮ Testable and untestable classes of first-order formulae ⋮ A new proof of the graph removal lemma ⋮ 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 ⋮ Distribution-free connectivity testing for sparse graphs ⋮ Is submodularity testable? ⋮ Property-preserving data reconstruction ⋮ Distributed discovery of large near-cliques ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Quantum spectrum testing ⋮ Testing of matrix-poset properties ⋮ Property testing of regular tree languages ⋮ Testing outerplanarity of bounded degree graphs ⋮ Quantum algorithms for learning and testing juntas ⋮ Shorter arithmetization of nondeterministic computations ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Non-interactive proofs of proximity ⋮ A separation theorem in property testing ⋮ Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs ⋮ Symmetric LDPC codes and local testing ⋮ Every minor-closed property of sparse graphs is testable ⋮ Property testing lower bounds via communication complexity ⋮ Testing periodicity ⋮ Testing convexity properties of tree colorings ⋮ Testing permutation properties through subpermutations ⋮ \(\omega\)-regular languages are testable with a constant number of queries ⋮ Testing hypergraph colorability ⋮ Attribute estimation and testing quasi-symmetry ⋮ Testing low-degree polynomials over prime fields ⋮ Testability and repair of hereditary hypergraph properties ⋮ Hierarchy theorems for testing properties in size-oblivious query complexity ⋮ Tolerant property testing and distance approximation ⋮ Two-sided error proximity oblivious testing ⋮ Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms ⋮ Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP ⋮ Arithmetic progressions, different regularity lemmas and removal lemmas ⋮ Functions that have read-once branching programs of quadratic size are not necessarily testable ⋮ Three-Player Entangled XOR Games are NP-Hard to Approximate ⋮ 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 ⋮ A combinatorial characterization of smooth LTCs and applications ⋮ Testing proximity to subspaces: approximate \(\ell_\infty\) minimization in constant time ⋮ Testing properties of functions on finite groups ⋮ Trigger Detection for Adaptive Scientific Workflows Using Percentile Sampling ⋮ Characterizations of locally testable linear- and affine-invariant families ⋮ Testing computability by width-two OBDDs ⋮ Self-correctors for Cryptographic Modules ⋮ A large lower bound on the query complexity of a simple Boolean function ⋮ Spot-checkers ⋮ Testing algebraic geometric codes ⋮ Robust characterizations of k -wise independence over product spaces and related testing results ⋮ Sharp local minimax rates for goodness-of-fit testing in multivariate binomial and Poisson families and in multinomials ⋮ Lower bounds for testing triangle-freeness in Boolean functions
This page was built for publication: Robust Characterizations of Polynomials with Applications to Program Testing
