Our press release this month features five papers: four of them are squarely property testing papers, and a fifth which I could not, in good conscience, bring myself to omit. Let us take a look: a paper that carries the submodularity testing story from two labels up to \(k\) of them; a striking super-polynomial quantum advantage for tolerant junta testing; a sublinear tester that decides whether a mystery multiplication table is an abelian group; and a rather pretty reworking of the Goldreich-Ron bipartiteness tester through the Max-Cut SDP. And then, saved for last, a rare treat that settles a question which has stood open since the 1980s, namely that bipartite matching is in NC. Without further ado, let us examine our spread.

Testing k-submodularity by Themistoklis Haris and Diptaksho Palit (arXiv) Let us begin where this story usually begins, with the question posed by Seshadhri and Vondrák in Is submodularity testable?: given oracle access to \(f \colon \{0,1\}^n \to \mathbb{R}\), can we distinguish submodular functions from those that are \(\varepsilon\)-far from every submodular function? Building up on a reduction to testing monotonicity over unbounded ranges, the authors exhibited a lower bound of \(\Omega(n)\) queries for testing submodularity. Blais and Bommireddi moved the question into the \(\ell_p\)​-testing model in Testing submodularity and other properties of valuation functions, where they obtained constant-query-complexity testers. The featured paper considers the following variation: take a partial partition of the ground set into \(k+1\) parts–eg, a string in \([k+1]^n\). Think of the last part as the elements unassigned so far (the “partial” in the “partial partition”). A function on these partial partitions is \(k\)-submodular if the marginal gains diminish no matter which part an element is assigned to. The main result of the paper, following in the tracks laid out by Blais-Bommireddi, presents constant-query-complexity testers for \(k\)-submodularity in \(\ell_p\) distance.

Quantum Advantage in Tolerant Junta Testing by Avishay Tal and Weiqiang Yuan (arXiv) Recall the tolerant junta testing problem: given parameters \((k, \varepsilon_1​, \varepsilon_2​)\) with \(0\leq \varepsilon_1 ​< \varepsilon_2 ​\leq 1/2\) and black-box access to a Boolean \(f\) on \(n\) variables, decide whether \(f\) is \(\varepsilon_1\)​-close to some \(k\)-junta or \(\varepsilon_2\)​-far from every \(k\)-junta. Our July 2016 News reported a result which presented tolerant testers with query complexity exponential in \(k\). Additionally, despite our research efforts, getting a good understanding of the query complexity of adaptive testers for tolerant junta testers has been out of reach.

The featured paper picks up on this investigation thread and establishes the first super-polynomial quantum advantage for this problem in the adaptive setting. The main result is a non-adaptive quantum toleratnt tester with query complexity growing as \(poly(k, 1/\varepsilon)\). On the other hand, the main result also proves that any adaptive, tolerant tester must cough up a number of queries that grows like \(k^{\Omega(\log{1/\varepsilon} )}\).

Sublinear Time Algorithms for Abelian Group Property Testing by Nader H. Bshouty (arXiv) You are given a finite set \(G\) and oracle access to a binary operation \(\ast \colon G^2 \to G\), and you want to decide whether $latex(G,\ast)$ is an abelian group or is \(\varepsilon\)-far from every abelian group over \(G\). The paper considers two access models: in the partially specified model the algorithm does not know \(|G|\) and only sees randomly sampled elements together with the Cayley table restricted to those elements, and in the fully specified model it knows \(|G|\) and has access to the full table. The main result is a tester in the weaker PS-model (and hence in the FS-model) which runs in time \(\widetilde{O}(\sqrt{|G|}​+1/\varepsilon)\), improving on testers of Goldreich and Tauber which run in time $latexO(|G|/\varepsilon)$.

Testing Bipartiteness in Logarithmic Rounds by Yumou Fei and Ronitt Rubinfeld (arXiv) Recall the seminal Goldreich-Ron tester for bipartiteness of bounded-degree graphs, which runs \(\widetilde{O}(\sqrt n)\) random walks of length \(O(\log^6 n)\) each and rejects when it discovers an odd cycle. The featured paper shows that \(O(\sqrt n​)\) walks of length \(O(\log n)\) already suffice. The proof departs from the Goldreich-Ron analysis and instead routes the argument through the Goemans-Williamson SDP relaxation for Max-Cut. As a corollary, the paper obtains an \(O(\log n)\)-pass, \(O(\sqrt n \cdot ​logn)\)-space streaming algorithm for testing bipartiteness, and the pass complexity is optimal thanks to a recent lower bound of Fei, Minzer and Wang. Looks like a great read before the new term rolls in.

And now, as promised, a result which is not property testing at all, but which I could not skip over.

Bipartite Matching is in NC by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj and Thomas Thierauf (ECCC) Whether the randomness in the Mulmuley-Vazirani-Vazirani RNC algorithm for matching can be removed is a question that has stood since the 1980s, with the state of the art being the quasi-NC bounds of Fenner-Gurjar-Thierauf for bipartite graphs and Svensson-Tarnawski for general graphs. The featured paper settles the bipartite case: bipartite matching is in NC. The techniques are based on the polynomial method, inspired by the subspace design construction of Guruswami and Kopparty. The result extends to weighted bipartite matching and to computing the noncommutative rank of a symbolic matrix, and as a consequence the decision version of linear matroid intersection lands in NC as well. As a curious aside, in a talk by Rohit Gurjar (one of the authors), I learnt a fact that I found rather remarkable.
Take two univariate polynomials \(\boldsymbol{p}, \boldsymbol{q} \in \mathbb{R}[X]_{\leq d}\), each of degree $d$. Suppose these polynomials are linearly independent, so that \(span(\boldsymbol{p}, \boldsymbol{q})\) is a two-dimensional space of polynomials of degree at most \(d\). Consider the following set of real numbers: \(S_1 = \{ \alpha \in \mathbb{R} : \boldsymbol{f}(\alpha) = 0 \text{ for some } \boldsymbol{f} \in span(\boldsymbol{p}, \boldsymbol{q}) \}. \) That is, \(S_1\) collects those reals that happen to be a root of some polynomial hiding in the span; call these the roots of the span. One notes that \(S_1\) contains infinitely many elements. So far so good. Next, consider the set \(S_2 = \{ \alpha \in \mathbb{R} : \alpha \text{ is a root of some } \boldsymbol{f} \in span(\boldsymbol{p}, \boldsymbol{q}) \text{ with multiplicity } 2 \}. \) Somewhat surprisingly (to me), \(S_2\) is a finite set, and in fact \(|S_2| \leq 2d\).