Lower Bounds and Separations for Torus Polynomials

Krishan, Vaibhav; Vishwanathan, Sundar

doi:10.4230/LIPIcs.ITCS.2026.88

Lower Bounds and Separations for Torus Polynomials

Vaibhav Krishan

The Institute of Mathematical Sciences, Chennai, India Sundar Vishwanathan Indian Institute of Technology Bombay, Mumbai, India

Abstract

The class $\mathsf{{ACC}}^{0}$ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with $\and,\mathsf{{NOT}}$ and $\mathsf{{MOD}}_{m}$ gates, where $m$ is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that $\mathsf{{MAJORITY}}$ does not belong to $\mathsf{{ACC}}^{0}$ .

A few years ago, Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach towards this conjecture. Torus polynomials approximate Boolean functions when the fractional part of their value on Boolean points is close to half the value of the function. They reduced the conjecture that $\mathsf{{MAJORITY}}\notin\mathsf{{ACC}}^{0}$ to a conjecture concerning the non-existence of low degree torus polynomials that approximate $\mathsf{{MAJORITY}}$ .

We reduce the non-existence problem further, to a statement about finding feasible solutions for an infinite family of linear programs. The main advantage of this statement is that it allows for incremental progress, which means finding feasible solutions for successively larger collections of these programs. As an immediate first step, we find feasible solutions for a large class of these linear programs, leaving only a finite set for further consideration. Our method is inspired by the method of dual polynomials, which is used to study the approximate degree of Boolean functions. Using our method, we also propose a way to progress further.

We prove several additional key results with the same method, which include:

$\blacksquare$

A lower bound on the degree of symmetric torus polynomials that approximate the $\and$ function. As a consequence, we get a separation that symmetric torus polynomials are weaker than their asymmetric counterparts.
$\blacksquare$

An error-degree trade-off for symmetric torus polynomials approximating the $\mathsf{{MAJORITY}}$ function, strengthening the corresponding result of Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019).
$\blacksquare$

The first lower bounds against torus polynomials approximating $\and$ , showcasing the power of the machinery we develop. This lower bound nearly matches the corresponding upper bound. Hence, we get an almost complete characterization of the torus polynomial approximation degree of $\and$ .
$\blacksquare$

Lower bounds against asymmetric torus polynomials approximating $\mathsf{{MAJORITY}}$ , or $\and$ , in the very low error regime. This partially answers a question posed in Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) about error-reduction for torus polynomials.

Keywords and phrases:

Circuit complexity, ACC, lower bounds, polynomials

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Circuit complexity

Acknowledgements:

We thank Shachar Lovett for helpful feedback on an earlier draft. We also thank anonymous referees for their detailed feedback.

DOI:

10.4230/LIPIcs.ITCS.2026.88

Event:

17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Editor:

Shubhangi Saraf

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Proving that an explicit function is not contained in a complexity class is the prime focus of complexity theorists, and such questions make up some of the hardest problems in computer science. We study such a question at the frontier of our knowledge about Boolean circuit complexity classes. To state the question, we first need to define the class of Boolean circuits we consider.

Denote by $\mathsf{{ACC}}^{0}$ the class of constant-depth Boolean circuits of polynomial size comprising $\and,\mathsf{{NOT}}$ , and $\mathsf{{MOD}}_{m}$ gates. A $\mathsf{{MOD}}_{m}$ gate outputs $1$ if and only if the count of $1$ s in the input is divisible by $m$ . Nearly 35 years ago, Barrington [2] conjectured that $\mathsf{{ACC}}^{0}$ does not contain $\mathsf{{MAJORITY}}$ . Here, $\mathsf{{MAJORITY}}$ outputs $1$ if and only if the number of $1$ s is at least half of the total number of inputs. This conjecture has remained unresolved since.

Conjecture 1 (Barrington’s conjecture [2]).

$\mathsf{{MAJORITY}}\notin\mathsf{{ACC}}^{0}$ .

The objective of the conjecture is to prove that a particular circuit class cannot compute a certain function. In the literature, this task is referred to as proving lower bounds against that class. We outline a few major approaches that have led to Boolean circuit lower bounds in the past.

One of the approaches is based on “simplification”, and the probabilistic method, for example: using random restrictions. This is a classical technique, developed for studying various complexity classes, such as $\mathsf{{AC}}^{0}$ , the class of constant-depth circuits comprising $\and$ and $\mathsf{{NOT}}$ gates. A classic example is the landmark result of Håstad [15], who proved that $\mathsf{{AC}}^{0}$ circuits simplify when a significant fraction of the input variables are assigned values randomly. It is easy to see that the parity function does not undergo such simplification. The author formalized this intuition to prove nearly optimal lower bounds against $\mathsf{{AC}}^{0}$ circuits. However, random restrictions do not seem useful for lower bounds against $\mathsf{{ACC}}^{0}$ , as it contains the parity function.

Another approach is to use the satisfiability algorithms–to–lower bounds connection, to prove lower bounds from high complexity classes such as $\mathsf{NEXP}$ . Williams [25] developed this approach in a groundbreaking work, and used it to prove that $\mathsf{NEXP}$ is not contained in $\mathsf{{ACC}}^{0}$ . Subsequent works [13, 20, 9, 12, 10] have considerably strengthened this connection. In particular, Murray and Williams [20] have proved that $\mathsf{NQP}$ is not contained in $\mathsf{{ACC}}^{0}$ , improving the lower bound. However, it is not clear how to use this method to prove that an easily computable function, such as $\mathsf{{MAJORITY}}$ , is not contained in $\mathsf{{ACC}}^{0}$ .

This leads us toward another classical approach, based on the polynomial method. In this framework, researchers study various notions of representing Boolean functions using polynomials. This framework is quite powerful, and has numerous applications across theoretical computer science, see Aaronson’s survey [1] for an interesting and insightful account. We describe two notions of polynomial representations that have found uses in the study of Boolean circuits.

The first notion, called real polynomial approximation, uses polynomials over the reals to approximate Boolean functions pointwise. Nisan and Szegedy [21], in a seminal work, studied this model, and proved its connections with other natural computational models, such as decision trees. Their work provided considerable impetus to the study of real polynomial approximations, and firmly established their use in mainstream complexity theory. Today, the study of real polynomial approximations is a subfield by itself, with well-developed techniques for lower bounds and upper bounds, and numerous applications. See Bun and Thaler’s survey [8] for a comprehensive discussion of real polynomial approximations.

The second notion of polynomial approximation, called probabilistic polynomials, uses a distribution of polynomials over a finite field. On any Boolean point, a polynomial from the distribution should match the value of the given function with “high” probability. Razborov [23], and Smolensky [24], pioneered the use of this model in independent works. Consider any function $f$ computable by constant-depth circuits of polynomial size with $\and,\mathsf{{NOT}}$ and $\mathsf{{MOD}}_{p}$ gates, for a prime $p$ . The authors, independently, proved that there exists a distribution of “low” degree polynomial over $\mathbb{F}_{p}$ that matches $f$ with “high” probability. They also proved that the same does not hold for $\mathsf{{MAJORITY}}$ , or $\mathsf{{MOD}}_{q}$ for a prime $q\neq p$ , leading to a lower bound.

Broadly speaking, in order to prove that a function $f$ is not contained in a class $\mathcal{C}$ , the theme here is to find a distinguisher. A distinguisher is a function $\mu$ that maps $f$ to a point outside the image of $\mathcal{C}$ under $\mu$ , proving $f\notin\mathcal{C}$ . That is, proving $\mu(f)\notin\mu(\mathcal{C})$ implies $f\notin\mathcal{C}$ . For example, in [23, 24], the degree of the probabilistic polynomial acts as the distinguisher. This degree is low for functions in $\mathsf{{AC}}^{0}[p]$ , while $\mathsf{{MAJORITY}}$ requires large degree, hence the lower bound $\mathsf{{MAJORITY}}\notin\mathsf{{AC}}^{0}[p]$ .

The models of polynomial approximation defined above do not seem to give a distinguisher against $\mathsf{{ACC}}^{0}$ . For example, $\mathsf{{ACC}}^{0}$ circuits can use $\mathsf{{MOD}}_{6}$ , which requires large degree in either model. In fact, for a long time, there were no polynomial method based approaches known for proving $\mathsf{{ACC}}^{0}$ lower bounds.

Then, in a pivotal work few years ago, Bhrushundi, Hosseini, Lovett and Rao [4] made an inspired suggestion of using the degree of torus polynomials as a distinguisher towards the $\mathsf{{MAJORITY}}$ vs $\mathsf{{ACC}}^{0}$ question. Torus polynomials approximate a Boolean function $f$ if their fractional part is close to $\frac{f}{2}$ ¹¹1 $0$ and $1$ have the same fractional part. Dividing $f:\{0,1\}^{n}\to\{0,1\}$ by $2$ makes the fractional parts different.. They proved that torus polynomial approximations extend both real polynomial approximations and approximation using probabilistic polynomials (see [4, Lemma 14]). In fact, torus polynomials are more powerful, they can efficiently approximate $\mathsf{{MOD}}_{m}$ for any $m$ . We define this model below, rephrasing [4, Definition 1].

Definition 2 (Torus Polynomial Approximation [4]).

Consider a Boolean function $f:\{0,1\}^{n}\to\{0,1\}$ , a polynomial $P\in\mathbb{R}[X_{1},\ldots,X_{n}]$ (we assume that $P$ is multilinear without losing generality) and a real number $0\leq\varepsilon<\frac{1}{4}$ . $P$ is a torus polynomial that $\varepsilon$ -approximates $f$ , if the following holds:

There exists a function $Z:\{0,1\}^{n}\to\mathbb{Z}$ , such that for any Boolean point $a\in\{0,1\}^{n}$ , we have $\left\lvert P(a)-\frac{f(a)}{2}-Z(a)\right\rvert\leq\varepsilon$ . In other words, the fractional part of $P(a)$ is within $\varepsilon$ of $\frac{f(a)}{2}$ .

Denote the minimum degree of such a polynomial by $\overline{{\mathop{{\deg}}}}_{\varepsilon}(f)$ .

Given any function $f:\{0,1\}^{n}\to\{0,1\}$ , consider the unique polynomial that exactly matches $f$ on all Boolean points²²2The existence of such a polynomial is folklore.. This would require degree $n$ for most functions, with zero error of approximation. Naturally, the question is, for which functions $f$ can we construct a torus polynomial of much smaller degree, say $\log^{2}(n)$ , that $\frac{1}{n^{2}}$ -approximate $f$ , for example. In [4, Corollary 20], the authors proved that something similar holds for all functions in $\mathsf{{ACC}}^{0}$ .

Theorem 3 ([4]).

Consider any function $f:\{0,1\}^{n}\to\{0,1\}$ such that $f\in\mathsf{{ACC}}^{0}$ . Then, $\overline{{\mathop{{\deg}}}}_{\varepsilon}(f)\leq\log(n)^{O(1)}$ for any $\varepsilon\geq\frac{1}{n^{O(1)}}$ .

