Author Archives: Seshadhri

Open problem for Jan 2014: Explicit lower bound for MAPs

Leave a reply

The open problem of the month is a new feature on PTReview. Every month we put up on open problem contributed by our readers. To know more about getting your problem broadcasted, check out the link “About Open Problem of the Month” at the top of the page.

The first ever open problem post is by Tom Gur on Merlin-Arthur proofs of proximity. This post doubles up a great survey on this new topic. Thanks Tom!

Primary reference: Non-interactive proofs of proximity by Gur and Rothblum, ECCC, 2013.

Basic setting: Recent work by Ron Rothblum and myself [GR13] initiates the study of \(\mathsf{MA}\) proof-system analogues of property testing, referred to as \(\mathsf{MA}\) proofs of proximity (\(\mathsf{MAP}\)s). A proof-aided tester for property \(\Pi\) is given oracle access to an input \(x\) and free access to a proof \(w\). A valid \(\mathsf{MAP}\) demands the following property. Given a proximity parameter \(\epsilon>0\), for inputs \(x \in \Pi\), there exists a proof that the tester accepts with high probability, and for inputs \(x\) that are \(\epsilon\)-far from \(\Pi\) no proof will make the tester accept, except with some small probability of error.

Open problem: Can one show an explicit property where \(\mathsf{MAP}\)s do not give additional power over standard testers? Formally, show an explicit property that requires any \(\mathsf{MAP}\) to make \(\Omega(|x|)\) queries even when given a long (e.g., length \(|x|/100\)) proof?

Background: Goldreich, Goldwasser, and Ron [GGR98] showed that “almost all” properties require probing a constant fraction of the tested object. This limitation was the primary motivation for \(\mathsf{MAP}\)s. Observe that given a sufficiently long proof, every property can be tested very efficiently by an \(\mathsf{MAP}\). Consider a proof that fully describes the object. The tester has free access to the proof, so all it has to do is verify the consistency of the proof and the object (which can be done by only making \(O(1/\epsilon)\) random queries). The tester can check for free that the object described in the proof has the desired property.

Indeed, the name of the game is to construct \(\mathsf{MAP}\)s with short proofs and significantly lower query complexity than standard testers. There exists a property that has an \(\mathsf{MAP}\) using a logarithmic-length proof and only a constant number of queries, but requires nearly linear number of queries for standard testing (see Section 3 of [GR13]).

Nevertheless, \(\mathsf{MAP}\)s with short proofs are far from being omnipotent. A random property requires any \(\mathsf{MAP}\) to perform \(\Omega(n)\) queries (where \(n\) is the length of the input), even when given a \(n/100\) length proof (Section 5 of [GR13]). The open problem is to find an explicit property that matches this lower bound. The best lower bound on explicit properties is far weaker; specifically, Fischer, Goldhirsh, and Lachish [FGL13] showed that testing a certain family of linear codes (namely, codes with “large” dual distance) requires any \(\mathsf{MAP}\) with a proof of length \(p \ge 1\) to make \(\Omega(n/p)\) queries.

References

[FGL13] E. Fischer, Y. Goldhirsh, and O. Lachish. Partial tests, universal tests and decomposability. Innovations in Theoretical Computer Science (ITCS), 2013.

[GGR98] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 1998.

[GR13] T. Gur and R. Rothblum. Non-interactive proofs of proximity. Electronic Colloquium on Computational Complexity (ECCC), 2013.

SODA 2014

Leave a reply

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

Leave a reply

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.

On Quantum Property Testing

Leave a reply

(A guest post by Ashley Montanaro on quantum property testing, a blogpost on his survey. Thanks Ashley!)

Quantum property testing

As readers of this blog will be aware, the field of property testing is a vibrant and active area of research, with hundreds of papers having been written covering a vast range of topics. One direction which has perhaps been underexplored in recent years is the extent to which quantum computers could be useful in property testing. In this blog post, I will briefly discuss some examples of this kind. This is all based on a recent survey of quantum property testing, which is joint work with Ronald de Wolf. For technical details about everything I discuss here, and for references, please see this paper.

