RANDOM-APPROX 2013 saw a bunch of property testing talks.

An optimal lower bound for monotonicity testing over hypergrids (Deeparnab Chakrabarty and C. Seshadhri). I talked about a lower bound for monotonicity testing over hypergrids. Given a function \(f:[n]^d \rightarrow \mathbb{N}\), we wish to test if \(f\) is monotone with respect to the coordinate-wise partial order. We proved a adaptive, two-sided \(\Omega(\varepsilon^{-1} d\log n)\) lower bound, matching recent upper bounds.

Testing Membership in Counter Automaton Languages (Yonatan Goldhirsh and Michael Viderman). In a seminal result, Alon, Krivelevich, Newman, and Szegedy proved that membership in regular languages is testable in constant queries. Can we extend this to richer languages? Lachish and Newman proved that membership in languages given by a pushdown automaton with a single stack symbol (a counter automaton) is not testable with constant queries. Yonathan talked about a weaker version of counter automata, for which membership is testable in constant queries.

Tight lower bounds for testing linear isomorphism (Elena Grigorescu, Karl Wimmer and Ning Xie). Understanding testability of functions that exhibit symmetries (like linear invariances) is an important program in property testing. A function \(f : \{0, 1\}^n \rightarrow \{0, 1\}\) is linear isomorphic to a \(g\) if \(f = g \circ A\), for non-singular transformation \(A\). Ning talked about a lower bound of \(\Omega(n^2)\) for testing if a function is linear isomorphic to the inner product function. (This is tight, as a simple algorithm shows.) In other words, consider the property of functions linear isomorphic to the inner product. This property is not testable in constant queries, suggesting that symmetries themselves do not suffice for (constant) testability.

Local reconstructors and tolerant testers for connectivity and diameter (Andrea Campagna, Alan Guo and Ronitt Rubinfeld). Local reconstructors are like property testers on steroids. Suppose we have access to some function \(f\) that does not satisfy some property \(\mathcal{P}\). A local reconstructor provides oracle access to a function \(g \in \mathcal{P}\) that is (approximately optimally) close to \(f\), and the reconstructor requires only sublinear queries to \(f\) to output a value of \(g\). Alan talked about reconstructors for \(k\)-connectivity in the general sparse-graph model. This also leads to new tolerant testers. Pretty intricate and neat algorithms, IMHO.

A local computation approximation scheme to maximum matching (Yishay Mansour and Shai Vardi). If you put local reconstructors on steroids, you get a local computation algorithm. Consider a graph \(G\), where want to “locally” find a maximum matching. We want a sublinear time procedure that given an edge of \(G\) outputs whether it is part of the matching or not. All these answers must be globally consistent and represent the final matching. Shai talked about a local \(\mathop{poly}(\log n)\) algorithm for finding \((1-\epsilon)\)-approximate matchings. Another impressive local algorithm.