Hence, proving that the same does not hold for the majority function would prove $\mathsf{{MAJORITY}}$ is not contained in $\mathsf{{ACC}}^{0}$ . This is precisely the goal of our work in this paper. While we could not take this task to completion, we do make progress towards it. Before discussing our contributions, we discuss previous work related to $\mathsf{{ACC}}^{0}$ as well as torus polynomials.

1.1 Previous Work

Various works in the 90’s had proved conversion results for $\mathsf{{ACC}}^{0}$ , with the purpose of proving $\mathsf{{ACC}}^{0}$ lower bounds. For example, strengthening the results from [26, 3], Green, Köbler, Regan, Schwentick and Torán [14] proved that all $\mathsf{{ACC}}^{0}$ functions have $\mathsf{{MidBit}}^{+}$ circuits computing them. Here, $\mathsf{{MidBit}}^{+}$ is the class of depth-two circuits, with $\and$ gates at the bottom and a $\mathsf{{MidBit}}$ gate³³3A $\mathsf{{MidBit}}$ outputs the middle bit from the binary expansion of the number of $1$ s, with a fixed tie-breaking choice. at the top. The authors proposed to prove lower bounds against $\mathsf{{MidBit}}^{+}$ as an approach to prove $\mathsf{{ACC}}^{0}$ lower bounds. They argued that the simpler structure of $\mathsf{{MidBit}}^{+}$ circuits might make it easier to prove lower bounds.

Along similar lines, by combining [16, 22], one gets a communication complexity based approach. These works together imply that lower bounds against the number-on-forehead communication model lead to $\mathsf{{ACC}}^{0}$ lower bounds. However, lower bounds against this communication model also imply $\mathsf{{MidBit}}^{+}$ lower bounds. Hence, logically speaking, lower bounds against $\mathsf{{MidBit}}^{+}$ are an easier route to $\mathsf{{ACC}}^{0}$ lower bounds.

In Krishan [17], the author proved that functions with low degree torus polynomial approximations belong to $\mathsf{{MidBit}}^{+}$ . Hence, one can argue that lower bounds against torus polynomials is an even more refined approach for $\mathsf{{ACC}}^{0}$ lower bounds. Moreover, Chen, Lu, Lyu and Oliveira [11] proved that lower bounds against torus polynomials lead to average-case lower bounds, and pseudorandom generators, against $\mathsf{{ACC}}^{0}$ . Both of these are major open questions, which gives us a further impetus for proving lower bounds against torus polynomials.

In [4], the authors introduced torus polynomials with the goal of proving that $\mathsf{{MAJORITY}}$ does not belong to $\mathsf{{ACC}}^{0}$ . Now, $\mathsf{{MAJORITY}}$ is a symmetric function, as its value only depends on the number of $1$ s in the input. Hence, it is natural to study symmetric⁴⁴4A polynomial is symmetric if it is invariant under permutation of its variables. torus polynomials that approximate $\mathsf{{MAJORITY}}$ as the first step. The authors used a counting-based argument to prove the following lower bound.

Theorem 4 (Corollary 23 of [4]).

Any symmetric torus polynomial, that $\frac{1}{20n}$ -approximates $\mathsf{{MAJORITY}}$ , must have degree $\Omega\left(\sqrt{\frac{n}{\log(n)}}\right)$ .

Now, a priori, this does not resolve Barrington’s conjecture, it needs an analogous statement for asymmetric torus polynomials. Indeed, in [4, Conjecture 5], the authors conjectured that Theorem 4 holds for asymmetric torus polynomials.

Conjecture 5 ([4]).

Any torus polynomial, that $\frac{1}{20n}$ -approximates $\mathsf{{MAJORITY}}$ , must have degree $\Omega\left(\sqrt{\frac{n}{\log(n)}}\right)$ .

This conjecture, if true, proves Barrington’s conjecture. Moreover, it will separate $\mathsf{P}$ from $\mathsf{{ACC}}^{0}$ , improving our knowledge well beyond what is currently known.

1.2 Our Results

The main goal of our work is to resolve Conjecture 5. Towards this end, we outline a plan of attack in Section 3. A major contribution of this paper is a reduction of Conjecture 5 to a statement that allows for incremental progress.

Fix $n$ and $d=o\left(\sqrt{\frac{n}{\log(n)}}\right)$ , and suppose the goal is to prove the following: Any torus polynomial that $\varepsilon$ -approximates $\mathsf{{MAJORITY}}$ over $n$ variables must have degree more than $d$ . Informally stated, we define a vector space $\Gamma$ of dimension $2^{n}$ , a vector $v^{\prime}$ of dimension $2^{n}$ , and conjecture that for any vector $v\in\mathbb{Z}^{2^{n}}$ , there is a $\gamma\in\Gamma$ such that:

\sum_{i=1}^{2^{n}}(v_{i}+v^{\prime}_{i})\gamma_{i}>\varepsilon\sum_{i=1}^{2^{n% }}\lvert\gamma_{i}\rvert

The vector $v^{\prime}$ has a very simple structure, it encodes the function for which we wish to prove the lower bound, say $\mathsf{{MAJORITY}}$ . See Theorem 8 for an exact statement. Incremental progress would mean proving the statement for larger and larger subsets of $\mathbb{Z}^{2^{n}}$ .

We take the first steps in this direction by first bounding the entries in $v$ , see Theorem 11. This immediately leaves us with only a finite subset of $\mathbb{Z}^{2^{n}}$ for which we need to argue further. Then, in Theorem 12, we take another step by showing that a few entries in $v$ determine the other entries.

We demonstrate the power of our method by proving a lower bound against torus polynomials approximating $\and$ . No lower bounds were known for asymmetric torus polynomials prior to our work, and the lower bound we prove is only quadratically away from the corresponding upper bound for inverse-polynomial error. Following is the formal statement of the result.

Theorem 6.

Any torus polynomial, that $\varepsilon$ -approximates $\and$ , must have degree $\Omega\left(\log\left(\frac{1}{\varepsilon}\right)\right)$ .

The result above also holds for $\mathsf{{MAJORITY}}$ , but it does not suffice to prove $\mathsf{{MAJORITY}}\notin\mathsf{{ACC}}^{0}$ , which requires a lower bound of the form $\log^{\omega(1)}(n)$ for some inverse-polynomial error. Further, as a special case of the result above, we study the case when $\varepsilon$ is exponentially small. We show that $\and$ requires full degree in this regime, and so does $\mathsf{{MAJORITY}}$ . In [4, Problem 6], the authors ask about error-reduction for torus polynomials. The full-degree lower bound allows us to conditionally answer this question for a particular error-regime, which we discuss in Subsection 4.1.

Our method also applies to symmetric torus polynomials, which we use to prove a much stronger lower bound against symmetric torus polynomials approximating $\and$ . This lower bound matches the lower bound from [4, Corollary 23] (refer to Theorem 4), but for $\and$ , rather than $\mathsf{{MAJORITY}}$ . Note that no such lower bound was known for $\and$ before our work, and it matches the corresponding upper bound, barring some log factors. We state the result below.

Theorem 7.

Any symmetric torus polynomial, that $\frac{1}{20n}$ -approximates $\and$ , must have degree $\Omega\left(\sqrt{\frac{n}{\log(n)}}\right)$ .

The lower bound for symmetric torus polynomials is higher than the upper bound for asymmetric torus polynomials approximating $\and$ . Hence, as a corollary, we prove that symmetric torus polynomials are weaker than their asymmetric counterparts, see Corollary 23. Moreover, this shows that a symmetrization based approach is unlikely to work for Conjecture 5.

We also strengthen [4, Corollary 23], and prove stronger degree lower bounds for smaller error. If one follows the proof of [4, Corollary 23], for symmetric torus polynomials that $\frac{1}{n^{2}}$ -approximate $\mathsf{{MAJORITY}}$ , the lower bound remains the same, i.e. $\Omega\left(\sqrt{\frac{n}{\log(n)}}\right)$ . We are able to prove $\Omega\left(\sqrt{n}\right)$ as the lower bound in this case, strictly improving the degree, albeit by a log factor. In fact, we are able to prove an error-degree trade-off, see Theorem 28 for the exact statement.

Our Method

We use a linear programming based approach to prove our lower bound results. This approach, based on duality in linear programs, allows us to find a witness that certifies the non-existence of a torus polynomial approximation. We describe a broad outline of the method below.

Consider a torus polynomial $P$ , of degree at most $d$ , that $\varepsilon$ -approximates $f$ . Then, there exists some integer function $Z:\{0,1\}^{n}\to\mathbb{Z}$ , such that $P(a)$ is at most $\varepsilon$ away from $Z(a)+\frac{f(a)}{2}$ for any $a\in\{0,1\}^{n}$ . For each $a$ , we can write $P(a)$ as a particular linear combination of its coefficients, hence, the condition above is a linear constraint. Here, we make a crucial choice, with respect to how we treat $Z$ . If we treat each $Z(a)$ as an integer-valued variable, we get a system of linear Diophantine inequalities, that are much harder to handle. Instead, we treat each $Z(a)$ as an indeterminate, and write one linear program for each possible function $Z$ .

Thereby, we get an infinite family of linear programs, such that $P$ exists if and only if some program from the family is feasible. Hence, to prove that $P$ does not exist, we need to prove that each program is infeasible, for which we look at the dual of these programs. Using strong duality in linear programs, $P$ does not exist if and only if each of the dual programs is feasible.

Now, given a function $Z$ , the dual program we obtain is as follows: For each $n$ , and each degree $d$ , we have a matrix $M(n,d)$ , comprising the evaluations of all monomials of degree at most $d$ on each Boolean point. The set of solutions for the dual program consists of the nullspace of $M(n,d)$ , i.e., vectors $\gamma$ such that $M(n,d)\gamma=0$ . Here, $\gamma$ is a vector with $2^{n}$ many real entries, with each entry $\gamma_{a}$ indexed by a Boolean point $a$ . A vector $\gamma$ is a feasible solution for the dual, if it satisfies $\left\lvert\sum_{a\in\{0,1\}^{n}}\gamma_{a}\left(Z(a)+\frac{f(a)}{2}\right)% \right\rvert>\varepsilon\sum_{a\in\{0,1\}^{n}}\lvert\gamma_{a}\rvert$ . For a detailed explanation on how we obtain the dual, please refer to Theorem 8.

With this method, our plan to prove Conjecture 5 is as follows. Fix $n$ , and any $d=o\left(\sqrt{\frac{n}{\log(n)}}\right)$ , with $f=\mathsf{{MAJORITY}}$ and $\varepsilon=\frac{1}{20n}$ . For any function $Z:\{0,1\}^{n}\to\mathbb{Z}$ , we plan to find a feasible solution $\gamma$ for the dual corresponding to $Z$ . To start, we find such a feasible solution if $\lvert Z(a)\rvert$ exceeds an upper bound for any $a\in\{0,1\}^{n}$ , where the upper bound depends on $a$ . Then, we show how to infer the values of $Z(a)$ for each $a$ with Hamming weight $\lvert a\rvert\geq(d+1)^{2}$ , when all $Z(a)$ for $\lvert a\rvert<(d+1)^{2}$ are fixed. In other words, if $Z(a)$ does not take the inferred value for some $a$ , we find a feasible solution for the dual corresponding to $Z$ . We propose to continue this plan further, by finding more feasible solutions to incrementally rule out all possible $Z$ s.

