So, we had a pretty fantastic September. Besides the fact that September saw eight papers, the Computer Science community also bagged two Nobel Prizes(!) — reactions to which are kind of mixed from what I see around me. Anyhow without further delay, let us circle back to property testing. So, eight papers, yes. Without further ado, let us look at our spread.

Public Coin Interactive Proofs for Label-Invariant Distribution Properties by Tal Herman (ECCC) Suppose you have an unknown distribution \(\mathcal{D}\) supported over \([N]\). Suppose I claim that this distribution has entropy \(\texttt{blah}\). You have sample access to \(\mathcal{D}\) and you want to check my claim. To this end, you decide to engage me, a suspicious shady prover, in an Interactive Protocol where you, the verifier is restricted to use public coin tosses. The main result of this paper asserts that you can do this with a mere \(\widetilde{O}(N^{2/3})\) samples. You also get the same bound on the communication complexity. What’s more is that you get algorithms with running time of the same order. What’s even more, is that you get similar algorithms for all label invariant properties of \(\mathcal{D}\). You can contrast this with the seminal result of Valiant and Valiant from 2011 which asserts that you can approximate the distance between your input distribution \(\mathcal{D}\) and the label invariant property of interest (without any prover) using \(\Theta(N/\log N)\) samples. So, this result shows that the computation under the interactive model is more efficient than standalone computation even in the public coin toss model.

How to Verify Any (Reasonable) Distribution Property: Computationally Sound Argument Systems for Distributions by Tal Herman and Guy Rothblum (arXiv) Let us consider the same setup as above. Again, you have an unknown distribution (supported over \([N]\)) which you have sample access to and I assert that this distribution has a certain property. You want to verify whether my claim is correct or bogus. The main algorithmic result of this paper has a cryptographic ring to it: Assuming the existence of collision resistant hash functions, the authors show that for any reasonable distribution property, you have set up an interactive protocol where the verifier can decide whether or not the prover’s claim is bogus using \(\widetilde{O}(\sqrt N)\) samples. Also, the communication complexity is of the same order.

Random local access for sampling k-SAT solutions by Dingding Dong and Nitya Mani (arXiv) I find this paper pretty intriguing. So, here is the setup. I give you some \(k\)-SAT instance and I promise that no variable in this instance shows up in more than \(d\) clauses. Recall that for \(d \leq 2^k/(2e k)\), Lovasz Local Lemma assures you that there exists a satisfying assignment. What’s more is that the famous Moser-Tardos algorithm even allows you to find one satisfying assignment in polynomial time. In a beautiful work, in the regime where \(d \leq 2^{ck}\) (where \(0 < c < 1\) is a sufficiently small constant), Moitra gave samplers which return an almost uniformly random satisfying assignment. Note that this is not possible direct adaptation the Moser-Tardos algorithm. Anyhow, back to the setting considered in this work. So, consider the following sublinear challenge. Denote by \(\mu\) the uniform distribution supported over all satisfying assignments to the given \(k\)-SAT instance where each variable shows up in more than \(d \leq 2^{ck}\) clauses. I want you to sample the assignment \(\sigma(v)\) for a variable \(v\) from the marginal \(\mu_v\) induced by \(\mu\) on \(v\) fast (in \(poly(\log n)\) time) in expectation. Of course this has to be done in some consistent fashion overall which is very LCAish in flavor and I will not detail that here. Rest assured the featured paper rises up to the challenge.

New Direct Sum Tests by Alek Westover, Edward Yu, Kai Zheng (arXiv) We say that a \(\mathbb{F}_2\)-valued function \(f\) over the \(d\)-dimensional grid \(f \colon [n]^d \to \mathbb{F}_2\) is a direct sum if there are \(d\) one-dimensional functions \(L_i \colon [n] \to \mathbb{F}_2\) such that \(f(x) = \sum_{i=1}^d L_i(x_i)\). In a paper we covered in October 2019, Dinur and Golubev presented an algorithm for direct sum testing and left its analysis for future research. The featured paper analyzes this test and shows that it is indeed a bonafide direct sum tester. I omit the description of the tester. I will just leave with one note — this looks like an appetizing read for Boolean Fourier Analysis aficionados.

Directed Hypercube Routing, a Generalized Lehman-Ron Theorem, and Monotonicity Testing by Deeparnab Chakrabarty and C. Seshadhri (arXiv) This is a very refreshing read with (our very own) Seshadhri as one of the authors. Chakrabarty and Seshadhri have teamed up (often in a trio with Hadley Black) in their attempts to understand the deep dark secrets of testing boolean monotonicity over the boolean hypercube. The featured paper conjectures a bold generalization of Lehman-Ron theorem over the hypercube and suggests that the conjectured routing once established could pave the path forward towards a more transparent understanding of directed isoperimetric inequalities over the boolean hypercube. In my opinion, it is worth your while to check this one out.

Lempel-Ziv (LZ77) Factorization in Sublinear Time by Dominik Kempa and Tomasz Kociumaka (arXiv) A pretty unique topic. The main result of this paper is what you see in the title — after 50 years since its introduction, finally we can factorize LZ77 in sublinear time. If you are like me, you might be asking but what does that mean? Quoting from the abstract

Lempel-Ziv (LZ77) factorization is a fundamental problem in string processing: Greedily partition a given string T from left to right into blocks (called phrases) so that each phrase is either the leftmost occurrence of a letter or the longest prefix of the unprocessed suffix that has another occurrence earlier in T.

Indeed, the abstract has more fascinating information about this problem. Quoting again.

Sublinear-time algorithms are known for nearly all other fundamental problems on
strings, but LZ77 seems resistant to all currently known techniques.

Looks like new year came early for PTReview readers. This paper promises to be fun by the contents I sampled so far.

Computing String Covers in Sublinear Time by Jakub Radoszewski and Wiktor Zuba (arXiv) A substring (actually prefix) \(C\) is called a cover of text \(T\) is \(T\) can be constructed by concatenations and superpositions of \(C\). Suppose the text string \(T\) contains \(n\) symbols from some alphabet of fixed size. The main theorem of the featured paper asserts that given a string \(T\), you can find a representation of all of its covers (at most \(n\) of them — they are all prefixes) in merely \(O(n/\log_{\sigma} n)\) time. This bound is also shown to be optimal — indeed the authors show that you cannot compute a representation (in a certain model formulated by Charalampopoulos et al in FOCS 2020) for the shortest cover in less than \(o(n/log n)\) time.

Quantum Channel Testing in Average-Case Distance by Gregory Rosenthal, Hugo Aaronson, Sathyawageeswar Subramanian, Animesh Datta and Tom Gur (arXiv) This paper considers a new diversion in quantum land. Namely, it considers the task of testing quantum channels. The setup is this: I have a \(d\)-dimensional quantum system which is just a \(\mathbb{C}^{d \times d}\) psd matrix over complex numbers with trace \(1\). A quantum channel is a just a linear transformation that maps \(d_{in}\) dimensional quantum systems to a \(d_{out}\)-dimensional quantum system. With repsect to some appropriate norm (the so-called diamond norm), one of the results in this paper proves a \(poly(d_{in})/\varepsilon\) lower bound for testing identity to any fixed channel in diamond distance. This lower bound is shown to hold in a very strong query model appropriate for the quantum setting.

This month we have only one paper. I imagine the community will be on fire when we come back with our news for August.

Constant Degree Direct Product Testers with Small Soundness by Mitali Bafna, Noam Lifshitz, and Dor Minzer (arXiv) (Please excuse my lack of technical comfort with the contents of this paper. Corrections Welcome) As the title indicates, and the authors also emphasize, the primary goal of the featured paper is to construct direct product testers with constant degree. Let us try to unpack this a little by first understanding what does a direct product test mean. So I have this function \(f \colon [n] \to \{0,1\}\). I give you access to this function in an indirect way via a table \(F\) to which you have query access. The central task in direct product testing is to check whether \(F\) is a valid encoding of \(f\) by querying \(F\) on a small number of locations. This paper focuses on those properties which you can test with two queries. Dinur and Kaufman noted that high dimensional expanders can be leveraged towards obtaining \(2\)-query direct product testers. The main result of this paper shows that there are high dimensional expanders for which the Dinur-Kaufman direct product test has small soundness.

We have seven papers for you this month. Our potpourri includes two papers apiece on each of the following themes: Distribution Testing, property testing with a quantum twist, graph property testing, and finally two papers on testing function properties. A featured paper this month covers progress on optimal non-adaptive junta testers. Without further ado, let’s dig in. As usual, please let us know if I missed any papers.

Testing \(C_k\) freeness in bounded-arboricity graphs by Talya Eden, Reut Levi, and Dana Ron (arXiv) Our post from July 2021 highlighted an open problem posed by Goldreich. This problem asks if it is possible to transform property testers for bounded degree graphs to property testers for unbounded degree graphs with general arboricity. The featured paper answers the question Goldreich posed in the negative. In particular, testing \(C_4\) freeness in bounded arboricity graphs (with possibly unbounded degree) already admits an \(\Omega(n^{1/4})\) one-sided lowerbound. Up to \(\log\) factors, the paper also proves a matching upperbound. The same bounds hold for \(C_5\)-freeness. Further, for every \(k \geq 6\), the paper proves an \(\Omega(n^{1/3})\) one-sided lower-bound.

Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach by Renato Ferreira Pinto Jr (arXiv) The featured paper considers a classic of property testing. So, you want to test whether an input real-valued function \(f \colon [0,1]^d \to \mathbb{R}\) over the solid cube is monotone or whether it is \(\varepsilon\)-far from being monotone. It is convenient to require that the input function better be differentiable and Lipschictz (for those of you keeping scores, this should remind you of our post from July 2023 where we covered a previous work in the same setting again by Renato). Motivated by the success of testers developed for the boolean hypercube domain, a natural analogy suggests to have in addition to a standard value oracle, an additional derivative oracle which takes as input a point \(x \in [0,1]^d\) and a direction \(\mathbf{v} \in \mathbb{R}^d\). This oracle allows you to query directional derivative at \(x\) along \(\mathbf{v}\). Renato’s punchline is a directed Poincare Inequality which in the above setup, connects the distance to monotonicity to the square root of directed analog of a suitable notion of influence. The techniques used in the paper seem intriguing. They are inspired by the original proof of the classic Poincare Inequality. In particular, as Renato notes “the main theme of our proof of this result is the study of the convergence of a partial differential equation.”

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators by Shivam Nadimpalli, Shyamal Patel (arXiv) The problem of Tolerant Junta testing is no stranger to our regular readers. This paper is fairly intriguing for those of you who care about testing function properties. As the abstract notes, this is the first paper to nail down the true (non-adaptive) query complexity for tolerantly testing some natural property of boolean functions. The main result of this paper presents a lower bound of \(2^{\widetilde{\Omega}(\sqrt{k \log(1/\varepsilon)})}\) on the task of non-adaptive tolerant \(k\)-junta testing. The paper presents an almost matching non-adaptive algorithm as well.

