WorksComputer Science
On Non-Deterministic Representation of Boolean Functions
Abstract
We study non-deterministic representation of Boolean functions by polynomials, introduced by (de Wolf, 2000). A polynomial is said to be a non-deterministic polynomial for a Boolean function if for all , iff . The non-deterministic degree of , denoted , is the minimal degree of a non-deterministic polynomial for . In this work, we show the following main results: - Almost all Boolean functions on variables have non-deterministic degree at most . This confirms a conjecture of (Iyer et al., 2023). Together with the lower bound of (Iyer et al., 2023) it establishes a tight bound on the rational degree of a random Boolean function up to lower order terms. - We disprove a conjecture of (Kothari et al., 2026) about effective hypercube nullstellensatz for more than two polynomials. On the positive side, we also identify a constraint under which an effective hypercube nullstellensatz holds for many polynomials.
2012 ACM Subject Classification Computing methodologies Representation of Boolean functions; Theory of computation Quantum complexity theory
Keywords and phrases Random Functions, Non-Deterministic Degree, Rational Degree, Polynomials, Nullstellensatz
Funding Nitin Saurabh: Supported by ANRF ARG-MATRICS grant ANRF/ARGM/2025/003191/MTR. He also acknowledges funding support from the National Quantum Mission (NQM), an initiative of the Department of Science and Technology (DST), Govt. of India.
Acknowledgements We would like to thank anonymous reviewers whose careful reading and thoughtful comments greatly improved the presentation of this paper. We would also like to highlight that no AI tools were used in this work. Nitin Saurabh also acknowledge the support provided by the Foundation for QC Innovation (FQCI), DST-NQM T-Hub at IISc Bengaluru, in facilitating the NQM project.
Introduction
A Boolean function is said to be exactly represented by a polynomial if for all , . It is a well-known fact (see, e.g., [2]) that there exists a unique multilinear polynomial exactly representing a function . The degree of a Boolean function is defined to be the degree of this unique multilinear polynomial exactly representing . Polynomials are probably the ‘nicest’ object in mathematics which is attested not only by the existence of a mathematically rich theory but also by their ubiquitous presence in mathematics and sciences. It is no wonder then that since the seminal work of Minsky and Papert [11], a long line of work in theoretical computer science has used various notions of representations by polynomials, e.g., sign representations, pointwise approximations, rational representations, etc., to study different complexity measures associated with computing Boolean functions.
In this work we focus on non-deterministic representation of Boolean functions by polynomials. A polynomial is said to be a non-deterministic polynomial for a function if iff . The non-deterministic degree of , denoted , is the minimum degree among all non-deterministic polynomials for . This notion was introduced by de Wolf [3] to study the non-deterministic quantum query complexity of . He showed that equals the non-deterministic quantum query complexity of up to a constant factor. The non-deterministic degree is also related to another natural complexity measure of Boolean functions called the rational degree.
The rational degree of , denoted , is the minimum value of such that and are polynomials satisfying for all . It is a folklore result (credited to de Wolf; see [7, 9]) that . Mahadev and de Wolf [10] showed an even tighter connection between rational degree and quantum query complexity by observing that exactly characterizes the exact postselected quantum query complexity (see also [9]).
Long before the quantum connections of rational degree came to fore, the motivation to study rational degree was rooted in the classical complexity theory. It was observed by [5] that if is polynomially bounded by then with respect to a generic oracle (see also [6]). Thus the question whether is polynomially related to was raised more than three decades ago in [12].
In a recent breakthrough result [9] resolved the deg vs. rdeg question by showing that where is the deterministic query complexity of . They further observed that their main result gives an effective version of Hypercube Nullstellensatz.
Theorem 1 ([9 Theorem 10]). Let such that they do not share any common zeroes on the hypercube . Further suppose for all . Then there exist such that
and
where the overline denotes multilinearization using the (Boolean) relations for all .
They conjectured, in view of well-known classical nullstellensatz results (see [8] and references therein), that the following natural generalization of Theorem 1 to any number of polynomial holds.
Conjecture 2 ([9 Conjecture 11]). For all integers , the following holds. Let . Suppose do not share any common zeroes on the hypercube . Further suppose for all . Then there exist such that
and
In this work, we disprove Conjecture 2 (Theorem 6) and prove a variant of it (Theorem 8). We also show that the counter-example in Theorem 6 is optimal (Theorem 7) with respect to the number of polynomials and their degrees. They are presented in § 4.
We also establish extremal bounds on the non-deterministic degree and rational degree of random Boolean functions. It was shown in [7] that all but a negligible fraction of Boolean functions have rational degree at least . They conjectured [7 Conjecture 3] that an upper bound of holds for a random Boolean function. We prove the conjecture (Theorem 3 and Corollary 5), in § 3, by showing that all but a negligible fraction of Boolean functions have rational degree at most and thereby establishing tight bounds up to lower order terms.
We now present a brief overview of our results and techniques.
Our Results and Techniques
In this paper, we first prove an extremal bound on non-deterministic degree of Boolean functions.
Theorem 3. All but a negligible fraction of Boolean functions on variables have non-deterministic degree at most .
To establish the upper bound in the theorem, we prove the following technical lemma (Lemma 4) that characterizes functions with . Let be the Hadamard matrix where the -entry is given by (Definition 10). Let denote the submatrix of obtained by keeping the rows indexed by strings of Hamming weight at least , and further let denote the submatrix of obtained by keeping columns indexed by strings in .
Lemma 4. Let be a Boolean function with . Then, if and only if there exists a coordinate-wise non-zero such that .
To be able to fruitfully use the above lemma we further establish a linear algebraic characterization of matrices having a ‘coordinate-wise non-zero vector in the nullspace’ (Lemma 24). It shows that for a coordinate-wise non-zero vector to exists in the nullspace, it is sufficient (and necessary) for the rowspace to have none of the standard -unit vectors . This in turn requires that rows remain independent even after removing a column . That is, the matrix remains full rank even after removing a column.
Observe that is random submatrix of obtained by keeping each column with probability . We need to show that is full with high probability, where denote the submatrix of obtained by removing its -th column. Now using the random Gram matrix and the matrix Chernoff inequalities (Lemma 20) we show that satisfies the characterization of Lemma 24 with very high probability.
As a corollary to Theorem 3, we also obtain the following extremal bound on rational degree proving a conjecture of [7].
Corollary 5. All but a negligible fraction of Boolean functions on variables have rational degree at most .
Our second result is a counterexample to Conjecture 2 about effective hypercube nullstellensatz for many polynomials (made in [9]).
Theorem 6. There exist three non-zero polynomials with the following properties:
(i) each of degree two, (ii) do not share any common zeroes in , and (iii) for all .
Let be any (multilinear) polynomials satisfying
for all and , and
for all .
Then,
This counterexample is optimal with respect to number of polynomials and their degrees as we state below.
Theorem 7. There exists no set of 3 degree-1 polynomials that is a counterexample to Conjecture 2.
In other words, let be three non-zero affine-linear forms such that they do not share any common zeroes on the hypercube . Further, suppose for all . Then, there exist such that
and
We also give a counterexample comprising of 5 linear polynomials (Proposition 26). These counterexamples build on a similar example (Proposition 25) from [9]. Finally, we identify an extra constraint on the zero set of polynomials that allows us to prove an effective version of hypercube nullstellensatz for many polynomials.
Theorem 8. Let be an integer and be non-zero polynomials satisfying the following:
(i) they do not share any common zeroes in ,
(ii) for all , and
(iii) there exists a non-empty such that , where for .
Then, there exist (multilinear) polynomials such that the following holds:
(a) for all and ,
(b) for all , and
(c) .
Preliminaries
For a positive integer , we denote the set by . We use to denote the disjoint union of sets. A polynomial is said to be multilinear if it is of the form with . It is a well-known fact (see, e.g., [2]) that every is exactly represented by a unique multilinear polynomial .
Definition 9. The degree of , denoted , is the degree of the unique multilinear polynomial exactly representing , i.e., for all .
We will use Fourier representation of Boolean functions. In particular, consider the space of all functions from to with the following inner-product
where the expectation is with respect to the uniform distribution on . For , define the character functions as . Then the set of character functions forms an orthonormal basis for the space of all real-valued functions on . Hence, every real-valued function has a unique Fourier expansion
where the Fourier coefficients .
It is easily seen that the Fourier-degree equals . From the orthonormality, it follows that . Fourier representation is intimately tied with the Hadamard matrices.
Definition 10. Let be an integer. Then, the Hadamard matrix of dimension is defined such that the rows and columns are indexed by Boolean strings in and -th entry of equals .
It is then easily seen that for a function , , where the vector of Fourier coefficients . Furthermore, .
Definition 11. A polynomial is said to be a non-deterministic polynomial for if for all , if and only if . The non-deterministic degree of , denoted , is the minimum degree among all non-deterministic polynomials for .
Definition 12. Polynomials and are said to be a rational polynomial for if for all , and . The rational degree of , denoted , is the minimum of among all rational polynomials for .
We note the following (folklore) fact about rational degree and non-deterministic degree. For a proof see [9].
Fact 13. For every Boolean function , .
We note the following facts from linear algebra.
Fact 14. Let . Then in if and only if is the zero function.
We need the following fact about the non-zeroness of a multilinear polynomial. For a proof see, e.g., [12].
Lemma 15 (Ore-Schwartz-Zippel-DeMillo-Lipton Lemma). Let be a non-zero multilinear polynomial of degree . Then, , where is chosen uniformly at random from .
We also note the following anti-concentration result about linear forms [4].
Lemma 16 ([4]). Let be real numbers with . Further let for each . Then the number of sums which fall in the interior of an arbitrary interval of length 2 is at most .
Let denote the -unit-vector with 1 at the -th location and 0 everywhere else. For a vector , let denote its transpose.
Definition 17. Let be a matrix over . Then, the nullspace of is defined to be the set of all vectors such that . It is a subspace of .
Further, the rowspace of is defined to be the subspace in generated by the rows of . That is, it is the set of all vectors where .
Fact 18. Let be a matrix over . Then, the rowspace of is the orthogonal complement of the nullspace of . That is, .
We need the following version of Chernoff-Hoeffding concentration inequality.
Lemma 19 (Chernoff-Hoeffding). Let be independent and identically distributed -random variables with . Let . Then, for any ,
We also need the following matrix Chernoff inequalities from [13, 14]. See [13 Corollary 5.2] or [14 Theorem 5.1.1] for the version stated here. See also Remark 5.3 in [13].
Lemma 20 (Matrix Chernoff Lower Tail Inequality [13, 14]). Consider a finite sequence of independent, random, self-adjoint matrices with common dimension that satisfy
and for each index .
Define and the minimum eigenvalue of the expectation as . Then, for ,
Extremal properties of non-deterministic polynomials
In this section we give extremal bounds on non-deterministic polynomial representations of Boolean functions. We begin with a simple characterization of functions having full non-deterministic degree. It is well-known that non-deterministic degree of is [1, 3]. (In fact, in combinatorics it is known as the Alon-Füredi theorem.) We observe that only have non-deterministic degree .
Definition 21. A Boolean function is called an indicator function if .
Proposition 22. Let be a Boolean function. Then, if and only if is an indicator function.
Proof. As mentioned before, the Alon-Füredi theorem [1] proves that the non-deterministic degree of an indicator function is (see also [3]). What remains to be shown is that if then must be an indicator function. To establish this, we prove the contrapositive. That is, if is not an indicator function then .
Let be a Boolean function such that , and be the -elements of . For , define to be the indicator function of the input , i.e., iff . Recall, . Let be the non-zero coefficient of the degree monomial in . Define . Clearly is well-defined and . Now consider the polynomial
We now claim that is a non-deterministic polynomial for of degree at most . It is easily seen from construction that evaluates to non-zero iff . Moreover, the coefficient of the degree monomial equals which equals by the choice of .
The proof, in Proposition 22, showing that non-indicator functions have non-deterministic degree at most is simple, and yet instructive enough to allow us to obtain a characterization of non-deterministic degree of arbitrary Boolean functions. This characterization in turn will help us bound the non-deterministic degree of random Boolean functions. Before we proceed further we recall the definition of Hadamard matrices (Definition 10). We need the following submatrices of them.
Definition 23. For and , let denote the submatrix of obtained by keeping columns indexed by and rows indexed by strings of Hamming weight . When for a Boolean function , then we will use the shorthand to denote the submatrix . When , we denote the submatrix by .
We are now ready to state the characterization.
Lemma 4. Let be a Boolean function with . Then, if and only if there exists a coordinate-wise non-zero such that .
Proof. Let and assume, without loss of generality, the columns of are indexed from left to right by .
Let and be a non-deterministic polynomial for with degree at most . Then define as follows: for all . Clearly is coordinate-wise non-zero. Further we claim . To see this first recall that . Secondly observe that is the restriction of to Fourier characters of degree at least . Now since , we must have .
Let be coordinate-wise non-zero such that . Define the function as follows:
Clearly is a non-deterministic polynomial for , i.e., . Therefore, . We now claim that ; thereby completing the proof.
To see that , consider the Fourier expansion . Further consider the restriction of to Fourier characters of degree at least . We have . Thus .
We now prove a linear algebraic lemma that helps utilize the characterization in Lemma 4.
Lemma 24. Let be a real matrix with columns. Then, there exists a coordinate-wise non-zero in the nullspace of (i.e., ) if and only if for all , is not in the rowspace of .
Proof. It is a well-known fact in linear algebra that the rowspace of is the orthogonal complement of the nullspace of (Fact 18).
Let be a coordinate-wise non-zero vector in the nullspace of . Then, since rowspace of is the orthogonal complement of the nullspace and , we must have rowspace of for all .
Let is not in the rowspace of for all . By Fact 18, for each , there must exist vectors in the nullspace of such that its -th coordinate . We now claim that there is a linear combination of ’s that is coordinate-wise non-zero.
Let be an arbitrary linear combination of ’s. We need to show that there exist a choice of ’s such that is coordinate-wise non-zero. Let us consider each coordinate as a polynomial in . Note that, since , each is a non-zero polynomial. Now consider the product polynomial . Since each is a non-zero polynomial, the product polynomial is also a non-zero polynomial (of degree ). Therefore, since is an infinite field, there exists a point such that , which in turn implies that each , thereby proving the existence of a coordinate-wise non-zero in the nullspace of .
We are now ready to prove that almost all Boolean functions have degree at most .
Theorem 3. All but a negligible fraction of Boolean functions on variables have non-deterministic degree at most .
Proof. Let us fix , for an appropriate choice of the constant to be made later. Consider for a random Boolean function . By Lemma 4, it suffices to show that with probability there exists a coordinate-wise non-zero vector such that . Which in turn, by Lemma 24, is equivalent to showing that for a uniformly at random , with probability , no standard basis vectors are in the rowspace of . We now prove this.
Recall denote the submatrix of obtained by keeping those rows indexed by Boolean strings of Hamming weight . Let denote the number of rows in . Then, , where the inequality follows from the choice of and the Chernoff-Hoeffding inequality (Lemma 19).
Let us fix a Boolean function . Suppose that a standard basis vector is in the row span of . Then there exists a non-zero vector such that . Let denote the submatrix of obtained by removing its -th column. Then, . That is, the rows of are linearly dependent. Therefore, if a standard basis vector is in the row span of then the rows of are linearly dependent, and therefore . Consider the Gram matrix . Since , we must therefore have .
Hence, for a random ,
We now estimate the probability that . Consider the matrix-valued function
where are the columns of and 's are independent -indicator variables. For a random , . Therefore,
We now bound the probability that minimum eigenvalue of the random Gram matrix equals zero using the matrix Chernoff inequality (Lemma 20). We note that the maximum eigenvalue of the rank-1 matrix is , since is a -vector of dimension . We also compute the expected Gram matrix
where is the identity matrix and, recall is the submatrix of obtained by removing its -th column. The first equality in Equation (4) follows from the linearity of expectation and writing the sum of outer products as matrix multiplication, the second follows from adding and subtracting the term , and finally the third follows from the fact that the rows of (Hadamard matrices) are mutually orthogonal.
It then follows from Equation (4) that the minimum eigenvalue of the expected Gram matrix . Therefore, using the lower tail of matrix Chernoff inequality (Lemma 20) we have
We can then bound the probability that any standard basis vector is in the row span of by the union bound
Choosing we can see that the failure probability in Equation (6) is , thus completing the proof of the theorem. ◀
An interesting special case of Theorem 3 occurs when we consider and for a random . By Theorem 3, the probability that, for a random , both and are not at most is . We thus obtain the following corollary proving a conjecture of [7].
Corollary 5. All but a negligible fraction of Boolean functions on variables have rational degree at most .
Together with a result of [7] it establishes a tight bound on the rational degree of random Boolean functions up to lower order terms.
Effective hypercube nullstellensatz for many polynomials
A recent breakthrough work [9] proved an effective version of nullstellensatz on Boolean hypercube.
Theorem 1 ([9 Theorem 10]). Let such that they do not share any common zeroes on the hypercube . Further suppose for all . Then there exist such that
and
where the overline denotes multilinearization using the (Boolean) relations for all .
They conjectured, in view of well-known classical nullstellensatz results (see [8] and references therein), that the following natural generalization of Theorem 1 to any number of polynomial holds.
Conjecture 2 ([9 Conjecture 1]). For all integers , the following holds. Let . Suppose do not share any common zeroes on the hypercube . Further suppose for all . Then there exist such that
and
In the following we disprove the conjecture even when . Note that when we have Theorem 1. We will need the following proposition from [9].
Proposition 25 ([9]). Let and . Let and . Further, define by if and only if . Then, any polynomial satisfying for all must have .
We are now ready to present a counterexample to Conjecture 2.
Theorem 6. There exist three non-zero polynomials with the following properties:
(i) each of degree two,
(ii) do not share any common zeroes in , and
(iii) for all .
Let be any (multilinear) polynomials satisfying
for all and , and
for all .
Then,
Proof. Let , , and , where and are as defined in Proposition 25. Clearly they are non-zero polynomials of degree 2. Furthermore, it is easily seen that a common zero of , and will also be a common zero of and . But we know from Proposition 25 that and do not share any common zero, and therefore, , , and do not share any common zero over the Boolean hypercube. Finally, for all since over the Boolean hypercube.
Let , , and be any polynomials as given in the statement of Theorem 6. Further, let and be the zero set of and , respectively. By definition, evaluates to 0 on and since and evaluates to 0 on , must evaluate to 1 on . Thus, by Proposition 25, .
We also present a counterexample with linear polynomials but the number of polynomials increases to 5. In fact, Theorem 6 is optimal with respect to the number of polynomials and their degrees, as we show in Theorem 7.
Proposition 26. Consider the following non-zero polynomials: , , , , and , where and are as defined in Proposition 25. Clearly, they do not share any common zeroes and on the Boolean hypercube. Let be any (multilinear) polynomials satisfying
for all and , and
for all .
Then,
Proof. Let and be the zero set of and , respectively. Note that , , , and all evaluate to 0 on , and thus must evaluate to 1 on , while it evaluates to 0 on by definition. Hence, by Proposition 25, .
Note that an important requirement in nullstellensatz is that polynomials do not share any common zeroes. However, this does not forbid some of them from sharing a common zero. In the following we identify a constraint on the zero sets of polynomials that allows to prove an effective version for many polynomials.
Theorem 8. Let be an integer and be non-zero polynomials satisfying the following:
(i) they do not share any common zeroes in ,
(ii) for all , and
(iii) there exists a non-empty such that , where for .
Then, there exist (multilinear) polynomials such that the following holds:
(a) for all and ,
(b) for all , and
(c) $\max_{i\in[m]}{\deg(p_i)}\le\operatorname{poly}(\deg(g_1),\ldots,\deg(g_m)).
Proof. Since and are non-empty, define the following polynomials:
Then, by property (iii), we have that and do not share any common zeroes. Furthermore, for all . Therefore, by Theorem 1, there exist and such that
(a) for all and ,
(b) for all , and
(c) .
Now fix a and . Define for all , , and . These polynomials satisfy the conclusion of the theorem statement.
Optimality of the example in Theorem 6
In this subsection, we show that a counterexample to Conjecture 2 with 3 polynomials, say , and must satisfy at least 2.
Theorem 7. There exists no set of 3 degree-1 polynomials that is a counterexample to Conjecture 2.
In other words, let be three non-zero affine-linear forms such that they do not share any common zeroes on the hypercube . Further, suppose for all . Then, there exist such that
and
Proof. Let be non-zero affine-linear forms such that
(i) for all , and
(ii) they share no common zeroes in .
For , define and . Thus, by property (i), we have . We now have two cases based on .
Case 1: Two of the hyperplanes, say and , cover the full hypercube on their own. That is, . Then, by Lemma 27, we have exactly one of the following subcases.
(a) For some , and . In this case, it suffices to take , and to obtain the conclusion in the theorem.
(b) For some distinct , and . In such a case, let , and .
In both cases we have .
Case 2: No two hyperplanes can cover the full hypercube . That is, for distinct , . Then, we claim that for each , .
Let us complete the proof of theorem assuming the claim. For , let be the number of variables with non-zero coefficients in the affine-linear form . Then by the Littlewood-Offord inequality (Lemma 16), we have , which in turn implies . Therefore, together 's depend on variables. Hence the solutions 's have degree at most .
We are now left to prove the claim that for all . We show it for . The argument is analogous for others. Consider the function for all . Since , is a non-zero multilinear polynomial of degree at most . Therefore, by Lemma 15, . It is then implied by property (i) that .
We are now ready to characterize a pair of affine-linear forms that together covers the Boolean hypercube.
Lemma 27. Let and be non-zero affine-linear forms over . Further, suppose . Then, up to multiplication by non-zero constants, and up to relabelling, exactly one of the following holds:
(a) For some , and .
(b) For some distinct , and .
Proof. We need the following two technical claims, which we prove afterwards.
Claim 28. For a non-zero affine-linear form on variables, .
Claim 29. If a non-zero affine-linear form on variables is such that , then, up to multiplication by a non-zero constant, , for distinct .
Assuming the claims we complete the proof now. By Claim 28 and the assumption , we must have and . By Claim 29, and moreover they should be complementary. Therefore, either and , or and . ◀
We now prove the two claims.
Proof of Claim 28. Let . Since is non-zero either there exists a variable with the non-zero coefficient , or is a non-zero constant function. If is a non-zero constant function, then clearly , for all . Henceforth, we assume, without loss of generality, that the variable has non-zero coefficient. Thus, for some affine-linear form on variables, we have
Now observe that for every setting , there is at most one solution to that satisfies . Therefore, the number of solutions to is at most . ◁
Proof of Claim 29. Since is a non-zero affine-linear form, we assume, without loss of generality, up to multiplication by a non-zero constant,
for some affine-linear form in the remaining variables. For every assignment to the variables of , at most one value of can satisfy . Since , there must be exactly one such zero for each . Therefore, for all . Thus, is a Boolean function of degree at most . That is, for . This completes the proof of the claim. ◁
Conclusion
In this paper, we studied non-deterministic polynomial representation of Boolean functions. We showed that almost all Boolean functions have non-deterministic degree as well as rational degree at most . This confirms a conjecture of [7] and together with their lower bound establishes tight extremal bounds for random Boolean functions up to lower order terms.
We also studied effective versions of hypercube nullstellensatz and disproved Conjecture 2 of [9]. On the positive side, we proved a variant of Conjecture 2. We also show the optimality of our counterexample to Conjecture 2.
For the future work, one of the most interesting question that remains open is to close the gap between and . In particular, de Wolf [3] conjectured that . The current best known separation is quadratic (see [9]). Even the weaker versions of this conjecture, namely and , remains open.
The question is also interesting from the perspective of effective hypercube nullstellensatz. If true it would match the well-known effective version of classical nullstellensatz [8].
References
- [1]Noga Alon and Zoltán Füredi. Covering the cube by affine hyperplanes. Eur. J. Comb., 14(2):79–83, 1993. URL: https://doi.org/10.1006/eujc.1993.1011, doi:10.1006/EJC.1993.1011.
- [2]Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21–43, 2002. doi:10.1016/S0304-3975(01)00144-X.DOI
- [3]Ronald de Wolf. Characterization of non-deterministic quantum query and quantum communication complexity. In Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pages 271–278. IEEE Computer Society, 2000. doi:10.1109/CCC.2000.856758.
- [4]P. Erdős. On a lemma of Littlewood and Offord. Bulletin of the American Mathematical Society, 51(12):898 – 902, 1945.DOI
- [5]Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, and Lide Li. An oracle builder’s toolkit. Inf. Comput., 182(2):95–136, 2003. doi:10.1016/S0890-5401(03)00018-X.DOI
- [6]Lance Fortnow. Computational complexity blog - rational functions and decision-tree complexity, 2003. URL: https://blog.computationalcomplexity.org/2003/11/rational-functions-and-decision-tree.html.
- [7]Vishnu Iyer, Siddhartha Jain, Robin Kothari, Matt Kovacs-Deak, Vinayak M. Kumar, Luke Schaeffer, Daochen Wang, and Michael Whitmeyer. On the rational degree of boolean functions and applications. CoRR, abs/2310.08004, 2023. URL: https://doi.org/10.48550/arXiv.2310.08004, doi:10.48550/ARXIV.2310.08004.
- [8]Zbigniew Jelonek. On the effective Nullstellensatz. Inventiones mathematicae, 162:1–17, 2005. doi:10.1007/s00222-004-0434-8.
- [9]Robin Kothari, Matt Kovacs-Deak, Daochen Wang, and Rain Zimin Yang. Rational degree is polynomially related to degree. CoRR, abs/2601.08727, 2026. URL: https://doi.org/10.48550/arXiv.2601.08727, doi:10.48550/ARXIV.2601.08727.
- [10]Urmila Mahadev and Ronald de Wolf. Rational approximations and quantum algorithms with postselection. Quantum Inf. Comput., 15(3&4):295–307, 2015. doi:10.26421/QIC15.3-4-5.DOI
- [11]Marvin Minsky and Seymour Papert. Perceptrons. MIT Press, Cambridge, MA, 1969.
- [12]Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Comput. Complex., 4:301–313, 1994. doi:10.1007/BF01263419.DOI
- [13]Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput. Math., 12(4):389–434, 2012. URL: https://doi.org/10.1007/s10208-011-9099-z, doi:10.1007/S10208-011-9099-Z.
- [14]Joel A. Tropp. An introduction to matrix concentration inequalities. Found. Trends Mach. Learn., 8(1-2):1–230, 2015. doi:10.1561/2200000048.DOI