Our method shares some similarities to how dual polynomials are used to prove lower bounds for real polynomial approximations. Each vector $\gamma$ in the nullspace of $M(n,d)$ is in fact a dual polynomial, with pure high-degree more than $d$ . We use a geometric perspective, as we find it more useful, especially for our lower bound results.

Organization

We discuss some preliminaries, and a general method for proving torus polynomial lower bounds, in Section 2. Based on this method, we propose a plan to prove Conjecture 5 in Section 3. Our lower bound results for asymmetric torus polynomials appear in Section 4. Finally, we prove lower bounds for symmetric torus polynomials in Section 5.

2 Preliminaries

We consider natural numbers without including $0$ , and denote it by $\mathbb{N}=\{1,2,\ldots\}$ . For $n\in\mathbb{N}$ and $d\in\mathbb{N}$ , we use the following notation for brevity:

$\displaystyle\binom{n}{\leq d}$	$\displaystyle=\sum_{i\leq d}\binom{n}{i}$	$\displaystyle\binom{n}{>d}$	$\displaystyle=\sum_{i>d}\binom{n}{i}$
$\displaystyle[n]$	$\displaystyle=\{1,\ldots,n\}$	$\displaystyle[n]^{*}$	$\displaystyle=\{0,\ldots,n\}$
$\displaystyle\binom{[n]}{\leq d}$	$\displaystyle=\{S:S\subseteq[n],\lvert S\rvert\leq d\}$	$\displaystyle\binom{[n]}{>d}$	$\displaystyle=\{S:S\subseteq[n],\lvert S\rvert>d\}$

2.1 Sets and Boolean Points

We identify $2^{[n]}$ with $\{0,1\}^{n}$ in the natural way, as follows. For $S\subseteq[n]$ , the corresponding Boolean point has a $1$ at position $i$ if and only if $i$ is present in $S$ . This defines a bijection between $2^{[n]}$ and $\{0,1\}^{n}$ . Using this bijection, we will often interpret a set $S\subseteq[n]$ as a Boolean point, and a Boolean point $a\in\{0,1\}^{n}$ as a set, making the interpretation explicit wherever it is not clear from the context. $\lvert a\rvert$ denotes the Hamming weight of $a\in\{0,1\}^{n}$ , which also equals its size when considered as a set.

2.2 Linear Algebra

Over the reals $\mathbb{R}$ , we denote the set of matrices of size $m\times n$ by $\mathcal{M}_{m\times n}(\mathbb{R})$ . For a matrix $M\in\mathcal{M}_{m\times n}(\mathbb{R})$ , we denote its nullspace by $\mathop{{nullspace}}(M)=\{\gamma\in\mathbb{R}^{n}:M\gamma=0\}$ . For a vector $\gamma\in\mathbb{R}^{n}$ , we denote its $\ell^{p}$ -norm by $\lVert\gamma\rVert_{p}=(\sum_{i=1}^{n}\lvert\gamma_{i}\rvert^{p})^{\frac{1}{p}}$ . Of particular interest to us are the $\ell^{1}$ -norm and the $\ell^{2}$ -norm, defined for $p=1,2$ respectively. We will also consider the $\ell^{\infty}$ -norm, defined as $\lVert\gamma\rVert_{\infty}=\max_{i=1}^{n}\lvert\gamma_{i}\rvert$ .

2.3 Our Method for Torus Polynomial Lower Bounds

Now, we describe a general method for proving lower bounds on torus polynomial approximations. Fix $n\in\mathbb{N}$ and $d\in\mathbb{N}$ , such that $d<n$ . Also, fix a Boolean function $f:\{0,1\}^{n}\to\{0,1\}$ , and an error of approximation $\varepsilon<\frac{1}{4}$ . We start by defining a family of set-inclusion matrices that will be relevant for the method. For each monomial of degree at most $d$ over $n$ variables, the matrix contains one row, and the row encodes the evaluation of the monomial over all Boolean points.

Construction 1.

Define the matrix $M(n,d)$ of size $\binom{n}{\leq d}\times 2^{n}$ as follows. Its rows are indexed by elements of $\binom{[n]}{\leq d}$ , and columns by elements of $2^{[n]}$ . The entries for $1\leq i\leq\binom{n}{\leq d},$ $1\leq j\leq 2^{n}$ are:

M_{i,j}=1_{S_{i}\subseteq S_{j}}

Here, $1_{S_{i}\subseteq S_{j}}$ is an indicator function, evaluating to $1$ if $S_{i}\subseteq S_{j}$ , and zero otherwise.

In the following statement, we convert the question of torus polynomial lower bounds to an existence based question.

Theorem 8.

The following are equivalent for any $n\in\mathbb{N},d\in\mathbb{N}$ such that $d<n$ , $\varepsilon<\frac{1}{4}$ and $f:\{0,1\}^{n}\to\{0,1\}$ :

$\blacksquare$

Any torus polynomial that $\varepsilon$ -approximates $f$ has degree more than $d$ .
$\blacksquare$

For any $Z:\{0,1\}^{n}\to\mathbb{Z}$ , there exists a vector $\gamma\in\mathop{{nullspace}}(M(n,d))$ , such that:

$\left\lvert\left\langle Z+\frac{f}{2},\gamma\right\rangle\right\rvert>% \varepsilon\lVert\gamma\rVert_{1}$

We do not present the proof here, as it is very similar to the method of dual polynomials (see [8] or refer to the full version for a proof).

3 Plan for Majority

In this section, we set up a program towards proving Conjecture 5. Fix the function for this section $f=\mathsf{{MAJORITY}}$ , some large enough $n\in\mathbb{N}$ , any $d\leq O\left(\sqrt{\frac{n}{\log(n)}}\right)$ , and $\varepsilon=\frac{1}{20n}$ . Call a function $Z:\{0,1\}^{n}\to\mathbb{Z}$ good, if there is a witness $\gamma\in\mathop{{nullspace}}(M(n,d))$ such that:

\left\lvert\left\langle Z+\frac{\mathsf{{MAJORITY}}}{2},\gamma\right\rangle% \right\rvert>\varepsilon\left\lVert\gamma\right\rVert_{1}

In other words, $Z$ is good, if we can prove that the dual corresponding to $Z$ is feasible. Conjecture 5 posits that all $Z$ s are good. In this language, the lower bound result by Bhrushundi, Hosseini, Lovett and Rao [4, Corollary 3.3] states that all symmetric $Z$ s are good.

Now, the challenge is that we need to argue about infinitely many $Z$ s, and find a feasible solution $\gamma$ from the vector space $\mathop{{nullspace}}(M(n,d))$ , which is also infinite. The latter is easy to fix using the theory of linear programming, as we can choose $\gamma$ from the set of basic solutions, which is a finite set. Therefore, we focus on the set of good $Z$ s, and show that it is cofinite. In other words, we show that all $Z$ s, except for a finite set, are good.

Towards this goal, we first make an observation that allows us to consider $Z$ s as functions over a smaller domain. Consider two functions $Z$ and $Z^{\prime}$ , such that $Z-Z^{\prime}\in\mathop{{row\text{--}span}}(M)$ . Then, $\langle Z,\gamma\rangle$ equals $\langle Z^{\prime},\gamma\rangle$ for any $\gamma\in\mathop{{nullspace}}(M)$ . Hence, if $Z$ is good, then any $Z^{\prime}$ such that $Z-Z^{\prime}\in\mathop{{row\text{--}span}}(M)$ is also good. Therefore, define the relation $Z\sim Z^{\prime}$ if $Z-Z^{\prime}\in\mathop{{row\text{--}span}}(M)$ , which is an equivalence relation. We can pick a representative $Z$ from each equivalence class of the relation, and it suffices to prove that the representative $Z$ is good. The following statement formalizes this intuition.

Lemma 9.

Consider a polynomial $P\in\mathbb{R}[X_{1},\ldots,X_{n}]$ of degree at most $d$ . Then, there exists a polynomial $P^{\prime}\in\mathbb{R}[X_{1},\ldots,X_{n}]$ of degree at most $d$ , satisfying the following conditions:

$\blacksquare$

If $P$ $\varepsilon$ -approximates $f$ , then $P^{\prime}$ also $\varepsilon$ -approximates $f$ .
$\blacksquare$

If $Z^{\prime}$ denotes the integer part of $P^{\prime}$ , then $Z^{\prime}(a)=0$ for any $a$ with $\lvert a\rvert\leq d$ .

The proof is based on a simple inductive argument, which we present in the full version. Henceforth, we will always assume that $Z(a)=0$ for any $a\in\{0,1\}^{n}$ with $\lvert a\rvert\leq d$ . Now, we begin the task of proving that certain $Z$ s are good. We will produce the vectors we need for this task using the following construction, which is only a minor generalization of the construction from [7].

Construction 2.

Construct a vector $\gamma$ as follows.

Input:

$\blacksquare$

two natural numbers $n\in\mathbb{N}$ and $d\in[n-1]^{*}$ ,
$\blacksquare$

two subsets $S_{1},S_{2}\subseteq[n]$ , such that $S_{1}\subseteq S_{2}$ , and $\lvert S_{2}\setminus S_{1}\rvert\geq d+1$ ,
$\blacksquare$

a set $I\subseteq[\lvert S_{2}\setminus S_{1}\rvert]^{*}$ of size $\lvert I\rvert=d+2$ .

Output:

A vector $\gamma\in\mathbb{R}^{2^{n}}$ .

Construction:

First, define a univariate polynomial $q_{I}(t)=\prod_{i\in[k]^{*}\setminus I}(t-i)$ , where $k=\lvert S_{2}\setminus S_{1}\rvert$ . For any set $T$ , if $S_{1}\subseteq T\subseteq S_{2}$ , keep $\gamma_{T}=(-1)^{\lvert T\rvert}q_{I}(\lvert T\setminus S_{1}\rvert)$ . Otherwise, keep $\gamma_{T}=0$ .

Output $\gamma$ .

Lemma 10.

Consider any $n\in\mathbb{N}$ , $d\in[n-1]^{*}$ , $S_{1},S_{2}\subseteq[n]$ such that $S_{1}\subseteq S_{2}$ and $\lvert S_{2}\setminus S_{1}\rvert\geq d+1$ , and $I\subseteq[\lvert S_{2}\setminus S_{1}\rvert]^{*}$ of size $\lvert I\rvert=d+2$ . Then, Construction 2, on input $n,d,S_{1},S_{2}$ and $I$ , outputs a vector $\gamma\in\mathop{{nullspace}}(M(n,d))$ .

As the proof is similar to the proof of [8, Lemma 31], we omit it here (refer to the full version for a proof). Using these vectors constructed above, we prove an upper bound on the value of each $Z(a)$ . In other words, for each $a$ we describe an upper bound, such that if $Z(a)$ violates this bound, then $Z$ is good. The reader may think of this as an upper bound on an appropriately defined weighted $\ell^{\infty}$ -norm of $Z$ .

Theorem 11.

