scientific article; zbMATH DE number 7559095

DOI10.4230/LIPICS.ITCS.2019.52MaRDI QIDQ5090430zbMATH OpenFDO

Authors Amit Levi, Erik Waingarten

Publication date 18 July 2022

Full work available at URL https://arxiv.org/abs/1805.01074

zbMATH Keywords

Boolean functionsjuntasproperty testingtolerant testing

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• A lower bound for testing juntas
• A tight upper bound for group testing in graphs
• Improved Bounds for Testing Juntas
• Almost optimal distribution-free junta testing
• Tight Bounds on Vertex Connectivity Under Sampling
• scientific article; zbMATH DE number 2097449
• Rejection sampling of bipartite graphs with given degree sequence
• A nonparametric two-sample hypothesis testing problem for random graphs
• Tight Bounds for Testing Bipartiteness in General Graphs
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

Cites work

• L_p-testing
• A \(o(n)\) monotonicity tester for Boolean functions over the hypercube
• A lower bound for testing juntas
• A polynomial lower bound for testing monotonicity
• Adaptivity helps for testing juntas
• Algorithmic and analysis techniques in property testing
• An O(n) queries adaptive tester for unateness
• An o(n) monotonicity tester for Boolean functions over the hypercube
• Approximating the distance to monotonicity in high dimensions
• Approximating the distance to properties in bounded-degree and general sparse graphs
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness
• Estimating the distance to a monotone function
• scientific article; zbMATH DE number 6292744 (Why is no real title available?)
• Improved Bounds for Testing Juntas
• Introduction to Property Testing
• Local reconstructors and tolerant testers for connectivity and diameter
• On being far from far and on dual problems in property testing (extended abstract)
• On sample-based testers
• Optimal unateness testers for real-valued functions: Adaptivity helps
• Property testing and its connection to learning and approximation
• Settling the query complexity of non-adaptive junta testing
• Testing juntas
• Testing juntas nearly optimally
• Testing monotonicity
• Testing probability distributions using conditional samples
• Testing versus Estimation of Graph Properties
• Tolerant junta testing and the connection to submodular optimization and function isomorphism
• Tolerant Linearity Testing and Locally Testable Codes
• Tolerant property testing and distance approximation
• Tolerant testers of image properties
• Tolerant versus intolerant testing for Boolean properties

Cited in

(5)

• A lower bound for testing juntas
• Approximating the distance to monotonicity of Boolean functions
• Sample-based distance-approximation for subsequence-freeness
• Let's try to be more tolerant: on tolerant property testing and distance approximation (invited talk)
• Relative-error testing of conjunctions and decision lists

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090430)