News for July 2022

Last month saw a flurry of activity in Property Testing. We had thirteen papers!! Without further ado, let us dig in.

Testing of Index-Invariant Properties in the Huge Object Model (by Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen)(arXiv) This paper explores a class of distribution testing problems in the Huge Object Model introduced by Goldreich and Ron (see our coverage of the model here). A quick refresher of this model: so, suppose you want to test whether a distribution $$\mathcal{D}$$ supported over, say the boolean hypercube $$\{0,1\}^n$$ has a certain property $$\mathcal{P}$$. You pick a string $$x \sim \mathcal{D}$$ where the length of $$x$$ is $$n$$. In situations where $$n$$ is really large, you might not want to read all of $$x$$ and you may instead want to read only a few bits from it. To this end, Goldreich and Ron formulated a model where you have query access to the strings you sample. The distribution $$\mathcal{D}$$ is deemed to be $$\varepsilon$$-far from $$\mathcal{P}$$ if $$EMD(\mathcal{D}, \mathcal{P}) \geq \varepsilon$$ (here $$EMD$$ denotes the earthmover distance with respect to the relative Hamming distance between bitstrings). In this model, one parameter of interest is the query complexity of your tester.

One of the results in the featured paper above shows the following: Let $$\sf{MONOTONE}$$ denote the class of monotone distributions supported over $$\{0,1\}^n$$ (a distribution $$D$$ belongs to the class $$\sf{MONOTONE}$$ if $$D(x) \leq D(y)$$ whenever $$0^n \preceq x \preceq y \preceq 1^n$$). Let $$\mathcal{B}_d$$ denote the class of distributions supported over $$\{0,1\}^n$$ whose supports have VC dimension at most $$d$$. Let $$\mathcal{P} = \sf{MONOTONE} \cap \mathcal{B}_d$$. Then, for any $$\varepsilon > 0$$, you can test whether a distribution $$\mathcal{D} \in \mathcal{P}$$ or whether it is $$\varepsilon$$ far from $$\mathcal{P}$$ with query complexity $$poly(1/\varepsilon)$$. In fact, the paper shows this for a much richer class $$\mathcal{P}$$ which is the class of so-called index-invariant distributions with bounded VC-dimensions. The paper also shows the necessity of both of these conditions for efficient testability. Do check it out!

Identity Testing for High-Dimensional Distributions via Entropy Tensorization (by Antonio Blanca, Zongchen Chen, Daniel Štefankovič, and Eric Vigoda)(arXiv)

This paper considers a classic in distribution testing. Namely, the problem of testing whether the hidden input distribution $$\pi$$ is identical to an explicitly given distribution $$\mu$$. Both distributions are supported over a set $$\Omega$$. The caveat is $$\Omega$$ is some high dimensional set (think $$\Omega = [k]^n$$) and that it has a size that grows exponentially in $$n$$. In this case, identity testing has sample complexity $$\Omega(k^{n/2})$$ even when $$\mu$$ is the uniform distribution. In an attempt to overcome this apparent intractability of identity testing in high dimensions, this paper takes the following route: in addition to the standard sample access to $$\pi$$, you also assume access to a stronger sampling oracle from $$\pi$$. And now you would like to understand for which class of explicitly given distributions $$\mu$$ can you expect algorithms with efficient sample complexity (assuming the algorithm is equipped with this stronger sampling oracle). For any $$i \in [n]$$ and $$\omega \in \Omega$$, the stronger oracle considered in this work allows you to sample $$x \sim \pi_{\omega(-i)}$$ where $$\pi_{\omega(-i)}$$ denotes the conditional marginal distribution of $$\pi$$ over the $$i$$-th coordinate when the remaining coordinates have been fixed according to $$\omega$$.

The paper shows if the known distribution $$\mu$$ satisfies some approximate tensorization of entropy criterion, then identity testing with such distributions $$\mu$$ can be done with $$\tilde{O}(n/\varepsilon)$$ queries. Thanks to the spectral independence toolkit pioneered by Anari et al, it turns out that the approximate tensorization property holds for a rich class of distributions. (A side note to self: It looks like I am running out of reasons to postpone learning about the new tools like Spectral Independence.)