Choose a large enough $n\in\mathbb{N}$ . Consider a torus polynomial $P$ , of degree at most $d<\frac{n}{2}$ , that approximates $f=\mathsf{{MAJORITY}}$ within an error of $\varepsilon$ . Then, the following holds for any $a\in\{0,1\}^{n}$ and the function $Z$ corresponding to $P$ :

\lvert Z(a)\rvert\leq\varepsilon 2^{d+1}\binom{\lvert a\rvert}{d+1}

In other words, if $\lvert Z(a)\rvert>\varepsilon 2^{d+1}\binom{\lvert a\rvert}{d+1}$ for some $a\in\{0,1\}^{n}$ , then $Z$ is good.

The statement above holds for any $f$ such that $f(a)=0$ for each $a\in\binom{[n]}{\leq d}$ , e.g. $f=\and$ ⁵⁵5As noted by an anonymous reviewer..

Proof.

Consider a set $S$ of size $\lvert S\rvert=k\geq d+1$ . Construct a ray $\overline{\gamma}\in\mathop{null}(M)$ using Construction 2 with $S_{1}=\emptyset,S_{2}=S$ and $I=[d]^{*}\cup\{k\}$ . The values we need to compare are $\left\langle Z+\frac{f}{2},\overline{\gamma}\right\rangle$ and $\varepsilon\lVert\overline{\gamma}\rVert_{1}$ . Note that $Z(a)=f(a)=0$ for any $a$ with $\lvert a\rvert\leq d$ . Hence, $\left\langle\overline{\gamma},Z+\frac{f}{2}\right\rangle=\overline{\gamma}_{S}% \left(Z(S)+\frac{f(S)}{2}\right)$ . Therefore, if $\left\lvert Z(S)+\frac{f(S)}{2}\right\rvert>\frac{\varepsilon\lVert\overline{% \gamma}\rVert_{1}}{\lvert\overline{\gamma}_{S}\rvert}$ , then $Z$ is good.

For a set $T\subseteq S$ of size $\lvert T\rvert\in\{d+1,\ldots,k-1\}$ , $\overline{\gamma}_{T}=0$ by construction. Then, $\lvert\overline{\gamma}_{S}\rvert=\prod_{i=1}^{k-(d+1)}i=(k-d-1)!$ . Finally, for a set $T\subseteq S$ of size $\lvert T\rvert=t\leq d$ , $\lvert\overline{\gamma}_{T}\rvert=\prod_{i=d+1}^{k-1}(i-t)=\frac{(k-1-t)!}{(d-% t)!}$ . Note that there are $\binom{k}{t}$ such sets $T$ .

Hence, $\lVert\overline{\gamma}\rVert_{1}=(k-d-1)!+\sum_{t=0}^{d}\binom{k}{t}\frac{(k-% 1-t)!}{(d-t)!}$ . Dividing by $\lvert\overline{\gamma}_{S}\rvert$ , we get:

$\displaystyle\frac{\lVert\overline{\gamma}\rVert_{1}}{\lvert\overline{\gamma}_% {S}\rvert}$	$\displaystyle=1+\sum_{t=0}^{d}\binom{k}{t}\frac{(k-1-t)!}{(d-t)!(k-d-1)!}$	$\displaystyle=1+\sum_{t=0}^{d}\frac{k!}{t!(d-t)!(k-d-1)!(k-t)}$
	$\displaystyle=1+\binom{k}{d+1}\sum_{t=0}^{d}\binom{d}{t}\frac{d+1}{k-t}$	$\displaystyle\leq 1+\binom{k}{d+1}\sum_{t=0}^{d}\binom{d}{t}\frac{d+1}{d+1-t}$
	$\displaystyle=1+\binom{k}{d+1}\sum_{t=0}^{d}\binom{d+1}{t}$	$\displaystyle=1+\binom{k}{d+1}\left(2^{d+1}-1\right)$
	$\displaystyle\leq 2^{d+1}\binom{k}{d+1}$

This proves the claim as desired. $\hfill\blacktriangleleft$

With the previous result, we have only a finite set of $Z$ s remaining, that we need to prove are good. We continue with our program of shrinking the set of remaining $Z$ s. Here, we consider some fixed value of $Z(a)$ for each $a$ with $\lvert a\rvert<(d+1)^{2}$ . Then, we show how to uniquely determine the remaining values of $Z(a)$ . In other words, if $Z(a)$ does not take the determined value for some $a$ , then $Z$ is good.

Theorem 12.

For any large enough $n\in\mathbb{N}$ , any $d<\sqrt{n}-1$ , and $\varepsilon=\frac{1}{20n}$ , the following holds: Fix values of $Z(b)$ for each point $b\in\{0,1\}^{n}$ with $\lvert b\rvert<(d+1)^{2}$ . Then, consider a point $a\in\{0,1\}^{n}$ with $\lvert a\rvert\geq(d+1)^{2}$ . For each $a^{\prime}\subseteq a$ with $\lvert a^{\prime}\rvert=\lvert a\rvert-(d+1)^{2}$ , define the following rational number:

R_{a,a^{\prime}}=2\sum_{i=1}^{d+1}(-1)^{i}\frac{\binom{d+1}{i}}{\binom{d+i+1}{% i}}\left(\frac{\sum_{a^{\prime}\subseteq b\subseteq a:\lvert b\rvert=\lvert a% \rvert-i^{2}}Z(b)+\frac{f(b)}{2}}{\binom{(d+1)^{2}}{i^{2}}}\right)

If the following holds for any $a^{\prime}$ :

\left\lvert Z(a)+R_{a,a^{\prime}}+\frac{f(a)}{2}\right\rvert>\frac{1}{\sqrt{n}}

Then, $Z$ is good. Note that all choices of $Z(a)\in\mathbb{Z}$ , except for possibly a single choice, lead to a good $Z$ . In other words, $Z(a)$ is uniquely determined.

Before we begin the proof, we would like to explain the expression in simple words as it may look complicated at first glance. First, the expression only looks at $Z(b)+\frac{f(b)}{2}$ where $b$ belongs to the Hamming sub-cube between $a^{\prime}$ and $a$ . The expression $\frac{\sum_{a^{\prime}\subseteq b\subseteq a:\lvert b\rvert=\lvert a\rvert-i^{% 2}}Z(b)+\frac{f(b)}{2}}{\binom{(d+1)^{2}}{i^{2}}}$ is simply the average over the Hamming layer at distance $i^{2}$ below $a$ . This average is multiplied with the coefficient $2\cdot(-1)^{i}\frac{\binom{d+1}{i}}{\binom{d+i+1}{i}}$ to obtain the expression. Now, we begin the proof.

Proof.

Fix a point $a\in\{0,1\}^{n}$ with $\lvert a\rvert\geq(d+1)^{2}$ , and choose a subset $a^{\prime}\subseteq a$ with $\lvert a^{\prime}\rvert=\lvert a\rvert-(d+1)^{2}$ . Use Construction 10 with $n,d,S_{1}=a^{\prime},S_{2}=a,I=\left\{(d+1)^{2}-i^{2}:i\in[d+1]^{*}\right\}$ , to obtain $\overline{\gamma}\in\mathop{{nullspace}}(M)$ . We denote the polynomial $q_{I}$ from the construction by $q$ for brevity.

Now, assume that the condition from the statement holds, which is as follows:

\left\lvert Z(a)+R_{a,a^{\prime}}+\frac{f(a)}{2}\right\rvert>\frac{1}{\sqrt{n}}

(1)

Then, we claim that $Z$ is good, with $\overline{\gamma}$ as the witness, i.e.,

\left\lvert\left\langle Z+\frac{f}{2},\overline{\gamma}\right\rangle\right% \rvert>\varepsilon\lVert\overline{\gamma}\rVert_{1}

(2)

To see why 1 implies 2, consider the following equalities:

$\displaystyle\left\langle Z+\frac{f}{2},\overline{\gamma}\right\rangle$	$\displaystyle=\sum_{b\in\{0,1\}^{n}}\left(Z(b)+\frac{f(b)}{2}\right)\overline{% \gamma}_{b}$	(3)
	$\displaystyle=\sum_{a^{\prime}\subseteq b\subseteq a}\left(Z(b)+\frac{f(b)}{2}% \right)\overline{\gamma}_{b}$	(4)
	$\displaystyle=\sum_{i=0}^{d+1}(-1)^{i^{2}}q((d+1)^{2}-i^{2})\sum_{a^{\prime}% \subseteq b\subseteq a:\lvert b\rvert=\lvert a\rvert-i^{2}}\left(Z(b)+\frac{f(% b)}{2}\right)$	(5)

Equality 3 follows by expanding the expression. Note that $\overline{\gamma}_{b}=0$ for any $b$ with either $a^{\prime}\not\subseteq b$ or $b\not\subseteq a$ , as per the construction of $\overline{\gamma}$ . Hence, equality 4 follows. Finally, we substitute the values of $\overline{\gamma}_{b}$ to obtain equality 5.

Now, to calculate the RHS of inequality 2, expand the $\ell^{1}$ -norm of $\overline{\gamma}$ as $\lVert\overline{\gamma}\rVert_{1}=\sum_{i=0}^{d+1}\binom{(d+1)^{2}}{i^{2}}% \left\lvert q((d+1)^{2}-i^{2})\right\rvert$ . We divide the expression of the inner-product, as well as the $\ell^{1}$ -norm, to modify inequality 2 as:

\left\lvert\sum_{i=0}^{d+1}\frac{q((d+1)^{2}-i^{2})}{q((d+1)^{2})}\left(\sum_{% \begin{subarray}{c}a^{\prime}\subseteq b\subseteq a\\ \lvert a\rvert-\lvert b\rvert=i^{2}\end{subarray}}Z(b)+\frac{f(b)}{2}\right)% \right\rvert>\varepsilon\sum_{i=0}^{d+1}\binom{(d+1)^{2}}{i^{2}}\frac{\left% \lvert q((d+1)^{2}-i^{2})\right\rvert}{q((d+1)^{2})}

Note that $q((d+1)^{2})>0$ , hence, dividing by $q((d+1)^{2})$ does not change the direction of the inequality. Next, we calculate $\binom{(d+1)^{2}}{i^{2}}\frac{q(i^{2})}{q((d+1)^{2})}$ as follows. Recall the expression for $q(t)=q_{I}(t)=\prod_{i\in[(d+1)^{2}]^{*}\setminus I}(t-i)$ . Hence, we get the following expression for $\binom{(d+1)^{2}}{i^{2}}\frac{q((d+1)^{2}-i^{2})}{q((d+1)^{2})}$ :

	$\displaystyle\binom{(d+1)^{2}}{i^{2}}\frac{q((d+1)^{2}-i^{2})}{q((d+1)^{2})}$	$\displaystyle=\binom{(d+1)^{2}}{i^{2}}\frac{\prod_{j\in[(d+1)^{2}]^{}% \setminus I}((d+1)^{2}-i^{2}-j)}{\prod_{j\in[(d+1)^{2}]^{}\setminus I}((d+1)^% {2}-j)}$
		$\displaystyle=\binom{(d+1)^{2}}{i^{2}}\frac{\prod_{j\in[(d+1)^{2}-2,(d+1)^{2}-% 3,\ldots,1]}((d+1)^{2}-i^{2}-j)}{\prod_{j\in[(d+1)^{2}-2,(d+1)^{2}-3,\ldots,1]% }((d+1)^{2}-j)}$
		$\displaystyle=\binom{(d+1)^{2}}{i^{2}}\frac{\prod_{j\in[2,3,5,\ldots,(d+1)^{2}% -1]}(j-i^{2})}{\prod_{j\in[2,3,5,\ldots,(d+1)^{2}-1]}(j)}$
		$\displaystyle=\frac{\prod_{j\in[d+1]}j^{2}}{\prod_{j\in[d+1]^{*}\setminus\{i\}% }(j-i)(j+i)}=(-1)^{i}\cdot 2\cdot\frac{\binom{d+1}{i}}{\binom{d+i+1}{i}}$

