lgorithmic and Analysis Techniques in Property Testing
From MaRDI portal
Publication:5190073
DOI10.1561/0400000029zbMath1184.68610OpenAlexW4241342151MaRDI QIDQ5190073
Publication date: 12 March 2010
Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1561/0400000029
random walkslocal searchenforce and test approachself-correcting approachSzemerédi's Regularity LemmaTesting by implicit learning
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10)
Related Items (53)
Testing Lipschitz functions on hypergrid domains ⋮ An adaptivity hierarchy theorem for property testing ⋮ Big Data on the Rise? ⋮ New techniques and tighter bounds for local computation algorithms ⋮ An optimal tester for \(k\)-linear ⋮ Testing list \(H\)-homomorphisms ⋮ Finding cycles and trees in sublinear time ⋮ On the Communication Complexity Methodology for Proving Lower Bounds on the Query Complexity of Property Testing ⋮ Discrimination of quantum states under locality constraints in the many-copy setting ⋮ On one-sided testing affine subspaces ⋮ Erasures versus errors in local decoding and property testing ⋮ Almost optimal proper learning and testing polynomials ⋮ An optimal tester for \(k\)-Linear ⋮ Testing the \((s,t)\) connectivity of graphs and digraphs ⋮ Hierarchy theorems for property testing ⋮ Testing shape restrictions of discrete distributions ⋮ Testable and untestable classes of first-order formulae ⋮ Algorithmic Aspects of Property Testing in the Dense Graphs Model ⋮ A Brief Introduction to Property Testing ⋮ Introduction to Testing Graph Properties ⋮ An Exponential Separation Between MA and AM Proofs of Proximity ⋮ Hierarchy Theorems for Property Testing ⋮ The power and limitations of uniform samples in testing properties of figures ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ An exponential separation between \textsf{MA} and \textsf{AM} proofs of proximity ⋮ Lower Bounds for Testing Computability by Small Width OBDDs ⋮ Non-interactive proofs of proximity ⋮ Almost Optimal Testers for Concise Representations. ⋮ Property testing lower bounds via communication complexity ⋮ TESTING FOR FORBIDDEN POSETS IN ORDERED ROOTED FORESTS ⋮ Sorting and selection on dynamic data ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fast distributed algorithms for testing graph properties ⋮ Testing piecewise functions ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ Proximity Oblivious Testing and the Role of Invariances ⋮ On the Average-Case Complexity of Property Testing ⋮ 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 ⋮ Almost optimal distribution-free junta testing ⋮ Testing properties of functions on finite groups ⋮ Trigger Detection for Adaptive Scientific Workflows Using Percentile Sampling ⋮ Testing computability by width-two OBDDs ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ Unnamed Item ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Testing Probability Distributions using Conditional Samples ⋮ Exponentially improved algorithms and lower bounds for testing signed majorities
This page was built for publication: lgorithmic and Analysis Techniques in Property Testing
