A blast from the (recent) past: the open problems from the Workshop on Data Summarization held in March 2018 in the University of Warwick have been posted online, and are available here.
Fast-forward to this summer: the recently concluded 3rd Workshop on Local Algorithms, which took place last month at ETH Zurich, featured an open problems session. The list of open problems can be found in this link, or here for a PDF version.
As open problems of the month, we state here the two questions discussed in our recent guest post by Oded Goldreich:
Note that this will yield a one-sided error tester for affinity, which we believe is not known. Actually, we would also welcome a two-sided error reduction that, when combined with the linearity tester, yields a tester of complexity \(O(1/\epsilon)\) rather than \(\tilde{O}(1/\epsilon)\).
Turning to the task of testing monomials, we recall that the solution of [PRS02] is based on employing self-correction to the following test that refers to the case that \(H=\{x:AX=b\}\) is an \((\ell-k)\)-dimensional affine space. Basically, the test selects a random \(x\in H\) and a random \(y\in\{0,1\}^\ell\), and checks whether it holds that \(y\in H\) if and only if \(x\wedge y \in H\), where \(\wedge\) denotes the bit-by-bit product of vectors. It is painfully shown in [5] that if \(H\) is not a translation by \(1^\ell\) of an axis-aligned linear space, then the check fails with probability \(\Omega(2^{-k})\). Furthermore, it is shown that for a constant fraction of the \(x\)’s (in \(H\)), the check fails on a \(\Omega(2^{-k})\) fraction of the \(y\)’s (in \(\{0,1\}^\ell\)). This strengthening is important, since selecting \(x\in H\) uniformly requires \(\Theta(2^k)\) trials. Recall that proving the foregoing assertion for \(k=1\) is quite easy (cf. [5]), which leads us to ask
[PRS02] M. Parnas, D. Ron, and A. Samorodnitsky. Testing Basic Boolean Formulae. SIAM Journal on Disc. Math. and Alg., Vol. 16 (1), pages 20–46, 2002.
Today’s post by Clément Canonne.
Following the Boolean monotonicity testing bonanza, here’s an open problem. In short, does adaptivity help for monotonicity testing of Boolean functions?
Problem: Consider the problem of monotonicity testing for Boolean functions on the hypercube. Given oracle access to \(f\colon \{0,1\}^n \to \{0,1\}\), we wish to decide if \(f\) is (i) monotone vs. (ii) \(\epsilon\)-far from monotone (in Hamming distance). For either the one-sided or two-sided version of the problem, what is the exact status of adaptive testers?
State of the art:
– Fischer et al. [FLN+02] showed one-sided non-adaptive testers require \(\sqrt{n}\) queries. This implies an \(\Omega(\log n)\) lower bound for one-sided adaptive testers.
– Chen et al. [CDST15] proved that two-sided non-adaptive testers require (essentially) \(\Omega(\sqrt{n})\) queries. This implies an \(\Omega(\log n)\) lower bound for 2-sided adaptive testers.
– Khot et al. [KMS15] recently gave a one-sided non-adaptive tester making \(\tilde{O}(\sqrt{n}/\epsilon^2)\) queries. The story is essentially complete for non-adaptive testing.
Comments: As of now, it is not clear whether adaptivity can help. Berman et al. [BRY14] showed the benefit of adaptivity for Boolean monotonicity testing over the domain \([n]^2\) (switch the \(2\) and the \(n\) from the hypercube). A gap provably exists between adaptive and non-adaptive testers: \(O(1/\epsilon)\) vs. \(\Omega(\log(1/\epsilon)/\epsilon)\).
References:
[FLN+02] E. Fischer, E. Lehman, I. Newman, S. Raskhodnikova, R. Rubinfeld, and A. Samorodnitsky. Monotonicity testing over general poset domains. Symposium on Theory of Computing, 2002
[BRY14] P. Berman, S. Raskhodnikova, and G. Yaroslavtsev. \(L_p\) testing. Symposium on Theory of Computing, 2014
[CDST15] X. Chen, A. De, R. Servedio, L.-Y. Tang. Boolean function monotonicity testing requires (almost) \(n^{1/2}\) non-adaptive queries. Symposium on Theory of Computing, 2015
[KMS15] S. Khot, D. Minzer, and S. Safra. On monotonicity testing and Boolean Isoperimetric type theorems. ECCC, 2015
Erratum: a previous version of this post stated (incorrectly) lower bound of \(\Omega(\sqrt{n}/\epsilon^2)\). This has been corrected to \(\Omega(\sqrt{n})\).
In the recently concluded Bertinoro Workshop on Sublinear Algorithms a list of open problems and research directions were discussed. The list of open problems can be fond in this link.
Slightly delayed, Feb’s open problem is by one of the three possible “yours truly”s, Sesh. Looking for more reader participation, hint, hint.
Basic setting: Consider \(f:\{0,1\}^n \rightarrow R\), where \(R\) is some ordered range. There is a natural coordinate-wise partial order denoted by \(\prec\). The function is monotone if for all \(x \prec y\), \(f(x) \leq f(y)\). The distance to monotonicity, \(\epsilon_f\) is the minimum fraction of values that must be changed to make \(f\) monotone. This is an old problem in property testing.
Open problem: Is there an efficient constant factor approximation algorithm for \(\epsilon_f\)? In other words, is there a \(poly(n/\epsilon_f)\) time procedure that can output a value \(\epsilon’ = \Theta(\epsilon_f)\)?
State of the art: Existing monotonicity testers give an \(O(n)\)-approximation for \(\epsilon_f\), so there is much much room for improvement. (I’d be happy to see a \(O(\log n)\)-approximation.) Basically, it is known that the number of edges of \(\{0,1\}^n\) that violate monotonicity is at least \(\epsilon_f 2^{n-1}\) [GGLRS00], [CS13]. A simple exercise (given below) shows that there are at most \(n\epsilon_f 2^n\) violated edges. So just estimate the number of violated edges for an \(O(n)\)-approximation.
(Consider \(S \subseteq \{0,1\}^n\) such that modifying \(f\) on \(S\) makes it monotone. Every violated edge must have an endpoint in \(S\).)
Related work: Fattal and Ron [FR10] is a great place to look at various related problems, especially for hypergrid domains.
References
[CS13] D. Chakrabarty and C. Seshadhri. Optimal Bounds for Monotonicity and Lipschitz Testing over Hypercubes and Hypergrids. Symposium on Theory of Computing, 2013.
[FR10] S. Fattal and D. Ron. Approximating the distance to monotonicity in high dimensions . ACM Transactions on Algorithms, 2010.
[GGL+00] O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky. Testing Monotonicity . Combinatorica, 2000.
The open problem of the month is a new feature on PTReview. Every month we put up on open problem contributed by our readers. To know more about getting your problem broadcasted, check out the link “About Open Problem of the Month” at the top of the page.
The first ever open problem post is by Tom Gur on Merlin-Arthur proofs of proximity. This post doubles up a great survey on this new topic. Thanks Tom!
Primary reference: Non-interactive proofs of proximity by Gur and Rothblum, ECCC, 2013.
Basic setting: Recent work by Ron Rothblum and myself [GR13] initiates the study of \(\mathsf{MA}\) proof-system analogues of property testing, referred to as \(\mathsf{MA}\) proofs of proximity (\(\mathsf{MAP}\)s). A proof-aided tester for property \(\Pi\) is given oracle access to an input \(x\) and free access to a proof \(w\). A valid \(\mathsf{MAP}\) demands the following property. Given a proximity parameter \(\epsilon>0\), for inputs \(x \in \Pi\), there exists a proof that the tester accepts with high probability, and for inputs \(x\) that are \(\epsilon\)-far from \(\Pi\) no proof will make the tester accept, except with some small probability of error.
Open problem: Can one show an explicit property where \(\mathsf{MAP}\)s do not give additional power over standard testers? Formally, show an explicit property that requires any \(\mathsf{MAP}\) to make \(\Omega(|x|)\) queries even when given a long (e.g., length \(|x|/100\)) proof?
Background: Goldreich, Goldwasser, and Ron [GGR98] showed that “almost all” properties require probing a constant fraction of the tested object. This limitation was the primary motivation for \(\mathsf{MAP}\)s. Observe that given a sufficiently long proof, every property can be tested very efficiently by an \(\mathsf{MAP}\). Consider a proof that fully describes the object. The tester has free access to the proof, so all it has to do is verify the consistency of the proof and the object (which can be done by only making \(O(1/\epsilon)\) random queries). The tester can check for free that the object described in the proof has the desired property.
Indeed, the name of the game is to construct \(\mathsf{MAP}\)s with short proofs and significantly lower query complexity than standard testers. There exists a property that has an \(\mathsf{MAP}\) using a logarithmic-length proof and only a constant number of queries, but requires nearly linear number of queries for standard testing (see Section 3 of [GR13]).
Nevertheless, \(\mathsf{MAP}\)s with short proofs are far from being omnipotent. A random property requires any \(\mathsf{MAP}\) to perform \(\Omega(n)\) queries (where \(n\) is the length of the input), even when given a \(n/100\) length proof (Section 5 of [GR13]). The open problem is to find an explicit property that matches this lower bound. The best lower bound on explicit properties is far weaker; specifically, Fischer, Goldhirsh, and Lachish [FGL13] showed that testing a certain family of linear codes (namely, codes with “large” dual distance) requires any \(\mathsf{MAP}\) with a proof of length \(p \ge 1\) to make \(\Omega(n/p)\) queries.
References
[FGL13] E. Fischer, Y. Goldhirsh, and O. Lachish. Partial tests, universal tests and decomposability. Innovations in Theoretical Computer Science (ITCS), 2013.
[GGR98] O. Goldreich, S. Goldwasser, and D. Ron. Property testing and its connection to learning and approximation. Journal of the ACM (JACM), 1998.
[GR13] T. Gur and R. Rothblum. Non-interactive proofs of proximity. Electronic Colloquium on Computational Complexity (ECCC), 2013.