The calculation here is similar to the calculation performed in Section 6.1 of [8], following Fact 32 in the survey. Now, we can replace the final expression in the LHS of inequality 2 to get the LHS of inequality 1. Moreover, this calculation allows us to infer the following upper bound on the absolute value of the final ratio, for any $i\in[d+1]$ :

\left\lvert\binom{(d+1)^{2}}{i^{2}}\frac{q((d+1)^{2}-i^{2})}{q((d+1)^{2})}% \right\rvert\leq 2

(6)

Hence, we get that $\frac{\lVert\overline{\gamma}\rVert_{1}}{q((d+1)^{2})}\leq 2\lvert I\rvert=2(d% +2)\leq 4\sqrt{n}$ for large enough $n$ . Therefore, if $\left\lvert Z(a)+R_{a,a^{\prime}}+\frac{f(a)}{2}\right\rvert>\frac{1}{\sqrt{n}% }\geq\frac{1}{20n}4\sqrt{n}$ holds, then $Z$ is good, with $\overline{\gamma}$ as the witness. This completes the proof. $\hfill\blacktriangleleft$

3.1 Proposed Directions

Finally, we pose the question to extend the set of good $Z$ s.

Open Problem 1.

Find witnesses to extend the set of good $Z$ s.

For example, can one find feasible solutions to prove that any $Z$ with $\{-1,0,1\}$ as its range is good?

Open Problem 2.

Prove that any $Z:\{0,1\}^{n}\to\{-1,0,1\}$ is good.

Such statements will complement Theorem 11, as they will prove lower bounds on the values of $Z$ . We believe that finding more structure in $\mathop{{nullspace}}(M(n,d))$ will help toward these problems. To that effect, we present a simple construction for vectors in $\mathop{{nullspace}}(M(n,d))$ , which we could not find in current literature.

Construction 3.

Fix some $n\in\mathbb{N}$ , $d\in\mathbb{N}$ such that $d<\left\lfloor\frac{n}{2}\right\rfloor$ , and $k\in\mathbb{N}$ such that $d<k<n-d$ . Construct a vector $\gamma\in\mathbb{R}^{2^{n}}$ , indexed by $2^{[n]}$ , as follows:

If the indexing set $T$ has size $\lvert T\rvert\neq k$ , then set $\gamma_{T}=0$ . Otherwise, for each $i\in[d+1]$ , check whether $\lvert T\cap\{i,d+1+i\}\rvert=1$ . If the check above fails for some $i\in[d+1]$ , set $\gamma_{T}=0$ .

Otherwise, $T$ intersects exactly once with each pair $\{i,d+1+i\}$ . Then, set $\gamma_{T}=(-1)^{\lvert T\cap[d+1]\rvert}$ .

Output $\gamma$ .

We claim that the construction above produces a vector $\gamma\in\mathop{{nullspace}}(M(n,d))$ . The proof follows by a simple argument, which we do not present.

Lemma 13.

For any $n\in\mathbb{N},d\in\mathbb{N}$ and $k\in\mathbb{N}$ , such that $d<k<n-d$ , Construction 3 produces a vector $\gamma\in\mathop{{nullspace}}(M(n,d))$ .

Intuitively speaking, the construction above produces a vector with balanced $-1$ and $1$ entries on the given Hamming layer. Hence, it may help with $Z$ s that are highly unbalanced along the entries of this vector. We leave it open to rule out more $Z$ s based on this vector.

Open Problem 3.

Use the vector from Construction 3 to extend the set of good $Z$ s.

4 Lower Bounds for AND

In this section, we prove a lower bound for torus polynomials approximating $\and$ . We restate the result below.

Theorem 6. [Restated, see original statement.]

Any torus polynomial, that $\varepsilon$ -approximates $\and$ , must have degree $\Omega\left(\log\left(\frac{1}{\varepsilon}\right)\right)$ .

We plan to use Theorem 8 to prove this result. In this task, the main challenge is that there are infinitely many choices for $Z$ , and we need to find a feasible solution $\gamma$ for each choice. To make this task easier, we find a vector $\gamma\in\mathop{{nullspace}}(M(n,d))$ with integer entries and small $\ell^{1}$ -norm. This vector will serve as a feasible solution for any $Z$ , if it satisfies the conditions that we detail in the next statement.

Lemma 14.

Fix a Boolean function $f:\{0,1\}^{n}\to\{0,1\}$ and some $d\in[n-1]$ . Consider a vector $\gamma\in\mathop{{nullspace}}(M(n,d))$ with integer entries, i.e. $\gamma\in\mathbb{Z}^{2^{n}}$ , such that $\langle f,\gamma\rangle$ is an odd integer. Then, for any $Z:\{0,1\}^{n}\to\mathbb{Z}$ and $\varepsilon<\frac{1}{2\lVert\gamma\rVert_{1}}$ , the following holds:

\left\lvert\left\langle Z+\frac{f}{2},\gamma\right\rangle\right\rvert>% \varepsilon\lVert\gamma\rVert_{1}

Proof.

Let $\langle f,\gamma\rangle=2z+1$ for some integer $z\in\mathbb{Z}$ . Then, $\left\langle\frac{f}{2},\gamma\right\rangle=z+\frac{1}{2}$ . Fix a function $Z:\{0,1\}^{n}\to\mathbb{Z}$ . Then, $\left\langle Z,\gamma\right\rangle=z^{\prime}$ for some integer $z^{\prime}\in\mathbb{Z}$ . Hence, $\left\langle Z+\frac{f}{2},\gamma\right\rangle=z^{\prime}+z+\frac{1}{2}$ . Consider the following two cases:

$\blacksquare$

$z+z^{\prime}\geq 0$ . In this case, $\left\langle Z+\frac{f}{2},\gamma\right\rangle\geq\frac{1}{2}$ .
$\blacksquare$

$z+z^{\prime}\leq-1$ . In this case, $\left\langle Z+\frac{f}{2},\gamma\right\rangle\leq-\frac{1}{2}$ .

In both the cases, we observe that $\left\lvert\left\langle Z+\frac{f}{2},\gamma\right\rangle\right\rvert\geq\frac% {1}{2}$ . Note that by the choice of $\varepsilon<\frac{1}{2\lVert\gamma\rVert_{1}}$ , we have $\varepsilon\lVert\gamma\rVert_{1}<\frac{1}{2}$ . This completes the proof. $\hfill\blacktriangleleft$

To use the preceding statement for $f=\and_{n}$ , we proceed as follows. For a vector $\gamma\in\mathop{{nullspace}}(M)$ , its inner product with $\and_{n}$ is $\langle\gamma,\and_{n}\rangle=\gamma_{[n]}$ . Hence, we need a vector $\gamma\in\mathop{{nullspace}}(M)\cap\mathbb{Z}^{2^{n}}$ , such that $\gamma_{[n]}$ is odd and $\lVert\gamma\rVert_{1}$ is not too large. We find this vector in a basis for $\mathop{{nullspace}}(M)$ , we will find the basis useful later, such that each vector in that basis is integral and has a small enough $\ell^{1}$ -norm. One such vector $\overline{\gamma}$ in this basis will have $\left\lvert\overline{\gamma}_{[n]}\right\rvert=1$ . We present the construction below.

Construction 4.

Construct a matrix $B$ as follows.

Input:: $n,d\in[n-1]$ .
Output:: A matrix $B\in\mathcal{M}_{2^{n}\times\binom{n}{>d}}(\mathbb{R})$ .
Construction:: For any set $S\subseteq[n]$ with $\lvert S\rvert\geq d+1$ , consider its elements $(s_{0},s_{1},\ldots,s_{\lvert S\rvert-1})$ in the increasing order $s_{0}<s_{1}<\ldots<s_{\lvert S\rvert-1}$ . Denote $S[>d]=\{s_{d+1},\ldots,s_{\lvert S\rvert-1}\}$ as the set remaining after ignoring the first $d$ elements.

Now, create a matrix $B$ , of size $2^{n}\times\binom{n}{>d}$ , and index its rows by elements of $2^{[n]}$ and columns by elements of $\binom{[n]}{>d}$ . For $1\leq i\leq 2^{n}$ and $1\leq j\leq\binom{n}{>d}$ , set the corresponding entry of $B$ as $B_{i,j}=(-1)^{\lvert S_{i}\rvert+\lvert S_{j}\rvert}\cdot 1_{S_{i}\subseteq S_% {j}}\cdot 1_{S_{j}[>d]\subseteq S_{i}}$ . Here, $S_{i}$ and $S_{j}$ denote the sets indexing the $i$ ^th row and the $j$ ^th column of $B$ , respectively.

Output $B$ .

We claim that this construction produces a basis for $\mathop{{nullspace}}(M(n,d))$ . A routine calculation proves the correctness of the construction, which we omit here (refer to the full version for a proof).

Claim 15.

Construction 4, on input $n,d\in[n-1]$ , outputs a basis for $\mathop{{nullspace}}(M(n,d))$ .

We use this basis to prove Theorem 6 as follows.

Proof of Theorem 6.

First, construct $B$ using Construction 4, with $n$ and $d$ as the inputs to the construction. Now, denote by $\overline{\gamma}$ the column of $B$ indexed by $[n]$ . Clearly, $\left\lvert\overline{\gamma}_{[n]}\right\rvert=1$ , hence, $\langle\and,\overline{\gamma}\rangle$ is an odd integer. Moreover, $\lVert\overline{\gamma}\rVert_{1}=2^{d+1}$ . Therefore, if we apply Lemma 14, we get the following lower bound for $\varepsilon<\frac{1}{2\cdot 2^{d+1}}$ : any torus polynomial that $\varepsilon$ -approximates the $\and$ function must have degree more than $d$ . This completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 16.

Consider the probabilistic polynomial that approximates $\and$ over $\mathbb{F}_{2}$ with probability $\varepsilon$ , from [23], and combine it with [4, Lemma 14]. Then, one gets the following upper bound on $\overline{{\mathop{{\deg}}}}_{\varepsilon}(\and)$ .

Lemma 17 ([4, 23]).

For any $\varepsilon>0$ , $\overline{{\mathop{{\deg}}}}_{\varepsilon}(\and)\leq\log^{2}\left(\frac{n}{% \varepsilon}\right)$ .