There are several ways in which one could generalise the idea of property testing to the quantum world. Perhaps the most obvious way, and the one which I will discuss in this post, is to consider quantum algorithms for testing properties of classical objects, with the goal being to find algorithms which are significantly faster than any possible classical property tester. We use the standard framework of property testing; the only difference is that our tester is allowed to be quantum.

A generalisation in a different direction which I will not discuss here is to testing whether quantum objects of some sort (such as quantum states or operations) have some property. This idea can be split into two cases, the first of which can be thought of as classical testers for quantum properties. While at first sight this idea might not seem to make much sense, in fact it is quite natural. For example, imagine we are given access to a quantum system which is claimed to be in a particular state, and we would like to verify that this is indeed the case. Further imagine that the only access to the system we are allowed is to perform measurements of some form, receiving classical measurement data. The problem of performing this kind of verification has been of both theoretical and practical interest to both physicists and computer scientists. Another, and very general, case we could consider is finding quantum testers for quantum properties. Here ideas and intuition from classical property testing can help develop algorithms for purely quantum tasks. See the survey and references therein for much more about the testing of quantum properties in each of these cases.

Quantum testers for classical properties

Quantum computers offer the prospect of dramatically faster algorithms for certain problems than are possible for classical computers. Property testing is a natural target for such algorithms, for at least a couple of reasons.

First, many of the most famous quantum algorithms known (such as Shor’s algorithm and Grover’s algorithm) operate in the query complexity model. Here the measure of complexity which we try to minimise is the number of queries to bits of the input used to compute some function of the input. Precisely the same model is usually used in property testing.

Second, it is known that quantum computers can only achieve super-polynomial speedups in the query complexity model for computing partial functions; that is, solving problems where we are promised that the algorithm will never receive certain inputs. In a property-testing problem we have such a promise: namely, the input either has some property, or is “far” from having that property.

This gives us hope that quantum algorithms could provide super-polynomial speedups for property-testing problems. However, it is not obvious that the (rather specific) nature of the promise in property testing lends itself to quantum speedup; indeed, it was only in 2002 that the first separation between quantum and classical property testers was demonstrated by Buhrman et al. In fact, this work gave two separations: \(O(1)\) vs. \(\Omega(\log n)\) for testing subsets of Hadamard codewords; and \(O(\log n \log \log n)\) vs. \(\Omega(n)\) for a property-testing variant of Simon’s problem.

Following these initial results, there has been a steady stream of other efficient quantum testers for classical properties. These are often based on applying in the property-testing context a quantum algorithm or primitive which has been useful elsewhere. One simple, and yet sometimes overlooked, way to obtain a more efficient quantum property tester from a classical property tester is via the important primitive of amplitude amplification, which is a more efficient quantum variant of classical probability amplification. Imagine we have a classical property tester for some property \(P\) such that the tester has perfect completeness (i.e. accepts objects with property \(P\) with certainty), uses \(q\) queries, and rejects objects \(\epsilon\)-far from \(P\) with probability \(p\). Then, using amplitude amplification, we obtain a quantum tester which rejects objects \(\epsilon\)-far from \(P\) with constant probability using \(O(q/\sqrt{p})\) queries. (Classical probability amplification would give \(O(q/p)\) queries.) For example, this can be applied to the standard classical tester for linearity of boolean functions to obtain a quantum property tester with constant success probability using \(O(1/\sqrt{\epsilon})\) queries, a quadratic improvement.

