On Approximating the Number of Relevant Variables in a Function

DOI10.1007/978-3-642-22935-0_57zbMath1343.68315OpenAlexW2120811043MaRDI QIDQ5894227

Dana Ron, Gilad Tsur

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_57

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items

Property testing lower bounds via communication complexity

Cites Work

• Unnamed Item
• Testing juntas
• Property testing lower bounds via communication complexity
• A lower bound for testing juntas
• Property testing and its connection to learning and approximation
• Improved Bounds for Testing Juntas
• Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem
• On Testing Computability by Small Width OBDDs
• Testing of Clustering
• Testing the diameter of graphs
• Robust Characterizations of Polynomials with Applications to Program Testing
• Testing juntas nearly optimally
• Estimating the unseen
• On Approximating the Number of Relevant Variables in a Function
• Testing problems with sublearning sample complexity