Author Archives: Gautam Kamath

News for August 2019

A comparatively slow month, as summer draws to a close: we found three papers online. Please let us know if we missed any! (Edit: And we added two papers missed from June.)

Testing convexity of functions over finite domains, by Aleksandrs Belovs, Eric Blais, and Abhinav Bommireddi (arXiv). This paper studies the classic problem of convexity testing, and proves a number of interesting results on the adaptive and non-adaptive complexity of this problem in single- and multi-dimensional settings. In the single-dimensional setting on domain \([n]\), they show that adaptivity doesn’t help: the complexity will be \(O(\log n)\) in both cases. However, in the simplest two-dimensional setting, a domain of \([3] \times [n]\), they give a polylogarithmic upper bound in the adaptive setting, but a polynomial lower bound in the non-adaptive setting, showing a strong separation. Finally, they provide a lower bound for \([n]^d\) which scales exponentially in the dimension. This leaves open the tantalizing open question: is it possible to avoid the curse of dimensionality when testing convexity?

Testing Isomorphism in the Bounded-Degree Graph Model, by Oded Goldreich (ECCC). This work investigates the problem of testing isomorphism of graphs, focusing on the special case when the connected components are only polylogarithmically large (the general bounded-degree case is left open). One can consider when a graph is given as input, and we have to query a graph to test if they are isomorphic. This can be shown to be equivalent (up to polylogarithmic factors) to testing (from queries) whether a sequence is a permutation of a reference sequence. In turn, this can be shown to be equivalent to the classic distribution testing question of testing (from samples) whether a distribution is equal to some reference distribution. The same sequence of equivalences almost works for the case where there is no reference graph/sequence/distribution, but we only have query/query/sample access to the object. The one exception is that the reduction doesn’t work to reduce from testing distributions to testing whether a sequence is a permutation, due to challenges involving sampling with and without replacement. However, the author still shows the lower bound which would be implied by such a reduction by adapting Valiant’s proof for the distribution testing problem to this case.

Learning Very Large Graphs with Unknown Vertex Distributions, by Gábor Elek (arXiv). In this note, the author studies a variant of distribution-free property testing on graphs, in which (roughly) neighboring vertices have probabilities of bounded ratio, and a query reveals this ratio. Applications to local graph algorithms and connections to dynamical systems are also discussed.

EDIT: We apparently missed two papers from June — the first paper was accepted to NeurIPS 2019, the second to COLT 2019.
The Broad Optimality of Profile Maximum Likelihood, by Yi Hao and Alon Orlitsky (arXiv). Recently, Acharya, Das, Orlitsky, and Suresh (ICML 2017) showed that the Profile Maximum Likelihood (PML) estimator enables a unified framework for estimating a number of distribution properties, including support size, support coverage, entropy, and distance to uniformity, obtaining estimates which are competitive with the best possible. The approach is rather clean: simply estimate the PML of the distribution (i.e., the maximum likelihood distribution of the data, if the the labels are discarded and only the multiplicities of elements are kept), and apply the plug-in estimator (i.e., if you want to estimate entropy, compute the entropy of the resulting PML distribution). The present work shows that PML is even more broadly applicable — such an approach applies to any property which is additive, symmetric, and appropriately Lipschitz. They also show specific results for many other properties which have been considered in the past, including Rényi entropy, distribution estimation, and identity testing.

Sample-Optimal Low-Rank Approximation of Distance Matrices by Piotr Indyk, Ali Vakilian, Tal Wagner, David Woodruff (arXiv). Getting a rank \(k\) approximation of an \(n \times m\) matrix \(M\) is about as classic a problem as it gets. Suppose we wanted a running time of \(O(n+m)\), which is sublinear in the matrix size. In general, this is not feasible, since there could be a single large entry that dominates the matrix norm. This paper studies the case where the matrix is itself a distance matrix. So there is an underlying point set in a metric space, and the \(i, j\)th entry of \(M\) is the distance between the $i$th and $j$th point. Previous work showed the existence of \(O((n+m)^{1+\gamma})\) time algorithms (for arbitrary small constant $\gamma > 0$, with polynomial dependence on \(k\) and error parameters). This work gives an algorithm that runs in \(\widetilde{O}(n+m)\) time. The main idea is to sample the rows and columns according to row/column norms.