Some other examples where quantum algorithms which originated elsewhere have been used as part of efficient quantum property testers include:

  • An algorithm of Chakraborty et al. for a variant of testing periodicity of a sequence, where the quantum algorithm uses \(O(1)\) queries but any classical algorithm must make \(\Omega(n^{1/4})\) queries. The algorithm is based on Shor’s algorithm and the classical lower bound is based on generalising prior work of Lachish and Newman. Quantum testers for periodic functions on groups, and some other group-theoretic properties, had previously been given by Friedl et al..
  • A quantum algorithm of Atici and Servedio for testing \(k\)-juntas (boolean functions depending on at most \(k\) variables) using \(O(k/\sqrt{\epsilon})\) queries, which is a somewhat better complexity than the (later) best known classical bound of \(O(k \log k + k/\epsilon)\). The algorithm is based on the primitive of sampling from the Fourier spectrum of a boolean function, one of the earliest algorithmic ideas in quantum computing. The original algorithm of Atici and Servedio had a linear dependence on \(1/\epsilon\), but this can be improved to a square root using amplitude amplification.
  • The use of quantum counting by Bravyi et al. and Chakraborty et al. to give polynomial speedups for testing a number of properties of probability distributions: whether two distributions are equal, whether a distribution is equal to a fixed distribution, whether two distributions have disjoint support, etc.
  • The use of Ambainis’s efficient quantum algorithm for element distinctness to give polynomial speedups for testing bipartiteness and expansion of bounded-degree graphs. The basic idea here is to use the algorithm to efficiently find collisions in short random walks on the graph.

The last of these highlights an important gap in our knowledge: could there exist an exponential quantum speedup for testing a property of graphs? It is known that for problems with “too much” symmetry, quantum algorithms can achieve only a polynomial speedup over classical algorithms in the query complexity model. Graph properties (being invariant under permutations of the vertices) have an intermediate level of symmetry, and it is not clear whether a super-polynomial speedup is achievable in this setting.

Lower bounds

As well as the development of new quantum algorithms, an integral part of many of the above works demonstrating quantum-classical separations is the proof of new lower bounds on the number of classical queries required for property testing. It is also of interest to prove lower bounds on the quantum query complexity of property testing. This can be a challenging task. Indeed, one of the most successful techniques for proving quantum lower bounds, the adversary method originally introduced by Ambainis, suffers from a “property testing barrier” which prevents its application to property testing problems. This technique has subsequently been generalised to the negative-weight adversary method, which overcomes this barrier and indeed completely characterises quantum query complexity. However, this bound can be difficult to apply in practice and I am not aware of any examples of its use in property testing.

A different technique which has been successfully applied to lower-bound the quantum query complexity of various property testing problems is the method of polynomials. Here the idea is to exploit the fact that the acceptance probability of any quantum algorithm making a small number of queries is a low-degree multivariate polynomial. By proving a lower bound on the degree of any bounded polynomial which takes a large value on inputs with property \(P\), and a small value on inputs far from having property \(P\), we get a lower bound on the number of queries required by any quantum algorithm which tests \(P\).

One example where this idea can be applied is the testing of properties which correspond to linear codes. It turns out that for any code whose dual code has minimum distance \(d\), we get an \(\Omega(d)\) quantum lower bound on the number of queries required to test membership in the code. One such case is the Reed-Muller code of order \(d\), or equivalently the set of degree-\(d\) polynomials over \(F_2\); this argument can be used to show that any quantum algorithm that tests the property of being a degree-\(d\) polynomial must make \(\Omega(2^d)\) queries. Another, and much more complicated, example of the use of this method is a lower bound by Ambainis et al. on the quantum query complexity of testing expansion in graphs, which rules out an exponential quantum speedup for testing this property.

Open questions

The field of quantum property testing is just getting started and there are a number of interesting open questions. In particular, the quantum complexity of testing many properties which have been studied classically is wide open. Some examples include monotonicity, decision tree complexity, and almost all properties of graphs. In some cases, we might hope to find significant (e.g. exponential) speedups over any possible classical tester. The quantum property testers which have been found so far are largely based on applying quantum algorithms which originated elsewhere; but we could also hope to develop entirely new algorithmic techniques to attack these problems.

As well as considering specific problems, there are more wide-ranging questions which could be addressed. Can we achieve significant quantum speedups for testing properties with a high degree of symmetry – and more generally, what can we say about the structure of properties which admit efficient quantum testers? Can we find better (or simpler) lower-bound techniques for quantum property testers? Blais et al. have proven classical lower bounds based on an elegant technique using communication complexity – can their ideas be extended to prove quantum lower bounds based on quantum communication complexity?

