Six papers for May, including new models, hierarchy theorems, separation results, resolution of conjectures, and a lot more fun stuff. A lot of things to read this month!

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs, by Amit Levi and Erik Waingarten (ECCC). This paper proves a number of new lower bounds for tolerant testing of Boolean functions, including non-adaptive \(k\)-junta testing and adaptive and non-adaptive unateness testing. Combined with upper bounds for these and related problems, these results establishes separation between the complexity of tolerant and non-tolerant testing for natural properties of Boolean functions, which have so far been elusive. As a technical tool, the authors introduce a new model for testing graph properties, termed the rejection sampling model. In this model, the algorithm queries a subset \(L\) of the vertices, and the oracle will sample an edge uniformly at random and output the intersection of the edge endpoints with the query set \(L\). The cost of an algorithm is measured as the sum of the query sizes. In order to prove the above lower bounds (in the standard model), they show a non-adaptive lower bound for testing bipartiteness (in their new model).

Hierarchy Theorems for Testing Properties in Size-Oblivious Query Complexity, by Oded Goldreich (ECCC). This work proves a hierarchy theorem for properties which are independent of the size of the object, and depend only on the proximity parameter \(\varepsilon\). Roughly, for essentially every function \(q : (0,1] \rightarrow \mathbb{N}\), there exists a property for which the query complexity is \(\Theta(q(\varepsilon))\). Such results are proven for Boolean functions, dense graphs, and bounded-degree graphs. This complements hierarchy theorems by Goldreich, Krivelevich, Newman, and Rozenberg, which give a hierarchy which depends on the object size.

Finding forbidden minors in sublinear time: a \(O(n^{1/2+o(1)})\)-query one-sided tester for minor closed properties on bounded degree graphs, by Akash Kumar, C. Seshadhri, and Andrew Stolman (ECCC). At the core of this paper is a sublinear algorithm for the following problem: given a graph which is \(\varepsilon\)-far from being \(H\)-minor free, find an \(H\)-minor in the graph. The authors provide a (roughly) \(O(\sqrt{n})\) time algorithm for such a task. As a concrete example, given a graph which is far from being planar, one can efficiently find an instance of a \(K_{3,3}\) or \(K_5\) minor. Using the graph minor theorem, this implies analogous results for any minor-closed property, nearly resolving a conjecture of Benjamini, Schramm and Shapira.

Learning and Testing Causal Models with Interventions, by Jayadev Acharya, Arnab Bhattacharyya, Constantinos Daskalakis, and Saravanan Kandasamy (arXiv). This paper considers the problem of learning and testing on causal Bayesian networks. Bayesian networks are a type of graphical model defined on a DAG, where each node has a distribution defined based on the value of its parents. A causal Bayesian network further allows “interventions,” where one may set nodes to have certain values. This paper gives efficient algorithms for learning and testing the distribution of these models, with \(O(\log n)\) interventions and \(\tilde O(n/\varepsilon^2)\) samples per intervention

Property Testing of Planarity in the CONGEST model, by Reut Levi, Moti Medina, and Dana Ron (arXiv). It is known that, in the CONGEST model of distributed computation, deciding whether a graph is planar requires a linear number of rounds. This paper considers the natural property testing relaxation, where we wish to determine whether a graph is planar, or \(\varepsilon\)-far from being planar. The authors show that this relaxation allows one to bypass this linear lower bound, obtaining a \(O(\log n \cdot \mathrm{poly(1/\varepsilon))}\) algorithm, complemented by an \(\Omega(\log n)\) lower bound.

Flexible models for testing graph properties, by Oded Goldreich (ECCC). Usually when testing graph properties, we assume that the vertex set is \([n]\), implying that we can randomly sample nodes from the graph. However, this assumes that the tester knows the value of \(n\), the number of nodes. This note suggests more “flexible” models, in which the number of nodes may be unknown, and we are only given random sampling access. While possible definitions are suggested, this note contains few results, leaving the area ripe for investigation of the power of these models.