Absolutely Sound Testing of Lifted Codes (Noga Ron-Zewi, Elad Haramaty and Madhu Sudan). Elad talked about more progress on the testing of affine-invariant properties. Previous work define a “lifting operation” for an affine-invariant base code (defined as say a function \(f:\mathbb{F}^t \rightarrow \mathbb{F}\). This is a codeword in many more variables (say a function \(f:\mathbb{F}^n \rightarrow \mathbb{F}\)), whose restriction to any t-dimensional affine subspace belongs to the base code. This paper gives absolutely sound testers for the lift of any affine-invariant base code. This work is a nice way of interpreting (and generalizing) the ideas behind low-degree testing.

To kick off PTReview, we have a (belated!) digest of talks from the Property Testing and Sublinear Time Algorithms workshop held at Haifa, Israel. Eldar Fischer and Ilan Newman hosted a bunch of Property Testing folks in beautiful Haifa, generously funded by the European Research Council under the European Union’s Seventh Framework Programme.

Without further ado, here’s what us at the workshop heard about (with minor editorializing on my part).

Sofya Raskhodnikova (Pennsylvania State University) on Testing Privacy: Sofya talked about algorithms for testing privacy. This is a continuation of work she initiated on connections between property testing and differential privacy. This involves a sort of “average-case” notion of differential privacy and requires property testing for the Lipschitz property for non-uniform distributions. Paper details here.

Gilad Tsur (Weizmann Institute of Science) on Approximate Image and Template Matching: Gilad has a very nice result on using property testing based sampling algorithms to find template matches in images. This is a real, practical vision result (with pretty pictures). I really like this because it takes theoretical ideas to the practical realm, and actually gives an implemented, usable algorithm. Not just putting a story about big data in the introduction and then ignoring it. The theoretical details here, and the practical results here.

Elad Haramati (Technion) on Optimal Testing of Multivariate Polynomials over Small Prime Fields: This is on the classic problem of testing of a function is close to a low-degree polynomial. The natural test is to restrict the function to a random low-dimensional subspace and run a trivial check of whether this restriction is low-degree. Elad talked about an optimal analysis of this tester. Paper here.

Mario Szegedy (Rutgers University) on On the Max-cut Problem: Suppose we had an incidence stream of a graph where we see all edges incident to a vertex together. The aim is to approximate the Max-cut. When a vertex is seen, the algorithm must commit to which side of the cut it is in. Mario discussed an (albeit exponential time) algorithm that can beat the trivial 0.5-approximation. He referred to the general problem as reverse property testing. The algorithm sees (say) 99% of the graph and can do something trivial (say random) here. But it has to do something clever on the remaining 1% to beat the trivial 0.5-approximation. So can we infer something about the 1% from the 99% (as opposed to property testing, where we infer something about the 99% from a random 1%)?

Reut Levi (Tel-Aviv University) on A Quasi-polynomial Time Partition Oracle for Graphs with an Excluded Minor: One of the important tools for property testing on bounded degree graphs is an efficient partition oracle. This is a constant-time local procedure that implicitly partitions the graph into constant sized connected pieces with few edges crossing pieces. A direct consequence of such a procedure is a constant time property testing for minor closed properties. Reut talked about an more efficient partition oracle that runs in time quasipolynomial in \(1/\varepsilon\), a significant improvement over previous work. Paper here.

Asaf Shapira (Tel-Aviv University) on Deterministic vs Non-deterministic Graph Property Testing: A (dense) graph property is non-deterministically testable if there exists a “certificate” whose correctness can be verified in constant time by random sampling. It was earlier shown by Lovasz and Vesztergombi that a non-deterministically testable property is also testable to deterministically testable. Asaf talked about a proof that gives a quantifiable bound on the query complexity. Paper here.

Yonatan Goldhirsh (Technion) on Some Properties are not Even Partially Testable: Consider a property P and a sub-property P’. P’ is called partially testable if inputs in P’ can be distinguished from inputs that are \(\varepsilon\)-far from P. Some natural non-testable properties can be partitioned into a small number of partially testable sub-properties. Is this always true? Yonatan showed us this is not the case, and this requires interesting information theoretic arguments. Paper here.

Arie Matsliah (Google) on On the Power of Conditional Samples in Distribution Testing: The problem of testing distributions is a well-studied problem in property testing. Arie talked about a neat twist on this problem. Suppose the distribution support is known in advance. In addition to simply getting a random sample, we can also get a conditional random sample on any subset of the support. In this model, uniformity testing can be done in constant time (which is known to be impossible in the standard setting). A nice collections of results have been discovered in this framework. Paper here.

Eric Blais (Massachusetts Institute of Technology) on Communication Complexity and Property Testing: beyond the Boolean Hypercube: Blais, Brody, and Matulef had a beautiful paper that uses communication complexity to prove property testing lower bounds. All those bounds were restricted to the Boolean hypercube domain. Eric talked about taking this method to hypergrids, and this requires finding and exploiting the right basis of functions for hypergrids. This leads to the first lower bounds for hypergrid properties. Paper here.

Christian Sohler (Technische Universität Dortmund) on Almost Optimal Canonical Property Testers for Satisfiability: A general class of properties is given by \((k, d)\)-Function-SAT. It can be thought of as a generalized hypergraph coloring problem. Christian’s result is about an almost optimal property tester for dense instances of \((k,d)\)-function-SAT. This is a classic well-studied problem and subsumes many classic graph properties. Paper details here.

Ning Xie (Florida International University) on Testing the Degree Sequence of a Graph: Understanding degree distributions on graphs is a large research area, because of its connections to social networks and the ubiquitous power law/Zipf distributions. Given a fixed degree sequence \(\vec{s}\) and an input graph \(G\), is \(G\) close to any graph with degree sequence? An independent question of interest is: if the degree sequence of \(G\) is close to \(\vec{s}\), is it also close to a graph \(H\) with degree sequence \(\vec{s}\). Ning showed that this not true in general, but does hold for power law degree sequences.

C. Seshadhri (Sandia National Laboratories) on Monotonicity Testing and Alternating Paths: I talked about monotonicity testing of functions on the Boolean hypercube. The main result is that the canonical “edge tester” for monotonicity is optimal. An interesting technique of alternating paths is used in the proof, which generalizes to other properties and hypergrid domains. Paper here.

Ronitt Rubinfeld (Massachusetts Institute of Technology) on Local Decompression: Suppose you zipped 100 files together (through say, gzip) and got a nice compressed representation. Now, you only wanted to read the 50th file. Currently, you would decompress the entire file and read the 50th file (and waste a lot of memory on storing the stuff you don’t want). Can you selectively “locally” decompress a contiguous section of the original input? Awesome question! (Why didn’t I think of that?) Ronitt talked about a locally decompressible version of the famous Lempel-Ziv compression. The aim is to add this new feature without losing much of the LZ compression. This was an actual implemented result that worked on a computer, and I thought that was uber-cool. My favorite talk of the workshop. Paper here.

Sourav Chakraborty (Chennai Mathematical Institute) on Testing of Boolean Function Isomorphism: Two Boolean functions are isomorphic if they are the same up to relabeling of inputs. Determining if two functions are isomorphic is a fundamental property testing problem (or really, area of problems) with a rich host of results. Sourav gave a great survey of the result and a list of tantalizing open questions. In full generality, this problem is hard, but for special subclasses, it is possible. The most prominent open problem is about characterizing functions for which isomorphism is testable.

Dana Ron (Tel-Aviv University) on Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities: A signed majority \(f:\{-1,1\}^n \to \{-1,1\}\) is a function of the form \(f(x) = sign(\sum_i \sigma_i x_i)\), where \(\sigma_i \in \{-1,1\}\). Dana talked about a \(\mathop{poly}(\log n)\) adaptive tester and \(n^{\Omega(1)}\) lower bound for non-adaptive testers. These are both exponential improvements on previous results. I personally liked the algorithmics: most property testers are usually “obvious”, and it’s the analysis that is hard. Here, the algorithm itself was quite non-trivial, and used many tools from previous work. Paper here.

A double feature of Oded Goldreich (Weizmann Institute of Science), On the Communication Complexity Methodology and on Multiple Input Problems: The first part of Oded’s talk was a (re)presentation on the communication complexity method introduced by Blais, Brody, Matulef. Oded argued that there was a cleaner (but equivalent) reductions from communication complexity to property testing. Eric Blais appeared to concur, though it is not clear whether out of politeness or conviction. (Ok, ok, I think Eric actually did agree.) Paper here.

The next part was on direct-sum and direct-product problems in property testing. For example: given multiple inputs, we want to accept if all inputs have the property, and reject if one of them is far from the property. How does this compare with the vanilla problem with one input? Oded talked about this and other variants. Paper here.