News for July 2013

Helly-Type Theorems in Property Testing by Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy, and Shubhangi Saraf (arXiv). Helly’s Theorem states that if every \(d+1\) sets in a family \(F\) of convex sets in \(\mathbb{R}^d\) have non-empty intersection, then the intersection of the whole family \(F\) is also non-empty. This paper establishes a new connection between Helly’s theorem and clustering problems. Specifically, extensions of Helly’s theorem are used to analyze algorithms that test whether a set of points can be partitioned into a small number of clusters or not.

On active and passive testing by Noga Alon, Rani Hod, and Amit Weinstein (arXiv). In the standard property testing setting, the tester is able to query any input it chooses. This model is unrealistic in some settings, where instead it is more appropriate to consider models where the tester can only choose queries from a restricted set of the inputs (active testing) or where the tester only sees bits sampled at random from the input (passive testing). This paper gives new upper and lower bounds on the number of queries required to test many natural properties of boolean functions—including juntas, partially symmetric functions, and low degree polynomials—in these two settings.

Explicit Maximally Recoverable Codes with Locality by Parikshit Gopalan, Cheng Huang, Bob Jenkins, and Sergey Yekhanin (ECCC). The central goal in the study of locally decodable codes is to maintain the rate and error tolerance while adding the condition that we can recover any bit of the original input with a small number of queries to the codeword. This paper considers and makes progress on an interesting relaxation of this problem: here the goal is to maintain local decoding when a small number of errors are introduced, while allowing more queries to be made to decode input bits when more errors occur.

Leave a Reply

Your email address will not be published.

Time limit is exhausted. Please reload the CAPTCHA.