Exponentially improved algorithms and lower bounds for testing signed majorities
From MaRDI portal
Publication:2354020
DOI10.1007/s00453-013-9858-0zbMath1322.68260OpenAlexW2116035124MaRDI QIDQ2354020
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
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)
Related Items
An adaptivity hierarchy theorem for property testing, Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Monotonicity testing and shortest-path routing on the cube
- Testing juntas
- Property testing. Current research and surveys
- Testing computability by width-two OBDDs
- Information theory in property testing and monotonicity testing in higher dimension
- Refinement of the upper bound of the constant in the central limit theorem
- Self-testing/correcting with applications to numerical problems
- Lower Bounds for Testing Computability by Small Width OBDDs
- Testing Halfspaces
- Testing low-degree polynomials over prime fields
- Property testing and its connection to learning and approximation
- Testing Polynomials over General Fields
- Testing monotonicity over graph products
- Improved Bounds for Testing Juntas
- Testing Reed–Muller Codes
- Monotonicity testing over general poset domains
- On Testing Computability by Small Width OBDDs
- Testing ±1-weight halfspace
- Projection constants of symmetric spaces and variants of Khintchine's inequality
- Testing Basic Boolean Formulae
- Testing juntas nearly optimally
- lgorithmic and Analysis Techniques in Property Testing
- Testing Fourier Dimensionality and Sparsity
- Concentration of Measure for the Analysis of Randomized Algorithms
- Testing monotonicity