Testing Intersectingness of Uniform Families by Ishay Haviv and Michal Parnas (arXiv) Let \(\mathcal{F}\) denote an intersecting family all sets in which are subsets of an underlying \(n\)-element universe. This means that for any \(F_1, F_2 \in \mathcal{F}\), you have that \(F_1 \cap F_2 \neq \emptyset\). Some of you might immediately recall Erdos-Ko-Rado theorem which asserts an upperbound on the size of such an intersecting family where every set has size \(k\). Another famous result is Lovasz’s (positive) resolution of Kneser’s conjecture which asserts an lowerbound on the number of intersecting families you need to cover all \(k\)-subsets of \([n]\). For ease of discussion, let us follow the authors and cook up a property testing problem \(\textsf{INTERSECTING}_{n,k, \varepsilon}\). In this problem, you are given access to the indicator \(f \colon {[n] \choose k} \to \{0,1\}\) encoding the family \(\mathcal{F}\) and you ask whether \(\mathcal{F}\) is intersecting or whether it is \(\varepsilon\)-far from it. Recently, Chen-De-Li-Nadimpalli-Servedio explored the non-uniform-set-size variant of this problem (which we covered here). They presented one-sided algorithms with a non-adaptive query bound of \(2^{\widetilde{O}(\sqrt{n \log(1/\varepsilon)})}\) for this problem and they also showed an almost matching lowerbound. The featured paper contrasts these results with the situation you obtain when all the set sizes are indeed the same (that is, the paper explores the testability of \(\textsf{INTERSECTING}_{n,k, \varepsilon}\). Of the numerous results in the paper, let me highlight one: you can test \(\textsf{INTERSECTING}_{n,k, \varepsilon}\) with two-sided error with a mere \(O\big(\log n \cdot \frac{1}{\varepsilon} \big)\) queries. This result holds for \(\varepsilon \geq \Omega(k/n)^r\) for a fixed \(r\).

Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries by Xi Chen, Yumou Fei and Shyamal Patel (arXiv) Decision lists are a popular and convenient way to represent a boolean function which is learnable from examples. In more detail, a decision list is a collection of pairs \((\alpha_1, \beta_1), (\alpha_2, \beta_2), \ldots (\alpha_k, \beta_k)\) (here, \(\alpha_j\)’s denote literals and \(\beta_j\)’s are bits). This list defines a boolean function \(f \colon \{0,1\}^n \to \{0,1\}\) as follows: for any \(\mathbf{x} \in \{0,1\}^n\), you let \(f(x) = \beta_j\) where \(j\) is the smallest index such that \(\alpha_j\) is satisfied by \(\mathbf{x}\). With this (not super rigorous) definition out of the way, I can now tell you about the main result of this featured paper. The main theorem of this paper asserts that in the distribution-free framework for property testing, you still get sublinear time algorithms for testing decision lists. In particular, thanks to this paper, now you can engineer a two-sided adaptive distribution free algorithm for testing decision lists which makes runs in time \(\widetilde{O}(n^{11/12})\).

Simple algorithms to test and learn local Hamiltonians by Francisco Escudero Gutiérrez (arXiv) The featured paper considers the task of (tolerantly) testing and learning an \(n\)-qubit \(k\)-local Hamiltonian from queries to its evolution operator. The main result of the paper asserts that the task of Tolerant Hamiltonian Locality Testing can be done with a mere \(1/(\varepsilon_2 – \varepsilon_1)^8\) queries to the evolution operator.

Local Test for Unitarily Invariant Properties of Bipartite Quantum States by Kean Chen, Qisheng Wang, Zhicheng Zhang (arXiv) Lots of investigations on quantum entanglement consider bipartite quantum states. The featured paper considers the task of testing properties of bipartite pure states. The paper begins by recalling a helpful duality between a property of bipartite pure states being unitarily invariant on one part, and the property being locally testable on the other part. This duality does not offer any insights into the query complexity of the local tester. The main result of the paper proves that the local tester indeed achieves optimal sample complexity over all global testers.

Learning Intersections of Halfspaces with Distribution Shift: Improved Algorithms and SQ Lower Bounds by Adam R. Klivans, Konstantinos Stavropoulos, Arsen Vasilyan (arXiv) Consider the standard setup of supervised learning with a twist. Namely, the distribution from which you receive samples in the training phase (\(\mathcal{D}\)) and the distribution from which the samples are taken in the test phase (\(\mathcal{D}’\)) are not necessarily the same (and hence the name — distribution shift). For example, this situation may arise if you use one set of equipments in the training phase and another during the test phase. This model was explored in a previous work by the same set of authors where they considered the task of obtaining a low-error classifier (on \(\mathcal{D}’\)) when they are additionally told that the training samples pass some helpful test. In this paper, the authors explore the problem of testing intersections of halfspaces with respect to Gaussian Training Distributions. The main contribution of the paper is a set of new positive results which extend the results from PAC learnability to the learnability under the new model. Indeed, under some reasonably mild assumptions, the bounds in the new model match the bounds from the standard PAC model. For quantitative details, please refer to the paper.

Welcome to the posting for first month of 2024! We hope you had a good start to this year. Last month, we had 3 papers. So, without further delay, let’s get started.

On locally-characterized expander graphs (a survey) by Oded Goldreich (ECCC) In this paper, written in an expository style, Goldreich surveys the result of Adler, Kohler and Peng which we covered in our posts on May 2021 and August 2020. The survey begins by reminding the reader what a locally-characterizable graph property is. A family of graphs \(\mathcal{G}\) is said to be characterized by a finite class \(\mathcal{F}\) of graphs if every graph \(G \in \mathcal{G}\) is \(F\)-free for all \(F \in \mathcal{G}\). Thanks to its connections with expressibility in first order logic, one would expect the a locally-characterizable graph property to admit testers depending only on the proximity parameter (in the bounded degree graph model). So, it was quite a surprise when Adler, Kohler and Peng showed that there are locally characterizable graph properties which provably require testers whose query complexity increases with the size of the graph. The main theorem of Adler, Kohler and Peng describes the locally characterizable property that is hard to test. This characterization asserts that you can get your hands on a finite class \(\mathcal{F}\) of graphs so that \(\mathcal{F}\)-freeness of a graph \(G\) means that the graph is a (bounded-degree) expander. One of the key ingredients used in this proof is the Zig-Zag construction of Reingold, Vadhan and Wigderson.

Fast Parallel Sampling under Isoperimetry by Nima Anari, Sinho Chewi, and Thuy-Duong Vuong (arXiv) The featured paper considers the task of sampling (in parallel) from a continuous distribution \(\pi\) supported over \(\mathbb{R}^d\). The main result in the paper shows that for distributions which satisfy a log-Sobolev inequality, you can use parallelized Langevin Algorithms and obtain samples from a distribution \(\pi’\) where \(\pi’\) and \(\pi\) are close in KL-divergence. As an application of their techniques, the authors show that their results can be used to do obtain RNC samples for directed Eulerian Tours and asymmetric Determinantal Point Processes.

Holey graphs: very large Betti numbers are testable by Dániel Szabó, Simon Apers (arXiv) This paper considers the problem of testing whether an input graph \(G\) has a very large \(k\)-th Betti Number (at least \((1-\delta) d_k\) where \(d_k\) denotes the number of \(k\)-cliques in \(G\) and \(\delta > 0\) is sufficiently small) in the dense graph model. As the title indicates, the result says that this property is testable for constant \(k\). Earlier in 2010, Elek investigated this question in the bounded degree model. Elek’s main result showed that with a number of queries \(q = q(\varepsilon\), you can obtain an estimate to the \(k\)-th Betti Number which is within an additive \(\pm \varepsilon n\) of the true \(k\)-th Betti Number. Let us contrast this result with the setting of dense graphs. The authors note that in the dense graph model, getting an estimate to the \(k\)-th Betti Number which is within an additive $\pm \varepsilon d_k$ of the true value needs \(\Omega(n)\) queries. This is the reason why the authors consider the formulation above.

Sorry for delay in getting this month’s post out. This time we had seven (EDIT) eight (LATER EDIT) nine papers. Thanks to our readers for pointing out a paper we missed. Do let us know if we missed any (EDIT) others. Alright, without further delay, let us look at this month’s spread.

Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas by Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, and Rocco A. Servedio (arXiv) Let us begin with a paper on property testing of boolean functions over the binary hypercube \(\{0,1\}^n\). Quoting from the abstract.

[This paper gives] the first superpolynomial (in fact, mildly exponential) lower bounds for tolerant testing of monotonicity, unateness, and juntas with a constant separation between yes and no cases.

Let us take a little dip to get a superficial feel for what techniques the paper uses for boolean monotonicity. The key lies in an adaptation of the lower bound techniques pioneered in the paper of Pallavoor-Raskhodnikova-Waingarten (PRW) which considers distributions over “yes functions” (which are \(\varepsilon/\sqrt{n}\)-close to monone) and “far functions” (which are $\eps$-far from being monotone). PRW split the \(n\) variables into \(n/2\) control variables and \(n/2\) action variables. PRW consider the subcubes indexed by bit-strings where the control variables are balanced. The function value is chosen carefully on these subcubes which ensures any tester that reliably distinguishes yes and no functions need to sample bit-strings from the same balanced subcube which differ in lots of action variables. As PRW argue, this event occurs with low probability if the allowed number of queries is small. The key insight of the featured paper is to modify the PRW construction by using random monotone DNF formulas due to Talagrand. If this sets up your appetite, go read the paper!

Testing Junta Truncation by William He and Shivam Nadimpalli (arXiv)

Let \(f \colon \{0,1\}^n \to \{0,1\}\) be a \(k\)-junta. You are given a set \(\mathcal{U}_{\text{yes}} = \bigl\{0,1\bigr\}^n\) and a set \(\mathcal{U}_{\text{no}} = \bigl\{x \in \{0,1\}^n \colon f(x) = 1 \bigr\}.\) Consider uniform distributions supported on both of these sets which we call \(\mathcal{D}_{\text{yes}}\) and \(\mathcal{D}_{\text{no}}\). Finally, we define a distribution \(\mathcal{D} = \begin{cases} \mathcal{D}_{\text{yes}} \text{ w.p. } 1/2 \\ \mathcal{D}_{\text{no}} \text{ w.p } 1/2 \end{cases}.\)

You are given \(t\) samples from the distribution \(D\). The task is to decide whether \(D\) is the yes distribution or the no distribution. The featured paper shows you can reliably solve this task with \(t \leq \min(2^k + \log{n \choose k }, 2^{k/2} \log^{1/2}{n \choose k})\) samples. The paper also supplements this result with a lower bound of \(t \geq \log{n \choose k}\) samples fewer than which cannot be used to reliably distinguish these two distributions. The results suggest that this “testing junta truncation” problem requires learning the set of relevant variables for the junta.

Longest Common Substring and Longest Palindromic Substring in \(\mathbf{\widetilde{O}(\sqrt n)}\) Time by Domenico Cantone, Simone Faro, Arianna Pavone, and Caterina Viola (arXiv) I paraphrase from the abstract of this paper. You know the longest common substring and longest palindromic substring as classic problems in computer science both of which can be solved in linear time using suffix trees. Recently, quantum algorithms were proposed for both of these problems in the query model both of which issue only \(o(n)\) quantum queries. The featured paper notes that this query model has a shortcoming namely when it comes to real life implementation on actual hardware. The current paper address this shortcoming by presenting \(o(n)\) quantum-query algorithms in the circuit model of computation.

Testing properties of distributions in the streaming model by Sampriti Roy and Yadu Vasudev (arXiv) Alright, now let us consider a different twist on distribution testing. Suppose you have a small memory. You obtain a bunch of samples to solve some standard distribution testing task but the twist is of course you cannot store all the samples. What can you say about how sample complexity trades off against space complexity? The featured paper studies this trade off in the standard access model and the conditional access model. One of the results of the paper asserts that in the conditional access model, you can do identity testing with \( \widetilde{O}\bigl(\frac{\log^4n}{\varepsilon^4}\bigr)\) samples while using only \(O\bigl(\frac{\log^2 n}{\varepsilon^2} \bigr)\) bits of memory.

Testing Spreading Behavior in Networks with Arbitrary Topologies by Augusto Modanese and Yuichi Yoshida (arXiv) We covered the problem of testing dynamic environments in this March 2014 post and that May 2021 post earlier. The goal here is to check whether a dynamically evolving system evolves according to some fixed rule or whether it evolves according to some fixed rule or whether the system is far from systems that evolve according to that fixed rule. The May 2021 post covered a paper which shows you can test dynamically evolving systems that evolve according to what is called the threshold rule. The featured paper considers rules motivated by some kind of models for infection spreading. One of the results in the paper presents one-sided and two-sided testers (with \(O(1/\varepsilon)\) query complexity) for testing a single step of evolution (on bounded degree graphs) with these rules.

A Tight Lower Bound of Ω(log n) for the Estimation of the Number of Defective Items by Nader Bshouty and Gergely Harcos (ECCC) The featured paper considers a problem in group testing. Let us quickly review the setup for group testing. You are given some ground set \(X\) of \(|X| = n\) items. Suppose the set of items in the set \(I \subseteq X\) is defective. The challenge is to devise a test which refers to some set \(Q \subseteq X\) where the test is said to be successful iff \(Q \cap I \neq \emptyset\). This paper presents lower bounds for non-adpative algorithms for group testing. And as the title says, if your algorithm wishes to estimate the number of defective items to within a constant factor, you better pay up \(\Omega(\log n)\) tests.

A tight lower bound on non-adaptive group testing estimation by Tsun-Ming Cheung, Hamed Hatami, and Anthony Ostuni (arXiv) As our readers pointed out, this paper is concurrent with the paper above and achieves the same lower bound. Indeed, this holds for both the one-sided and the two-sided variants. Furthermore, as this paper shows if one knows the set \(I\) satisfies \(L \leq |I| \leq U\) then you can show both one-sided and two-sided lower bounds of \(\Omega(U/L)\) non-adaptive queries if you want a constant approximation to \(|I|\).

On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model by Oded Goldreich and Laliv Tauber (ECCC) This paper looks like a fantastic read for your students — especially when written in such an engaging style spanning (only) 18 highly readable pages. As the title indicates, this paper considers the challenge of testing isomorphism to a fixed graph in the bounded degree model. The main result of this paper asserts that for almost all \(d\)-regular graphs \(H\) on \(|V(H)| = n\) vertices, testing isomorphism to \(H\) can be done in about \(\approx \sqrt n\) queries. The paper also presents an almost matching (query) lower bound which also holds for almost all graphs \(H\).

Tolerant Testing of High-Dimensional Samplers with Subcube Conditioning by Gunjan Kumar, Kuldeep S. Meel, and Yash Pote (arXiv) Let us consider the distribution testing setup with a twist: Suppose you are given some unknown distribution \(\mathcal{Q}\) supported over \(\{0,1\}^n\) and you want to sample from it conditioned on some predicate \(\mathcal{Q}\). The question is can you efficiently check whether these are legit samples (satisfying the predicate) which are taken from the distribution \(\mathcal{Q}\). Our October 2020 news covered a tolerant tester on this problem which involved some subset of the authors of the current paper. The featured paper considers what additional leverage you gain if you are given access to a sampling oracle which can sample from “conditioned subcubes.” In this model, you can query some subcube and after issuing a query, you will receive an element \(x\) from this subcube with probability proportional to original probability weight of \(x\). The paper provides a tolerant tester in this setup which makes at most \(\widetilde{O}(n^3/(\varepsilon_2 – \varepsilon_1)^5)\) queries to this sampling oracle.

Apologies, dear readers for the delay in getting out this month’s post. This month we had three papers — all on testing properties of graphs! (EDIT: Updated later) four papers: three on property testing problems on graphs and the last one on testing convexity. One of the featured papers this month revisits the problem of testing the properties of directed graphs and comes back with a happy progress report. Alright, let’s dig in.

A Distributed Conductance Tester Without Global Information Collection by Tugkan Batu, Chhaya Trehan (arXiv) One of the classic questions in property testing considers the task of testing expansion. Here, you are interested in knowing whether the input graph has conductance at least \(\alpha\) or it is far from having conductance at most \(\alpha^2\). On a parallel track, we recall that thanks to the classic work of Parnas and Ron, we know there are connections between distributed algorithms and graph property testing. Meditating on these connections led to the emergence of distributed graph property testing as an active area of research. The featured paper considers the task of testing expansion in the distributed framework. The algorithms presented give a distributed implementation of multiple random walks from all vertices, and controls the congestion of the implementation. In particular, this leads to a \(O(\log n/\alpha^2)\) round expansion-tester. In a first attempt at such an implementation, you might note that you need to track how well short random walks mix when started from a bunch of randomly chosen vertices. This seems to require maintaining some global state/global aggregate information. One of the important features of their algorithm (as mentioned in the title) does away with the need to maintain such global states. As a closing remark, I note the algorithm presented in this paper does not require the graph to be bounded degree.

Testing versus estimation of graph properties, revisited by Lior Gishboliner, Nick Kushnir, Asaf Shapira (arXiv) This paper considers the task of additively estimating the distance to a property \(\mathcal{P}\) of a dense graph. Let me set up some context to view the results in the featured paper by summarizing what was known before. One of the early important results in this area is the original result of Fischer and Newman which shows that any testable graph property admits a \(\pm \varepsilon\) distance approximation algorithm, which follows from the regularity lemma. However, the query complexity of the resulting algorithm is a Wowzer-style bound. Later, Hoppen et al., building upon tools from the classic work of Conlon and Fox, demonstrated that this bound of \(twr(poly(1/\varepsilon))\) also holds for testable hereditary properties. Fiat and Ron introduced a decomposition machinery that allowed them to decompose a “complex” property into a collection of simpler properties. They used this decomposition to estimate distances to a vast collection of graph properties. They also asked if it was possible to find a transformation using which one can bypass the blowup in query complexity incurred by Fischer and Newman for some rich class of graph properties. The featured paper proves that for a hereditary graph property, you can in fact get algorithms where the query complexity for distance estimation only grows as \(\exp(1/\varepsilon)\). Additionally, for every testable graph property, you can get distance estimators for that property whose query complexity only grows doubly exponentially in \(1/\varepsilon\) (as opposed to the tower bound earlier).

An Optimal Separation between Two Property Testing Models for Bounded Degree Directed Graphs by Pan Peng, Yuyang Wang (arXiv) Unlike undirected graphs, directed graph properties have not received as much attention in the property testing community. In a classic work, Bender and Ron considered two natural models for studying property testing on directed graphs. The first model is one where you can only follow the “out” edges or the so-called unidirectional model. In the other model, you are allowed to follow both the “out” edges and the “in” edges incident on the vertex which is also called the bidirectional model. The featured paper considers directed graphs where the in-degree and the out-degrees are both bounded in both of the models mentioned above. The graph is presented to you in the adjacency list format (tailored for the model you consider). The paper shows that even for the fundamental task of subgraph-freeness, the directed world has some interesting behavior with respect to the two models above. Let me showcase one of the catchy results from the paper which illustrates this separation nicely. Take a connected directed graph \(H\) with \(k\) source components. The paper shows that for sufficiently small \(\varepsilon\), testing whether a directed graph \(G\) is \(H\)-free or \(\varepsilon\)-far from being \(H\)-free requires \(\Omega(n^{1-1/k})\) unidirectional queries. On the other hand, in the bidirectional model, this can be done with a mere \(O_{\varepsilon, d, k}(1)\) number of queries.

(EDIT: Added later)

Testing Convexity of Discrete Sets in High Dimensions by Hadley Black, Eric Blais, Nathaniel Harms (arXiv) As the title suggests, this paper explores the problem of testing convexity. To understand the notion of convexity explored in the paper, consider the following setup: You call a set \(S \subseteq \{-1, 0, 1\}^n\) convex if there exists a convex set \(S’ \subseteq \mathbb{R}^n\) such that \(S = S’ \cap \{-1,0,1\}^n\). And you call a set \(S \subseteq \{-1,0,1\}^n\) far from being convex if for every convex \(T \subseteq \{-1,0,1\}^n\), you have \(|S \oplus T| \geq \varepsilon 3^n\). The paper shows that when you are allowed membership queries, you can test convexity non-adaptively with a one-sided error by issuing \(3^{O(\sqrt{n \log(1/\varepsilon)})}\) queries. Also, they prove an almost matching lower bound. Finally, with a lower bound of \(3^{\Omega(n)}\) when confined to using sample-based testers, authors provably demonstrate that membership queries indeed buy you some undeniable power for testing convexity in high dimensions.

After an empty month, the engines of PTReview are roaring back to life with a fresh batch of papers for this month’s edition. In total, we have four papers that are sure to pique your interest. It’s been an action-packed month with a diverse range of topics covered in the featured papers. The first paper delves into new variations in distribution testing, while the second paper discusses optimal testers for Bayes Nets. The third paper focuses on optimal tolerant junta-testers, and the final paper presents a cool monotonicity tester over hypergrids.

Distribution Testing Under the Parity Trace by Renato Ferreira Pinto Jr and Nathaniel Harms (arXiv) The featured paper considers the classic setup in distribution testing with a twist. To explain the results, let me introduce the framework considered in this work. Consider distributions supported over \([n]\). Suppose I want to design distribution testers where instead of obtaining samples in the usual way, I first obtain an ordered list of samples, I store it in a sequence \(S\) and only the least significant bit of each element of \(S\) is made available to your distribution testing algorithm. This is called a parity trace. Note that with this access model, suddenly a bunch of standard tasks become non-trivial. To take an example from the paper, you can no longer distinguish between the uniform distribution supported on \(\{1,2, \ldots, n\}\) and the uniform distribution supported on \(\{n+1, n+2, \ldots 2n\}\) in this access model. Nevertheless, the paper shows, you can still obtain testers which require only sublinear number of accesses for testing uniformity in this model.

Another cool feature of this big paper is an unexpected foray into the trace reconstruction literature from a property testing viewpoint. I wish I understood the formal connection better to describe a bit more about it. But for now, let me leave that as an appetizer which (hopefully) encourages you to take a look at the paper.

New Lower Bounds for Adaptive Tolerant Junta Testing by Xi Chen and Shyamal Patel (arXiv) If you are a regular here on the PTReview corner, you are probably no stranger to the tolerant junta testing problem. As a corollary to the main result, the paper in question proves a lower bound of \(k^{\Omega(\log k)}\) queries on any adaptive algorithm that wishes to test whether the input function \(f\) is \(\varepsilon_1\) close to being a \(k\)-junta or whether it is \(\varepsilon_2\)-far \(\left(\text{where } \varepsilon_2 \geq \varepsilon_1 + \displaystyle\frac{1}{poly(k)}\right)\). Indeed, another remarkable achievement of the paper is that it achieves a superpolynomial separation between non-tolerant versions and the tolerant versions of any natural property of boolean functions under the adaptive setting.

Near-Optimal Degree Testing for Bayes Nets by Vipul Arora, Arnab Bhattacharyya, Clément L. Canonne (our own!) and Joy Qiping Yang (arXiv) This paper continues a line of investigation which a subset of the authors were a part of (which we also covered in our News for April 2022). Let us remind ourselves of the setup. You are given a probability distribution \(\mathcal{P}\) supported over the Boolean Hypercube. Suppose \(\mathcal{P}\) can be generated by a Bayseian Network. You may think of a Bayesian Network as a DAG where each vertex tosses a coin (with different heads probabilities). The question seeks to test whether \(\mathcal{P}\) admits a sparse Bayesian Net (in the sense of each vertex having small in-degree). The main result of the paper gives an algorithm for this task which requires \(\Theta(2^{n/2}/\varepsilon^2)\) samples. The paper also proves an almost matching lower bound.

A \(d^{1/2+o(1)}\) Monotonicity Tester for Boolean Functions on \(d\)-Dimensional Hypergrids by Hadley Black, Deeparnab Chakrabarty and C. Seshadhri (again, our own!) (arXiv) Again, the problem of monotonicity testing of boolean functions hardly requires any detailing to the regular readers of PTReview. As you can see in our News from November 2022 there were two concurrent papers mulling over this problem over the hypergrid domain. The featured paper is the result of a dedicated pursuit by the authors and the key result is what the title says. Namely, you can test monotonicity with a number of (non-adaptive, one-sided) queries that has no dependence on \(n\).

All the best to everyone for a Happy 2023. The holiday season is ripe with lots of papers to engage our readers. So, we have nine papers and we hope some of those will catch your fancy. As a new year treat, we also feature Gilmer’s constant lower bound on the union-closed sets problem of Frankl. On we go.

Sublinear Time Algorithms and Complexity of Approximate Maximum Matching by Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein (arXiv) This paper makes significantly advances our understanding of the maximum matching problem in the sublinear regime. Your goal is to estimate the size of the maximum matching and you may assume that you have query access to the adjacency list of your graph. Our posts from Dec 2021 and June 2022 reported some impressive progress on this problem. The upshot from these works essentially said that you can beat greedy matching and obtain a \(\frac{1}{2} + \Omega(1)\) approximate maximum matching in sublinear time. Let me first go over the algorithmic results from the current paper. The paper shows the following two algorithmic results:

(1) An algorithm that runs in time \(n^{2 – \Omega_{\varepsilon}(1)}\) and returns a \(2/3 – \varepsilon\) approximation to maximum matching in general graphs, and

(2) An algorithm that runs in time \(n^{2 – \Omega_{\varepsilon}(1)}\) and returns a \(2/3 + \varepsilon\) approximation to maximum matching size in bipartite graphs.

The question remained — can we show a lower bound that grows superlinearly with \(n\). The current work achieves this and shows that even on bipartite graphs, you must make at least \(n^{1.2 – o(1)}\) queries to the adjacency list to get a better than \(2/3 + \Omega(1)\) approximation. (An aside: A concurrent work by Bhattacharya-Kiss-Saranurak from December also obtains similar algorithmic results for approximating the maximum matching size in general graphs).

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an \(\widetilde{O}(n \sqrt d)\) Monotonicity Tester by Hadley Black, Deeparnab Chakrabarty, C. Seshadhri (arXiv) Boolean Monotonicity testing is as classic as classic gets in property testing. Encouraged by the success of isoperimetric theorems over the hypercube domain and the monotonicity testers powered by these isoperimetries (over the hypercube), one may wish to obtain efficient monotonicity testers for the hypergrid \([n]^d\). Indeed, the same gang of authors as above showed in a previous work that a Margulis style directed isoperimetry can be extended from the lowly hypercube to the hypergrid. This resulted in a tester with \(\widetilde{O}(d^{5/6})\) queries. The more intricate task of proving a directed Talagrand style isoperimetry that underlies the Khot-Minzer-Safra breakthrough was a challenge. Was. The featured work extends this isoperimetry from the hypercube to the hypergrid and this gives a tester with query complexity \(\widetilde{O}(n \sqrt d)\) which is an improvement over the \(d^{5/6}\) bound for domains where \(n\) is (say) some small constant. But as they say, when it rains, it pours. This brings us to a concurrent paper with the same result.

Improved Monotonicity Testers via Hypercube Embeddings by Mark Braverman, Subhash Khot, Guy Kindler, Dor Minzer (arXiv) Similar to the paper above, this paper also obtains monotonicity testers over the hypergrid domain, \([n]^d\), with \(\widetilde{O}(n^3 \sqrt d)\) queries. This paper also presents monotonicity testers over the standard hypercube domain — \(\{0,1\}^d\) in the \(p\)-biased setting. In particular, their tester issues \(\widetilde{O}(\sqrt d)\) queries to successfully test monotonicity on the \(p\)-biased cube. Coolly enough, this paper also proves directed Talagrand style isoperimetric inequalities both over the hypergrid and the \(p\)-biased hypercube domains.

Toeplitz Low-Rank Approximation with Sublinear Query Complexity by Michael Kapralov, Hannah Lawrence, Mikhail Makarov, Cameron Musco, Kshiteej Sheth (arXiv) Another intriguing paper for the holiday month. So, take a Toeplitz matrix. Did you know that any psd Toeplitz matrix admits a (near-optimal in the Frobenius norm) low-rank approximation which is itself Toeplitz? This is a remarkable statement. The featured paper proves this result and uses it to get more algorithmic mileage. In particular, suppose you are given a \(d \times d\) Toeplitz matrix \(T\). Armed with the techniques from the paper you get algorithms that return a Toeplitz matrix \(\widetilde{T}\) with rank slightly bigger than \(rank(T)\) which is a very good approximation to \(T\) in the Frobenius norm. Moreover, the algorithm only issues a number of queries sublinear in the size of \(T\).

Sampling an Edge in Sublinear Time Exactly and Optimally by Talya Eden, Shyam Narayanan and Jakub Tětek (arXiv) Regular readers of PTReview are no strangers to the fundamental task of sampling a random edge from a graph which you can access via query access to its vertices. Of course, you don’t have direct access to the edges of this graph. This paper considers the task of sampling a truly uniform edge from the graph \(G = (V,E)\) with \(|V| = n, |E| = m\). In STOC 22, Tětek and Thorup presented an algorithm for a relaxation of this problem where you want an \(\varepsilon\)-approximately unifrom edge. This algorithm runs in time \(O\left(\frac{n}{\sqrt{m}} \cdot \log(1/\varepsilon) \right)\). The featured paper presents an algorithm that samples an honest to goodness uniform edge in expected time \(O(n/\sqrt{m})\). This closes the problem as we already know a matching lower bound. Indeed, just consider a graph with \(O(\sqrt m)\) vertices which induce a clique and all the remaining components are singletons. You need to sample at least \(\Omega(n/\sqrt m)\) vertices before you see any edge.

Support Size Estimation: The Power of Conditioning by Diptarka Chakraborty, Gunjan Kumar, Kuldeep S. Meel (arXiv) This work considers the classic problem of support size estimation with a slight twist. You are given access to a stronger (conditioning based) sampling oracle. Let me highlight one of the results from this paper. So, you are given a distribution \(D\) where \(supp(D) \subseteq [n]\). You want to obtain an estimate to \(supp(D)\) that lies within \(supp(D) \pm \varepsilon n\) with high probability. Suppose you are also given access to the following sampling oracle. You may choose any subset \(S \subseteq [n]\) and you may request a sample \(x \sim D\vert_S\). An element \(x \in S\) is returned with probability \(D\vert_S(x) = D(x)/D(S)\) (for simplicity of this post, let us assume \(D(S) > 0\)). In addition, this oracle also reveals for you the value \(D(x)\). The paper shows that the algorithmic task of obtaining a high probability estimate to the support size (to within \(\pm \varepsilon n\)) with this sampling oracle admits a lower bound of \(\Omega(\log (\log n)\) calls to the sampling oracle.

Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time by Valerie King, Alex Thomo, Quinton Yong (arXiv) Degeneracy is one of the important graph parameters which is relevant to several problems in algorithmic graph theory. A graph \(G = (V,E)\) is \(\delta\)-degenerate if all induced subgraphs of \(G\) contain a vertex with degree at most \(\delta\). The featured paper presents algorithms for a \((1 + \varepsilon)\)-approximation to degeneracy of \(G\) where you are given access to \(G\) via its adjacency list.

Learning and Testing Latent-Tree Ising Models Efficiently by Davin Choo, Yuval Dagan, Constantinos Daskalakis, Anthimos Vardis Kandiros (arXiv) Ising models are emerging as a rich and fertile frontier for Property Testing and Learning Theory researchers (at least to the uninitiated ones like me). This paper considers latent-tree ising models. These are ising models that can only be observed at their leaf nodes. One of the results in this paper gives an algorithm for testing whether the leaf distributions attached to two latent-tree ising models are close or far in the TV distance.

A constant lower bound for the union-closed sets conjecture by Justin Gilmer (arXiv) The union-closed sets conjecture of Frankl states that for any union closed set system \(\mathcal{F} \subseteq 2^{[n]}\), it holds that there is a mysterious element \(i \in [n]\) that shows up in at least \(c = 1/2\) of the sets in \(\mathcal{F}\). Gilmer took a first swipe on this problem and gave a constant lower bound of \(c = 0.01\). This has already been improved by at least four different groups to \(\frac{3-\sqrt{5}}{2}\), a bound which is the limit of Gilmer’s method (which takes all of only 9 pages!).

The key lemma Gilmer proves is the following. Suppose you sample two sets: \(A, B \sim \mathcal{D}_n\) (iid) from some distribution \(\mathcal{D}_n\) over the subsets of \([n]\). Suppose for every index \(i \in [n]\), it holds that the probability that the element \(i\) shows up in the random set \(A\) is at most $0.01$. Then you have \(H(A \cup B) \geq 1.26 H(A)\). This is all you need to finish Gilmer’s proof (of \(c = 0.01\)). The remaining argument is as follows. Suppose, by the way of contradiction, that no element shows up in at least \(0.01\) fraction of sets in the union closed family \(\mathcal{F}\). An application of the key lemma would then give \(H(A \cup B) > H(A)\) which is a contradiction if \(A,B\) are chosen uniformly from \(\mathcal{F}\). The proof of the key lemma is also fairly slick and uses pretty simple information theoretic tools.