Publication:4638079
From MaRDI portal
DOI10.4230/LIPIcs.ITCS.2017.29zbMath1402.68192arXiv1609.00265MaRDI QIDQ4638079
Elena Grigorescu, Akash Kumar, Clément L. Canonne, Siyao Guo, Karl Wimmer
Publication date: 3 May 2018
Full work available at URL: https://arxiv.org/abs/1609.00265
Computational learning theory (68Q32) Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30) Randomized algorithms (68W20)
Related Items
Unnamed Item, Erasure-Resilient Property Testing, Almost Optimal Distribution-Free Sample-Based Testing of k-Modality, Earthmover Resilience and Testing in Ordered Structures, Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity, Unnamed Item
Cites Work
- 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
- Learning regular sets from queries and counterexamples
- Spot-checkers
- Fast approximate PCPs for multidimensional bin-packing problems
- On learning monotone DNF under product distributions
- On the strength of comparisons in property testing
- Tolerant property testing and distance approximation
- An $o(n)$ Monotonicity Tester for Boolean Functions over the Hypercube
- Approximating the distance to monotonicity in high dimensions
- Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
- On the Inversion Complexity of a System of Functions
- Learning Monotone Decision Trees in Polynomial Time
- Testing monotonicity over graph products
- Agnostically Learning Halfspaces
- Monotonicity testing over general poset domains
- A theory of the learnable
- Cryptographic limitations on learning Boolean formulae and finite automata
- Monotone circuits for matching require linear depth
- On the Fourier spectrum of monotone functions
- On Monotonicity Testing and Boolean Isoperimetric-type Theorems
- Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
- Analysis of Boolean Functions
- Testing Probability Distributions Underlying Aggregated Data
- KKL, Kruskal-Katona, and Monotone Nets
- 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
- A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
- Testing problems with sublearning sample complexity
- Testing monotonicity
