Oded Goldreich has posted an excellent summary of the recent Sublinear Algorithms Workshop, at Johns Hopkins University.

A list of open problems from the workshop has been compiled at our “mother” site, sublinear.info.

Leave a reply

Oded Goldreich has posted an excellent summary of the recent Sublinear Algorithms Workshop, at Johns Hopkins University.

A list of open problems from the workshop has been compiled at our “mother” site, sublinear.info.

SODA 2014 had a bunch of property testing papers, all but one of which have been covered by our monthly reports. (This, arguably, shows that the monthly reports have some value.) I’ll just give the list of papers, and only give a summary for the “new” papers.

**Testing equivalence between distributions using conditional samples** by Clément Canonne, Dana Ron and Rocco A. Servedio

**Optimal Algorithms for Testing Closeness of Discrete Distributions** by Siu On Chan, Ilias Diakonikolas, Gregory Valiant and Paul Valiant

**Testing Surface Area** by Chenggang Wu, Ryan O’Donnell, Amir Nayyeri, and Pravesh Kothari

**Hereditary properties of permutations are strongly testable** by Tereza Klimosova and Daniel Kral (Arxiv). This papers solves an important open problem in permutation testing, and shows that all hereditary properties of permutations are testable, when the distance is given by the Kendall-Tau metric. Such a result was already known for the rectangular metric. The Kendall-Tau metric is the right analogue to the standard edit distance for graph properties, and so this result becomes the analogue of testing of hereditary graph properties.

ITCS 2014 had a nice selection of property testing papers, some of which were covered in our monthly posts. One of our reporters was around, and sent us this report.

**Partial tests, universal tests and decomposability** by Eldar Fischer, Oded Lachish and Yonatan Goldhirsh. Yonathan talked about the notion of “partial testing”, where one wishes to test a subproperty of a property. This paper has results on when properties cannot be decomposed in testable subproperties, and, as Yonathan hinted at, uses sunflowers! This work is related to recent work of Gur and Rothblum on Merlin-Arthur proofs of proximity.

**High Dimensional Expanders and Property Testing** by Tali Kaufman and Alexander Lubotsky. Consider a function \(f\) on the vertices of a graph and suppose we wish to check if \(f\) is constant. The simple edge tester queries an edge and checks if both endpoints have distinct values. The success probability of this tester is the expansion of the graph. This paper generalizes this notion to high-dimensional simplicial complices, and this gives a tester for the tensor power property.

**Parameterized Testability** by Kazuo Iwama and Yuichi Yoshida. Many NP-hard problems are fixed-parameter tractable (FPT). Determining if a graph has a vertex cover of size \(k\) can be done in \(O(poly(n)) + 2^k\) time, as opposed to the trivial \(n^k\) bound. Yuichi talked about getting fixed-parameter *testing* algorithms, where the tester is constant when the property parameter is constant. The paper has a number of results, notably testing algorithms for \(k\)-vertex feedback set and \(k\)-path freeness.

The new Simons Institute for the Theory of Computing opened its doors this August, and kicked things off with a workshop on real analysis and its applications in property testing, learning theory, and inapproximability. Among many great talks (see here for the full schedule) were the following presentations on property testing and related topics.

Ryan O’Donnell on **Testing Surface Area**. Given a subset \(S \in [0,1]^2\) of the unit square, can we efficiently test whether the set has small perimeter? Buffon’s needle suggests a natural test: drop a (small) needle at random in the square and see if exactly one of its endpoints lands in the set \(S\). Ryan showed how elegant noise sensitivity arguments show the correctness of this test and its higher-dimensional analogues.

I gave a talk on **The Analysis of Partially Symmetric Functions**. I gave a brief introduction to partially symmetric functions, tools from the analysis of boolean functions that help us understand them, and their role in theoretical computer science, with a particular emphasis on the function isomorphism testing conjecture.

Hamed Hatami on **Testing Affine-Invariant Properties of Algebraic Functions**. Hamed gave a fascinating survey of the recent progress on testing affine-invariant properties. He showed how the tools that have been used to analyze the testability of properties of graphs can be combined with tools from higher-order Fourier analysis of boolean functions to analyze the testability of algebraic properties of functions.

Parikshit Gopalan on **Locally Testable Codes and Cayley Graphs**. Despite a considerable amount of interest and attention, many fundamental questions regarding locally testable codes remain open. Parikshit’s talk gave a very nice connection between LTCs and some Cayley graphs which enables us to view LTCs from a different angle and will hopefully lead to further progress on these open problems.

Nati Linial on **Local Combinatorics, Or: What to do with all those gigantic graphs?**. Let’s say that you want to keep a snapshot of a huge graph \(G\), but only have a very small amount of space available. What can you do? One natural solution is to keep a *local k-profile* of the graph: for each graph \(H\) on \(k\) vertices, count the number of embedded copies of \(H\) in \(G\). Nati’s talk showed that the study of the connections between local k-profiles of graphs and global properties of graphs leads to very nice results as well as a wealth of intriguing open problems.

Many other interesting workshops on real analysis in computer science and on the theoretical foundations of big data analysis will be held throughout the semester. See the respective pages for all the details, and for videos of the talks.

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.