News for May 2019

We were able to find four new papers for May 2019 — as usual, please let us know if we missed any!
EDIT: We did, in fact, miss one paper, which is the bottom one listed below.

On Local Testability in the Non-Signaling Setting, by Alessandro Chiesa, Peter Manohar, and Igor Shinkar (ECCC). This paper studies testability of a certain generalization of (distributions over) functions, known as \(k\)-non-signalling functions, objects which see use in hardness of approximation and delegation of computation. Prior work by the authors show the effectiveness of the linearity test in this setting, leading to the design of PCPs. On the other hand, in this work, the authors show that two types of bivariate tests are ineffective in revealing low-degree structure of these objects.

Computing and Testing Small Vertex Connectivity in Near-Linear Time and Queries, by Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai (arXiv). This work, apparently simultaneous with the one by Forster and Yang that we covered last month, also studies the problem of locally computing cuts in a graph. The authors also go further, and study approximation algorithms for the same problems. Inspired by the connections to property testing in the work of Forster and Yang, they apply these approximation algorithms to get even more query-efficient algorithms for the problems of testing \(k\)-edge- and \(k\)-vertex-connectivity.

Testing Graphs against an Unknown Distribution, by Lior Gishboliner and Asaf Shapira (arXiv). This paper studies graph property testing, under the vertex-distribution-free (VDF) model, as recently introduced by Goldreich. In the VDF model, rather than the ability to sample a random node, the algorithm has the ability to sample a node from some unknown distribution, and must be accurate with respect to the same distribution (reminiscent of the PAC learning model). In Goldreich’s work, it was shown that every property which is testable in the VDF model is semi-hereditary. This work strengthens this statement and proves a converse, thus providing a characterization: a property is testable in the VDF model if and only if it is both hereditary and extendable. These descriptors roughly mean that the property is closed under both removal and addition of nodes (with the choice of addition of edges in the latter case). This is a far simpler characterization than that of properties which are testable in the standard model, which is a special case of the VDF model.

Private Identity Testing for High-Dimensional Distributions, by Clément L. Canonne, Gautam Kamath, Audra McMillan, Jonathan Ullman, and Lydia Zakynthinou (arXiv). This work continues a recent line on distribution testing under the constraint of differential privacy. The settings of interest are multivariate distributions: namely, product distributions over the hypercube and Gaussians with identity covariance. An application of a statistic of CDKS, combined with a Lipschitz extension from the set of datasets likely to be generated by such structured distributions, gives a sample-efficient algorithm. A time-efficient version of this extension is also provided, at the cost of some loss in the sample complexity. Some tools of independent interest include reductions between Gaussian mean and product uniformity testing, balanced product identity to product uniformity testing, and an equivalence between univariate and “extreme” product identity testing.

Testing Bipartitness in an Augmented VDF Bounded-Degree Graph Model, by Oded Goldreich (arXiv). Another work on the vertex-distribution-free (VDF) model, as described above. In this one, Goldreich considers an augmentation of the model, where the algorithm is further allowed to query the probability of each node. With this augmentation, he gives \(\tilde O(\sqrt{n})\)-time algorithms for testing bipartiteness and cycle-free-ness, where \(n\) is the “effective support” of the distribution. That is, \(n\) is the number of nodes in the graph after discarding the nodes with minimal probability until \(\varepsilon/5\) mass is removed.

News for January 2019

Minimax Testing of Identity to a Reference Ergodic Markov Chain, by Geoffrey Wolfer and Aryeh Kontorovich (arXiv). This work studies distributional identity testing on Markov chains from a single trajectory, as recently introduced by Daskalakis, Dikkala, and Gravin: we wish to test whether a Markov chain is equal to some reference chain, or far from it. This improves on previous work by considering a stronger distance measure than before, and showing that the sample complexity only depends on properties of the reference chain (which we are trying to test identity to). It additionally proves instance-by-instance bounds (where the sample complexity depends on properties of the specific chain we wish to test identity to).