Near-Optimal Bounds for Testing Histogram Distributions (by Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Sihan Liu)(arXiv) Histograms comprise one of the most natural and widely used ways for summarizing some relevant aspects of massive datasets. Let $$\Omega$$ denote an $$n$$-element dataset (with elements being $$\{1,2, \ldots, n \}$$). A $$k$$-histogram is a function that is piecewise constant over $$k$$ interval pieces. This paper studies the sample complexity of the following fundamental task: given a distribution $$\mathcal{P}$$ supported over $$\Omega$$, is $$\mathcal{P}$$ a $$k$$-histogram or is $$\mathcal{P}$$ far from being a $$k$$-histogram. The main result of the paper is a (near) sample optimal algorithm for this problem. Specifically, this paper shows that $$k$$-histogram testing has sample complexity $$\Theta\left(\sqrt{nk}/\varepsilon + k/\varepsilon^2 + \sqrt{n}/\varepsilon^2\right)$$.

Comments on “Testing Conditional Independence of Discrete Distributions” (by Ilmun Kim)(arXiv) Probability is full of subtleties and conditional probability is perhaps the biggest landmine of subtleties in this venerable discipline. The featured paper closely examines some subtleties in Theorem 1.3 of the CDKS18 paper on testing conditional independence of discrete distributions. Essentially, this theorem undertakes the following endeavor: you would like to test whether a bivariate discrete distribution has independent marginals conditioned on values assumed by a third random variable. Theorem 1.3 of CDKS18 asserts that there exists a computationally efficient tester for conditional independence with small sample complexity. The featured paper fixes the sample complexity bound claimed in Theorem 1.3 of CDKS18.

Cryptographic Hardness of Learning Halfspaces with Massart Noise (by Ilias Diakonikolas, Daniel M. Kane, Pasin Manurangsi, and Lisheng Ren)(arXiv) The study of robust supervised learning in high dimensions has seen a lot of impressive progress in the last few years. The paper under review presents sample complexity lower bounds for the task of learning halfspaces in this overarching framework. Let us unpack this paper slowly. So, let us recall the classic task of learning halfspaces in $$\mathbb{R}^n$$. You know the drill. I have a known concept class $$\mathcal{C}$$ (comprising of boolean functions) in my hand. Unbeknownst to you, I have a boolean function $$f \in \mathcal{C}$$. You get as input a multiset $$\{x_i, f(x_i)\}_{i \in [s]}$$ of labeled examples from a distribution $$\mathcal{D}$$ where $$x_i \sim \mathcal{D}_x$$ and $$\mathcal{D}_x$$ is fixed but arbitrary. Your goal is to develop an algorithm that returns a hypothesis with a small misclassification rate. The classic stuff.

Now, consider the same setup with a little twist: the so-called Massart noise setup. The labels $$f(x_i)$$ are no longer reliable and the label on each $$x_i$$ gets flipped adversarially with probability $$\eta_i \leq \eta < 1/2$$. In a breakthrough Diakonikolas, Gouleakis, and Tzamos made the first algorithmic progress on this problem and gave algorithms with running time $$poly(n/\varepsilon)$$ and misclassification rate $$\eta + \varepsilon$$. The current paper shows a lower-bound result. Assuming the hardness of the so-called “Learning With Errors” problem, this paper shows that under Massart Noise, it is not possible for a polynomial time learning algorithm to achieve a misclassification rate of $$o(\eta)$$.

Locally-iterative (Δ+1)-Coloring in Sublinear (in Δ) Rounds (by Xinyu Fu, Yitong Yin, and Chaodong Zheng)(arXiv) A time-honored problem in Distributed Computing is Distributed graph coloring. Let us first understand what problem this paper studies. So, you are given a graph $$G = (V,E)$$ with maximum degree $$\Delta$$. In a seminal work, Szegedy and Vishwanathan introduced the framework of locally-iterative algorithms as a natural family of distributed graph coloring algorithms. These algorithms proceed in $$r$$ rounds. In each round, you update the color of a vertex $$v$$ where the new color of $$v$$ is a function of the current color of $$v$$ and the current color of its neighbors. The current paper shows that you can in the locally-iterative framework, you can in fact, obtain a proper coloring of $$G$$ with $$\Delta(G) + 1$$ colors in $$r = O(\Delta^{3/4} \log \Delta) + \log^* n$$ rounds.