Thinking more widely still, the question of just what it is about the structure of certain problems which makes them amenable to quantum speedup is of great interest and far from being resolved. Property testing provides a lens with which to study this question, whether by finding new examples of quantum speedup (or the lack thereof), or by uncovering deeper structural features of properties which determine whether they have efficient quantum testers. In both cases, there is the potential for new developments in quantum property testing to significantly influence quantum algorithmics more generally.

News for November 2013

Leave a reply

The action in November is mainly in algebraic property testing.

On Testing Affine-Invariant Properties by Arnab Bhattacharyya (ECCC). As mentioned here, Arnab put together an excellent survey on testing, ahem, affine-invariant properties. It gives a great overview of this area for a non-expert, and is highly recommended for anyone wanting to get a sense of the existing results and open problems.

Algorithmic Regularity for Polynomials and Applications by Arnab Bhattacharyya, Pooya Hatami, and Madhur Tulsiani (Arxiv). Not a pure property testing paper per se. But you can’t complain about papers related to regularity lemmas in a property testing blog. Think of the Szemerédi regularity lemma as the following: given any partition of a graph, one can “refine” it, so that the resulting partition has “few” pieces and is “regular”. Analogously, the regularity lemma for polynomials says that given any set of polynomials, one can “refine” it to get a “small regular” set of polynomials. This has direct applications in Reed-Muller testing (there’s your property testing connection!). This paper is on giving an algorithm that actually constructs this regular set of polynomials. Among other things, this algorithm can be used in decoding of Reed-Muller codes beyond the list-decoding radius.

Survey on Testing Affine-Invariant Properties

Leave a reply

Arnab has put together a wonderful survey on testing affine-invariant properties (ECCC). Consider functions \(f:\mathbb{F}^n_p \to R\) (where \(R\) is usually a finite range). A property is called affine-invariant if it closed under affine transformations of the domain. The classic example of such a property is that of being a low-degree polynomial. This is a very rich and beautiful area of research, with the initial inspiration being work in trying to understand what makes a property testable. I will also add that this is a deep (somewhat inaccessible to the non-expert?) area of research, so thanks Arnab for this excellent survey!

News for August 2013

Leave a reply

August saw a couple of conferences: RANDOM-APPROX and a seminar at the Simon’s institute. Here’s a report on the new papers we saw in August, including much progress on distribution testing.

On sample based testers by Oded Goldreich and Dana Ron (ECCC).The usual setting for property testing is beloved query model, where the tester gets to make any query it pleases. A much weaker setting would be to simply get random (labeled) samples of the domain. These are called sample based testers, and are more akin to setting in learning theory. Sampled based testers were also discussed in the seminal Goldreich, Goldwasser, and Ron paper. Since then, there have been variants, such as distribution-free testing and active testing. In this paper, it is shown that constant-query proximity-oblivious testers imply the existence of sublinear (polynomial dependence in size) sample based testers.

Instance-by-instance optimal identity testing by Gregory Valiant and Paul Valiant (ECCC). The problem of distribution testing is a problem that we all love. Given a known discrete distribution \(p\), we wish to test equality (with \(p\)) of an unknown distribution \(q\). How many independent samples are required of \(q\)? This paper gives an optimal algorithm for each distribution \(p\), subsuming much past work. The analysis involves a characterization of Hölder and norm-monotonicity type inequalities. Definitely on my list to read!

Optimal algorithms for testing closeness of discrete distributions by Siu-On Chan, Ilias Diakonikolas, Gregory Valiant, Paul Valiant (Arxiv). Now consider the setting where both \(p\) and \(q\) are unknown (over a support of size \(n\)), and we wish to test equality. (We define “far” in terms of variation distance.) A (by-now) classic paper of Batu et al. gives an \(O(n^{2/3}\log n/\varepsilon^{8/3})\) and Valiant proved an \(\Omega(n^{2/3})\) lower bound. This paper completely resolves this problem problem with an algorithm and matching lower bound of \(\max(n^{2/3}/\varepsilon^{4/3}, n^{1/2}/\varepsilon^2)\).

Aug 21-23: RANDOM-APPROX 2013

1 Reply

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.

June 17-18, 2013: Property Testing and Sublinear Time Algorithms, at Haifa

1 Reply

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.