One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $$P \not\subseteq {NC}^1$$ ). Karchmer et al. (Comput Complex 5(3/4):191–204, 1995) suggested to approach this problem by proving that depth complexity behaves “as expected” with respect to the composition of functions $$f \Diamond g$$ . They showed that the validity of this conjecture would imply that $$P \not\subseteq {NC}^1$$ . Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function f, but only for few inner functions g. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions. In this work, we extend significantly the range of inner functions that can be handled. First, we consider the monotone version of the KRW conjecture. We prove it for every monotone inner function g whose depth complexity can be lower-bounded via a query-to-communication lifting theorem. This allows us to handle several new and well-studied functions such as the s-t-connectivity, clique, and generation functions. In order to carry this progress back to the non-monotone setting, we introduce a new notion of semi-monotone composition, which combines the non-monotone complexity of the outer function f with the monotone complexity of the inner function g. In this setting, we prove the KRW conjecture for a similar selection of inner functions g, but only for a specific choice of the outer function f.

We study the power of randomized complexity classes that are given oracle access to a natural property of Razborov and Rudich (JCSS, 1997) or its special case, the Minimal Circuit Size Problem (MCSP). We show that in a number of complexity-theoretic results that use the SAT oracle, one can use the MCSP oracle instead. For example, we show that $$\mathsf{ZPEXP}^\mathsf{MCSP}\nsubseteq \mathsf{P} / \mathsf {poly}$$ , which should be contrasted with the previously known circuit lower bound $$\mathsf{ZPEXP}^\mathsf{NP}\nsubseteq \mathsf{P} / \mathsf{poly}$$ . We also show that, assuming the existence of indistinguishability obfuscators (IOs), SAT and MCSP are equivalent in the sense that one has an efficient randomized (BPP) algorithm if and only if the other one does. We interpret our results as providing some evidence that MCSP may be NP-hard under randomized polynomial-time reductions.

Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of symmetric functions, in Representation theory Stanley (1999), in Schubert calculus Ledoux & Malham (2010) as well as in Enumerative combinatorics Gasharov (1996); Stanley (1984, 1999). In recent years, they have also shown up in various incarnations in Computer Science, e.g, quantum computation Hallgren et al. (2000); O'Donnell & Wright (2015) and geometric complexity theory Ikenmeyer & Panova (2017). However, unlike some other families of symmetric polynomials like the elementary symmetric polynomials, the power symmetric polynomials and the complete homogeneous symmetric polynomials, the computational complexity of syntactically computing Schur polynomials has not been studied much. In particular, it is not known whether Schur polynomials can be computed efficiently by algebraic formulas. In this work, we address this question and show that unless every polynomial with a small algebraic branching program (ABP) has a small algebraic formula, there are Schur polynomials that cannot be computed by algebraic formula of polynomial size. In other words, unless the algebraic complexity class VBP is equal to the complexity class VF, there exist Schur polynomials which do not have polynomial size algebraic formulas. As a consequence of our proof, we also show that computing the determinant of certain generalized Vandermonde matrices is essentially as hard as computing the general symbolic determinant. To the best of our knowledge, these are one of the first hardness results of this kind for families of polynomials, which are not multilinear. A key ingredient of our proof is the study of composition of well behaved algebraically independent polynomials with a homogeneous polynomial, which might be of independent interest.

The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH do not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, $$\rm{QCPH}$$ , uses classical proofs, and the second, $$\rm{QPH}$$ , uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, $$\rm{Q\Sigma_3}$$ , into NEXP using the ellipsoid method for efficiently solving semidefinite programs. These results yield two implications for $$\rm{QMA(2)}$$ , the variant of Quantum Merlin-Arthur ( $$\rm{QMA}$$ ) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if $$\rm{QCPH = QPH}$$ (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs ``equivalent''), then QMA(2) is in the counting hierarchy (specifically, in $${\rm P}^{{\rm pp}^{{\rm pp}}}$$ ). Second, because $$\rm{QMA(2)}\subseteq \rm{Q\Sigma_3}$$ , $$\rm{QMA(2)}$$ is strictly contained in NEXP unless $$\rm{QMA(2)}=\rm{Q\Sigma_3}$$ (i.e., alternating quantifiers do not help in the presence of ``unentanglement'').