Almost Optimal Distribution-free Junta Testing, by Nader H. Bshouty (arXiv). This paper provides a \(\tilde O(k/\varepsilon)\)-query algorithm with two-sided error for testing if a Boolean function is a \(k\)-junta (that is, its value depends only on \(k\) of its variables) in the distribution-free model (where distance is measured with respect to an unknown distribution from which we can sample). This complexity is a quadratic improvement over the \(\tilde O(k^2)/\varepsilon\)-query algorithm of Chen, Liu, Servedio, Sheng, and Xie. This complexity is also near-optimal, as shown in a lower bound by Saglam (which we covered back in August).

Exponentially Faster Massively Parallel Maximal Matching, by Soheil Behnezhad, MohammadTaghi Hajiaghayi, and David G. Harris (arXiv). The authors consider maximal matching in the Massively Parallel Computation (MPC) model. They show that one can compute a maximal matching in \(O(\log \log \Delta)\)-rounds, with \(O(n)\) space per machine. This is an exponential improvement over the previous works, which required either \(\Omega(\log n)\) rounds or \(n^{1 + \Omega(1)}\) space per machine. Corollaries of their result include approximation algorithms for vertex cover, maximum matching, and weighted maximum matching.

News for October 2018

As October draws to a close, we are left with four new papers this month.

Testing Matrix Rank, Optimally, by Maria-Florina Balcan, Yi Li, David P. Woodruff, Hongyang Zhang (arXiv). This work investigates the problem of non-adaptively testing matrix properties, in both the standard query model and the more general sensing model, in which the algorithm may query the component-wise inner product of the matrix with “sensing” matrices. It proves tight upper and lower bounds of \(\tilde \Theta(d^2/\varepsilon)\) for the query model, and eliminating the dependence on \(\varepsilon\) in the sensing model. Furthermore, they introduce a bounded entry model for testing of matrices, in which the entries have absolute value bounded by 1, in which they prove various bounds for testing stable rank, Schatten-\(p\) norms, and SVD entropy.

Testing Halfspaces over Rotation-Invariant Distributions, by Nathaniel Harms (arXiv). This paper studies the problem of testing from samples whether an unknown boolean function over the hypercube is a halfspace. The algorithm requires \(\tilde O(\sqrt{n}/\varepsilon^{7})\) random samples (which has a dependence on \(n\) which is tight up to logarithmic factors) and works for any rotation-invariant distribution, generalizing previous works that require the distribution be Gaussian or uniform.

Testing Graphs in Vertex-Distribution-Free Models, by Oded Goldreich (ECCC). While distribution-free testing has been well-studied in the context of Boolean functions, it has not been significantly studied in the context of testing graphs. In this context, distribution-free roughly means that the algorithm can sample nodes of the graph according to some unknown distribution \(D\), and must be accurate with respect to the measure assigned to nodes by the same distribution. The paper investigates various properties which may be tested with a size-independent number of queries, including relationships with the complexity of testing in the standard model.

A Theory-Based Evaluation of Nearest Neighbor Models Put Into Practice, by Hendrik Fichtenberger and Dennis Rohde (arXiv). In the \(k\)-nearest neighbor problem, we are given a set of points \(P\), and the answer to a query \(q\) is the set of the \(k\) points in \(P\) which are closest to \(q\). This paper considers the following property testing formulation of the problem: given a set of points \(P\) and a graph \(G = (P,E)\), is each point \(p \in P\) connected to its \(k\)-nearest neighbors, or is it far from being a \(k\)NN graph? The authors prove upper and lower bounds on the complexity of this problem, which are both sublinear in the number of points \(n\).

News for August 2018

Three papers this month close out Summer 2018.

Test without Trust: Optimal Locally Private Distribution Testing, by Jayadev Acharya, Clément L. Canonne, Cody Freitag, and Himanshu Tyagi (arXiv). This work studies distribution testing in the local privacy model. While private distribution testing has recently been studied, requiring that the algorithm’s output is differentially private with respect to the input dataset, local privacy has this requirement for each individual datapoint. The authors prove optimal upper and lower bounds for identity and independence testing, using a novel public-coin protocol named RAPTOR which can outperform any private-key protocol.

