Exponentially improved algorithms and lower bounds for testing signed majorities

DOI10.1007/S00453-013-9858-0MaRDI QIDQ2354020zbMATH OpenOpenAlexFDO

Authors Dana Ron, Rocco A. Servedio

Publication date 10 July 2015

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-013-9858-0

zbMATH Keywords

majority functionproperty testinglinear threshold function

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Exponentially improved algorithms and lower bounds for testing signed majorities
• A polynomial lower bound for testing monotonicity
• A polynomial lower bound for testing monotonicity
• Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries
• Improved Bounds for Testing Juntas

Cites work

• scientific article; zbMATH DE number 1819631 (Why is no real title available?)
• scientific article; zbMATH DE number 1418269 (Why is no real title available?)
• scientific article; zbMATH DE number 5485570 (Why is no real title available?)
• Algorithmic and analysis techniques in property testing
• Concentration of Measure for the Analysis of Randomized Algorithms
• Improved Bounds for Testing Juntas
• Information theory in property testing and monotonicity testing in higher dimension
• Lower Bounds for Testing Computability by Small Width OBDDs
• Monotonicity testing and shortest-path routing on the cube
• Monotonicity testing over general poset domains
• On testing computability by small width OBDDs
• Projection constants of symmetric spaces and variants of Khintchine's inequality
• Property testing and its connection to learning and approximation
• Property testing. Current research and surveys
• Refinement of the upper bound of the constant in the central limit theorem
• Self-testing/correcting with applications to numerical problems
• Testing Basic Boolean Formulae
• Testing Fourier dimensionality and sparsity
• Testing Halfspaces
• Testing Polynomials over General Fields
• Testing Reed–Muller Codes
• Testing computability by width-two OBDDs
• Testing juntas
• Testing juntas nearly optimally
• Testing low-degree polynomials over prime fields
• Testing monotonicity
• Testing monotonicity over graph products
• Testing ±1-weight halfspace

Cited in

(3)

• Adaptivity is exponentially powerful for testing monotonicity of halfspaces
• Exponentially improved algorithms and lower bounds for testing signed majorities
• An adaptivity hierarchy theorem for property testing

This page was built for publication: Exponentially improved algorithms and lower bounds for testing signed majorities

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