This summer is a very exciting one for property testing, with seven (!) papers uploaded during the month of August. In particular, there have been a number of results on testing unateness.

An \(\tilde O(n)\) Queries Adaptive Tester for Unateness, by Subhash Khot and Igor Shinkar (arXiv, ECCC). A Boolean function is unate if, for each \(i \in [n]\), it is monotone non-increasing or monotone non-decreasing in coordinate \(i\). This is a generalization of monotonicity, one of the most studied problems in the property testing literature. This paper gives an adaptive algorithm for testing if a Boolean function is unate. The algorithm requires \(\tilde O(n)\) queries, improving on the \(O(n^{1.5})\) query tester of Goldreich et al. from 2000.

A \(\tilde O(n)\) Non-Adaptive Tester for Unateness, by Deeparnab Chakrabarty and C. Seshadhri (arXiv, ECCC). The unateness testing continues! This paper also gives a \(\tilde O(n)\) algorithm for this problem, but improves upon the previous work by making non-adaptive queries. The algorithm and analysis are very clean and elegant — with a theorem by Chakrabarty et al. in place, they take up just a single page!

Testing Unateness of Real-Valued Functions, by Roksana Baleshzar, Meiram Murzabulatov, Ramesh Krishnan S. Pallavoor, and Sofya Raskhodnikova (arXiv). The final paper this month on testing unateness, this work studies real-valued functions on the hypergrid \([n]^d\) (as opposed to Boolean functions on the hypercube). They give an adaptive algorithm requiring \(O\left(\frac{d \log (\max (d,n))}{\varepsilon}\right)\) queries, generalizing the above result by Khot and Shinkar, which works only for Boolean functions on the hypercube and requires \(O\left(\frac{d \log d}{\varepsilon}\right)\) queries. Additionally, they prove lower bounds for this setting (of \(\Omega(\min(d, |R|^2))\), where \(R\) is the range of the function) and the Boolean hypercube setting (of \(\Omega(\sqrt{d}/\varepsilon)\)). The latter lower bound leaves open a tantalizing question: does a \(O(\sqrt{d})\) query algorithm exist? In other words, is testing unateness no harder than testing monotonicity?

Testing k-Monotonicity, by Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer (arXiv, ECCC). And now, a different generalization of monotonicity! This paper studies testing \(k\)-monotonicity, where a Boolean function over a poset \(\mathcal{D}\) is \(k\)-monotone if it alternates between the values \(0\) and \(1\) at most \(k\) times on any ascending chain in \(\mathcal{D}\). Classical monotonicity is then \(1\)-monotone in this definition. On the hypercube domain, the authors prove a separation between testing monotonicity and testing \(k\)-monotonicity and a separation between testing and learning. They also present a tolerant test for \(k\)-monotonicity over the hypergrid \([n]^d\) with complexity independent of \(n\).

The Dictionary Testing Problem, by Siddharth Barman, Arnab Bhattacharyya, and Suprovat Ghoshal (arXiv). The dictionary learning problem has enjoyed extensive study in computer science. In this problem, given a matrix \(Y\), one wishes to construct a decomposition \(Y = AX\) such that each column of \(X\) is \(k\)-sparse. In the settings typically studied, such a decomposition is guaranteed to exist. This paper initiates the dictionary testing problem, in which one wishes to test whether \(Y\) admits such a decomposition, or is far from it. The authors provide a very elegant characterization — it admits a decomposition iff the columns of \(Y\) have a sufficiently narrow Gaussian width.

The Sparse Awakens: Streaming Algorithms for Matching Size Estimation in Sparse Graphs, by Graham Cormode, Hossein Jowhari, Morteza Monemizadeh, and S. Muthukrishnan (arXiv). This paper provides streaming algorithms for estimating the size of the maximum matching in graphs with some underlying sparsity. They give a one-pass algorithm for insert-only and dynamic streams with bounded arboricity, and a two-pass algorithm for random order streams with bounded degree. Interestingly, for the latter result, they use local exploration techniques, which have seen previous use in the property testing literature.

Testing Assignments to Constraint Satisfaction Problems, by Hubie Chen, Matt Valeriote, and Yuichi Yoshida (arXiv). Given a CSP from a finite relational structure \(A\) and query access to an assignment, is the CSP satisfied? This paper shows a dichotomy theorem which characterizes which \(A\) admit a constant-query test. They go on to show a trichotomy theorem for when instances may include existentially quantified variables, classifying which \(A\) admit a constant-query test, which admit only a sublinear-query test, and which require a linear number of queries.

Minimizing Quadratic Functions in Constant Time, by Kohei Hayashi and Yuichi Yoshida (arXiv). This paper investigates the problem of (approximately) minimizing quadratic functions in high-dimensions. Prior approaches to this problem scale poorly with the dimension — at least linearly, if not worse. This work uses a sampling-based method to avoid paying this cost: the resulting time complexity is completely independent of the dimension!