Learning Hierarchical Structure of Clusterable Graphs (by Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar)(arXiv) [Disclaimer: I am one of the authors of this paper.] Hierarchical clustering of graph data is a fundamentally important task in the current big data era. In 2016, Dasgupta introduced the notion of Dasgupta cost which essentially allows one to measure the quality of a hierarchical clustering. This paper presents algorithms that can estimate the Dasgupta Cost of a graph coming from a special family of $$k$$-clusterable graphs in the semi-supervised setting. These graphs have $$k$$ clusters. These clusters are essentially subsets of vertices that induce expanders and these clusters are sparsely connected to each other. We are given query access to the adjacency list of $$G$$. Also, for an initial “warmup” set of randomly chosen vertices, we are told the clusters they belong to. Armed with this setup, this paper presents algorithms that run in time $$\approx \sqrt{n}$$ and return an estimate to the Dasgupta Cost of $$G$$ which is within a $$\approx \sqrt{\log k}$$ factor of the optimum cost.

Finding a Hidden Edge (by Ron Kupfer and Noam Nisan)(arXiv) Let us consider as a warmup (as done in the paper) the following toy problem. You have a graph on $$n$$ vertices whose edge set $$E$$ is hidden from you. Your objective is to return any $$(i,j) \in E$$. The only queries you are allowed are of the following form. You may consider any subset $$Q \subseteq V \times V$$ and you can ask whether $$Q$$ contains any edge. A simple binary search solves this question with $$\log m$$ queries (where $$m = {n \choose 2}$$). However, if you want a non-adaptive algorithm for this problem (unlike binary search) you can show that any deterministic algorithm must issue $$m$$ non-adaptive queries. Turns out randomness can help you get away with only $$O(\log^2m)$$ non-adaptive queries for this special toy problem. Now, let me describe the problem considered in this work in earnest. Suppose the only queries you are allowed are of the following form: you may pick any $$S \subseteq V$$ and you may ask whether the graph induced on $$S$$ contains an edge. The paper’s main result is that there is an algorithm for finding an edge in $$G$$ which issues nearly linear in $$n$$ many non-adaptive queries. The paper also presents an almost matching lower bound.

On One-Sided Testing Affine Subspaces (by Nader Bshouty)(ECCC) Dictatorship testing is one of the classics in property testing of boolean functions. A more generalized problem considers testing whether the presented function is a $$k$$-monomial. If you are a regular reader of the posts on PTReview, you might have seen this problem essentially asks you to test whether a boolean function $$f \colon \mathcal{F}^n \to {0,1}$$ is an indicator of an $$(n-d)$$ dimensional affine/linear subspace of $$\mathcal{F}^n$$ (here $$\mathcal{F}$$ denotes a finite field). Namely, you would like to test whether the set $$f^{-1}$$ is an $$(n-k)$$ dimensional affine subspace of $$\mathcal{F}^n$$. The paper under review improves the state-of-the-art query complexity for this problem from a previous value of $$O\left(|\mathcal{F}|/\varepsilon\right)$$ to $$\tilde{O}\left(1/\varepsilon\right)$$.

Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries (by Raghavendra Addanki, Andrew McGregor, and Cameron Musco)(arXiv) If you have been around the PTReview corner for a while, you know that sublinear time estimation of graph properties is one of our favorite pastimes here. Classic work in this area considers the following queries: vertex degree queries, $$i$$-th neighbor queries, and edge existence queries. This classic query model has received a lot of attention and thanks to the work of Eden and Rosenbaum we know algorithms for near-uniform edge sampling with query complexity $$O(n/\sqrt{m}) \cdot poly(\log n) \cdot poly(1/\varepsilon)$$. Motivated by a desire to obtain more query-efficient algorithms, Beame et al. introduced an augmented query model where you are also allowed the following queries: you may pick $$L, R \subseteq V$$ and you get a yes/no response indicating whether there exists an edge in $$E(L, R)$$. These are also called the bipartite independent set (BIS) queries. The featured paper shows that with (BIS) queries you get non-adaptive algorithms for near-uniform edge sampling with query complexity being a mere $$\widetilde{O}(\varepsilon^{-4} \log^6 n)$$. The main result of the paper gives a non-adaptive algorithm for estimating the number of edges in $$G$$ with query complexity (under BIS) being a mere $$\widetilde{O}(\varepsilon^{-5} \log^5 n)$$.

