This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal. The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.
This thesis studies three complexity measures of total Boolean functions f:{0,1}n → {0,1}: maximum sensitivity s(f), polynomial degree deg(f), and spectral sensitivity λ(f), where λ(f) is defined as the spectral norm of the adjacency matrix of the sensitivity graph. Building on the results of Aaronson et al., we examine the inequality chain √s(f) ≤ λ(f) ≤ deg(f) and investigate whether all three quantities can be simultaneously equal. The first part of the thesis reverse engineers the equality cases of the two known inequalities to isolate necessary extremal conditions on both the Fourier structure of f and the local geometry of its sensitivity graph. The second part develops Python-based exhaustive and constrained searches to test the first nontrivial candidate profiles. We compute full distributions of s(f), deg(f), and λ(f) for all Boolean functions on n=3 and n=4, showing in particular that no function realizes the candidate (s(f), λ(f), deg(f)) = (4,2,2) at n=4. We then use Möbius-based and CSP-based enumeration to study all real-degree-≤2 Boolean functions through higher dimensions, obtaining repeated evidence that s(f) ≤ 3 in this family and thereby excluding the (4,2,2) case in the tested range. Together, the theoretical and computational results support the view that the simultaneous tightness of √s(f) = λ(f) = deg(f) is obstructed by strong structural incompatibilities beyond the trivial degree-1 case.
The spectral sensitivity λ(f) of a Boolean function is the largest eigenvalue of the adjacency matrix of its sensitivity graph. It lower-bounds every standard measure of query complexity, and Aaronson, Ben-David, Kothari, Rao and Tal, who introduced it, asked whether block sensitivity is at most quadratic in it: is bs(f)=O(λ(f)2)? We show that it is not. We construct a total Boolean function on 2017584 variables with bs(f)≥14011 and λ(f)≤89.0162, so that bs(f)≥λ(f)2.127, and hence by composition a family with λ(fn)→∞ and bs(fn)=Ω(λ(fn)2.127). The function is the indicator of a union of k subcubes indexed by the vertices of a doubly regular tournament, and the freedom left in the construction is fixed by the Lovász local lemma. The main result has been formally verified in Lean. We also give numerical evidence that a member of the same family on 1255 variables reaches an exponent near 2.20, and exhibit a member on 30 variables whose exponent already exceeds 2 and whose spectral sensitivity can be computed exactly.
We study a natural complexity measure of Boolean functions known as the rational degree. Denoted rdeg(f), it is the minimal degree of a rational function that is equal to f on the Boolean hypercube. For total functions f, it is conjectured that rdeg(f) is polynomially related to the Fourier degree of f, deg(f). Towards this conjecture, we show that: - Symmetric functions have rational degree at least Ω(deg(f)) and unate functions have rational degree at least deg(f). We observe that both of these lower bounds are asymptotically tight. - Read-once AC and TC formulae have rational degree at least Ω(deg(f)). If these formulae contain parity gates, we show a lower bound of Ω(deg(f)1/2d), where d is the depth. - Almost every Boolean function on n variables has rational degree at least n/2−O(n). In contrast, we exhibit partial functions that witness unbounded separations between rational and approximate degree, in both directions. As a consequence, we show that for quantum computers, post-selection and bounded-error are incomparable resources in the black-box model. In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity.
The approximate degree of a Boolean function is the least degree of a real multilinear polynomial approximating it in the ℓ∞-norm over the Boolean hypercube. We show that the approximate degree of the Bipartite Perfect Matching function, which is the indicator over all bipartite graphs having a perfect matching, is Θ(n3/2). The upper bound is obtained by fully characterizing the unique multilinear polynomial representing the Boolean dual of the perfect matching function, over the reals. Crucially, we show that this polynomial has very small ℓ1-norm -- only exponential in Θ(nlogn). The lower bound follows by bounding the spectral sensitivity of the perfect matching function, which is the spectral radius of its cut-graph on the hypercube \cite{aaronson2020degree, huang2019induced}. We show that the spectral sensitivity of perfect matching is exactly Θ(n3/2).
The sensitivity of a Boolean function f is the maximum over all inputs x, of the number of sensitive coordinates of x. The well-known sensitivity conjecture of Nisan (see also Nisan and Szegedy) states that every sensitivity-s Boolean function can be computed by a polynomial over the reals of degree poly(s). The best known upper bounds on degree, however, are exponential rather than polynomial in s. Our main result is an approximate version of the conjecture: every Boolean function with sensitivity s can be epsilon-approximated (in L_2) by a polynomial whose degree is O(s log(1/epsilon)). This is the first improvement on the folklore bound of s/epsilon. Further, we show that improving the bound to O(s^c log(1/epsilon)^d)$ for any d < 1 and any c > 0 will imply the sensitivity conjecture. Thus our result is essentially the best one can hope for without proving the conjecture. We postulate a robust analogue of the sensitivity conjecture: if most inputs to a Boolean function f have low sensitivity, then most of the Fourier mass of f is concentrated on small subsets, and present an approach towards proving this conjecture.
In this thesis, Quantum computing, norms, and polynomials, we investigate the interplay between quantum mechanics, complexity theory, and functional analysis, three central areas of physics, computer science, and mathematics, respectively. The unifying theme throughout the thesis is the dynamic exchange between quantum computing and functional analysis: we explore new applications of functional inequalities in quantum computing, and, in the process, establish novel results in functional analysis itself. In the first part, we study quantum query algorithms through their correspondence with completely bounded polynomials, as established in earlier work. We begin by revisiting this correspondence, extending it, and presenting it in a new form. Building on this foundation, we draw an analogy between quantum query algorithms and the Grothendieck inequality. Finally, we conclude this part by employing completely bounded polynomials to solve a special case of one of the main open problems in quantum query complexity, the Aaronson–Ambainis conjecture. In the second part, we turn to quantum learning theory, which seeks to determine how much information must be extracted from a quantum system to fully characterize it. We begin by applying existing versions of the Bohnenblust–Hille inequalities and deriving new ones to obtain results in the learning of low-degree quantum objects. We conclude by presenting some of the first results in the emerging area of Hamiltonian testing and learning. We also include a third part, as a bonus, where we gather three new proofs, that we find elegant and concise, of known results related to the analysis of Boolean functions.
In this paper we study the fractional block sensitivity of Boolean functions. Recently, Tal [Tal13] and Gilmer, Saks, and Srinivasan [GSS13] independently introduced this complexity measure, denoted by fbs(f), and showed that it is equal (up to a constant factor) to the randomized certificate complexity, denoted by RC(f), which was introduced by Aaronson [Aar03]. In this paper, we relate the fractional block sensitivity to other complexity measures such as sensitivity s(f) and approximate degree deg(f). As a consequence we obtain the following results: 1. We show that deg(f) = Ω( √ RC(f)), solving an open question posed by Aaronson [Aar03]. This also implies that deg(f) = Ω(QC(f)), where QC(f) is the quantum certificate complexity of f. As both deg(f) and QC(f) serve as lower bounds for the bounded error quantum query complexity, this shows that deg(f) is always a tighter lower bound compared to QC(f). 2. (a) We show that every transitive function on n variables must have RC(f) = Ω(n), QC(f) = Ω(n) and deg(f) = Ω(n), and note that all these bounds are tight. This is a strengthening of the previous lower bounds given by [SYZ04] and [Sun07]. (b) We show that Chakraborty’s [Cha11] example of a transitive function with s(f) = O(n) is optimal unless there is better than quadratic separation between the block sensitivity and the sensitivity. 3. Using fractional block sensitivity, we show that the zero error randomized decision tree complexity, R0(f), is upper bounded by O(R2(f) 2 · logR2(f)) where R2(f) is the two-sided bounded error randomized decision tree complexity of f . This improves the previous best relation between these two complexity measures given by Midrijanis [Mid05] of R0(f) = O(R2(f) 2 · log n) (where n is the number of variables). 4. We show that the (non-negative weight) adversary methods to lower bound the bounded error quantum query complexity of f can not give better bounds than √ RC(f)RC(f). This refines the earlier bound of √ C0(f)C1(f) by Spalek and Szegedy [SS06] and strengthens the so called certificate complexity barrier to its randomized analogue. ∗Centre for Quantum Technologies, Singapore Email: kulraghav@gmail.com †The Weizmann Institute of Science, Rehovot, Israel. Email: avishay.tal@weizmann.ac.il. Research supported by an Adams Fellowship of the Israel Academy of Sciences and Humanities, by an Israel Science Foundation grant and by the Israeli Centers of Research Excellence (I-CORE) program. ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Revision 1 of Report No. 168 (2013)