scientific article; zbMATH DE number 1418269
From MaRDI portal
Publication:4941829
zbMath0949.68178MaRDI QIDQ4941829
Oded Goldreich, Yevgeniy Dodis, Sofya Raskhodnikova, Dana Ron, Eric Lehman, Alex Samorodnitsky
Publication date: 19 March 2000
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Testing Lipschitz functions on hypergrid domains, On the strength of comparisons in property testing, Parameterized property testing of functions, Testing properties of directed graphs: acyclicity and connectivity*, Information theory in property testing and monotonicity testing in higher dimension, Testing juntas, On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing, Steiner transitive-closure spanners of low-dimensional posets, Approximating the distance to monotonicity of Boolean functions, Improved algorithm for permutation testing, Unnamed Item, Unnamed Item, Erasure-Resilient Property Testing, Monotonicity testing and shortest-path routing on the cube, Distribution-free connectivity testing for sparse graphs, Is submodularity testable?, The power and limitations of uniform samples in testing properties of figures, Testing of matrix-poset properties, Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces, Adaptive Lower Bound for Testing Monotonicity on the Line, Almost Optimal Distribution-Free Sample-Based Testing of k-Modality, Testing whether a digraph contains \(H\)-free \(k\)-induced subgraphs, Property testing lower bounds via communication complexity, Estimating the Longest Increasing Sequence in Polylogarithmic Time, Fast approximate PCPs for multidimensional bin-packing problems, Transitive-Closure Spanners: A Survey, Invariance in Property Testing, Local Property Reconstruction and Monotonicity, Static extensivity analysis for \(\lambda\)-definable functions over lattices, Tolerant property testing and distance approximation, Earthmover Resilience and Testing in Ordered Structures, An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube, Adaptive Boolean Monotonicity Testing in Total Influence Time, Functions that have read‐twice constant width branching programs are not necessarily testable, A Polynomial Lower Bound for Testing Monotonicity, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, Unnamed Item, Exponentially improved algorithms and lower bounds for testing signed majorities