Testing Graph Clusterability: Algorithms and Lower Bounds, by Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres (arXiv). This paper studies the problem of testing whether a graph is \(k\)-clusterable (based on the conductance of each cluster), or if it is far from all such graphs — this is a generalization of the classical problem of testing whether a graph is an expansion. It manages to solve this problem under weaker assumptions than previously considered. Technically, prior work embedded a subset of the graph into Euclidean space and clustered based on distances between vertices. This work uses richer geometric structure, including angles between the points, in order to obtain stronger results.

Near log-convexity of measured heat in (discrete) time and consequences, by Mert Saglam (ECCC). Glancing at the title, it might not be clear how this paper relates to property testing. The primary problem of study is the quantity \(m_t = uS^tv\), where \(u, v\) are positive unit vectors and \(S\) is a symmetric substochastic matrix. This quantity can be viewed as a measurement of the heat measured at vector \(v\), after letting the initial configuration of \(u\) evolve according to \(S\) for \(t\) time steps. The author proves an inequality which roughly states \(m_{t+2} \geq t^{1 – \varepsilon} m_t^{1 + 2/t}\), which can be used as a type of log-convexity statement. Surprisingly, this leads to lower bounds for the communication complexity of the \(k\)-Hamming problem, which in turns leads to optimal lower bounds for the complexity of testing \(k\)-linearity and \(k\)-juntas.

News for May 2018

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.

 

News for February 2018

February had a flurry of conference deadlines, and they seem to have produced six papers for us to enjoy, including three on estimating symmetric properties of distributions.

Locally Private Hypothesis Testing, by Or Sheffet (arXiv). We now have a very mature understanding of the sample complexity of distributional identity testing — given samples from a distribution \(p\), is it equal to, or far from, some model hypothesis \(q\)? Recently,  several papers have studied this problem under the additional constraint of differential privacy. This paper strengthens the privacy constraint to local privacy, where each sample is locally noised before being provided to the testing algorithm.

Distribution-free Junta Testing, by Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, and Jinyu Xie (arXiv). Testing whether a function is a \(k\)-junta is very well understood — when done with respect to the uniform distribution. In particular, the adaptive complexity of this problem is \(\tilde \Theta(k)\), while the non-adaptive complexity is \(\tilde \Theta(k^{3/2})\). This paper studies the more challenging task of distribution-free testing, where the distance between functions is measured with respect to some unknown distribution. The authors show that, while the adaptive complexity of this problem is still polynomial (at \(\tilde O(k^2)\)), the non-adaptive complexity becomes exponential: \(2^{\Omega(k/3)}\). In other words, there’s a qualitative gap between the adaptive and non-adaptive complexity, which does not appear when testing with respect to the uniform distribution.

The Vertex Sample Complexity of Free Energy is Polynomial, by Vishesh Jain, Frederic Koehler, and Elchanan Mossel (arXiv). This paper studies the classic question of estimating (the logarithm of) the partition function of a Markov Random Field, a highly-studied topic in theoretical computer science and statistical physics. As the title suggests, the authors show that the vertex sample complexity of this quantity is polynomial. In other words, randomly subsampling a \(\mathrm{poly}(1/\varepsilon)\)-size graph and computing its free energy gives a good approximation to the free energy of the overall graph. This is in contrast to more general graph properties, for the vertex sample complexity is super-exponential in \(1/\varepsilon\).

Entropy Rate Estimation for Markov Chains with Large State Space, by Yanjun Han, Jiantao Jiao, Chuan-Zheng Lee, Tsachy Weissman, Yihong Wu, and Tiancheng Yu (arXiv). Entropy estimation is now quite well-understood when one observes independent samples from a discrete distribution — we can get by with a barely-sublinear sample complexity, saving a logarithmic factor compared to the support size. This paper shows that these savings can also be enjoyed in the case where we observe a sample path of observations from a Markov chain.

Local moment matching: A unified methodology for symmetric functional estimation and distribution estimation under Wasserstein distance, by Yanjun Han, Jiantao Jiao, and Tsachy Weissman (arXiv). Speaking more generally of the above problem: there has been significant work into estimating symmetric properties of distributions, i.e., those which do not change when the distribution is permuted. One natural method for estimating such properties is to estimate the sorted distribution, then apply the plug-in estimator for the quantity of interest. The authors give an improved estimator for the sorted distribution, improving on the results of Valiant and Valiant.