Hence, the lower bound we have proved in Theorem 6 is only quadratically away from the upper bound for any $\varepsilon=\frac{1}{n^{\Omega(1)}}$ .

Although we had infinitely many linear programs to work with, we have only used one vector for proving their feasibility. One could use multiple vectors in $\mathop{{nullspace}}(M(n,d))$ , such that for each dual corresponding to $Z\in\mathbb{Z}^{2^{n}}$ , one of these vectors is a feasible solution. By using multiple vectors, we believe that one can get stronger degree lower bounds, bringing it closer to the upper bound. We leave this task as an open problem.

Open Problem 4.

Bridge the gap between the lower and upper bound for the $\and$ function.

4.1 The Very Small Error Case

The literature on polynomial approximations usually focuses on inverse-polynomial error regime. We study the case where the error is very small, as it allows us to partially answer a question posed in [4, Problem 6]. In [4, Problem 6], the authors ask about the relationship between $\overline{{\mathop{{\deg}}}}_{\frac{1}{3}}(f)$ and $\overline{{\mathop{{\deg}}}}_{\varepsilon}(f)$ . In general, one can ask if there is an error-reduction procedure for torus polynomials. This procedure should take as input $\varepsilon,\varepsilon^{\prime}<\varepsilon,\overline{{\mathop{{\deg}}}}_{% \varepsilon}(f)$ , and output an estimate for $\overline{{\mathop{{\deg}}}}_{\varepsilon^{\prime}}(f)$ . Ideally, the output should not depend on $f$ , and the estimate should be reasonably close to optimal.

In what follows, we prove that torus polynomials require the same degree to approximate $\and$ and $\mathsf{{MAJORITY}}$ when the error is very small. Now, if we assume Conjecture 5, then the degree required to $\frac{1}{20n}$ -approximate $\and$ is much smaller than the degree required for $\mathsf{{MAJORITY}}$ . Hence, any error-reduction procedure as described above will produce a suboptimal output if it does not depend on the function being approximated, conditionally answering [4, Problem 6] for the error-regime $\varepsilon<\frac{1}{2^{n+1}}$ . Formally, we prove the following result.

Theorem 18.

Depending on the value of $\varepsilon$ , the following cases hold.

$\blacksquare$

If $\varepsilon<\frac{1}{2^{n+1}}$ , then the following holds for $f=\mathsf{{MAJORITY}}$ as well as $f=\and$ , and infinitely many $n$ . Any torus polynomial that $\varepsilon$ -approximates $f$ has degree $n$ .
$\blacksquare$

If $\varepsilon\geq\frac{1}{2^{n+1}}$ , then the following holds for any Boolean function $f:\{0,1\}^{n}\to\{0,1\}$ . There exists a torus polynomial $P$ of degree at most $n-1$ approximating $f$ within an error of $\varepsilon$ . Moreover, if $f$ is symmetric, then we can take $P$ to be symmetric as well.

We do not prove the statement here (refer to the full version for a proof), as it is a special case of the proof of Theorem 6. The upper bound above only states the existence of torus polynomials approximating Boolean functions for a tiny error. We leave it as an open problem to explicitly construct them.

Open Problem 5.

For $\varepsilon=\frac{1}{2^{n+1}}$ and a given function $f:\{0,1\}^{n}\to\{0,1\}$ , construct a torus polynomial of degree at most $n-1$ that $\varepsilon$ -approximates $f$ .

5 Lower Bounds for the Symmetric Case

In this section, we prove lower bounds against symmetric torus polynomials approximating symmetric functions. To describe the general method, we proceed along the lines of the proof for Theorem 8, with two crucial modifications. The polynomial is symmetric if each monomial of the same degree has the same coefficient, which reduces the number of variables to $d+1$ . Similarly, as the function is symmetric, the number of constraints reduces to $n+1$ . To describe the much shorter linear program we obtain, we first construct the following matrix.

Construction 5.

Define the matrix $\widehat{{M}}(n,d)$ of size $(d+1)\times(n+1)$ . For $0\leq j\leq d,0\leq i\leq n$ , the corresponding entry is $\widehat{{M}}_{j,i}=\binom{i}{j}$ .

Now, the analogue of Theorem 8 for symmetric torus polynomials is as follows. Note that we define symmetric functions with $[n]^{*}$ as the domain, such that $f(i)$ is the output when the input has Hamming weight $i$ .

Theorem 19.

The following statements are equivalent for any $n, d$ , $\varepsilon<\frac{1}{10}$ , and any symmetric function $f:[n]^{*}\to\{0,1\}$ .

$\blacksquare$

Any symmetric torus polynomial that $\varepsilon$ -approximates $f$ has degree more than $d$ .
$\blacksquare$

For any function $Z:[n]^{*}\to\mathbb{Z}$ , there exists a vector $\psi\in\mathop{{nullspace}}(\widehat{{M}}(n,d))$ such that:

$\left\lvert\left\langle Z+\frac{f}{2},\psi\right\rangle\right\rvert>% \varepsilon\lVert\psi\rVert_{1}$

The proof of this statement is very similar to the proof of Theorem 8, which we skip. The challenge here is also similar, having to deal with infinitely many linear programs, and proving that they are all feasible. We proceed similar to the previous section, by choosing a short enough $\psi$ with integer entries, which gives us the following analogue of Lemma 14.

Lemma 20.

Fix a symmetric Boolean function $f:[n]^{*}\to\{0,1\}$ and some $d\in[n]^{*}$ . Consider a vector $\psi\in\mathop{{nullspace}}(\widehat{{M}}(n,d))$ with integer entries, i.e. $\psi\in\mathbb{Z}^{n+1}$ , such that $\langle f,\psi\rangle$ is an odd integer. Then, for any $Z:[n]^{*}\to\mathbb{Z}$ and $\varepsilon<\frac{1}{2\lVert\psi\rVert_{1}}$ , the following holds:

\left\lvert\left\langle Z+\frac{f}{2},\psi\right\rangle\right\rvert>% \varepsilon\lVert\psi\rVert_{1}

Now, we recall the statement of our main lower bound against symmetric torus polynomial approximations.

Theorem 7. [Restated, see original statement.]

Any symmetric torus polynomial, that $\frac{1}{20n}$ -approximates $\and$ , must have degree $\Omega\left(\sqrt{\frac{n}{\log(n)}}\right)$ .

Proof.

To prove this statement, we claim that for any $d\leq O\left(\sqrt{\frac{n}{\log(n)}}\right)$ , $\mathop{{nullspace}}(\widehat{{M}}(n,d))$ contains a vector $\overline{\psi}$ with $\ell^{\infty}$ -norm $1$ . Moreover, the last entry of $\overline{\psi}$ is $\overline{\psi}_{n}=1$ . Hence, its inner product with the $\and$ function is $\langle\and,\overline{\psi}\rangle=1$ , which is an odd integer. We state the claim formally below.

Claim 21.

For some universal constant $c$ , consider any large enough $n\in\mathbb{N}$ and $d\leq\sqrt{\frac{n}{c\log(n)}}$ . Then, $\mathop{{nullspace}}(M(n,d))$ contains a vector $\overline{\psi}$ with $\lVert\overline{\psi}\rVert_{\infty}=1$ and $\overline{\psi}_{n}=1$ .

Assume, for now, that the claim is true. Then, we have $\langle\and,\overline{\psi}\rangle=1$ . Further, we get $\lVert\overline{\psi}\rVert_{1}\leq(n+1)\lVert\overline{\psi}\rVert_{\infty}% \leq n+1$ . Finally, we use Lemma 20, using $\overline{\psi}$ , which we can apply for any $\varepsilon\leq\frac{1}{2\lVert\overline{\psi}\rVert_{1}}\leq\frac{1}{2(n+1)}$ . Note that our choice of $\varepsilon=\frac{1}{20n}$ satisfies this inequality for large enough $n$ . This completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 22.

Buhrman, Cleve, de Wolf and Zalka [6] proved an upper bound of $O\left(\sqrt{n\log\left(\frac{1}{\varepsilon}\right)}\right)$ on the degree of a real polynomial approximating the $\and$ function within an error of $\varepsilon$ . Note that we can consider this real polynomial, after symmetrizing, as a symmetric torus polynomial approximating the $\and$ function within an error of $\varepsilon$ . For $\varepsilon=\frac{1}{O(n)}$ , this gives an upper bound of $O(\sqrt{n\log(n)})$ on the degree. Hence, the lower bound of $\Omega\left(\sqrt{\frac{n}{\log(n)}}\right)$ we have proved above is tight within logarithmic factors in $n$ .

We also get a separation between symmetric torus polynomials and asymmetric torus polynomials as a corollary of Theorem 7.

Corollary 23.

Symmetric torus polynomials are weaker than their asymmetric counterparts.

Proof.

We compare the symmetric torus polynomial lower bound with the upper bound from Lemma 17. Using Lemma 17, we get $\overline{{\mathop{{\deg}}}}_{\frac{1}{20n}}(\and)\leq\log^{2}(n)$ . On the other hand, symmetric torus polynomials require much higher degree to $\frac{1}{20n}$ -approximate $\and$ . This proves the separation of their power. $\hfill\blacktriangleleft$

We complete the remaining part of the proof for Theorem 7, which is to prove Claim 21. For this purpose, we will need the following statement from [5].

Theorem 24 ([5]).

Consider a full-rank integer matrix $B$ of size $n\times m$ , with $n>m$ . Then, $\mathcal{L}(B)=B\mathbb{Z}^{m}$ contains a non-zero vector $\mathbf{v}\in\mathbb{Z}^{n}$ with its $\ell^{\infty}$ -norm bounded by:

\lVert\mathbf{v}\rVert_{\infty}\leq\left(\frac{\sqrt{\det(B^{T}B)}}{D}\right)^% {\frac{1}{n-m}}

Here, $D$ is the GCD of all $m\times m$ minors of $B$ .

To prove Claim 21 using Theorem 24, we first describe a basis for $\mathop{{nullspace}}(\widehat{{M}}(n,d))$ . We state the construction without proof, omitting tedious calculations.

Lemma 25.

For $n\in\mathbb{N}$ , and $d\in[n-1]^{*}$ , construct a matrix $\widehat{{B}}(n,d)$ , of size $(n+1)\times(n-d)$ . Keep the following entry for $i\in[n]^{*}$ and $j\in[n-d-1]^{*}$ : $\widehat{{B}}(n,d)_{i,k}=(-1)^{i-k}\binom{d+1}{i-k}$ .

Then, the columns of $\widehat{{B}}(n,d)$ form a basis for $\widehat{{M}}(n,d)$ .

Now, to apply Theorem 24, we need to estimate $\det(\widehat{{B}}(n,d)^{T}\widehat{{B}}(n,d))$ . We state the result below without proof, omitting tedious calculations (refer to the full version for a proof).

Lemma 26.

There exists a universal constant $c$ such that $\det({\widehat{{B}}(n,d)}^{T}\widehat{{B}}(n,d))\leq 2^{cd^{2}\log(n)}$ .