We show that any Algebraic Branching Program (ABP) computing the polynomial $$\sum _{i = 1}^n x_i^n$$ has at least $$\Omega (n^2)$$ vertices. This improves upon the lower bound of $$\Omega (n\log n)$$ , which follows from the classical result of Strassen (1973a) and Baur & Strassen (1983), and extends the results in Kumar (2019), which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial. Our proof relies on a notion of depth reduction, which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial $$\sum _{i=1}^n x_i^n$$ can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial $$\sum _{i = 1}^n x_i^n + \varepsilon ({\bf x})$$ , for a structured “error polynomial” $$\varepsilon ({\bf x})$$ . To complete the proof, we then observe that the lower bound in Kumar (2019) is robust enough and continues to hold for all polynomials $$\sum _{i = 1}^n x_i^n + \varepsilon ({\bf x})$$ , where $$\varepsilon ({\bf x})$$ has the appropriate structure. We also use our ideas to show an $$\Omega (n^2)$$ lower bound of the size of algebraic formulas computing the elementary symmetric polynomial of degree 0.1n on n variables. This is a slight improvement upon the prior best known formula lower bound (proved for a different polynomial) of $$\Omega (n^2/\log n)$$ Kalorkoti (1985); Nechiporuk (1966); Shpilka & Yehudayoff (2010). Interestingly, this lower bound is asymptotically better than $$n^2/\log n$$ , the strongest lower bound that can be proved using previous methods. This lower bound also matches the upper bound, due to Ben-Or, who showed that elementary symmetric polynomials can be computed by algebraic formula (in fact depth-3 formula) of size $$O(n^2)$$ . Prior to this work, Ben-Or’s construction was known to be optimal only for algebraic formulas of depth-3 (Shpilka & Wigderson 2001).

We investigate the power of randomness in two-party communication complexity. In particular, we study the model where the parties can make a constant number of queries to a function that has an efficient one-sided-error randomized protocol. The complexity classes defined by this model comprise the Randomized Boolean Hierarchy, which is analogous to the Boolean Hierarchy but defined with one-sidederror randomness instead of nondeterminism. Our techniques connect the Nondeterministic and Randomized Boolean Hierarchies, and we provide a complete picture of the relationships among complexity classes within and across these two hierarchies. In particular, we prove that the Randomized Boolean Hierarchy does not collapse, and we prove a query-to-communication lifting theorem for all levels of the Nondeterministic Boolean Hierarchy and use it to resolve an open problem stated in the paper by Halstenberg and Reischuk (CCC 1988) which initiated the study of this hierarchy.

For any finite Galois field extension K/F, with Galois group G = Gal (K/F), there exists an element $$\alpha \in $$ K whose orbit $$G\cdot\alpha$$ forms an F-basis of K. Such an $$\alpha$$ is called a normal element, and $$G\cdot\alpha$$ is a normal basis. We introduce a probabilistic algorithm for testing whether a given $$\alpha \in$$ K is normal, when G is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether $$\alpha$$ is normal can be reduced to deciding whether $$\sum_{g \in G} g(\alpha)g \in$$ K[G] is invertible; it requires a slightly subquadratic number of operations. Once we know that $$\alpha$$ is normal, we show how to perform conversions between the power basis of K/F and the normal basis with the same asymptotic cost.

We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formula over G in size t + 1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.