INSPECTRE: Privately Estimating the Unseen, by Jayadev Acharya, Gautam Kamath, Ziteng Sun, and Huanyu Zhang (arXiv). One final work in this area — this paper studies the estimation of symmetric distribution properties (including entropy, support size, and support coverage), but this time while maintaining differentially privacy of the sample. By using estimators for these tasks with low sensitivity, one can additionally obtain privacy for a low or no additional cost over the non-private sample complexity.

News for November 2017

A quiet month, with only two papers. Perhaps the calm before the storm? Please let us know in the comments if something slipped under our radar.

Agreement tests on graphs and hypergraphs, by Irit Dinur, Yuval Filmus, and Prahladh Harsha (ECCC). This work looks at agreement tests and agreement theorems, which argue that if one checks if a number of local functions agree, then there exists a global function which agrees with most of them. This work extends previous work on direct product testing to local functions of higher degree, which corresponds to agreement tests on graphs and hypergraphs.

Testing Conditional Independence of Discrete Distributions, by Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart (arXiv). This paper focuses on testing whether a bivariate discrete distribution has independent marginals, conditioned on the value of a tertiary discrete random variable. More precisely, given realizations of \((X, Y, Z)\), test if \(X \perp Y \mid Z\). Unconditional independence testing (corresponding to the case when \(Z\) is constant) has been extensively studied by the community, with tight upper and lower bounds showing that the sample complexity has two regimes, depending on the tradeoff between the support size and the accuracy desired. This paper shows gives upper and lower bounds for this more general problem, showing a rich landscape depending on the relative value of the parameters.

News for August 2017

This month has been comparatively slow, with only five papers. I suppose we’re lucky that five papers is considered to be a slow month!

Local Testing and Decoding of High-Rate Error-Correcting Codes, by Swastik Kopparty and Shubhangi Saraf (ECCC). This is a survey article, covering recent results in locally testable, correctable, and decodable codes. A good place to start for any who have fallen behind on the recent literature.

Sample-Optimal Identity Testing with High Probability, by Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price (arXiv). Distribution testing results are  often stated in the regime where the probability of failure is some constant, i.e. \(\delta = 1/3\). These can be boosted to arbitrarily high probability of success at a multiplicative cost of \(\log (1/\delta)\) using the “median trick” — repeat the test \(\log (1/\delta)\) times and choose the majority result. This paper shows that this method is suboptimal for identity testing with small values of \(\delta\). In particular, they give upper and lower bounds for the entire tradeoff curve between \(n, \varepsilon\), and \(\delta\).

Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average, by Michael Kapralov (arXiv). The Sparse Fourier Transform problem has seen a wealth of study in the past few years, with various tradeoffs between sample and time complexity. This paper gives the first result achieving the optimal sample complexity of \(O(k \log n)\) while maintaining a time complexity which is sublinear in the length of the signal, \(n\). In order to obtain this, the author introduces a new technique for analyzing noisy hashing schemes.

Generalized Uniformity Testing, by Tuğkan Batu and Clément L. Canonne (arXiv). Uniformity testing is one of the most studied problems in distribution testing, and it is well known that the complexity is \(\Theta(\sqrt{n})\). This paper studies a slightly different question: given samples from a distribution \(p\), is it uniform over some (unknown) subset of its domain? The authors give upper and lower bounds for this question, showing that the complexity is \(\Theta(1/\|p\|_3)\). Interestingly, when \(p\) is uniform over a set of size \(\Omega(n)\), the complexity is \(\Theta(n^{2/3})\), which is more than the \(\Theta(\sqrt{n})\) cost of vanilla uniformity testing.

Boolean Unateness Testing with \(\tilde O(n^{3/4})\) Adaptive Queries, by Xi Chen, Erik Waingarten, and Jinyu Xie (arXiv). At this point, we have a fairly mature understanding of testing monotonicity over the Boolean hypercube: for non-adaptive algorithms, the complexity is \(\tilde \Theta(\sqrt{n})\). There exists a gap for adaptive algorithms — the best known lower bound is \(\tilde \Omega(n^{1/3})\), while the best upper bound is the same as for the non-adaptive case \(\tilde O(n^{1/2})\). However, many conjecture that adaptivity does not help for monotonicity testing. More recently, there has been study of testing unateness — a function is unate if it is monotone non-decreasing or non-increasing with respect to each coordinate. Interestingly, this work proves an adaptive upper bound of \(\tilde O(n^{2/3})\) which beats the lower bound of \(\tilde \Omega(n)\) for non-adaptive algorithms, thus showing that adaptivity does help for unateness testing.