Finally, we need the following statement to find a vector $\psi$ with an odd entry at the desired place. Informally speaking, consider a vector $\psi$ such that $\psi_{n}=0$ . Then, we note that $\widehat{{B}}$ is a column-circulant matrix, with $0$ s beyond the two main diagonals. Hence, we can shift $\psi$ to obtain $\overline{\psi}^{\prime}$ such that $\overline{\psi}^{\prime}_{n}$ contains the last non-zero entry of $\psi$ . We formalize this in the statement below, stated without proof.

Lemma 27.

Consider a vector $\psi\in\mathop{{nullspace}}(\widehat{{M}}(n,d))$ such that the maximum index $i$ where $\psi_{i}\neq 0$ is $i_{0}$ . Define the following vector $\psi^{\prime}$ :

\psi^{\prime}_{i}=\begin{cases}\psi_{i+i_{0}-n}&n-i_{0}\leq i\leq n\\ 0&0\leq i<n-i_{0}\end{cases}

Then, $\psi^{\prime}\in\mathop{{nullspace}}(\widehat{{M}}(n,d))$ .

Now, we are ready to prove Claim 21, as follows.

Proof of Claim 21.

First, choose any $d\leq\sqrt{\frac{n}{c\log(n)}}$ . Then, apply Theorem 24 for $\mathop{{nullspace}}(\widehat{{M}}(n,d))$ with $\widehat{{B}}(n,d)$ as its basis. Note that $\widehat{{B}}(n,d)$ contains a minor, of size $(n-d)\times(n-d)$ , with value $1$ . Hence, we get $D=1$ when we apply Theorem 24. Therefore, there exists a non-zero vector $\overline{\psi}\in\mathop{{nullspace}}(\widehat{{M}})\cap\mathbb{Z}^{n+1}$ with $\lVert\overline{\psi}\rVert_{\infty}\leq 2^{c\frac{n}{c\log(n)}\log(n)\frac{1}% {2(n-d)}}\leq\sqrt{2}$ . As $\lVert\overline{\psi}\rVert_{\infty}$ must be a positive integer, and $\sqrt{2}<2$ , this shows that $\lVert\overline{\psi}\rVert_{\infty}=1$ .

Now, if $\overline{\psi}_{n}=\pm 1$ , then, either $\overline{\psi}$ or $-\overline{\psi}$ satisfies the claimed conditions. Otherwise, if $\overline{\psi}_{n}=0$ , use Lemma 27 to obtain $\overline{\psi^{\prime}}$ from $\overline{\psi}$ . Note that $\lVert\overline{\psi^{\prime}}\rVert_{1}=\lVert\overline{\psi}\rVert_{1}\leq n+1$ , and $\lvert\overline{\psi^{\prime}}_{n}\rvert=1$ . Hence, we get the desired lower bound using $\psi^{\prime}$ . This completes the proof of the claim. $\hfill\vartriangleleft$

5.1 Error-Degree Trade-off

The lower bound described in Theorem 7 applies to a particular error. It is natural to attempt to prove a stronger lower bound for a tighter error. Indeed, we are able to prove stronger lower bounds for tighter errors, but for $\mathsf{{MAJORITY}}$ . This significantly strengthens the lower bound from [4, Corollary 23]. Following is the statement of the lower bound.

Theorem 28.

Fix $r\in\mathbb{R}$ , $r\geq 0$ . For any $\varepsilon\leq 2^{-\Omega(\log^{r+1}(n))}$ , any symmetric torus polynomial that $\varepsilon$ -approximates $\mathsf{{MAJORITY}}_{n}$ has degree at least $\Omega\left(\sqrt{n\log^{r}(n)}\right)$ .

To prove this statement, we plan to use Minkowski’s Theorem on the length of shortest vectors in a lattice. Following is the version we need.

Lemma 29 (Minkowski’s Theorem [19]).

Consider a full-rank integer matrix $B$ of size $n\times m$ , with $n>m$ . Then, the lattice $\mathcal{L}(B)=B\mathbb{Z}^{m}$ contains a vector $\mathbf{v}\neq 0$ with

\lVert\mathbf{v}\rVert_{1}\leq\sqrt{mn}\mathop{det}(B^{T}B)^{\frac{1}{2n}}

We plan to produce short vectors using Minkowski’s Theorem, and then invoke Lemma 20 to argue the lower bound. Toward this, we need to argue that $\langle\mathsf{{MAJORITY}},\overline{\psi}\rangle$ should be odd for a short vector $\overline{\psi}$ which, unfortunately, we could not prove. We prove the lower bound indirectly, by looking at a wider class of symmetric functions. The $\Delta_{w}$ function is defined as follows: $\Delta_{w}(x)=1$ if and only if $\lvert x\rvert=w$ . We obtain the following lower bound for these functions.

Lemma 30.

For any large enough $n\in\mathbb{N}$ , there exists a $w\in[n]^{*}$ , such that the following holds:

Any symmetric torus polynomial that $\varepsilon$ -approximates the $\Delta_{w}$ function over $n$ variables, for $\varepsilon\leq 2^{-\Omega(\log^{r+1}(n))}$ , must have degree $\Omega\left(\sqrt{n\log^{r}(n)}\right)$ .

Proof.

We start by appealing to Minkowski’s theorem (Lemma 29).

Say $d=o\left(\sqrt{n\log^{r}(n)}\right)$ for some $r\geq 0$ , and denote $\widehat{{M}}=\widehat{{M}}(n,d)$ . We use Lemma 26, together with Minkowski’s theorem, to get that there exists a non-zero vector $\overline{\psi}\in\mathop{{nullspace}}(\widehat{{M}})\cap\mathbb{Z}^{n+1}$ with $\lVert\overline{\psi}\rVert_{1}\leq n2^{o\left(\log^{r+1}(n)\right)}$ . We want to choose a $w$ , and prove the lower bound with respect to that $\Delta_{w}$ . Hence, we need to find a $w$ such that $\langle\overline{\psi},\Delta_{w}\rangle$ is odd.

Consider a non-zero vector $\overline{\psi}\in\mathop{{nullspace}}(\widehat{{M}})\cap\mathbb{Z}^{n+1}$ with the smallest $\ell^{1}$ -norm. At least one of the entries of $\overline{\psi}$ must be odd. Otherwise, if they are all even, then $\overline{\psi}/2$ has strictly smaller $\ell^{1}$ -norm. The containment $\overline{\psi}/2\in\mathop{{nullspace}}(\widehat{{M}})\cap\mathbb{Z}^{n+1}$ follows, because $\mathop{{nullspace}}(\widehat{{M}})$ is a vector space, and $\overline{\psi}/2$ has integral entries. This is a contradiction.

This still does not tell us which entry of $\overline{\psi}$ will be odd. Hence, it is still not clear which $\Delta_{w}$ we should choose. Note that we have to choose $w$ to write the family of linear programs, all of them must use the same function $f=\Delta_{w}$ . To make our life easy, we turn the problem over its head.

We notice that we just need to choose $w$ independent of $Z$ , but it can depend on $n, d$ . Hence, as the vector $\overline{\psi}$ with the smallest $\ell^{1}$ -norm depends only on $n, d$ , we can choose $w$ based on $\overline{\psi}$ . This is exactly what we do, we choose $w$ such that $\overline{\psi}_{w}$ is odd. Note that at least one such $w$ must exist, we pick one of them arbitrarily. This completes the proof of the statement. $\hfill\blacktriangleleft$

Now, we apply a trick employed in the proof of [4, Corollary 23]. We describe it below without proof, as it is very similar to [4, Lemma 22].

Lemma 31.

For any $r\geq 0$ , $\varepsilon\leq 2^{-\Omega\left(\log^{r+1}(n)\right)}$ , and large enough $n$ , the following holds: If there exists a symmetric torus polynomial of degree $o\left(\sqrt{n\log^{r}(n)}\right)$ that $\varepsilon$ -approximates $\mathsf{{MAJORITY}}$ , then for any $w\in[n]^{*}$ , there exists a symmetric torus polynomial of degree $o\left(\sqrt{n\log^{r}(n)}\right)$ that $\varepsilon$ -approximates $\Delta_{w}$ .

Now, we can finish the proof of Theorem 28 as follows.

Proof of Theorem 28.

For some $r\in\mathbb{R},r\geq 0$ , consider $\varepsilon=2^{-\Omega\left(\log^{r+1}(n)\right)}$ . Assume that there exists a symmetric torus polynomial that $\varepsilon$ -approximates $\mathsf{{MAJORITY}}$ with degree $d=o\left(\sqrt{n\log^{r}(n)}\right)$ . Then, for each $w\in[n]^{*}$ , there exists a symmetric torus polynomial that $\varepsilon$ -approximates $\Delta_{w}$ . Moreover, each of these polynomials have degree $d=o\left(\sqrt{n\log^{r}(n)}\right)$ . This contradicts Lemma 30, completing the proof of the theorem. $\hfill\blacktriangleleft$

To us, it is a bit unsatisfactory that we cannot prove this lower bound for $\and$ . Note that the main hurdle for us is not knowing which entry of $\overline{\psi}$ is odd. If we can prove that $\overline{\psi}_{n}$ is odd, then the lower bound goes through for $\and$ . Hence, we state a conjecture that will prove the error-degree trade-off for $\and$ as well. In fact, we believe that the following holds, which is stronger than what we need.

Conjecture 32.

For any $n\in\mathbb{N},0\leq d<n$ , there is a vector $\overline{\psi}\in\mathop{{nullspace}}(\widehat{{M}}(n,d))\cap Z^{n+1}$ with the smallest $\ell^{1}$ -norm and $\overline{\psi}_{n}=1$ .

References

