Monotonicity testing over general poset domains

No abstract is available for this paper.

• Publication year

  2002

• Venue

  Symposium on the Theory of Computing

• Publication date

  2002-05-19

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/509907.509977
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• The Probabilistic Method

  2015cited by this paper
• THE ART OF UNINFORMED DECISIONS: A PRIMER TO PROPERTY TESTING

  2004cited by this paper
• On the strength of comparisons in property testing

  2004cited by this paper
• The Probabilistic Method: Alon/Probabilistic Method

  2004cited by this paper
• Functions that have read-twice constant width branching programs are not necessarily testable

  2002cited by this paper
• Property Testing in Bounded Degree Graphs

  2002cited by this paper
• Simple analysis of graph tests for linearity and PCP

  2001influential reference
• Testing of matrix properties

  2001cited by this paper
• Property Testing in Computational Geometry

  2000cited by this paper
• Efficient Testing of Large Graphs

  2000cited by this paper
• Regular ArticleSpot-Checkers☆

  2000cited by this paper
• Improved Testing Algorithms for Monotonicity

  1999influential reference
• Regular languages are testable with a constant number of queries

  1999cited by this paper
• Fast approximate PCPs for multidimensional bin-packing problems

  1999cited by this paper
• Testing Monotonicity

  1998cited by this paper
• Spot-checkers

  1998cited by this paper
• Property testing and its connection to learning and approximation

  1996cited by this paper
• Robust Characterizations of Polynomials with Applications to Program Testing

  1996cited by this paper
• Probability: Theory and Examples

  1993cited by this paper
• A Separator Theorem for Planar Graphs

  1977cited by this paper
• A DECOMPOSITION THEOREM FOR PARTIALLY ORDERED SETS

  1950cited by this paper
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression.

  1946cited by this paper
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression.

  1942cited by this paper

• An improved construction for the triangle removal lemma

  2025cites this paper
• Lower Bounds for Non-adaptive Local Computation Algorithms

  2025cites this paper
• Computational Complexity in Property Testing

  2025cites this paper
• Relative-error testing of conjunctions and decision lists

  2025cites this paper
• Constructing Long Paths in Graph Streams

  2025cites this paper
• Let's Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation (Invited Talk)

  2025cites this paper
• Monotone Classification with Relative Approximations

  2025cites this paper
• Query Complexity of Stochastic Minimum Vertex Cover

  2025cites this paper
• A Distance Amplification Lemma for Monotonicity

  2025cites this paper
• Improved Bounds for Fully Dynamic Matching via Ordered Ruzsa-Szemerédi Graphs

  2024cites this paper
• Relative-error monotonicity testing

  2024cites this paper
• A Novel Construction of Coded Caching Schemes with Polynomial Subpacketizations via Projective Geometry

  2024cites this paper
• Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs

  2024cites this paper
• Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing

  2024cites this paper
• Streaming and Communication Complexity of Load-Balancing via Matching Contractors

  2024influential citation
• Catalytic Communication

  2024cites this paper
• Stochastic Matching via In-n-Out Local Computation Algorithms

  2024cites this paper
• Directed Poincaré Inequalities and $L^1$ Monotonicity Testing of Lipschitz Functions

  2023cites this paper
• Streaming Edge Coloring with Subquadratic Palette Size

  2023cites this paper
• Nearly Optimal Bounds for Sample-Based Testing and Learning of $k$-Monotone Functions

  2023cites this paper
• Testing Intersecting and Union-Closed Families

  2023cites this paper
• On the Pauli Spectrum of QAC0

  2023cites this paper
• Hidden Permutations to the Rescue: Multi-Pass Streaming Lower Bounds for Approximate Matchings

  2023influential citation
• Directed Poincaré Inequalities and L1 Monotonicity Testing of Lipschitz Functions

  2023cites this paper
• Local Lipschitz Filters for Bounded-Range Functions

  2023cites this paper
• Recent Advances in Multi-Pass Graph Streaming Lower Bounds

  2023cites this paper
• Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas

  2023cites this paper
• A d1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids*

  2023cites this paper
• On Regularity Lemma and Barriers in Streaming and Dynamic Matching

  2022cites this paper
• On Monotonicity Testing and the 2-to-2 Games Conjecture

  2022cites this paper
• Improved Monotonicity Testers via Hypercube Embeddings

  2022cites this paper
• Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an Õ(n√d) Monotonicity Tester

  2022cites this paper
• Weak learning convex sets under normal distributions

  2021cites this paper
• A Two-Pass Lower Bound for Semi-Streaming Maximum Matching

  2021cites this paper
• Sublinear-Time Computation in the Presence of An Online Adversary

  2021cites this paper
• Sublinear-Time Computation in the Presence of Online Erasures

  2021cites this paper
• On Two-Pass Streaming Algorithms for Maximum Bipartite Matching

  2021cites this paper
• Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error

  2021cites this paper
• Almost optimal super-constant-pass streaming lower bounds for reachability

  2021cites this paper
• Beating Two-Thirds For Random-Order Streaming Matching

  2021cites this paper
• L0 Isotonic Regression With Secondary Objectives

  2021cites this paper
• Towards tight bounds for spectral sparsification of hypergraphs

  2020cites this paper
• Isoperimetric inequalities for real‐valued functions with applications to monotonicity testing

  2020cites this paper
• Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms

  2020cites this paper
• Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets

  2020cites this paper
• VC dimension and distribution-free sample-based testing

  2020cites this paper
• Almost Optimal Distribution-Free Sample-Based Testing of k-Modality

  2020cites this paper
• Stochastic matching with few queries: (1-ε) approximation

  2020cites this paper
• Downsampling for Testing and Learning in Product Distributions

  2020cites this paper
• Kruskal-Katona for convex sets, with applications

  2019cites this paper
• Finding Monotone Patterns in Sublinear Time

  2019cites this paper
• Almost Optimal Testers for Concise Representations

  2019cites this paper
• Approximating the distance to monotonicity of Boolean functions

  2019cites this paper
• J an 2 01 9 Almost Optimal Distribution-free Junta Testing

  2019cites this paper
• Almost optimal distribution-free junta testing

  2019cites this paper
• Testing k-Monotonicity: The Rise and Fall of Boolean Functions

  2019influential citation
• Towards Testing Monotonicity of Distributions Over General Posets

  2019influential citation
• Universally Sparse Hypergraphs with Applications to Coding Theory

  2019cites this paper
• Colorings with only rainbow arithmetic progressions

  2019cites this paper
• Testing unateness nearly optimally

  2019cites this paper
• Constant-Query Testability of Assignments to Constraint Satisfaction Problems

  2019influential citation
• BIROn - Birkbeck Institutional Research Online

  2019cites this paper
• The Stochastic Matching Problem with (Very) Few Queries

  2019cites this paper
• Sparse Hypergraphs with Applications to Coding Theory

  2019cites this paper
• Testability of Homomorphism Inadmissibility: Property Testing Meets Database Theory

  2019cites this paper
• Near log-convexity of measured heat in (discrete) time and consequences

  2018cites this paper
• Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions on Hypergrids

  2018cites this paper
• Is your function low dimensional?

  2018cites this paper
• Adaptive Boolean Monotonicity Testing in Total Influence Time

  2018cites this paper
• Near Log-Convexity of Measured Heat in (Discrete) Time and Consequences

  2018cites this paper
• Combinatorial Optimization On Massive Datasets: Streaming, Distributed, And Massively Parallel Computation

  2018cites this paper
• Adaptive Lower Bound for Testing Monotonicity on the Line

  2018cites this paper
• On the Monotonicity Property of the TSK Fuzzy Inference System: The Necessity of the Sufficient Conditions and the Monotonicity Test

  2018cites this paper
• Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

  2018cites this paper
• Is your data low-dimensional?

  2018cites this paper
• Distribution-free junta testing

  2018cites this paper
• Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions

  2018cites this paper
• Testing for forbidden order patterns in an array

  2017cites this paper
• On Estimating Maximum Matching Size in Graph Streams

  2017cites this paper
• A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d

  2017cites this paper
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

  2017cites this paper
• Computing With Distributed Information

  2017cites this paper
• K-Monotonicity is Not Testable on the Hypercube

  2017cites this paper
• Settling the Query Complexity of Non-adaptive Junta Testing

  2017cites this paper
• XX : 3 1 . 1 Parameters and Properties Studied in this Work

  2017cites this paper
• Adaptivity is exponentially powerful for testing monotonicity of halfspaces

  2017cites this paper
• Parameterized Property Testing of Functions

  2017influential citation
• Introduction to Property Testing

  2017cites this paper
• The Stochastic Matching Problem: Beating Half with a Non-Adaptive Algorithm

  2017cites this paper
• U . S . Patent Sep . 14 , 2010 Sheet 1 of 4 US 7 , 797 , 326 B 2 102 Scan Elements Of Data Stream in Single Pass

  2017cites this paper
• Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

  2017cites this paper
• Flipping out with Many Flips: Hardness of Testing k-Monotonicity

  2017cites this paper
• Erasure-Resilient Property Testing

  2016influential citation
• A characterization of constant‐sample testable properties

  2016cites this paper
• Testing Assignments to Constraint Satisfaction Problems

  2016cites this paper
• The Stochastic Matching Problem with (Very) Few Queries

  2016cites this paper
• Testing k-Monotonicity

  2016cites this paper
• An Õ(n) Queries Adaptive Tester for Unateness

  2016cites this paper
• Linear Size Distance Preservers

  2016cites this paper
• On Being Far from Far and on Dual Problems in Property Testing: [Extended Abstract]

  2016cites this paper