News for May 2017

May brought us a wealth of new papers, including four (!) on distributed property testing.

Distributed Property Testing for Subgraph-Freeness Revisited, by Orr Fischer, Tzlil Gonen, and Rotem Oshman (arXiv). This paper studies subgraph-freeness testing in the CONGEST model of distributed computation. This problem was previously studied — this paper provides a number of new algorithms, which either improve upon the running time of prior work or are the first non-trivial results for these problems. Some cases they study include testing for freeness of \(k\)-cycles, constant-size trees, and \(k\)-cliques. For the latter case, they prove that a dependence on \(\varepsilon\) is necessary.

Faster and Simpler Distributed Algorithms for Testing and Correcting Graph Properties in the CONGEST-Model, by Guy Even, Reut Levi, and Moti Medina (arXiv). This paper also studies graph property testing in the CONGEST model. There appears to be some overlap in problems with the previous paper, including testing subgraph-freeness for cycles and constant size trees. As the title suggests, they also study graph property correction in the case of \(k\)-cycles, and other properties such as bipartiteness.

K-Monotonicity is Not Testable on the Hypercube, by Elena Grigorescu, Akash Kumar, and Karl Wimmer (arXiv, ECCC). Recent work introduced the concept of \(k\)-monotonicity, where a function may switch value between \(0\) to \(1\) at most \(k\)-times on any ascending chain. This generalizes the common notion of monotonicity, which corresponds to \(k = 1\). Since \(1\)-monotonicity on the hypercube is testable in \(O(\sqrt{n})\) queries, it was conjectured that \(k\)-monotonicity may be tested in \(poly(n^k)\) queries. This paper disproves this conjecture, showing that even \(2\)-monotonicity requires a number of queries which is exponential in \(\sqrt{n}\).

The coin problem for product tests, by Chin Ho Lee and Emanuele Viola (ECCC). The coin problem asks, if \(f\) is a product of \(k\) functions on disjoint inputs of length \(n\) bits, what is the smallest \(\varepsilon\) such that \(f\) can distinguish between an input of \(m = nk\) fair bits versus an input of \(m\) \(\varepsilon\)-biased bits. This paper proves tight bounds in a few cases of interest — when the range of \(f\) is \(\{0, 1\}\) or \(\{\pm 1\}\), the answer is \(\Theta(1/\sqrt{n\log k})\), while if the range is the set of unit-norm complex numbers, the answer is \(\Theta(1/\sqrt{nk})\).

Distributed Testing of Conductance, by Hendrik Fichtenberger and Yadu Vasudev (arXiv). Another paper on testing in the CONGEST model — this one studies the problem of testing conductance. In particular, they give an \(O(\log n)\) round two-sided tester which distinguishes between graphs with conductance at least \(\Phi\) and graphs which are \(\varepsilon\)-far from having conductance at least \(\Omega(\Phi)\). They also prove a lower bound of \(\Omega(\log n)\), even in the (easier) LOCAL model.

On The Multiparty Communication Complexity of Testing Triangle-Freeness, by Orr Fischer, Shay Gershtein, and Rotem Oshman (arXiv). The final paper in May on distributed graph property testing — in contrast to the other papers, this paper considers multiparty communication complexity in the coordinator model. A graph is divided up among \(k\) players, and each player can only communicate with a coordinator and not each other. The authors show upper bounds on the communication, in both the vanilla and the simultaneous model (which allows only \(1\) round of communication). They also show a near-matching lower bound for simultaneous protocols on graphs of constant degree.

Exponentially Small Soundness for the Direct Product Z-test, by Irit Dinur and Inbal Livni Navon (ECCC). This paper studies the problem of direct product testing, in which one tests whether the output of a function on a coordinate depends only on the input to that coordinate (approximately). The authors investigate the Z-test of Impagliazzo, Kabanets, and Wigderson, and show that it achieves the optimal soundness of \(\varepsilon \geq \exp(-O(k))\).