An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex s, and end vertex t and each edge having a weight which is an affine form in $$\mathbb{F}[x_1, x_2, \ldots , x_n]$$ . An ABP computes a polynomial in a natural way, as the sum of weights of all paths from s to t, where the weight of a path is the product of the weights of the edges in the path. An ABP is said to be homogeneous if the polynomial computed at every vertex is homogeneous. In this paper, we show that any homogeneous algebraic branching program which computes the polynomial $$x^n_1 + x^n_2 + \cdots + x^n_n$$ has at least $$\Omega(n^2)$$ vertices (and hence edges). To the best of our knowledge, this seems to be the first non-trivial super-linear lower bound on the number of vertices for a general homogeneous ABP and slightly improves the known lower bound of $$\Omega(n \,{\rm log}\, n)$$ on the number of edges in a general (possibly non-homogeneous) ABP, which follows from the classical results of Strassen (Numer Math 20:238–251, 1973) and Baur and Strassen (Theor Comput Sci 22:317–330, 1983). On the way, we also get an alternate and unified proof of an $$\Omega(n \,{\rm log}\, n)$$ lower bound on the size of a homogeneous arithmetic circuit (follows from the work of Strassen (1973) and Baur & Strassen (1983)), and an n/2 lower bound $$(n \,{\rm over}\, \mathbb{R})$$ on the determinantal complexity of an explicit polynomial (Mignon and Ressayre in Int Math Res Notes 2004(79):4241–4253, 2004; Cai et al. in Comput Complex 19(1):37–56, 2010, http://dx.doi.org/10.1007/s00037-009-0284-2 ; Yabe in CoRR, 2015, http://arxiv.org/abs/1504.00151 ). These are currently the best lower bounds known for these problems for any explicit polynomial and were originally proved nearly two decades apart using seemingly different proof techniques.

Unfortunately, the inline image was not processed in the original version and the images are updated here. The original article has been corrected.

We prove that the PNP-type query complexity (alternatively, decision list width) of any Boolean function f is quadratically related to the PNP-type communication complexity of a lifted version of f. As an application, we show that a certain “product” lower bound method of Impagliazzo and Williams (CCC 2010) fails to capture PNP communication complexity up to polynomial factors, which answers a question of Papakonstantinou, Scheder, and Song (CCC 2014).

Semiring complexity is the version of arithmetic circuit complexity that allows only two operations: addition and multiplication. We show that semiring complexity of a Schur polynomial $${s_\lambda(x_1,\dots,x_k)}$$ labeled by a partition $${\lambda=(\lambda_1\ge\lambda_2\ge\cdots)}$$ is bounded by $${O(\log(\lambda_1))}$$ provided the number of variables k is fixed.

We prove several results which, together with prior work, provide a nearly-complete picture of the relationships among classical communication complexity classes between $${\mathsf{P}}$$ and $${\mathsf{PSPACE}}$$ , short of proving lower bounds against classes for which no explicit lower bounds were already known. Our article also serves as an up-to-date survey on the state of structural communication complexity. Among our new results we show that $${\mathsf{MA} \not\subseteq \mathsf{ZPP}^{\mathsf{NP}[1]}}$$ , that is, Merlin–Arthur proof systems cannot be simulated by zero-sided error randomized protocols with one $${\mathsf{NP}}$$ query. Here the class $$\mathsf{ZPP}^{\mathsf{NP}[1]}$$ has the property that generalizing it in the slightest ways would make it contain $${\mathsf{AM} \cap \mathsf{coAM}}$$ , for which it is notoriously open to prove any explicit lower bounds. We also prove that $${\mathsf{US} \not\subseteq \mathsf{ZPP}^{\mathsf{NP}[1]}}$$ , where $${\mathsf{US}}$$ is the class whose canonically complete problem is the variant of set-disjointness where yes-instances are uniquely intersecting. We also prove that $${\mathsf{US} \not\subseteq \mathsf{coDP}}$$ , where $${\mathsf{DP}}$$ is the class of differences of two $${\mathsf{NP}}$$ sets. Finally, we explore an intriguing open issue: Are rank-1 matrices inherently more powerful than rectangles in communication complexity? We prove a new separation concerning $${\mathsf{PP}}$$ that sheds light on this issue and strengthens some previously known separations.

We show that unbounded fan-in Boolean formulas of depth d + 1 and size s have average sensitivity $${O(\frac{1}{d} \log s)^d}$$ . In particular, this gives a tight $${2^{\Omega(d(n^{1/d}-1))}}$$ lower bound on the size of depth d + 1 formulas computing the parity function. These results strengthen the corresponding $${2^{\Omega(n^{1/d})}}$$ and $${O(\log s)^d}$$ bounds for circuits due to Håstad (Proceedings of the 18th annual ACM symposium on theory of computing, ACM, New York, 1986) and Boppana (Inf Process Lett 63(5): 257–261, 1997). Our proof technique studies a random process where the switching lemma is applied to formulas in an efficient manner.

The concepts of quantum correlation complexity and quantum communication complexity were recently proposed to quantify the minimum amount of resources needed in generating bipartite classical or quantum states in the single-shot setting. The former is the minimum size of the initially shared state $${\sigma}$$ on which local operations by the two parties (without communication) can generate the target state $${\rho}$$ , and the latter is the minimum amount of communication needed when initially sharing nothing. In this paper, we generalize these two concepts to multipartite cases, for both exact and approximate state generation. Our results are summarized as follows.

For a class $${\mathcal{F}}$$ of formulas (general de Morgan or read-once de Morgan), the shrinkage exponent $${\Gamma_{\mathcal{F}}}$$ is the parameter measuring the reduction in size of a formula $${F\in\mathcal{F}}$$ after $${F}$$ is hit with a random restriction. A Boolean function $${f\colon \{0,1\}^n\to\{1,-1\}}$$ is Fourier-concentrated if, when viewed in the Fourier basis, $${f}$$ has most of its total mass on “low-degree” coefficients. We show a direct connection between the two notions by proving that shrinkage implies Fourier concentration: For a shrinkage exponent $${\Gamma_{\mathcal{F}}}$$ , a formula $${F\in\mathcal{F}}$$ of size $${s}$$ will have most of its Fourier mass on the coefficients of degree up to about $${s^{1/\Gamma_{\mathcal{F}}}}$$ . More precisely, for a Boolean function $${f\colon\{0,1\}^n\to\{1,-1\}}$$ computable by a formula of (large enough) size $${s}$$ and for any parameter $${r > 0}$$ , $$\sum_{A\subseteq [n]\; :\; |A|\geq s^{1/\Gamma} \cdot r} \hat{f}(A)^2\leq s\cdot{\mathscr{polylog}}(s)\cdot exp\left(-\frac{r^{\frac{\Gamma}{\Gamma-1}}}{s^{o(1)}} \right),$$ where $${\Gamma}$$ is the shrinkage exponent for the corresponding class of formulas: $${\Gamma=2}$$ for de Morgan formulas, and $${\Gamma=1/\log_2(\sqrt{5}-1)\approx 3.27}$$ for read-once de Morgan formulas. This Fourier concentration result is optimal, to within the $${o(1)}$$ term in the exponent of $${s}$$ . As a standard application of these Fourier concentration results, we get that subquadratic-size de Morgan formulas have negligible correlation with parity. We also show the tight $${\Theta(s^{1/\Gamma})}$$ bound on the average sensitivity of read-once formulas of size $${s}$$ , which mirrors the known tight bound $${\Theta(\sqrt{s})}$$ on the average sensitivity of general de Morgan $${s}$$ -size formulas.

We consider variants of the minimum circuit size problem MCSP, where the goal is to minimize the size of oracle circuits computing a given function. When the oracle is QBF, the resulting problem MSCP QBF is known to be complete for PSPACE under ZPP reductions. We show that it is not complete under logspace reductions, and indeed it is not even hard for TC 0 under uniform AC 0 reductions. We obtain a variety of consequences that follow if oracle versions of MCSP are hard for various complexity classes under different types of reductions. We also prove analogous results for the problem of determining the resource-bounded Kolmogorov complexity of strings, for certain types of Kolmogorov complexity measures.

An errorless circuit for a Boolean function is one that outputs the correct answer or “don’t know” on each input (and never outputs the wrong answer). The goal of errorless hardness amplification is to show that if f has no size s errorless circuit that outputs “don’t know” on at most a $${\delta}$$ fraction of inputs, then some f′ related to f has no size s′ errorless circuit that outputs “don’t know” on at most a $${1-\epsilon}$$ fraction of inputs. Thus, the hardness is “amplified” from $${\delta}$$ to $${1-\epsilon}$$ . Unfortunately, this amplification comes at the cost of a loss in circuit size. If the reduction makes q queries to the hypothesized errorless circuit for f′, then we obtain a result with s′ = s/q. Hence, it is desirable to keep the query complexity to a minimum. The first results on errorless hardness amplification were obtained by Bogdanov and Safra. They achieved query complexity $${O\big((\frac{1}{\delta} \log\frac{1}{\epsilon})^2\cdot\frac{1}{\epsilon} \log\frac{1}{\delta} \big)}$$ when f′ is the XOR of several independent copies of f. We improve the query complexity (and hence the loss in circuit size) to $${O\big(\frac{1}{\epsilon} \log\frac{1}{\delta} \big)}$$ , which is optimal up to constant factors for non-adaptive black-box errorless hardness amplification. Bogdanov and Safra also proved a result that allows for errorless hardness amplification within NP. They achieved query complexity $${O\big(k^3\cdot\frac{1}{\epsilon^2} \log\frac{1}{\delta} \big)}$$ when f′ consists of any monotone function applied to the outputs of k independent copies of f, provided the monotone function satisfies a certain combinatorial property parameterized by $${\delta}$$ and $${\epsilon}$$ . We improve the query complexity to $${O\big(\frac{k}{t} \cdot\frac{1}{\epsilon} \log\frac{1}{\delta} \big)}$$ , where $${t\geq 1}$$ is a certain parameter of the monotone function. Using the best applicable monotone functions (which were constructed by Bogdanov and Safra), our result yields a query complexity of $${\widetilde{O} \big(\frac{1}{\epsilon^3} \cdot\frac{1}{\delta} \big)}$$ for balanced functions f, improving on the $${\widetilde{O} \big(\frac{1}{\epsilon^8} \cdot\frac{1}{\delta^6} \big)}$$ query complexity that follows from the Bogdanov–Safra result. As a side result, we prove a lower bound on the advice complexity of black-box reductions for errorless hardness amplification.

Existing definitions of the relativizations of NC 1, L and NL do not preserve the inclusions $${{\bf NC}^1 \subseteq {\bf L}, {\bf NL}\subseteq {\bf AC}^1}$$ . We start by giving the first definitions that preserve them. Here for L and NL we define their relativizations using Wilson’s stack oracle model, but limit the height of the stack to a constant (instead of log(n)). We show that the collapse of any two classes in $${\{{\bf AC}^0 (m), {\bf TC}^0, {\bf NC}^1, {\bf L}, {\bf NL}\}}$$ implies the collapse of their relativizations. Next we exhibit an oracle α that makes AC k (α) a proper hierarchy. This strengthens and clarifies the separations of the relativized theories in Takeuti (1995). The idea is that a circuit whose nested depth of oracle gates is bounded by k cannot compute correctly the (k + 1) compositions of every oracle function. Finally, we develop theories that characterize the relativizations of subclasses of P by modifying theories previously defined by the second two authors. A function is provably total in a theory iff it is in the corresponding relativized class, and hence, the oracle separations imply separations for the relativized theories.

An algorithm is presented that probabilistically computes the exact inverse of a nonsingular n × n integer matrix A using $${({n^3(\log||A||+\log \kappa(A)))}^{1+o(1)}}$$ bit operations. Here, $${||A||= \max_{ij}|A_{ij}|}$$ denotes the largest entry in absolute value, $${\kappa(A) := n ||A^{-1}||\,||A||}$$ is the condition number of the input matrix, and the “+o(1)” in the exponent indicates a missing factor $${c_1 {(\log n)}^{c_2}{({\rm loglog} ||A||)}^{c_3}}$$ for positive real constants c 1, c 2, c 3. A variation of the algorithm is presented for polynomial matrices that computes the inverse of a nonsingular n × n matrix whose entries are polynomials of degree d over a field using $${{(n^3d)}^{1+o(1)}}$$ field operations. Both algorithms are randomized of the Las Vegas type: failure may be reported with probability at most 1/2, and if failure is not reported, then the output is certified to be correct in the same running time bound.

We show that circuit lower bound proofs based on the method of random restrictions yield non-trivial compression algorithms for “easy” Boolean functions from the corresponding circuit classes. The compression problem is defined as follows: given the truth table of an n-variate Boolean function f computable by some unknown small circuit from a known class of circuits, find in deterministic time poly(2 n ) a circuit C (no restriction on the type of C) computing f so that the size of C is less than the trivial circuit size $${2^n/n}$$ . We get non-trivial compression for functions computable by AC 0 circuits, (de Morgan) formulas, and (read-once) branching programs of the size for which the lower bounds for the corresponding circuit class are known. These compression algorithms rely on the structural characterizations of “easy” functions, which are useful both for proving circuit lower bounds and for designing “meta-algorithms” (such as Circuit-SAT). For (de Morgan) formulas, such structural characterization is provided by the “shrinkage under random restrictions” results by Subbotovskaya (Doklady Akademii Nauk SSSR 136(3):553–555, 1961) and Håstad (SIAM J Comput 27:48–64, 1998), strengthened to the “high-probability” version by Santhanam (Proceedings of the Fifty-First Annual IEEE Symposium on Foundations of Computer Science, pp 183–192, 2010), Impagliazzo, Meka & Zuckerman (Proceedings of the Fifty-Third Annual IEEE Symposium on Foundations of Computer Science, pp 111–119, 2012b), and Komargodski & Raz (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 171–180, 2013). We give a new, simple proof of the “high-probability” version of the shrinkage result for (de Morgan) formulas, with improved parameters. We use this shrinkage result to get both compression and #SAT algorithms for (de Morgan) formulas of size about n 2. We also use this shrinkage result to get an alternative proof of the result by Komargodski & Raz (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 171–180, 2013) of the average-case lower bound against small (de Morgan) formulas. Finally, we show that the existence of any non-trivial compression algorithm for a circuit class $${\mathcal{C} \subseteq \mathsf{P}/ \mathsf{poly}}$$ would imply the circuit lower bound $${\mathsf{NEXP} \not \subseteq \mathcal{C}}$$ ; a similar implication is independently proved also by Williams (Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp 21–30, 2013). This complements the result by Williams (Proceedings of the Forty-Second Annual ACM Symposium on Theory of Computing, pp 231–240, 2010) that any non-trivial Circuit-SAT algorithm for a circuit class $${\mathcal{C}}$$ would imply a superpolynomial lower bound against $${\mathcal{C}}$$ for a language in NEXP.

The problem of determining whether several finite automata accept a word in common is closely related to the well-studied membership problem in transformation monoids. We raise the issue of limiting the number of final states in the automata intersection problem. For automata with two final states, we show the problem to be $${\oplus}$$ L-complete or NP-complete according to whether a nontrivial monoid other than a direct product of cyclic groups of order 2 is allowed in the automata. We further consider idempotent commutative automata and (Abelian, mainly) group automata with one, two, or three final states over a singleton or larger alphabet, elucidating (under the usual hypotheses on complexity classes) the complexity of the intersection nonemptiness and related problems in each case.

Goldreich et al. (CRYPTO 1999) proved that the promise problem for estimating the Shannon entropy of a distribution sampled by a given circuit is NISZK-complete. We consider the analogous problem for estimating the min-entropy and prove that it is SBP-complete, where SBP is the class of promise problems that correspond to approximate counting of NP witnesses. The result holds even when the sampling circuits are restricted to be 3-local. For logarithmic-space samplers, we observe that this problem is NP-complete by a result of Lyngsø and Pedersen on hidden Markov models (JCSS 65(3):545–569, 2002).

We introduce a notion of the quantum query complexity of a certificate structure. This is a formalization of a well-known observation that many quantum query algorithms only require the knowledge of the position of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by certificates of bounded size, we construct a relatively general class of functions having this property. The construction is based on orthogonal arrays and generalizes the quantum query lower bound for the k-sum problem derived recently by Belovs and Špalek (Proceeding of 4th ACM ITCS, 323–328, 2013). Finally, we use these results to show that the learning graph for the triangle problem by Lee et al. (Proceeding of 24th ACM-SIAM SODA, 1486–1502, 2013) is almost optimal in the above settings. This also gives a quantum query lower bound for the triangle sum problem.