A Query-Optimal Algorithm for Finding Counterfactuals (by Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan)(arXiv) Given an abstract space $$X^d$$, an instance $$x^* \in X^d$$ and a model $$f$$ (which you think of as a boolean function over $$X^d$$), a point $$x’ \in X^d$$ is called a counterfactual to $$x^*$$ if $$x^*, x’$$ differ in few features (i.e., have a small Hamming distance) and $$f(x^*) \neq f(x’)$$. Ideally, you would like to find counterfactuals that are as close to each other in Hamming Distance. The main result of this paper is the following: Take a monotone model $$f \colon \{0,1\}^d \to \{0,1\}$$, an instance $$x^* \in \{0,1\}^d$$ with small sensitivity (say $$\alpha$$). Then there exists an algorithm that makes at most $$\alpha^{\Delta(x^*)}$$ queries to $$f$$ and returns all optimal counterfactuals of $$f$$. Here $$\Delta(x^*) = \min_{x \in \{0,1\}^d} \{\Delta_H(x, x^*) \colon f(x) \neq f(x^*) \}$$. The paper also proves a matching lower bound on query complexity which is obtained by some monotone model $$f$$.

A Sublinear-Time Quantum Algorithm for Approximating Partition Functions (by Arjan Cornelissen and Yassine Hamoudi)(arXiv) For the classical Hamiltonian $$H \colon \Omega \to \{0,1, \ldots, n\}$$, at inverse temperature $$\beta$$, the probability, under the so-called Gibbs distribution, assigned to a state $$x \in \Omega$$ is proportional to $$\exp(-\beta H(x))$$. The partition function is given by $$Z(\beta) = \sum_{x \in \Omega} \exp(-\beta H(x))$$. At high temperatures (or low values of $$\beta$$) the partition function is typically easy to compute. However, the low-temperature regime is often challenging. You use MCMC methods to compute $$Z(\infty)$$. In particular, you write this as the following telescoping product $$Z(\infty) = Z(0) \cdot \prod_{i = 0}^{i = \ell – 1} \frac{Z(\beta_{i+1})}{Z(\beta_i)}$$ where $$0 = \beta_1 < \beta_2 < \ldots < \beta_{\ell} = \infty$$ is some increasing sequence of inverse temperatures with limited fluctuations in Gibbs distribution between two consecutive values and you use MCMC methods to estimate each of the $$\ell$$ ratios in the above product. The main result of this paper presents a quantum algorithm that on input a Gibbs distribution generated by a Markov Chain with a large spectral gap performs sublinearly few steps (in size of the logarithm of the state space) of the quantum walk operator and returns a $$\pm \varepsilon Z(\infty)$$ additive estimate to $$Z(\infty)$$.

A Near-Cubic Lower Bound for 3-Query Locally Decodable Codes from Semirandom CSP Refutation (by Omar Alrabiah, Venkatesan Guruswami, Pravesh Kothari, and Peter Manohar)(ECCC) If you made it till here, it is time for a treat. Let us close (hopefully, I did not miss any papers this time!) with a breakthrough in Locally Decodable Codes. So, for 2-query LDCs, we know fairly tight bounds on the block length. For 3-query LDCs, on the other hand, we know a sub-exponential upper bound on the block length. However, the best-known lower bound on the block length was merely quadratic. The featured paper improves this to a cubic lower bound on the block length. The main tool used to achieve this is a surprising connection between the existence of locally decodable codes and the refutation of Boolean CSP instances with limited randomness. This looks like a fantastic read to close off this month’s report!