[1] Scott Aaronson. The Polynomial Method in Quantum and Classical Computing. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, October 25-28, 2008, page 3. IEEE, IEEE Computer Society, 2008. doi:10.1109/FOCS.2008.91.
[2] David A. Mix Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. J. Comput. Syst. Sci., 38(1):150–164, 1989. doi:10.1016/0022-0000(89)90037-8.
[3] Richard Beigel and Jun Tarui. On ACC. Comput. Complex., 4:350–366, 1994. doi:10.1007/BF01263423.
[4] Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, and Sankeerth Rao. Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 13:1–13:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ITCS.2019.13.
[5] Enrico Bombieri and Jeffrey D. Vaaler. On Siegel’s lemma. Inventiones mathematicae, 73:11–32, 1983. URL: https://api.semanticscholar.org/CorpusID:121274024.
[6] Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for Small-Error and Zero-Error Quantum Algorithms. In 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999, pages 358–368. IEEE, IEEE Computer Society, 1999. doi:10.1109/SFFCS.1999.814607.
[7] Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput., 243:2–25, 2015. doi:10.1016/j.ic.2014.12.003.
[8] Mark Bun and Justin Thaler. Approximate Degree in Classical and Quantum Computing. Found. Trends Theor. Comput. Sci., 15(3-4):229–423, 2022. doi:10.1561/0400000107.
[9] Lijie Chen. Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1281–1304. IEEE, IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00079.
[10] Lijie Chen. New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 34:1–34:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ITCS.2023.34.
[11] Lijie Chen, Zhenjian Lu, Xin Lyu, and Igor C. Oliveira. Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 51:1–51:20. Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.51.
[12] Lijie Chen, Xin Lyu, and R. Ryan Williams. Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1–12. IEEE, IEEE, 2020. doi:10.1109/FOCS46700.2020.00009.
[13] Ruiwen Chen, Igor C. Oliveira, and Rahul Santhanam. An Average-Case Lower Bound Against ACC⁰. In Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 317–330. Springer, Springer, 2018. doi:10.1007/978-3-319-77404-6_24.
[14] Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, and Jacobo Torán. The Power of the Middle Bit of a #P Function. J. Comput. Syst. Sci., 50(3):456–467, 1995. doi:10.1006/jcss.1995.1036.
[15] Johan Håstad. Almost Optimal Lower Bounds for Small Depth Circuits. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6–20. ACM, 1986. doi:10.1145/12130.12132.
[16] Johan Håstad and Mikael Goldmann. On the Power of Small-Depth Threshold Circuits. Comput. Complex., 1(2):113–129, 1991. doi:10.1007/BF01272517.
[17] Vaibhav Krishan. Upper Bound for Torus Polynomials. In Rahul Santhanam and Daniil Musatov, editors, Computer Science - Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28 - July 2, 2021, Proceedings, volume 12730 of Lecture Notes in Computer Science, pages 257–263. Springer, Springer, 2021. doi:10.1007/978-3-030-79416-3_15.
[18] Vaibhav Krishan and Sundar Vishwanathan. Degree Lower Bounds for Torus Polynomials and MAJORITY vs ACC⁰. Electron. Colloquium Comput. Complex., TR24-074, 2024. URL: https://eccc.weizmann.ac.il/report/2024/074/#revision1.
[19] Hermann Minkowski. Geometrie der zahlen. BG Teubner, 1910.
[20] Cody D. Murray and R. Ryan Williams. Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma. SIAM J. Comput., 49(5):STOC18–300, 2020. doi:10.1137/18M1195887.
[21] Noam Nisan and Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Comput. Complex., 4:301–313, 1994. doi:10.1007/BF01263419.
[22] Alexander A. Razborov and Avi Wigderson. $n^{\Omega(logn)}$ Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom. Inf. Process. Lett., 45(6):303–307, 1993. doi:10.1016/0020-0190(93)90041-7.
[23] Alexander Alexandrovich Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Matematicheskie Zametki, 41(4):598–607, 1987.
[24] Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77–82. ACM, 1987. doi:10.1145/28395.28404.
[25] Ryan Williams. Nonuniform ACC Circuit Lower Bounds. J. ACM, 61(1):2:1–2:32, 2014. doi:10.1145/2559903.
[26] Andrew Chi-Chih Yao. On ACC and Threshold Circuits. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, pages 619–627. IEEE, IEEE Computer Society, 1990. doi:10.1109/FSCS.1990.89583.

[bib.bib1] [1] Scott Aaronson. The Polynomial Method in Quantum and Classical Computing. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, Philadelphia, PA, USA, October 25-28, 2008, page 3. IEEE, IEEE Computer Society, 2008. doi:10.1109/FOCS.2008.91.

[bib.bib2] [2] David A. Mix Barrington. Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. J. Comput. Syst. Sci., 38(1):150–164, 1989. doi:10.1016/0022-0000(89)90037-8.

[bib.bib3] [3] Richard Beigel and Jun Tarui. On ACC. Comput. Complex., 4:350–366, 1994. doi:10.1007/BF01263423.

[bib.bib4] [4] Abhishek Bhrushundi, Kaave Hosseini, Shachar Lovett, and Sankeerth Rao. Torus Polynomials: An Algebraic Approach to ACC Lower Bounds. In Avrim Blum, editor, 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 13:1–13:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2019. doi:10.4230/LIPIcs.ITCS.2019.13.

[bib.bib5] [5] Enrico Bombieri and Jeffrey D. Vaaler. On Siegel’s lemma. Inventiones mathematicae, 73:11–32, 1983. URL: https://api.semanticscholar.org/CorpusID:121274024.

[bib.bib6] [6] Harry Buhrman, Richard Cleve, Ronald de Wolf, and Christof Zalka. Bounds for Small-Error and Zero-Error Quantum Algorithms. In 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999, pages 358–368. IEEE, IEEE Computer Society, 1999. doi:10.1109/SFFCS.1999.814607.

[bib.bib7] [7] Mark Bun and Justin Thaler. Dual lower bounds for approximate degree and Markov-Bernstein inequalities. Inf. Comput., 243:2–25, 2015. doi:10.1016/j.ic.2014.12.003.

[bib.bib8] [8] Mark Bun and Justin Thaler. Approximate Degree in Classical and Quantum Computing. Found. Trends Theor. Comput. Sci., 15(3-4):229–423, 2022. doi:10.1561/0400000107.

[bib.bib9] [9] Lijie Chen. Non-deterministic Quasi-Polynomial Time is Average-Case Hard for ACC Circuits. In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1281–1304. IEEE, IEEE Computer Society, 2019. doi:10.1109/FOCS.2019.00079.

[bib.bib10] [10] Lijie Chen. New Lower Bounds and Derandomization for ACC, and a Derandomization-Centric View on the Algorithmic Method. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, January 10-13, 2023, MIT, Cambridge, Massachusetts, USA, volume 251 of LIPIcs, pages 34:1–34:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.ITCS.2023.34.

[bib.bib11] [11] Lijie Chen, Zhenjian Lu, Xin Lyu, and Igor C. Oliveira. Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 51:1–51:20. Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.51.

[bib.bib12] [12] Lijie Chen, Xin Lyu, and R. Ryan Williams. Almost-Everywhere Circuit Lower Bounds from Non-Trivial Derandomization. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1–12. IEEE, IEEE, 2020. doi:10.1109/FOCS46700.2020.00009.

[bib.bib13] [13] Ruiwen Chen, Igor C. Oliveira, and Rahul Santhanam. An Average-Case Lower Bound Against ACC⁰. In Michael A. Bender, Martin Farach-Colton, and Miguel A. Mosteiro, editors, LATIN 2018: Theoretical Informatics - 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings, volume 10807 of Lecture Notes in Computer Science, pages 317–330. Springer, Springer, 2018. doi:10.1007/978-3-319-77404-6_24.

[bib.bib14] [14] Frederic Green, Johannes Köbler, Kenneth W. Regan, Thomas Schwentick, and Jacobo Torán. The Power of the Middle Bit of a #P Function. J. Comput. Syst. Sci., 50(3):456–467, 1995. doi:10.1006/jcss.1995.1036.

[bib.bib15] [15] Johan Håstad. Almost Optimal Lower Bounds for Small Depth Circuits. In Juris Hartmanis, editor, Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6–20. ACM, 1986. doi:10.1145/12130.12132.

[bib.bib16] [16] Johan Håstad and Mikael Goldmann. On the Power of Small-Depth Threshold Circuits. Comput. Complex., 1(2):113–129, 1991. doi:10.1007/BF01272517.

[bib.bib17] [17] Vaibhav Krishan. Upper Bound for Torus Polynomials. In Rahul Santhanam and Daniil Musatov, editors, Computer Science - Theory and Applications - 16th International Computer Science Symposium in Russia, CSR 2021, Sochi, Russia, June 28 - July 2, 2021, Proceedings, volume 12730 of Lecture Notes in Computer Science, pages 257–263. Springer, Springer, 2021. doi:10.1007/978-3-030-79416-3_15.

[bib.bib18] [18] Vaibhav Krishan and Sundar Vishwanathan. Degree Lower Bounds for Torus Polynomials and MAJORITY vs ACC⁰. Electron. Colloquium Comput. Complex., TR24-074, 2024. URL: https://eccc.weizmann.ac.il/report/2024/074/#revision1.

[bib.bib19] [19] Hermann Minkowski. Geometrie der zahlen. BG Teubner, 1910.

[bib.bib20] [20] Cody D. Murray and R. Ryan Williams. Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma. SIAM J. Comput., 49(5):STOC18–300, 2020. doi:10.1137/18M1195887.

[bib.bib21] [21] Noam Nisan and Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Comput. Complex., 4:301–313, 1994. doi:10.1007/BF01263419.

[bib.bib22] [22] Alexander A. Razborov and Avi Wigderson. $n^{\Omega(logn)}$ Lower Bounds on the Size of Depth-3 Threshold Circuits with AND Gates at the Bottom. Inf. Process. Lett., 45(6):303–307, 1993. doi:10.1016/0020-0190(93)90041-7.

[bib.bib23] [23] Alexander Alexandrovich Razborov. Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Matematicheskie Zametki, 41(4):598–607, 1987.

[bib.bib24] [24] Roman Smolensky. Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. In Alfred V. Aho, editor, Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pages 77–82. ACM, 1987. doi:10.1145/28395.28404.

[bib.bib25] [25] Ryan Williams. Nonuniform ACC Circuit Lower Bounds. J. ACM, 61(1):2:1–2:32, 2014. doi:10.1145/2559903.

[bib.bib26] [26] Andrew Chi-Chih Yao. On ACC and Threshold Circuits. In 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, USA, October 22-24, 1990, Volume II, pages 619–627. IEEE, IEEE Computer Society, 1990. doi:10.1109/FSCS.1990.89583.

Lower Bounds and Separations for Torus Polynomials

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editor:

Series and Publisher:

1 Introduction

Conjecture 1 (Barrington’s conjecture [2]).

Definition 2 (Torus Polynomial Approximation [4]).

Theorem 3 ([4]).

1.1 Previous Work

Theorem 4 (Corollary 23 of [4]).

Conjecture 5 ([4]).

1.2 Our Results

Theorem 6.

Theorem 7.

Our Method

Organization

2 Preliminaries

2.1 Sets and Boolean Points

2.2 Linear Algebra

2.3 Our Method for Torus Polynomial Lower Bounds

Construction 1.

Theorem 8.

3 Plan for Majority

Lemma 9.

Construction 2.

Lemma 10.

Theorem 11.

Proof.

Theorem 12.

Proof.

3.1 Proposed Directions

Open Problem 1.

Open Problem 2.

Construction 3.

Lemma 13.

Open Problem 3.

4 Lower Bounds for AND

Theorem 6. [Restated, see original statement.]

Lemma 14.

Proof.

Construction 4.

Claim 15.

Proof of Theorem 6.

▶ Remark 16.

Lemma 17 ([4, 23]).

Open Problem 4.

4.1 The Very Small Error Case

Theorem 18.

Open Problem 5.

5 Lower Bounds for the Symmetric Case

Construction 5.

Theorem 19.

Lemma 20.

Theorem 7. [Restated, see original statement.]

Proof.

Claim 21.

▶ Remark 22.

Corollary 23.

Proof.

Theorem 24 ([5]).

Lemma 25.

Lemma 26.

Lemma 27.

Proof of Claim 21.

5.1 Error-Degree Trade-off

Theorem 28.

Lemma 29 (Minkowski’s Theorem [19]).

Lemma 30.

Proof.

Lemma 31.

Proof of Theorem 28.

Conjecture 32.

References

$\blacktriangleright$ Remark 16.

$\blacktriangleright$ Remark 22.