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 December 2013

Leave a reply

 

Here’s a report on the new papers we saw in December 2013.

Property Testing on Linked Lists by Peyman Afshani, Kevin Matulef and  Bryan T. Wilkinson (ECCC). Monotonicity testing has been an important problem for past many years. In the usual settings either the input is accessed by random sampling or the input is given in an easy to access form (like an array). In this paper they have consider a model which is somewhere in the middle of the other two models. Here the input is given as an linked list. They have shown that, in this model, monotonicity testing requires Θ(n^{1/3}) queries.

Direct Product Testing by Irit Dinur and David Steurer (ECCC).  In this paper they have considered the problem “Does there exist a two-query test that distinguishes between direct products and functions that are far from direct products with constant probability?” This is a very important problem that has application in gap amplification in PCP. They answer the question in the affirmative.

Property-Testing in Sparse Directed Graphs: 3-Star-Freeness and Connectivity by  Frank Hellweg and Christian Sohler (ArXiv).  There are different models, for querying, in the case of property testing in sparse directed graphs.  In one such model, proposed by Bender and Ron, only the outgoing edges are queried.  In this paper upper bounds on the query complexity for testing subgraph freeness and strong connectivity has been obtained.

High Dimensional Expanders and Property Testing by Tali Kaufman and Alexander Lubotzky (ArXiv).   Expanders have always played an important role in property testing. Usually expanders are either used for designing testers or proving correctness of testers. We sometimes test for expansion property also. In this paper they have linked expansion property of some structure to testability of some other property. They study the higher dimensional expansion property, as studied by Gromov, Linial and Meshulam. They show that a simplicial complex is a high dimensional expander if and only if a suitable property is testable.

 

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 October 2013

Leave a reply

We saw two new property testing papers in October. During the month, we also saw a great presentation on estimating the distance to testable affine-invariant properties (discussed here) at FOCS, and we saw some intriguing property testing papers in the list of accepted papers for ITCS 2014.

Survey on Quantum Property Testing by Ashley Montanaro and Ronald de Wolf (arxiv). We already mentioned this survey here, but it is worth discussing it again. With a clear presentation of fundamental results in the area, this survey is a great reference for any researcher in property testing or in quantum complexity that wants to learn about the intersection of the two fields. And with 12 open questions presented throughout the text, this is also the ideal starting point for any researcher who wants to jump into the area.

Property Testing Bounds for Linear and Quadratic Functions via Parity Decision Trees by Abhishek Bhrushundi, Sourav Chakraborty, and Raghav Kulkarni (ECCC). The authors observe that the problem of testing a property \(P\) of linear or quadratic boolean functions is equivalent to determining the parity decision tree complexity of a function \(f\) determined by \(P\). This connection is used to obtain strong lower bounds on the query complexity required to test \(k\)-linearity, bent functions, and other related properties. It also provides further motivation for the the study of parity decision trees and the related problems on the Fourier structure of boolean functions.

 

News for September 2013

Leave a reply

Here’s a report on the new papers we saw in September. The list of accepted papers in SODA 2014 also came out in September. While we have covered one of the accepted papers in our “News for August 2013″ post we look at two more accepted paper in this post.

Non-Interactive Proofs of Proximity by Tom Gur and Ron D. Rothblum (ECCC). In a proof-systems a verifier tries to ascertain the validity of a statement by using the help of a proof. PCP, PCPP are classical examples of proof-systems. The kind of access a verifier has to the statement and the proof determines the power of the proof system. This paper considers the proof system when the verifier has full access to the proof (which is sub-linear) and oracle access to the statement. And the goal of the verifier is to accept a valid statement and reject a statement that is far from true while optimizing the queries to the statement. This paper tries to understand the power of this proof system (in terms of query complexity) in comparison to other proof systems.

Testing Surface Area by Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell and Chenggang Wu (accepted in SODA 2014) [preprint].  Estimating the surface area of a set  F ⊆ Rn given point-query access is a very fundamental problem in geometry. Usually one assumes some structure on the surface for estimating the area, like convexity. This paper considers general surface areas and the goal is to distinguish the case when the surface area is less than A from the case when the surface is far from having a surface area less than κA (κ a parameter ≥1). In the 1, 2 or 3 dimension constant query algorithm is obtained for certain κ.

A connection between surface area and noise sensitivity by Joe Neeman (ArXiv). This paper also considers the problem of estimating the surface area of a set. It improves some of the results from the above mentioned paper – “Testing Surface Area” by Pravesh Kothari, Amir Nayyeri, Ryan O’Donnell and Chenggang Wu.

Testing equivalence between distributions using conditional samples by Clement Canonne, Dana Ron and Rocco A. Servedio (accepted in SODA 2014) [preprint]. Testing whether two distributions are equivalent is an important and well studied problem. Usually a distribution is accessed by drawing random samples according to the distribution. But other variants of how to access the distributions has also been studied. One such is the conditional query: here one can specify a set S and draws a random sample according to the distribution conditioned on the fact that outcome comes from S.  This paper shows that conditional queries can help in improving the query complexity by an exponential amount (or more) for testing equivalence of distributions (both when one distribution is known and when none of them are known). Some restricted versions of conditional queries (where the size of S is fixed) have also been studied.

 

Aug. 26-30: Real Analysis in Testing, Learning and Inapproximability at the Simons Institute

Leave a reply

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.