scientific article; zbMATH DE number 7378652
From MaRDI portal
Publication:5009536
DOI10.4230/LIPIcs.APPROX-RANDOM.2018.40zbMath1496.68378arXiv1705.04205MaRDI QIDQ5009536
Karl Wimmer, Elena Grigorescu, Akash Kumar
Publication date: 4 August 2021
Full work available at URL: https://arxiv.org/abs/1705.04205
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monotonicity testing and shortest-path routing on the cube
- Boolean function complexity. Advances and frontiers.
- Property testing lower bounds via communication complexity
- Information theory in property testing and monotonicity testing in higher dimension
- Self-testing/correcting with applications to numerical problems
- Spot-checkers
- A removal lemma for systems of linear equations over finite fields
- Fast approximate PCPs for multidimensional bin-packing problems
- On the strength of comparisons in property testing
- Tolerant property testing and distance approximation
- A Szemerédi-type regularity lemma in abelian groups, with applications
- Alternation, sparsity and sensitivity: combinatorial bounds and exponential gaps
- An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
- Approximating the distance to monotonicity in high dimensions
- Property testing and its connection to learning and approximation
- On the Inversion Complexity of a System of Functions
- Testing monotonicity over graph products
- Monotonicity testing over general poset domains
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Testing for Forbidden Order Patterns in an Array
- Improved Bounds for Testing Forbidden Order Patterns
- An ~O(n) Queries Adaptive Tester for Unateness
- Robust Characterizations of Polynomials with Applications to Program Testing
- Green’s Conjecture and Testing Linear Invariant Properties
- Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
- A unified framework for testing linear‐invariant properties
- Optimal unateness testers for real-valued functions: Adaptivity helps
- Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
- Testing Probability Distributions Underlying Aggregated Data
- A characterization of locally testable affine-invariant properties via decomposition theorems
- L p -testing
- Testing surface area with arbitrary accuracy
- The Power of Negations in Cryptography
- Learning circuits with few negations
- Negation-Limited Formulas.
- A polynomial lower bound for testing monotonicity
- Testing Surface Area
- A o(n) monotonicity tester for boolean functions over the hypercube
- Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids
- Every locally characterized affine-invariant property is testable
- Testing Low Complexity Affine-Invariant Properties
- Testing problems with sublearning sample complexity
- Testing monotonicity
This page was built for publication: