text:
# Toward Attribute Efficient Learning Algorithms

## 1 Introduction

### 1.1 Attribute Efficient Learning

A central goal in machine learning is to design efficient, effective algorithms for learning from small amounts of data. An obstacle to achieving this goal is that learning problems are often characterized by an abundance of irrelevant information. In many learning problems each data point is naturally viewed as a high dimensional vector of attribute values; as a motivating example, in a natural language domain a data point representing a text document may be a vector of word frequencies over a lexicon of 100,000 words (attributes). A newly encountered word in a corpus may typically have a simple definition which uses only a dozen or so words from the entire lexicon. One would like to be able to learn the meaning of such a word using a number of examples which is closer to a dozen (the actual number of relevant attributes) than to 100,000 (the total number of attributes).

Towards this end, an important goal in machine learning theory is to design attribute efficient algorithms for learning various classes of Boolean functions. A class $`𝒞`$ of Boolean functions over $`n`$ variables $`x_1,\mathrm{},x_n`$ is said to be attribute-efficiently learnable if there is a poly$`(n)`$ time algorithm which can learn any function $`fC`$ using a number of examples which is polynomial in the “size” (description length) of the function $`f`$ to be learned, rather than in $`n`$ (the number of features in the domain over which learning takes place). (Note that the running time of the learning algorithm must in general be at least $`n`$ since each example is an $`n`$-bit vector.) Thus an attribute efficient learning algorithm for, say, the class of Boolean conjunctions must be able to learn any Boolean conjunction of $`k`$ literals over $`x_1,\mathrm{},x_n`$ using poly$`(k,\mathrm{log}n)`$ examples, since $`k\mathrm{log}n`$ bits are required to specify such a conjunction.

### 1.2 Decision Lists

A longstanding open problem in machine learning, posed first by Blum in 1990  and again by Valiant in 1998 , is to determine whether or not there exist attribute efficient algorithms for learning decision lists. A decision list is essentially a nested “if-then-else” statement (we give a precise definition in Section 2).

Attribute efficient learning of decision lists is of both theoretical and practical interest. Blum’s motivation for considering the problem came from the infinite attribute model ; in this model there are infinitely many attributes but the concept to be learned depends on only a small number of them, and each example consists of a finite list of active attributes. Blum et al.  showed that for a wide range of concept classes (including decision lists) attribute efficient learnability in the standard $`n`$-attribute model is equivalent to learnability in the infinite attribute model. Since simple classes such as disjunctions and conjunctions are attribute efficiently learnable (and hence learnable in the infinite attribute model), this motivated Blum  to ask whether the richer class of decision lists is thus learnable as well.111 Additional motivation comes from the fact that decision lists have such a simple algorithm in the PAC model. Several researchers have subsequently considered this problem, see e.g. ; we summarize some of this previous work in Section 1.6.

From an applied perspective, Valiant  relates the problem of learning decision lists attribute efficiently to the question “how can human beings learn from small amounts of data in the presence of irrelevant information?” He points out that since decision lists play an important role in various models of cognition, a first step in understanding this phenomenon would be to identify efficient algorithms which learn decision lists from few examples. Due to the lack of progress in developing such algorithms for decision lists, Valiant suggests that models of cognition should perhaps focus on “flatter” classes of functions such as projective DNF .

### 1.3 Parity Functions

Another outstanding challenge in machine learning is to determine whether there exist attribute efficient algorithms for learning parity functions. The parity function on a set of 0/1-valued variables $`x_{i_1},\mathrm{},x_{i_k}`$ is equal to $`x_{i_1}+\mathrm{}+x_{i_k}`$ modulo 2. As with the class of decision lists, a simple PAC learning algorithm is known for the class of parity functions but no attribute efficient PAC learning algorithm is known. Learning parity functions plays an important rule in Fourier learning methods  and is closely related to decoding random linear codes . Both A. Blum  and Y. Mansour  cite attribute efficient learning of parity functions as an important open problem.

### 1.4 Our Results: Decision Lists

We give the first learning algorithm for decision lists that is subexponential in both sample complexity (in the relevant parameters $`k`$ and $`\mathrm{log}n`$) and running time (in the relevant parameter $`k`$). Our results demonstrate for the first time that it is possible to simultaneously avoid the “worst case” in both sample complexity and running time, and thus suggest that it may indeed be possible to learn decision lists attribute efficiently.

Our main learning result for decision lists is:

###### Theorem 1

There is an algorithm for learning decision lists over $`\{0,1\}^n`$ which, when learning a decision list of length $`k`$, has mistake bound222Throughout this section we use “sample complexity” and “mistake bound” interchangeably; as described in Section 2 these notions are essentially identical. $`2^{\stackrel{~}{O}(k^{1/3})}\mathrm{log}n`$ and runs in time $`n^{\stackrel{~}{O}(k^{1/3})}`$.

We prove Theorem 1 in two parts; first we generalize Littlestone’s well known Winnow algorithm  for learning linear threshold functions to learn polynomial threshold functions. In previous learning results, polynomial threshold functions are learned by applying techniques from linear programming: a Boolean function computed by a polynomial threshold function of degree $`d`$ can be learned in time $`n^{O(d)}`$ by using polynomial time linear programming algorithms such as the Ellipsoid algorithm (see e.g. ). In contrast, we use the Winnow algorithm to learn polynomial threshold functions. Winnow learns using few examples in a small amount of time provided that the degree of the polynomial is low and the integer coefficients of the polynomial are not too large:

###### Theorem 2

Let $`𝒞`$ be a class of Boolean functions over $`\{0,1\}^n`$ with the property that each $`f𝒞`$ has a polynomial threshold function of degree at most $`d`$ and weight at most $`W.`$ Then there is an online learning algorithm for $`𝒞`$ which runs in $`n^d`$ time per example and has mistake bound $`O(W^2d\mathrm{log}n).`$

At this point we have reduced the problem of learning decision lists attribute efficiently to the problem of representing decision lists with polynomial threshold functions of low weight and low degree. To this end we prove

###### Theorem 3

Let $`L`$ be a decision list of length $`k`$. Then $`L`$ is computed by a polynomial threshold function of degree $`\stackrel{~}{O}(k^{1/3})`$ and weight $`2^{\stackrel{~}{O}(k^{1/3})}`$.

Theorem 1 follows directly from Theorems 2 and 3.

Polynomial threshold function constructions have recently been used to obtain the fastest known algorithms for a range of important learning problems such as learning DNF formulas , intersections of halfspaces , and Boolean formulas of superconstant depth . For each of these learning problems the sole goal was to obtain fast learning algorithms, and hence the only parameter of interest in these polynomial threshold function constructions is their degree, since degree bounds translate directly into running time bounds for learning algorithms (see e.g. ). In contrast, for the decision list problem we are interested in both the running time and the number of examples required for learning. Thus we must bound both the degree and the weight (magnitude of integer coefficients) of the polynomial threshold functions which we use.

Our polynomial threshold function construction is essentially optimal in the tradeoff between degree and weight which it achieves. In 1994 Beigel gave a lower bound showing that any degree $`d`$ polynomial threshold function for a particular decision list must have weight $`2^{\mathrm{\Omega }(n/d^2)}`$. For $`d=n^{1/3}`$, Beigel’s lower bound implies that the construction stated in Theorem 3 is essentially optimal. Furthermore, for any decision list $`L`$ of length $`n`$ and any $`dn^{1/3}`$, we will in fact construct polynomial threshold functions of degree $`d`$ and weight $`2^{\stackrel{~}{O}(n/d^2)}`$ computing $`L`$. Beigel’s lower bound thus implies that our degree $`d`$ polynomial threshold functions are of roughly optimal weight for all $`dn^{1/3},`$ and hence strongly suggests that our analysis is the best possible for the algorithm we use.

### 1.5 Our Results: Parity Functions

For parity functions, we give an $`O(n^3)`$ time algorithm which can learn an unknown parity on $`k`$ variables out of $`n`$ using $`O(n^{11/k})`$ examples. For values of $`k=o(\mathrm{log}n)`$ the sample complexity of this algorithm is $`o(n)`$. This is the first algorithm for learning parity on a superconstant number of variables with sublinear sample complexity.

The standard PAC learning algorithm for learning an unknown parity function is based on viewing a set of $`m`$ labelled examples as a system of $`m`$ linear equations modulo 2. Using Gaussian elimination it is possible to solve the system and find a consistent parity function. It can be shown that the solution thus obtained is a “good” hypothesis if its weight (number of nonzero entries) is small relative to $`m`$, the number of examples. However, using Gaussian elimination can result in a solution of weight as large as $`\mathrm{min}(m,n)`$ even if $`k`$ (the number of variables in the target parity) is very small. Thus in order for this approach to give a successful learning algorithm, it is necessary to use $`m=\mathrm{\Omega }(n)`$ examples regardless of the value of $`k`$. In contrast, observe that an attribute efficient algorithm for learning a parity of length $`k`$ should use only poly$`(k,\mathrm{log}n)`$ examples.

Our algorithm works by finding a “low weight” solution to a system of $`m`$ linear equations. We prove that with high probability we can find a solution of weight $`O(n^{11/k})`$ irrespective of $`m`$. Thus by taking $`m`$ to be only slightly larger than $`n^{11/k}`$ we have that our solution is a “good” hypothesis.

### 1.6 Previous Results: Decision Lists

In previous work several algorithms with different performance bounds (in terms of running time and number of examples used) have been given for learning decision lists.

* Rivest  gave the first algorithm for learning decision lists in Valiant’s PAC model of learning from random examples. Littlestone  subsequently gave an analogue of Rivest’s algorithm in the online learning model. The algorithm can learn any decision list of length $`k`$ in $`O(kn^2)`$ time using $`O(kn)`$ examples.
* A brute-force approach to learning decision lists of length $`k`$ is to maintain a collection of all such lists which are consistent with the examples seen so far, and to predict at each stage using majority vote over the surviving hypotheses. This “halving algorithm” (proposed in various forms by Barzdin and Freivald , Mitchell , and Angluin ) can learn decision lists of length $`k`$ using only $`O(k\mathrm{log}n)`$ examples, but the running time is $`n^{O(k)}.`$
* Several researchers  have observed that Littlestone’s well-known Winnow algorithm  can learn decision lists of length $`k`$ from $`2^{O(k)}\mathrm{log}n`$ examples in time $`2^{O(k)}n\mathrm{log}n`$. This follows from the observation that decision lists of length $`k`$ can be viewed as linear threshold functions with integer coefficients of magnitude $`2^{\mathrm{\Theta }(k)}`$. We note that our algorithm in this paper always has improved sample complexity over the basic Winnow algorithm, and for $`k(\mathrm{log}n)^{3/2}`$ our approach improves on the time complexity of Winnow as well.
* Finally, several researchers have considered the special case of learning a decision list of length $`k`$ over $`n`$ variables in which the output bits of the decision list have at most $`D`$ alternations. Valiant  and Nevo and El-Yaniv  have given refined analyses of Winnow’s performance for this special case, and Dhagat and Hellerstein  have also studied this problem. However, for the general case in which $`D`$ can be as large as $`k,`$ the results thus obtained do not improve on the straightforward Winnow analysis described in the previous bullet.

These previous algorithmic results are summarized in Figure 1. We observe that all of these earlier algorithms have an exponential dependence on the relevant parameter(s) ($`k`$ and $`\mathrm{log}n`$ for sample complexity, $`k`$ for running time) for either the running time or the sample complexity.

### 1.7 Previous Results: Parity Functions

Little previous work has been published on learning parity functions attribute efficiently in the PAC model. The standard PAC learning algorithm for parity (based on solving a system of linear equations) is due to Helmbold et al. ; however as described above this algorithm is not attribute efficient since it uses $`\mathrm{\Omega }(n)`$ examples.

Several authors have considered learning parity attribute efficiently in a model where the learner is allowed to make membership queries. Attribute efficient learning is easier in this framework since membership queries can help identify relevant variables. Blum et al.  give a randomized polynomial time membership-query algorithm for learning parity on $`k`$ variables using only $`O(k\mathrm{log}n)`$ examples. These results were later refined by Uehara et al. .

### 1.8 Organization

In Section 2 we give the necessary background on online learning and polynomial threshold functions. In Section 3 we show how known results from learning theory enable us to reduce the decision list learning problem to a problem of finding suitable polynomial threshold function representations of decision lists. In Sections 4.1 and 4.2 we give two different proofs of a weak tradeoff between degree and weight for polynomial threshold function representations of decision lists, and in Section 4.3 we combine these techniques to prove Theorem 3. In Section 5 we show how to apply our techniques to give a tradeoff between sample complexity and running time for learning decision trees. In Section 6 we discuss the connection with Beigel’s ODDMAXBIT lower bound and related issues. In Section 7 we give our new algorithm for learning parity functions, and in Section 8 we suggest directions for future work.

## 2 Preliminaries

Attribute efficient learning has been chiefly studied in the on-line mistake-bound model of concept learning which was introduced in . In this model learning proceeds in a series of trials, where in each trial the learner is given an unlabelled boolean example $`x\{0,1\}^n`$ and must predict the value $`f(x)`$ of the unknown target function $`f.`$ After each prediction the learner is given the true value of $`f(x)`$ and can update its hypothesis before the next trial begins. The mistake bound of a learning algorithm on a target concept $`c`$ is measured by the worst-case number of mistakes that the algorithm makes over all (possibly infinite) sequences of examples, and the mistake bound of a learning algorithm on a concept class (class of Boolean functions) $`C`$ is the worst-case mistake bound across all functions $`fC.`$ The running time of a learning algorithm $`A`$ for a concept class $`C`$ is defined as the product of the mistake bound of $`A`$ on $`C`$ times the maximum running time required by $`A`$ to evaluate its hypothesis and update its hypothesis in any trial.

Our main interests in this paper are the classes of decision lists and parity functions.

A decision list $`L`$ of length $`k`$ over the Boolean variables $`x_1,\mathrm{},x_n`$ is represented by a list of $`k`$ pairs and a bit

$$(\mathrm{}_1,b_1),(\mathrm{}_2,b_2),\mathrm{},(\mathrm{}_k,b_k),b_{k+1}$$

where each $`\mathrm{}_i`$ is a literal and each $`b_i`$ is either $`1`$ or $`1.`$ Given any $`x\{0,1\}^n,`$ the value of $`L(x)`$ is $`b_i`$ if $`i`$ is the smallest index such that $`\mathrm{}_i`$ is made true by $`x`$; if no $`\mathrm{}_i`$ is true then $`L(x)=b_{k+1}.`$

A parity function of length $`k`$ is defined by a set of variables $`S\{x_1,\mathrm{},x_n\}`$ such that $`|S|=k`$. The parity function $`\chi _S(x)`$ takes value $`1`$ on inputs which set an even number of variables in $`S`$ to $`1`$ and takes value $`1`$ on inputs which set an odd number of variables in $`S`$ to $`1.`$

Given a concept class $`C`$ over $`\{0,1\}^n`$ and a Boolean function $`fC,`$ let size$`(f)`$ denote the description length of $`f`$ under some reasonable encoding scheme. (Note that if $`f`$ has $`r`$ relevant variables then size$`(f)`$ will be at least $`r\mathrm{log}n`$ since this many bits are required just to specify which variables are relevant). We say that a learning algorithm $`A`$ for $`C`$ in the mistake-bound model is attribute-efficient if the mistake bound of $`A`$ on any concept $`cC`$ is polynomial in size$`(f).`$ In particular, the description length of a length $`k`$ decision list (parity) is $`O(k\mathrm{log}n)`$, and thus we would ideally like to have an algorithm which learns decision lists (parities) of length $`k`$ with a mistake bound of poly$`(k,\mathrm{log}n)`$ and runs in time poly$`(n).`$

(We note here that attribute efficiency has also been studied in other learning models, namely Valiant’s Probably Approximately Correct (PAC) model of learning from random examples. Standard conversion techniques are known  which can be used to transform any mistake bound algorithm into a PAC learning algorithm. This transformation essentially preserves the running time of the mistake bound algorithm, and the sample size required by the PAC algorithm is essentially the mistake bound. Thus, positive results for mistake bound learning, such as those we give for decision lists in this paper, directly yield corresponding positive results for the PAC model.)

Finally, our results for decision lists are achieved by a careful analysis of polynomial threshold functions. Let $`f`$ be a Boolean function $`f:\{0,1\}^n\{1,1\}`$ and let $`p`$ be a polynomial in $`n`$ variables with integer coefficients. Let $`d`$ denote the degree of $`p`$ and let $`W`$ denote the sum of the absolute values of $`p`$’s integer coefficients. If the sign of $`p(x)`$ equals $`f(x)`$ for every $`x\{0,1\}^n,`$ then we say that $`p`$ is a polynomial threshold function of degree $`d`$ and weight $`W`$ for $`f.`$

## 3 Expanded-Winnow: Learning Polynomial Threshold Functions

Littlestone introduced the online Winnow algorithm in 1988 and showed that it can attribute efficiently learn Boolean conjunctions, disjunctions, and low weight linear threshold functions. Throughout its execution Winnow maintains a linear threshold function as its hypothesis; at the heart of the algorithm is a novel update rule which makes a multiplicative update to each coefficient of the hypothesis (rather than an additive update as in the Perceptron algorithm) each time a mistake is made. Since its introduction Winnow has been intensively studied from both applied and theoretical standpoints (see e.g. ) and multiplicative updates have become widespread in machine learning algorithms.

The following theorem (which, as noted in , is implicit in Littlestone’s analysis in ) gives a mistake bound for Winnow when learning linear threshold functions:

###### Theorem 4

Let $`f(x)`$ be the linear threshold function sign$`(_{i=1}^nw_ix_i\theta )`$ where $`\theta `$ and $`w_1,\mathrm{},w_n`$ are integers. Let $`W=_{i=1}^n|w_i|`$. Then Winnow learns $`f(x)`$ with mistake bound $`O(W^2\mathrm{log}n)`$, and uses $`n`$ time steps per example.

We will use a generalization of the Winnow algorithm, called Expanded-Winnow, to learn polynomial threshold functions of degree at most $`d.`$ Our generalization introduces $`_{i=1}^d\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$ new variables (one for each monomial of degree up to $`d`$) and runs Winnow to learn a linear threshold function over these new variables. More precisely, in each trial we convert the $`n`$-bit received example $`x=(x_1,\mathrm{},x_n)`$ into a $`_{i=1}^d\left(\genfrac{}{}{0pt}{}{n}{d}\right)`$ bit expanded example (where the bits in the expanded example correspond to monomials over $`x_1,\mathrm{},x_n`$), and we give the expanded example to Winnow. Thus the hypothesis which Winnow maintains – a linear threshold function over the space of expanded features – is a polynomial threshold function of degree $`d`$ over the original $`n`$ variables $`x_1,\mathrm{},x_n.`$ Theorem 2, which follows directly from Theorem 4, summarizes the performance of Expanded-Winnow:

Theorem 2 Let $`𝒞`$ be a class of Boolean functions over $`\{0,1\}^n`$ with the property that each $`f𝒞`$ has a polynomial threshold function of degree at most $`d`$ and weight at most $`W.`$ Then Expanded-Winnow algorithm runs in $`n^d`$ time per example and has mistake bound $`O(W^2d\mathrm{log}n)`$ for $`𝒞.`$

Theorem 2 shows that the degree of a polynomial threshold function corresponds to Expanded-Winnow’s running time, and the weight of a polynomial threshold function corresponds to its sample complexity.

## 4 Constructing Polynomial Threshold Functions for Decision Lists

In previous constructions of polynomial threshold functions for computational learning theory applications  the sole goal has been to minimize the degree of the polynomials regardless of the size of the coefficients. As an extreme example, the construction of  of $`\stackrel{~}{O}(n^{1/3})`$ degree polynomial threshold functions for DNF formulae yields polynomials whose coefficients can be doubly exponential in the degree. In contrast, given Theorem 2 we must now construct polynomial threshold functions that have low degree and low weight.

We give two constructions of polynomial threshold functions for decision lists, each of which has relatively low degree and relatively low weight. We then combine these approaches to achieve an optimal construction with improved bounds on both degree and weight.

### 4.1 Outer Construction

Let $`L`$ be a decision list of length $`k`$ over variables $`x_1,\mathrm{},x_k.`$ We first give a simple construction of a degree $`h`$, weight $`\frac{2k}{h}2^{(k/h+h)}`$ polynomial threshold function for $`L`$ which is based on breaking the list $`L`$ into sublists. We call this construction the “outer construction” since we will ultimately combine this construction with a different construction for the “inner” sublists.

We begin by showing that $`L`$ can be expressed as a threshold of modified decision lists which we now define. The set $`_h`$ of modified decision lists is defined as follows: each function in $`_h`$ is a decision list $`(\mathrm{}_1,b_1),(\mathrm{}_2,b_2),\mathrm{},(\mathrm{}_h,b_h),0`$ where each $`\mathrm{}_i`$ is some literal over $`x_1,\mathrm{},x_n`$ and each $`b_i\{1,1\}.`$ Thus the only difference between a modified decision list $`f_h`$ and a normal decision list of length $`h`$ is that the final output value is $`0`$ rather than $`b_{h+1}\{1,+1\}.`$

Without loss of generality we may suppose that the list $`L`$ is $`(x_1,b_1),\mathrm{},(x_k,b_k),b_{k+1}.`$ We break $`L`$ sequentially into $`k/h`$ blocks each of length $`h`$. Let $`f_i_h`$ be the modified decision list which corresponds to the $`i`$-th block of $`L,`$ i.e. $`f_i`$ is the list $`(x_{(i1)h+1},b_{(i1)h+1}),\mathrm{},(x_{(i+1)h},b_{(i+1)h}),0`$. Intuitively $`f_i`$ computes the $`i`$th block of $`L`$ and equals $`0`$ only if we “fall of the edge” of the $`i`$th block. We then have the following straightforward claim:

###### Claim 5

The decision list $`L`$ is eqivalent to

$`\text{sign}\left({\displaystyle \underset{i=1}{\overset{k/h}{}}}2^{k/hi+1}f_i(x)+b_{k+1}\right).`$ (1)
Proof: Given an input $`x0^k`$ let $`r=(i1)h+c`$ be the first index such that $`x_r`$ is satisfied. It is easy to see that $`f_j(x)=0`$ for $`j<i`$ and hence the value in (1) is $`2^{k/hi+1}b_r+_{j=i+1}^{k/h}2^{k/hj+1}f_j(x)+b_{k+1}`$, the sign of which is easily seen to be $`b_r.`$ Finally if $`x=0^k`$ then the argument to (1) is $`b_{k+1}`$. $`\mathrm{}`$

Note: It is easily seen that we can replace the $`2`$ in formula (1) by a 3; this will prove useful later.

As an aside, note that Claim 5 can already be used to obtain a tradeoff between running time and sample complexity for learning decision lists. The class $`_h`$ contains at most $`(4n)^h`$ functions. Thus as in Section 3 it is possible to run the Winnow algorithm using the functions in $`_h`$ as the base features for Winnow. (So for each example $`x`$ which it receives, the algorithm would first compute the value of $`f(x)`$ for each $`f_h`$, and would then use this vector of $`(f(x))_{f_h}`$ values as the example point for Winnow.) A direct analogue of Theorem 2 now implies that Expanded-Winnow (run over this expanded feature space of functions from $`_h`$) can be used to learn $`L_k`$ in time $`n^{O(h)}2^{O(k/h)}`$ with mistake bound $`2^{O(k/h)}h\mathrm{log}n`$.

However, it will be more useful for us to obtain a polynomial threshold function for $`L`$. We can do this from Claim 5 as follows:

###### Theorem 6

Let $`L`$ be a decision list of length $`k`$. Then for any $`h<k`$ we have that $`L`$ is computed by a polynomial threshold function of degree $`h`$ and weight $`42^{k/h+h}`$.

Proof: Consider the first modified decision list $`f_1=(\mathrm{}_1,b_1),(\mathrm{}_2,b_2),\mathrm{},(\mathrm{}_h,b_h),0`$ in the expression (1). For $`\mathrm{}`$ a literal let $`\stackrel{~}{\mathrm{}}`$ denote $`x`$ if $`\mathrm{}`$ is an unnegated variable $`x`$ and let $`\stackrel{~}{\mathrm{}}`$ denote $`1x`$ if if $`\mathrm{}`$ is a negated variable $`\overline{x}.`$ We have that for all $`x\{0,1\}^h`$, $`f_1(x)`$ is computed exactly by the polynomial

$$f_1(x)=\stackrel{~}{\mathrm{}}_1b_1+(1\stackrel{~}{\mathrm{}}_1)\stackrel{~}{\mathrm{}}_2b_2+(1\stackrel{~}{\mathrm{}}_1)(1\stackrel{~}{\mathrm{}}_2)\stackrel{~}{\mathrm{}}_3b_3+\mathrm{}+(1\stackrel{~}{\mathrm{}}_1)\mathrm{}(1\stackrel{~}{\mathrm{}}_{h1})\stackrel{~}{\mathrm{}}_hb_h.$$

This polynomial has degree $`h`$ and has weight at most $`2^{h+1}.`$ Summing these polynomial representations for $`f_1,\mathrm{},f_{k/h}`$ as in (1) we see that the resulting polynomial threshold function given by (1) has degree $`h`$ and weight at most $`2^{k/h+1}2^{h+1}=42^{k/h+h}.`$ $`\mathrm{}`$

Specializing to the case $`h=\sqrt{k}`$ we obtain:

###### Corollary 7

Let $`L`$ be a decision list of length $`k`$. Then $`L`$ is computed by a polynomial threshold function of degree $`k^{1/2}`$ and weight $`42^{2k^{1/2}}.`$

We close this section by observing that an intermediate result of  can be used to give an alternate proof of Corollary 7 with slightly weaker parameters; see Appendix A.

### 4.2 Inner Approximator

In this section we construct low degree, low weight polynomials which approximate (in the $`L_{\mathrm{}}`$ norm) the modified decision lists from the previous subsection. Moreover, the polynomials we construct are exactly correct on inputs which “fall off the end”:

###### Theorem 8

Let $`f_h`$ be a modified decision list of length $`h`$ (without loss of generality we may assume that $`f`$ is $`(x_1,b_1),\mathrm{},(x_h,b_h),0`$). Then there is a degree $`2\sqrt{h}\mathrm{log}h`$ polynomial $`p`$ such that

* for every input $`x\{0,1\}^h`$ we have $`|p(x)f(x)|1/h`$.
* $`p(0^h)=f(0^h)=0`$.

Proof: As in the proof of Theorem 6 we have that

$$f(x)=b_1x_1+b_2(1x_1)x_2+\mathrm{}+b_h(1x_1)\mathrm{}(1x_{h1})x_h.$$

We will construct a lower (roughly $`\sqrt{h}`$) degree polynomial which closely approximates $`f`$. Let $`T_i`$ denote $`(1x_1)\mathrm{}(1x_{i1})x_i`$, so we can rewrite $`f`$ as

$$f(x)=b_1T_1+b_2T_2+\mathrm{}+b_hT_h.$$

We approximate each $`T_i`$ separately as follows: set $`A_i(x)=hi+x_i+_{j=1}^{i1}(1x_j)`$. Note that for $`x\{0,1\}^h,`$ we have $`T_i(x)=1`$ iff $`A_i(x)=h`$ and $`T_i(x)=0`$ iff $`0A_i(x)h1.`$ Now define the polynomial

$$Q_i(x)=q\left(A_i(x)/h\right)\text{ where }q(y)=C_d\left(y\left(1+1/h\right)\right).$$

As in , here $`C_d(x)`$ is the $`d`$th Chebyshev polynomial of the first kind (a univariate polynomial of degree $`d`$) with $`d`$ set to $`\sqrt{h}`$. We will need the following facts about Chebyshev polynomials :

* $`|C_d(x)|1`$ for $`|x|1`$ with $`C_d(1)=1;`$
* $`C_d^{}(x)d^2`$ for $`x>1`$ with $`C_d^{}(1)=d^2.`$
* The coefficients of $`C_d`$ are integers each of whose magnitude is at most $`2^d`$.

These first two facts imply that $`q(1)2`$ but $`|q(y)|1`$ for $`y[0,1\frac{1}{h}].`$ We thus have that $`Q_i(x)=q(1)2`$ if $`T_i(x)=1`$ and $`|Q_i(x)|1`$ if $`T_i(x)=0.`$ Now define $`P_i(x)=\left(\frac{Q_i(x)}{q(1)}\right)^{2\mathrm{log}h}.`$ This polynomial is easily seen to be a good approximator for $`T_i`$: if $`x\{0,1\}^h`$ is such that $`T_i(x)=1`$ then $`P_i(x)=1`$, and if $`x\{0,1\}^h`$ is such that $`T_i(x)=0`$ then $`|P_i(x)|<\left(\frac{1}{2}\right)^{2\mathrm{log}h}<\frac{1}{h^2}.`$

Now define $`R(x)=_{i=1}^{\mathrm{}}b_iP_i(x)`$ and $`p(x)=R(x)R(0^h).`$ It is clear that $`p(0^h)=0.`$ We will show that for every input $`0^hx\{0,1\}^h`$ we have $`|p(x)f(x)|1/h`$. Fix some such $`x`$; let $`i`$ be the first index such that $`x_i=1.`$ As shown above we have $`P_i(x)=1.`$ Moreover, by inspection of $`T_j(x)`$ we have that $`T_j(x)=0`$ for all $`ji,`$ and hence $`|P_j(x)|<\frac{1}{h^2}`$. Consequently the value of $`R(x)`$ must lie in $`[b_i\frac{h1}{h^2},b_i+\frac{h1}{h^2}]`$. Since $`f(x)=b_i`$ we have that $`p(x)`$ is an $`L_{\mathrm{}}`$ approximator for $`f(x)`$ as desired.

Finally, it is straightforward to verify that $`p(x)`$ has the claimed bound on degree. $`\mathrm{}`$

Strictly speaking we cannot discuss the weight of the polynomial $`p`$ since its coefficients are rational numbers but not integers. However, by multiplying $`p`$ by a suitable integer (clearing denominators) we obtain an integer polynomial with essentially the same properties. Using the third fact about Chebyshev polynomials from our proof above, we have that $`q(1)`$ is a rational number $`N_1/N_2`$ where $`N_1,N_2`$ are each integers of magnitude $`h^{O(\sqrt{h})}.`$ Each $`Q_i(x)`$ for $`i=1,\mathrm{},h`$ can be written as an integer polynomial (of weight $`h^{O(\sqrt{h})}`$) divided by $`h^\sqrt{h}.`$ Thus each $`P_i(x)`$ can be written as $`\stackrel{~}{P}_i(x)/(h^\sqrt{h}N_1)^{2\mathrm{log}h}`$ where $`\stackrel{~}{P}_i(x)`$ is an integer polynomial of weight $`h^{O(\sqrt{h}\mathrm{log}h)}`$. It follows that $`p(x)`$ equals $`\stackrel{~}{p}(x)/C,`$ where $`C`$ is an integer which is at most $`2^{O(h^{1/2}\mathrm{log}^2h)}`$ and $`\stackrel{~}{p}`$ is a polynomial with integer coefficients and weight $`2^{O(h^{1/2}\mathrm{log}^2h)}.`$ We thus have

###### Corollary 9

Let $`f_h`$ be a modified decision list of length $`h`$. Then there is an integer polynomial $`p(x)`$ of degree $`2\sqrt{h}\mathrm{log}h`$ and weight $`2^{O(h^{1/2}\mathrm{log}^2h)}`$ and an integer $`C=2^{O(h^{1/2}\mathrm{log}^2h)}`$ such that

* for every input $`x\{0,1\}^h`$ we have $`|p(x)Cf(x)|C/h`$.
* $`p(0^h)=f(0^h)=0`$.

The fact that $`p(0^h)`$ is exactly 0 will be important in the next subsection when we combine the inner approximator with the outer construction.

### 4.3 Composing the Constructions

In this section we combine the two constructions from the previous subsections to obtain our main polynomial threshold construction:

###### Theorem 10

Let $`L`$ be a decision list of length $`k`$. Then for any $`h<k`$, $`L`$ is computed by a polynomial threshold function of degree $`O(h^{1/2}\mathrm{log}h)`$ and weight $`2^{O(k/h+h^{1/2}\mathrm{log}^2h)}.`$

Proof: We suppose without loss of generality that $`L`$ is the decision list $`(x_1,b_1),\mathrm{},(x_k,b_k),b_{k+1}.`$ We begin with the outer construction: from the note following Claim 5 we have that

$$L(x)=\text{sign}\left(C\left[\underset{i=1}{\overset{k/h}{}}3^{k/hi+1}f_i(x)+b_{k+1}\right]\right)$$

where $`C`$ is the value from Corollary 9 and each $`f_i`$ is a modified decision list of length $`h`$ computing the restriction of $`L`$ to its $`i`$th block as defined in Subsection 4.1. Now we use the inner approximator to replace each $`Cf_i`$ above by $`p_i`$, the approximating polynomial from Corollary 9, i.e. consider sign$`(H(x))`$ where

$$H(x)=\underset{i=1}{\overset{k/h}{}}(3^{k/hi+1}p_i(x))+Cb_{k+1}.$$

We will show that sign$`(H(x))`$ is a polynomial threshold function which computes $`L`$ correctly and has the desired degree and weight.

Fix any $`x\{0,1\}^k.`$ If $`x=0^k`$ then by Corollary 9 each $`p_i(x)`$ is $`0`$ so $`H(x)=Cb_{k+1}`$ has the right sign. Now suppose that $`r=(i1)h+c`$ is the first index such that $`x_r=1.`$ By Corollary 9, we have that

* $`3^{k/hj+1}p_j(x)=0`$ for $`j<i`$;
* $`3^{k/hi+1}p_i(x)`$ differs from $`3^{k/hi+1}Cb_r`$ by at most $`C3^{k/hi+1}\frac{1}{h}`$;
* The magnitude of each value $`3^{k/hj+1}p_j(x)`$ is at most $`C3^{k/hj+1}(1+\frac{1}{h})`$ for $`j>i.`$

Combining these bounds, the value of $`H(x)`$ differs from $`3^{k/hi+1}Cb_r`$ by at most

$$C\left(\frac{3^{k/hi+1}}{h}+\left(1+\frac{1}{h}\right)\left[3^{k/hi}+3^{k/hi1}+\mathrm{}+3\right]+1\right)$$

which is easily seen to be less than $`C3^{k/hi+1}`$ in magnitude. Thus the sign of $`H(x)`$ equals $`b_r`$, and consequently sign$`(H(x))`$ is a valid polynomial threshold representation for $`L(x).`$ Finally, our degree and weight bounds from Corollary 9 imply that the degree of $`H(x)`$ is $`O(h^{1/2}\mathrm{log}h)`$ and the weight of $`H(x)`$ is $`2^{O(k/h)+O(h^{1/2}\mathrm{log}^2h)}`$, and the theorem is proved. $`\mathrm{}`$

Taking $`h=k^{2/3}/\mathrm{log}^{4/3}k`$ in the above theorem we obtain our main result on representing decision lists as polynomial threshold functions:

Theorem 3 Let $`L`$ be a decision list of length $`k`$. Then $`L`$ is computed by a polynomial threshold function of degree $`k^{1/3}\mathrm{log}^{1/3}k`$ and weight $`2^{O(k^{1/3}\mathrm{log}^{4/3}k)}.`$

Theorem 3 immediately implies that Expanded-Winnow can learn decision lists of length $`k`$ using $`2^{\stackrel{~}{O}(k^{1/3})}\mathrm{log}n`$ examples and time $`n^{\stackrel{~}{O}(k^{1/3})}`$.

## 5 Application to Learning Decision Trees

In 1989 Ehrenfeucht and Haussler  gave an a time $`n^{O(\mathrm{log}s)}`$ algorithm for learning decision trees of size $`s`$ over $`n`$ variables. Their algorithm uses $`n^{O(\mathrm{log}s)}`$ examples, and they asked if the sample complexity could be reduced to $`\mathrm{poly}(n,s)`$. We can apply our techniques here to give an algorithm using $`2^{\stackrel{~}{O}(s^{1/3})}\mathrm{log}n`$ examples, if we are willing to spend $`n^{\stackrel{~}{O}(s^{1/3})}`$ time.

First we need to generalize Theorem 10 for higher order decision lists. An $`r`$-decision list is like a standard decision list but each pair is now of the form $`(C_i,b_i)`$ where $`C_i`$ is a conjunction of at most $`r`$ literals and as before $`b_i=\pm 1`$. The output of such an $`r`$-decision list on input $`x`$ is $`b_i`$ where $`i`$ is the smallest index such that $`C_i(x)=1.`$

We have the following:

###### Corollary 11

Let $`L`$ be an $`r`$-decision list of length $`k`$. Then for any $`h<k`$, $`L`$ is computed by a polynomial threshold function of degree $`O(rh^{1/2}\mathrm{log}h)`$ and weight $`2^{r+O(k/h+h^{1/2}\mathrm{log}^2h)}`$.

Proof: Let $`L`$ be the $`r`$-decision list $`(C_1,b_1),\mathrm{},(C_k,b_k),b_{k+1}.`$ By Theorem 10 there is a polynomial threshold function of degree $`O(h^{1/2}\mathrm{log}h)`$ and weight $`2^{O(k/h+h^{1/2}\mathrm{log}^2h)}`$ over the variables $`C_1,\mathrm{},C_k.`$ Now replace each variable $`C_i`$ by the interpolating polynomial which computes it exactly as a function from $`\{0,1\}^n`$ to $`\{0,1\}.`$ Each such interpolating polynomial has degree $`r`$ and integer coefficients of total magnitude at most $`2^r`$, and the corollary follows. $`\mathrm{}`$

###### Corollary 12

There is an algorithm for learning $`r`$-decision lists over $`\{0,1\}^n`$ which, when learning an $`r`$-decision list of length $`k`$, has mistake bound $`2^{\stackrel{~}{O}(r+k^{1/3})}\mathrm{log}n`$ and runs in time $`n^{\stackrel{~}{O}(rk^{1/3})}`$.

Now we can apply Corollary 12 to obtain a tradeoff between running time and sample complexity for learning decision trees:

###### Theorem 13

Let $`D`$ be a decision tree of size $`s`$ over $`n`$ variables. Then $`D`$ can be learned using $`2^{\stackrel{~}{O}(s^{1/3})}\mathrm{log}n`$ examples in time $`n^{\stackrel{~}{O}(s^{1/3})}.`$

Proof: Blum  has shown that any decision tree of size $`s`$ is computed by a $`(\mathrm{log}s)`$-decision list of length $`s.`$ Applying Corollary 12 we thus see that Expanded-Winnow can be used to learn decision trees of size $`s`$ over $`\{0,1\}^n`$ with the claimed bounds on time and sample complexity. $`\mathrm{}`$

## 6 Lower Bounds for Decision Lists

Here we observe that our construction from Theorem 10 is essentially optimal in terms of the tradeoff it achieves between polynomial threshold function degree and weight.

In , Beigel constructs an oracle separating $`\mathrm{𝖯𝖯}`$ from $`𝖯^{\mathrm{𝖭𝖯}}`$. At the heart of his construction is a proof that any low degree polynomial threshold function for a particular decision list, called the the $`\mathrm{ODDMAXBIT}_n`$ function, must have large weights:

###### Definition 14

The $`\mathrm{ODDMAXBIT}_n`$ function on input $`x=x_1,\mathrm{},x_n\{0,1\}^n`$ equals $`(1)^i`$ where $`i`$ is the index of the first nonzero bit in $`x.`$

It is clear that the $`\mathrm{ODDMAXBIT}_n`$ function is equivalent to a decision list of length $`n`$:

$$(x_1,1),(x_2,1),(x_3,1),\mathrm{},(x_n,(1)^n),(1)^{n+1}.$$

The main technical theorem which Beigel proves in  states that any polynomial threshold function of degree $`d`$ computing $`\mathrm{ODDMAXBIT}_n`$ must have weight $`2^{\mathrm{\Omega }(n/d^2)}`$:

###### Theorem 15

Let $`p`$ be a degree $`d`$ polynomial threshold function with integer coefficients computing $`\mathrm{ODDMAXBIT}_n`$. Then $`w=2^{\mathrm{\Omega }(n/d^2)}`$ where $`w`$ is the weight of $`p.`$333Beigel actually proves something stronger, namely that there must exists a coefficient whose absolute value is at least $`2^{\mathrm{\Omega }(n/d^2)}`$.

(As stated in  the bound is actually $`w\frac{1}{s}2^{\mathrm{\Omega }(n/d^2)}`$ where $`s`$ is the number of nonzero coefficients in $`p`$. Since $`sw`$ this implies the result as stated above.)

A lower bound of $`2^{\mathrm{\Omega }(n)}`$ on the weight of any linear threshold function ($`d=1`$) for $`\mathrm{ODDMAXBIT}_n`$ has long been known ; Beigel’s proof generalizes this lower bound to all $`d=O(n^{1/2}).`$ A matching upper bound of $`2^{O(n)}`$ on weight for $`d=1`$ has also long been known . Our Theorem 10 gives an upper bound which matches Beigel’s lower bound (up to logarithmic factors) for all $`d=O(n^{1/3})`$:

###### Observation 16

For any $`d=O(n^{1/3})`$ there is a polynomial threshold function of degree $`d`$ and weight $`2^{\stackrel{~}{O}(n/d^2)}`$ which computes $`\mathrm{ODDMAXBIT}_n`$.

Proof: Set $`d=h^{1/2}\mathrm{log}h`$ in Theorem 10. The weight bound given by Theorem 10 is $`2^{O(\frac{n\mathrm{log}^2d}{d^2}+d\mathrm{log}d)}`$ which is $`\stackrel{~}{O}(n/d^2)`$ for $`d=O(n^{1/3}).`$ $`\mathrm{}`$

Note that since the $`\mathrm{ODDMAXBIT}_n`$ function has a polynomial size DNF (see Appendix A), Beigel’s lower bound gives a polynomial size DNF $`f`$ such that any degree $`\stackrel{~}{O}(n^{1/3})`$ polynomial threshold function for $`f`$ must have weight $`2^{\stackrel{~}{\mathrm{\Omega }}(n^{1/3})}`$. This suggests that the Expanded-Winnow algorithm cannot learn polynomial size DNF in $`2^{\stackrel{~}{O}(n^{1/3})}`$ time from $`2^{n^{1/3ϵ}}`$ examples for any $`ϵ>0,`$ and thus suggests that improving the sample complexity of the DNF learning algorithm from  while maintaining its $`2^{\stackrel{~}{O}(n^{1/3})}`$ running time may be difficult.

## 7 Learning Parity Functions

We first briefly review the standard algorithm for learning parity functions.

The standard algorithm for learning parity functions works by viewing a set of $`m`$ labelled examples as a set of $`m`$ linear equations over GF(2). Each labelled example $`(x,b)`$ induces the equation $`_{i:x_i=1}a_i=bmod2.`$ Since the examples are labelled according to some parity function, this parity function will be a consistent solution to the system of equations. Using Gaussian elimination it is possible to efficiently find a solution to the linear system, which yields a parity function consistent with all $`m`$ examples. The following standard fact from learning theory (often referred to as “Occam’s Razor”) shows that finding a consistent hypothesis suffices to establish PAC learnability:

###### Fact 17

Let $`C`$ be a concept class and $`H`$ a finite set of hypotheses. Set $`m=1/ϵ(\mathrm{log}|H|+\mathrm{log}1/\delta )`$ where $`ϵ`$ and $`\delta `$ are the usual accuracy and confidence parameters for PAC learning. Suppose that there is an algorithm $`A`$ running in time $`t`$ which takes as input $`m`$ examples which are labelled according to some element of $`C`$ and outputs a hypothesis $`hH`$ consistent with these examples. Then $`A`$ is a PAC learning algorithm for $`C`$ with running time $`t`$ and sample complexity $`m.`$

Consider using the above algorithm to learn an unknown parity of length at most $`k.`$ Even though there is a solution of weight at most $`k`$, Gaussian elimination (applied to a system of $`m`$ equations in $`n`$ variables over GF(2)) may yield a solution of weight as large as $`\mathrm{min}(m,n).`$ Using Fact 17 we thus obtain a sample complexity bound of $`O(n)`$ examples for learning a parity of length at most $`k.`$

We now present a simple polynomial-time algorithm for learning an unknown parity function on $`k`$ variables using $`O(n^{11/k})`$ examples. To the best of our knowledge this is the first improvement on the standard algorithm and analysis given above.

###### Theorem 18

The class of all parity functions on at most $`k`$ variables is learnable in polynomial time using $`O(n^{11/k}\mathrm{log}n)`$ examples. The hypothesis output by the learning algorithm is a parity function on $`O(n^{11/k}\mathrm{log}n)`$ variables.

Proof: If $`k=\mathrm{\Omega }(\mathrm{log}n)`$ then the standard algorithm suffices to prove the claimed bound. We thus assume that $`k=o(\mathrm{log}n)`$.

Let $`H`$ be the set of all parity functions of size at most $`n^{11/k}`$. Note that $`|H|n^{n^{11/k}}`$ so $`\mathrm{log}|H|n^{11/k}\mathrm{log}n.`$ Consider the following algorithm:

1. Choose $`m=1/ϵ(\mathrm{log}|H|+\mathrm{log}(1/\delta ))`$ examples. Express each example as a linear equation over $`n`$ variables mod $`2`$ as described above.
2. Randomly choose a set of $`nn^{11/k}`$ variables and assign them the value $`0`$.
3. Use Gaussian elimination to attempt to solve the resulting system of equations on the remaining $`n^{11/k}`$ variables. If the system has a solution, output the corresponding parity (of size at most $`n^{11/k}`$) as the hypothesis. If the system has no solution, output “FAIL.”

If the simplified system of equations has a solution, then by Fact 17 this solution is a good hypothesis. We will show that the simplified system has a solution with probability $`\mathrm{\Omega }(1/n)`$. The theorem follows by repeating steps 2 and 3 of the above algorithm until a solution is found (an expected $`O(n)`$ repetitions will suffice).

Let $`V`$ be the set of $`k`$ relevant variables on which the unknown parity function depends. It is easy to see that as long as no variable in $`V`$ is assigned a 0, the resulting simplified system of equations will have a solution. Let $`\mathrm{}=n^{11/k}.`$ The probability that in Step 2 the $`n\mathrm{}`$ variables chosen do not include any variables in $`V`$ is exactly $`\left(\genfrac{}{}{0pt}{}{nk}{n\mathrm{}}\right)/\left(\genfrac{}{}{0pt}{}{n}{\mathrm{}}\right)`$ which equals $`\left(\genfrac{}{}{0pt}{}{nk}{\mathrm{}k}\right)/\left(\genfrac{}{}{0pt}{}{n}{\mathrm{}}\right).`$ Expanding binomial coefficients we have

$$\frac{\left(\genfrac{}{}{0pt}{}{nk}{\mathrm{}k}\right)}{\left(\genfrac{}{}{0pt}{}{n}{\mathrm{}}\right)}=\underset{i=1}{\overset{k}{}}\frac{\mathrm{}k+i}{nk+i}>\left(\frac{\mathrm{}k}{nk}\right)^k=\left(\frac{\mathrm{}}{n}\right)^k\left(\frac{1\frac{k}{\mathrm{}}}{1\frac{k}{n}}\right)^k=\frac{1}{n}\left[\left(1\frac{k}{\mathrm{}}\right)\left(1+\frac{2k}{n}\right)\right]^k.$$
(2)
The bound $`k=o(\mathrm{log}n)`$ implies that $`\left(1\frac{k}{\mathrm{}}\right)\left(1+\frac{2k}{n}\right)>(1\frac{3k}{\mathrm{}}).`$ Consequently (2) is at least $`\frac{1}{n}\left(1\frac{3k^2}{\mathrm{}}\right)>\frac{1}{2n}`$ and the theorem is proved. $`\mathrm{}`$

## 8 Future Work

An obvious goal for future work is to improve our algorithmic results for learning decision lists. The question still remains: can decision lists of length $`k`$ be learned in poly$`(n)`$ time from poly$`(k,\mathrm{log}n)`$ examples? As a first step, one might attempt to extend the tradeoffs we achieve: is it possible to learn decision lists of length $`k`$ in $`n^{k^{1/2}}`$ time from poly$`(k,\mathrm{log}n)`$ examples?

Another goal is to extend our results for decision lists to broader concept classes. In particular, since decision lists are a special case of linear threshold functions, it would be interesting to obtain analogues of our algorithmic results for learning general linear threshold functions (independent of their weight). We note here that Goldmann et al.  have given a linear threshold function over $`\{1,1\}^n`$ for which any polynomial threshold function must have weight $`2^{\mathrm{\Omega }(n^{1/2})}`$ regardless of its degree. Moreover Krause and Pudlak  have shown that any Boolean function which has a polynomial threshold function over $`\{0,1\}^n`$ of weight $`w`$ has a polynomial threshold function over $`\{1,1\}^n`$ of weight $`n^2w^4.`$ These results imply that representational results akin to Theorem 3 for general linear threshold functions must be quantitatively weaker than Theorem 3; in particular, there is a linear threshold function over $`\{0,1\}^n`$ with $`k`$ nonzero coefficients for which any polynomial threshold function, regardless of degree, must have weight $`2^{\mathrm{\Omega }(k^{1/2})}.`$

For parity functions, one challenge is to learn parity functions on $`k=\mathrm{\Theta }(\mathrm{log}n)`$ variables in polynomial time using a sublinear number of examples. Another challenge is to improve the sample complexity of learning size $`k`$ parities from our current bound of $`O(n^{11/k}).`$

## 9 Acknowledgements

We thank Les Valiant for his observation that Claim 5 can be reinterpreted in terms of polynomial threshold functions. We thank Jean Kwon for suggesting the Chebychev polynomial.

## Appendix A Alternate Proof of Corollary 7

The alternate proof of Corollary 7 is based on the observation that any decision list $`L=(\mathrm{}_1,b_1),\mathrm{},`$ $`(\mathrm{}_k,b_k),b_{k+1}`$ of length $`k`$ has a $`k`$-term DNF in which each term is a conjunction of at most $`k`$ literals. To see this, note that we obtain a DNF for $`L`$ simply by taking the OR of all terms $`\overline{\mathrm{}}_1\overline{\mathrm{}}_2\mathrm{}\overline{\mathrm{}}_{i1}\mathrm{}_i`$ for each $`i`$ such that $`b_i=1.`$ Now we use the following result from :

###### Theorem 19 (Corollary 12 of )

Let $`f`$ be a DNF formula of $`s`$ terms, each of length at most $`t.`$ Then there is a polynomial threshold function for $`f`$ of degree $`O(\sqrt{t}\mathrm{log}s)`$ and weight $`t^{O(\sqrt{t}\mathrm{log}s)}.`$

Applying this result to the DNF representation for $`L,`$ we immediately obtain that there is a polynomial threshold function for $`L`$ which has degree $`O(k^{1/2}\mathrm{log}k)`$ and weight $`2^{O(k^{1/2}\mathrm{log}^2k)}.`$ (In Section 4.2, though, we need the construction given in our original proof of Corollary 7.)


format: text

text:
# A note on quasinormal modes: A tale of two treatments

## I Introduction

For a long time, a fascinating problem in gravitational physics was what happens to small perturbations in an otherwise stationary black hole geometry? Fortunately, at least the basic elements of this problem are now well understood: Such perturbations will essentially be scattered by the gravitational potential and, ultimately, radiated away with a discrete set of complex-valued frequencies. Such behavior, which is reminiscent of the last dying tones of a ringing bell, can be recognized as the quasinormal mode solutions associated with the black hole spacetime. If nothing else, these modes are expected to be significant in the context of gravitational-wave astronomy .

Thanks to an intriguing (albeit conjectural) connection between quasinormal modes and quantum gravity, there has been a recent surge of interest into resolving the quasinormal mode spectra for various black hole spacetimes. (See  for summarized accounts of recent work and the relevant references.) In a sense, such a connection is surprising, given that quasinormal modes represent a purely classical consequence of the black hole gravitational field. Nonetheless, as first advocated by Hod , there is reason to believe that quasinormal modes can be used to fix the level spacing of the black hole area spectrum. (An evenly spaced area spectrum follows from arguments, as made initially by Bekenstein , that the horizon area of a black hole is an adiabatic invariant.) Moreover, this rationale can even be extended into the realm of loop quantum gravity, where it has been suggested by Dreyer  that similar considerations can be utilized to fix, unambiguously, the elusive “Immirzi parameter” .

In the above circle of ideas, a pivotal role is played by the real part of the quasinormal mode frequency when the modes are highly damped (i.e., when the magnitude of the imaginary part is very large). It is generally believed (or perhaps hoped) that, for a given black hole spacetime, this real part will asymptote to a fixed value, independently of the details of the perturbation. In light of this comment, it is instructive to consider a specific model; let us therefore call upon the Schwarzschild mode spectrum for illustrative purposes. In this case, one obtains (with appropriately chosen boundary conditions) the following set of frequencies for either scalar or axial gravitational perturbations :

$$k_{qnm}=\kappa \left[i\left(n+\frac{1}{2}\right)+\frac{1}{2\pi }\mathrm{ln}3\right]+𝒪[n^{1/2}]n=0,1,2,\mathrm{}.$$
(1)
Note that $`\kappa `$ is the (Schwarzschild) surface gravity ***Here and throughout, all fundamental constants have been set to unity. and this expression becomes increasingly accurate as $`n\mathrm{}`$.

This (asymptotically valid) spectral form has long been known by numerical means (e.g., ) and has even, quite recently, been confirmed by analytical treatments. In , for instance, the authors have invoked a method that is based on calculating the monodromy of the perturbed field when the radial coordinate has been analytically continued to the complex plane. In any event, the above spectrum substantiates that the real part of the frequencies does indeed asymptote to a constant value, independent of any details about the perturbation field itself. Actually, the type of perturbation field does play a role, as the above form applies, strictly speaking, to only scalar and axial gravitational perturbations. Nonetheless, it could be argued that fundamental considerations should be restricted to a certain class of gravitational perturbations, so this is generally not a concern. As a further point of interest, it is a generic feature of black hole spacetimes that the asymptotic spacing (between the imaginary levels) goes precisely as the surface gravity .

Let us re-emphasize that the real part of the (highly damped) quasinormal frequencies is a critical ingredient in the proposals made by both Hod  and Dreyer . Moreover, the stance of these authors is that this real portion represents a fundamental (transition) frequency associated with the black hole horizon. Hence, if their arguments are to hold up, it is essential that this real part is strictly characterized by the horizon geometry and, hence, not overly sensitive to specifics of the perturbation field. It does, however, remain somewhat controversial as to whether or not this “non-sensitivity” is indeed a universal feature of black hole spacetimes.

For instance, a viable counterexample is provided by Schwarzschild–de Sitter space when the black hole and cosmological horizon are closely “squeezed” together. We often refer to the degenerate (or very nearly degenerate) Schwarzschild–de Sitter model as being in the “squeezed-horizon” limit . Such terminology is meant to distinguish this scenario from one in which the observer is exterior to a pair of (nearly) coincident horizons; that is, exterior to a black hole at (or near) extremality. The two scenarios are, of course, operationally distinct. To elaborate, a recent study  — based on identifying the relevant scattering potential with that of the Poschl–Teller model  — found a quasinormal spectrum that depends strongly on the orbital angular momentum ($`\mathrm{}`$) of the perturbation field. Moreover, in the degenerate limit, the real part of the frequency, for any mode, goes almost linearly with $`\mathrm{}`$. (In fact, it has since been demonstrated that this behavior is a generic feature of squeezed-horizon spacetimes .) However, this is not yet the full story. In a more recent paper , the quasinormal mode spectrum was calculated for non-degenerate Schwarzschild–de Sitter space by way of the monodromy method . When this form of the spectrum is then subjected to the horizon-degeneracy limit, as was done explicitly in , there is absolutely no $`\mathrm{}`$ dependence in evidence. Hence, what we have is two quite conflicting predictions for precisely the same model.

The purpose of the current paper is to provide a possible resolution for this rather disturbing discrepancy. Our basic point of view is that the Poschl–Teller-inspired calculation is, given its elegant simplicity, most likely correct.§§§Moreover, the Poschl–Teller spectral form for nearly degenerate Schwarzschild–de Sitter space has also been substantiated semi-analytically (particularly for large values of $`\mathrm{}`$) by Moss and Norman  using continued-fraction techniques , as well as by Zhidenko  and Konoplya  using WKB methodology . For other recent studies on Schwarzschild–de Sitter quasinormal modes, see . Meanwhile, the monodromy-based calculation, although perfectly valid in the non-degenerate regime, can not necessarily be extrapolated up to the point of horizon coincidence. The remainder of the paper contains the analysis in support of our argument (Section II), followed by a pertinent discussion (Section III). Note that we skip over most of the details of these interesting methodologies — “Poschl–Teller”  and “monodromy”  — and refer the reader to the cited works.

## II Analysis

Before getting to the crux of the matter, let us introduce some necessary formalism. The metric for a Schwarzschild–de Sitter spacetime can be expressed (in a static coordinate gauge) as follows:

$$ds^2=f(r)dt^2+f^1(r)dr^2+r^2d\mathrm{\Omega }^2,$$
(2)
where

$$f(r)=1\frac{2M}{r}\frac{r^2}{a^2},$$
(3)
with $`M`$ representing the black hole mass and $`a`$ denoting the de Sitter curvature radius (alternatively, $`\mathrm{\Lambda }=3/a^2`$ is the positive cosmological constant).

The function $`f(r)`$ has three zeroes, two of which locate the black hole horizon, $`r_b`$, and the cosmological horizon, $`r_c`$, with $`r_brr_c`$ indicating the “observable” portion of the spacetime. \[The third zero locates a fictitious negative horizon, $`r_0=\left(r_b+r_c\right)`$.\] For future reference, it is useful to take note of the following relations:

$$a^2=r_b^2+r_br_c+r_c^2,$$
(4)
$$2Ma^2=r_br_c\left(r_b+r_c\right).$$
(5)
Each horizon is endowed with a surface gravity, which can be evaluated via standard methods (essentially, one half of the derivative of $`f(r)`$ evaluated at the appropriate horizon ) to yield

$$\kappa _b=\frac{\left(r_cr_b\right)\left(2r_b+r_c\right)}{2a^2r_b},$$
(6)
$$\kappa _c=\frac{\left(r_cr_b\right)\left(2r_c+r_r\right)}{2a^2r_c},$$
(7)
for the black hole and cosmological horizon respectively. Note that these quantities are, by definition, positive definite.

It is often convenient — especially, in the context of quasinormal modes — to introduce a (generalized) “tortoise coordinate”; that is, $`dx=dr/f(r)`$ or

$$x=\frac{dr}{f(r)}.$$
(8)
Substituting in equation (3) and integrating, one obtains

$$x=\frac{1}{2\kappa _b}\mathrm{ln}\left[\frac{r}{r_b}1\right]\frac{1}{2\kappa _c}\mathrm{ln}\left[1\frac{r}{r_c}\right]+\frac{1}{2}\left(\frac{1}{\kappa _c}\frac{1}{\kappa _b}\right)\mathrm{ln}\left[\frac{r}{r_b+r_c}+1\right].$$
(9)
Keep in mind that $`r(r_b,r_c)`$ maps into the region $`x(\mathrm{},+\mathrm{})`$.

Let us now focus specifically on the quasinormal mode problem, which entails the study of how small (massless) perturbations of the background spacetime are scattered by the gravitational potential. As has been well documented, one can formally cast this picture into a one-dimensional, Schrodinger-like scattering situation . Generically speaking, one obtains an equation that conforms to

$$\frac{d^2}{dx^2}\psi V[r(x)]\psi =k^2\psi ,$$
(10)
where $`\psi =\psi \left[r(x)\right]`$ describes the radial behavior of the perturbation field, $`V[r(x)]`$ is a model-dependent “scattering potential”, and $`k`$ is the frequency (that is, $`e^{\pm ikt}`$ is the time dependence of the perturbation; with $`e^{+ikt}`$ then chosen to ensure that the imaginary part of $`k`$ is positive for an exponentially decaying solution). Note that the potential generally depends on both the spin, $`j`$, and the orbital angular momentum, $`\mathrm{}`$, of the perturbed field.

For a Schwarzschild–de Sitter spacetime, in particular, it has been shown that the scattering potential takes on the form

$$V[r]=f(r)\left[\frac{\mathrm{}\left(\mathrm{}+1\right)}{r^2}+\left(1j^2\right)\left(\frac{2M}{r^3}\frac{2}{a^2}\right)\right],$$
(11)
at least for scalar ($`j=0`$) and axial gravitational ($`j=2`$) perturbations. (Generalizations to other cases are indeed possible  but, for simplicity, will not be considered here.)

As a brief but important aside, let us point out that resolving the quasinormal mode problem requires suitably chosen initial conditions. Normally, one imposes “radiation boundary conditions” such that $`\psi (x)e^{\pm ikx}`$ as $`x\mathrm{}`$; that is, an ingoing (outgoing) plane wave at the inner (outer) boundary. It is also necessary, in the case of dual-horizon scenarios, to make a decision as to where the scattering takes place. In the case of black hole scattering, the “incident” wave should be coming in from the outer boundary (i.e., positive infinity in $`x`$ coordinates) whereas, for cosmological horizon scattering, the incident wave should be coming out from the inner boundary. (For a more quantitative description, see .) In the (current) case of nearly coincident horizons, however, this distinction becomes effectively irrelevant.

Since our current interest is specifically with the nearly degenerate (or “squeezed”) horizon scenario, we will now re-express the above formalism as appropriate for this regime. First, let us put the notion of nearly coincident horizons into quantitative terms. This can be accomplished with the introduction of the following “squeezing parameter”:

$$\mathrm{\Delta }\frac{\left(r_cr_b\right)}{r_b}<<1.$$
(12)
Given the extent of the relevant manifold ($`r_brr_c`$), it immediately follows that, up to corrections of the relative order $`\mathrm{\Delta }`$, $`r_brr_c`$ and $`\kappa _b\kappa _c`$. (For the duration, $``$ will always be used to signify corrections of this order.)

In view of the above, the metric function (3), surface gravities (6,7), tortoise coordinate (9) and scattering potential (11) will now simplify as follows:

$$f(r)2\kappa _b(rr_b),$$
(13)
$$\kappa _b\kappa _c\frac{\left(r_cr_b\right)}{2r_b^2},$$
(14)
$$x\frac{1}{2\kappa _b}\left(\mathrm{ln}\left[\frac{r}{r_b}1\right]\mathrm{ln}\left[1\frac{r}{r_c}\right]+\left(\frac{\kappa _b\kappa _c}{\kappa _b}\right)\mathrm{ln}\left[\frac{r}{r_b+r_c}+1\right]\right),$$
(15)
$$V[r]f(r)\frac{\mathrm{}\left(\mathrm{}+1\right)}{r^2}.$$
(16)
Take particular note of the scattering potential; it depends, up to corrections that vanish as $`\mathrm{\Delta }0`$, on the orbital angular momentum but not on the spin of the perturbation.

Given this simplified form of the potential, it turns out that one can directly extract the quasinormal mode frequencies from equation (10). More to the point, as shown in  (and later generalized in ), the potential $`V[x]`$ takes on a Poschl–Teller form , for which the quasinormal mode spectrum is known exactly . Following this reasoning, one eventually obtains

$$k_{qnm}=\kappa _b\left[i\left(n+\frac{1}{2}\right)+\sqrt{\mathrm{}(\mathrm{}+1)\frac{1}{4}}+𝒪[\mathrm{\Delta }]\right]n=0,1,2,\mathrm{}.$$
(17)
Next, we would like to know what the monodromy method  can say about the quasinormal modes for Schwarzschild–de Sitter space when the horizons are closely squeezed. In fact, this monodromy calculation has already been carried out in , although under the presumption of non-degenerate horizons. Still, the authors of  considered (near) horizon degeneracy as a limiting case of the general analysis. It should, however, be emphasized that the appropriate limit was taken only after the calculation of the mode spectrum was completed. We will now proceed to argue that this particular limiting procedure may not be technically correct

One of the underlying premises of the monodromy method  is the viability of an analytic continuation of $`r`$ (and, by implication, $`x`$) into the complex-valued plane. This continuation allows the real part of $`r`$ to enter the “unobserved” region ($`r<r_b`$) including all the way to the singularity at $`r=0`$. However, as pointed out in , it is essential to the program that the geometry (specifically, $`f(r)`$ and related quantities) is first defined in the observable region ($`rr_b`$) and then analytically continued. That is to say, the “physical” geometry of the black hole interior \[i.e., $`f(r)`$ as defined for $`r<r_b`$ sans any continuation\] must not be allowed to enter into the quasinormal mode problem. This is because, in the original definition of the problem, one sets up strict boundary conditions at the black hole horizon and the cosmological horizon, For as asymptotically flat spacetime, the boundary conditions are rather fixed at the black hole horizon and spatial infinity. thus rendering the black hole interior (and the cosmological horizon exterior) as being operationally irrelevant.

In view of the above discussion, it becomes clear that a “squeezed observer” would find it most appropriate to analytically continue the geometry described by equations (13-16). (Admittedly, this is somewhat naive — see Section III for an elaboration.) Now, considering that the “focal point” of the monodromy calculation is at (or rather near) the singularity, $`r=0`$, let us see what happens to these expressions near the spatial origin. Firstly, defining a “shifted tortoise coordinate” or $`z=x+constant`$ such that $`z(r=0)=0`$ , we are able to deduce \[after expanding equation (15) near $`r=0`$ and then incorporating equation (14)\]

$$z\frac{3}{2}r+𝒪[r^2].$$
(18)
Next, let us consider the potential \[cf, equations (13,16)\] as $`r`$ or $`z`$ goes to zero. This is simply

$`V[z(r)]`$ $``$ $`2{\displaystyle \frac{r_b\kappa _b\mathrm{}\left(\mathrm{}+1\right)}{r^2}}+𝒪[r^1]`$ (19)
$``$ $`{\displaystyle \frac{9}{2}}{\displaystyle \frac{r_b\kappa _b\mathrm{}\left(\mathrm{}+1\right)}{z^2}}+𝒪[z^1].`$ (20)
Conveniently, this is the same form of near-the-origin potential ($`Vz^2`$) as obtained for the non-degenerate Schwarzschild–de Sitter case . Hence, the rest of the monodromy-based calculation can proceed, in the same manner as , but with the necessary substitution

$`\nu `$ $`=`$ $`{\displaystyle \frac{1}{2}}\sqrt{1+z^2V[z0]}`$ (21)
$`=`$ $`{\displaystyle \frac{1}{2}}\sqrt{1{\displaystyle \frac{9}{2}}r_b\kappa _b\mathrm{}\left(\mathrm{}+1\right)},`$ (22)
where $`\nu `$ is the “Bessel-function index” as explicitly defined in equations (12-13) of .

Referring the reader again to  (also see ), let us quote the quasinormal mode spectrum as obtained via the prescribed procedure: $`e^{2\pi k/\kappa _b}=\left(1+2\mathrm{cos}2\pi \nu \right)`$ or

$$k_{qnm}=\kappa _b\left[i\left(n+\frac{1}{2}\right)\pm \frac{1}{2\pi }\mathrm{ln}\left|1+2\mathrm{cos}2\pi \nu \right|\right]n=0,1,2,\mathrm{},$$
(23)
which can be expected to be valid up to corrections of the order $`n^{1/2}`$ (in general) and the relative order $`\mathrm{\Delta }`$ (in our specific case). Substituting in equation (22) and expanding under the assumption that $`\frac{9}{2}r_b\kappa _b\mathrm{}\left(\mathrm{}+1\right)`$ is somewhat less than unity, Since $`r_b\kappa _b\mathrm{\Delta }`$ and $`\mathrm{\Delta }<<1`$, this assumption must be true as long as $`\mathrm{}`$ is not too large. we then have

$$k_{qnm}=\kappa _b\left[i\left(n+\frac{1}{2}\right)\pm \frac{91}{32}\pi r_b^2\kappa _b^2\mathrm{}^2\left(\mathrm{}+1\right)^2\right]\mathrm{as}n\mathrm{}\mathrm{and}\mathrm{\Delta }0.$$
(24)
## III Discussion

Some commentary is, of course, in order. First of all, it is interesting to compare this last (monodromy) calculation with the spectrum obtained from the “Poschl–Teller method”  \[as depicted in equation (17)\]. We immediately see that the asymptotic spacing between the imaginary levels is correctly realized; an outcome which is, in itself, by no means trivial. On the other hand, the real part of the (asymptotic) frequency is somewhat different; in particular, take note of the quartic versus linear dependence of $`\mathrm{}`$. It is, however, possible to explain this discrepancy as follows (also see the Addendum):

It is not quite clear that equation (16) is truly the correct form of the potential that should extrapolated down to $`r=0`$. More to the point, one can always add additional terms to the potential that do not significantly alter its structure in the observable region but which would, nevertheless, dominate at the origin and, thus, make a significant contribution to the monodromy. That is to say, more care is needed in addressing the contributions from such “neglected” terms. To understand the type of analysis that might be required, one can turn to a close cousin of the monodromy calculation; namely, the WKB method of quantum mechanics. As discussed in , the Stokes and anti-Stokes lines (with three of each emanating from the $`r=0`$ singularity) need to be addressed. We will defer the fully rigorous treatment of the monodromy calculation until a later time. It does, however, seem feasible that such a treatment could still give back equation (17) \[that is, it does not appear to be the naively simple matter of just summing up the various contributions\]. Such speculation aside, the point we are really trying to make is that, as $`\mathrm{\Delta }0`$, the $`\mathrm{}`$-dependent term clearly dominates the potential so that, regardless of any neglected contributions, this $`\mathrm{}`$-dependence can not just be blatantly ignored.\**\**\**Alternatively, one might consider the quasinormal mode problem strictly in the observable region (as advocated by Born-approximation-inspired methods ), where the $`\mathrm{}`$-dependence is so evidently prominent.

Secondly, it is of interest to see how things match up when equation (24) is compared with the spectral form predicted by the (“non-degenerate”) monodromy calculation of . To reiterate, these authors obtain equation (23) but with a different expression for the index $`\nu `$. To be precise, they have found

$$\nu =\frac{1}{2}\sqrt{1+(4M\beta )^2\left(j^21\right)},$$
(25)
where $`\beta `$ is a parameter that depends strictly on $`r_b`$, $`r_c`$, $`\kappa _b`$ and $`\kappa _c`$. The philosophy of  was that the (nearly) degenerate limit could then be dealt with by directly extrapolating this non-degenerate form for the spectrum. Following this approach, one observes that the quasinormal frequencies of (nearly) degenerate Schwarzschild–de Sitter space can certainly depend on the spin, $`j`$, but definitely not on the orbital angular momentum, $`\mathrm{}`$. How can we make sense of this discrepancy in the $`\mathrm{}`$ dependence of the frequencies? Well, although a reasonable argument could be made both ways — that is to say, it is not particularly clear what is the rigorously correct limiting procedure — strong support for an $`\mathrm{}`$-dependent spectrum follows from the Poschl–Teller calculation. Significantly, this methodology — which is unambiguous and exact in the squeezed-horizon limit — implies that the real part of the frequency can depend only on $`\mathrm{}`$ and $`\kappa _b`$ when the horizons coincide.

Let us now make a couple of general observations. Firstly, we can see from the subtleties of the current case that other quasinormal mode calculations that go on to apply extremal (or near-extremal) limits should probably be viewed with a healthy dose of scepticism. Which is to say, the precise moment (in the calculation) that such a limit can safely be enforced would appear to be a subject worthy of debate. Secondly, let us re-emphasize that a strongly $`\mathrm{}`$-dependent quasinormal mode spectrum (particularly, in the real part of the highly damped frequencies) should cast significant doubt on the status of quasinormal modes in quantum gravity. (Let us recall that the real part of the frequency can be used, conjecturally speaking, to fix the spacing of the black hole area spectrum  and, by implication, the Immirzi parameter of loop quantum gravity .) It is not clear, at least to the current authors, how the fundamental quantum theory can be sensitive to the details of the perturbation field or, alternatively, why would only certain classes of horizons be susceptible to quantization?

Finally, it is worthwhile to point out another discrepancy, in the literature, which centers around the Schwarzschild–de Sitter black hole spacetime. With emphasis on a scenario of non-degenerate horizons, it has been argued (by the current authors and M. Visser  — also see ) that both the cosmological and the black hole horizon will “contribute” to the quasinormal mode spectrum. That is, we anticipate one set of modes that goes (asymptotically) as $`in\kappa _b`$ and another set that goes as $`in\kappa _c`$. Our argument is essentially that, from the perspective of an observer in this spacetime, there would be no reason to give one horizon a preferred status over the other. Hence, for a complete calculation, it would be necessary to deal with two separate scattering problems which can be distinguished by the choice of initial conditions (see the related discussion in Section II). Nonetheless, a contrary opinion has been expressed in , where it is claimed that the cosmological horizon scattering conditions would not be physically relevant. The current authors, however, can see no convincing reason why one horizon should be singled out a priori. Unfortunately, any study which focuses on the case of horizon degeneracy can offer nothing substantial to this particular argument. Hence, we have nothing to add at this time but hope to readdress the matter, by more rigorous means, in the near future.

## Addendum

It has been brought to our attention, in a response to the first archival version of the paper , that the monodromy calculation used in  is not quite correct. The main sticking point seems to be that, upon continuation to the complex plane, the generalized tortoise coordinate does not go to infinity as $`r`$ goes to $`r_c`$; thus invalidating part of the matching procedure used in . Given this breakdown, it is even less surprising that our monodromy result (24) fails to reproduce the Poschl–Teller calculation (17). It should also be emphasized that the invalidation of the original (Schwarzschild–de Sitter) monodromy analysis in no way undermines any of our prior discussion. To elaborate: in , the near-the-origin scattering potential depends on $`j`$ but not $`\mathrm{}`$, whereas our analogue depends on $`\mathrm{}`$ but not $`j`$. So, even if equation (23) \[that is, the spectrum predicted by the original monodromy calculation\] is wrong, our “corrected form” must necessarily differ from that of  in a substantial way. Namely, $`\mathrm{}`$ dependence versus no $`\mathrm{}`$ dependence.

## Acknowledgments

The authors thank M. Visser for guidance. The authors also thank K. Castello-Branco, R. Konoplya and J.P. Norman for helpful comments with regard to the first version of the paper. Research is supported by the Marsden Fund (c/o the New Zealand Royal Society) and the University Research Fund (c/o Victoria University).


text:
# The dark matter halos of spheroidal galaxies and clusters of galaxies

## 1. Introduction

Decades after the discovery of dark matter around spiral galaxies little is known about dark matter in early-type galaxies. Mass tracers at large radii (such as stellar kinematics, kinematics of globular clusters and of planetary nebulae, and X-ray halos) generally indicate that a constant mass-to-light ratio cannot reproduce the observations, although there are typically large uncertainties and a wide variety of behavior is seen. The main source of uncertainty in interpreting kinematic measures is that the derived mass profile depends on the assumed orbital structure. This is commonly referred to as the mass-anisotropy degeneracy.

The situation is even more uncertain outside the local Universe, because traditional kinematic tracers at large radii are generally not feasible at cosmological distances. However, additional constraints can be gathered by looking at early-type galaxies that are gravitational lenses. The configuration of multiple images provides information on the mass distribution of the lens; first and foremost a robust measurement of the mass enclosed within the Einstein Radius (typically larger than the effective radius), independent of its kinematic status.

The Lenses Structure and Dynamics (LSD) Survey (Koopmans & Treu 2002, 2003; Treu & Koopmans 2002a,2003; hereafter KT) is obtaining internal kinematics for a sample of of 11 relatively isolated E/S0 lens galaxies at $`z=0.041.01`$. A joint lensing and dynamical analysis is used to break the mass-anisotropy degeneracy and determine the amount and distribution of luminous and dark matter. The first results from this project are briefly summarized and discussed in Section 2.

At the cluster scale, the presence of dark matter has been known for a long time (Zwicky 1937). The distribution of dark matter has been probed over a wide range of scales using X-ray analysis, dynamical studies and gravitational lensing, showing that dark matter dominates in mass. The wealth of mass tracers in clusters – in particular the existence of giant radial arcs – makes them an ideal laboratory to test the existence of universal mass density profiles predicted by cold dark matter (CDM) simulations. Combining a lensing analysis of clusters with giant arcs with a dynamical analysis of the kinematics of the brightest cluster galaxy (BCG), we can measure very accurately the mass density profile within $`100`$ kpc, disentangle the stellar and dark matter, and pinpoint the inner logarithmic slope of the dark matter halo. This has motivated a search of suitable systems with a central dominant BCG and giant arcs through the entire HST-WFPC2 archive (Sand et al. 2004, in preparation), and the spectroscopic follow-up at Keck (Sand, Treu & Ellis 2002; Sand et al. 2003). The first results from this project are briefly summarized and discussed in Section 3.

## 2. Early-type galaxies: dark halos and cosmic evolution

Figure 1 illustrates via the lens 0047-281 ($`z=0.485`$; Warren et al. 1996) the data we are collecting as part of the LSD Survey. Archival HST imaging data (mostly from the CASTLeS collaboration) are combined with stellar kinematic data obtained using ESI at the Keck-II Telescope. In excellent conditions (seeing $`0.6^{\prime \prime }`$) it is possible to obtain a spatially resolved stellar velocity dispersion profile (hatched boxes in the right panel) out to the Einstein Radius (typically 1-2 effective radii, 1-2 arcseconds). A joint lensing and dynamical analysis is used to constrain the free parameters of a family of two-component mass models. One component represents the stellar mass and follows the HST luminosity profile scaled by a stellar mass-to-light ratio, the other component represents the dark matter halo and is modeled as a generalized Navarro, Frenk & White (1997) profile (see TK for details).

The main results from analysis of the first two objects (0047-281 and MG2016) are:

1. Extended dark matter halos are detected in high redshift E/S0 galaxies at high significance ($`>10`$ $`\sigma `$); dark matter contributes 50–75 % of the total mass within the Einstein radius.

2. The evolution of the stellar mass-to-light ratio with redshift, obtained from a two-component dynamical model, agrees with the independent estimate obtained by studying the evolution of the Fundamental Plane with redshift (Treu et al. 2002; van Dokkum & Ellis, Gebhardt et al. 2003). This is consistent with no structural or dynamical evolution of E/S0s between $`z=1`$ and today.

3. The effective slope (i.e. the average slope measured between roughly the effective and Einstein radius) of the total mass distribution is very close to isothermal, i. e. $`\rho r^\gamma ^{}`$ with $`\gamma ^{}2.0`$ (to within 5%), which we interpret as a possible indication of (incomplete) violent relaxation. This result, if confirmed by a larger sample, indicates that already at $`z1`$ there is a mechanism by which dark and luminous component conspire with each other to produce almost perfectly flat rotation curves, while still preserving their spatial segregation.

Clearly, analysis of the rest of the sample is essential to confirm and extend these findings. For example, an open question – which we intend to address and has profound cosmological implications – is understanding what is the distribution of the effective slope of total mass density profile. An intrinsic scatter is expected on the basis of local studies (e.g. Gerhard et al. 2001). It is necessary to quantify this scatter in order to estimate the uncertainties in the determination of the cosmological parameters from lens statistics, of velocity dispersion of early-type galaxies from image separation, and of the Hubble Constant from gravitational time delays. The Hubble Constant is highly sensitive to the slope of the mass density profile, and some external information is needed if one wants to measure it with precision better than a few tens of per cent. In an effort parallel to the LSD Survey, an enlarged collaboration is targeting lenses with known time-delays for spectroscopic follow-up with Keck and VLT. Although this is generally complicated by the presence of bright QSO images outshining the lens galaxy, analysis of the first two systems (Treu & Koopmans 2002a; Koopmans et al. 2003) confirms that with suitable kinematic data it is possible to measure H0 at $``$15% accuracy from each individual system, including the uncertainty on the mass density profile. We are collecting data for more systems, with the goal of measuring H0 from time-delays with precision comparable to the HST Key Project (Freedman et al. 2001).

## 3. Galaxy clusters: the inner density profile and the CDM “cusp” problem

As part of our study of the inner regions of clusters of galaxies we have measured arc redshifts and BCG stellar velocity dispersions for 6 clusters of galaxies (Figure 2; Sand et al. 2002, 2003). Three systems (upper panels) are selected to have both a radial and a tangential gravitational arc, while three systems (lower panels) are selected to have only tangential arcs. The location of the symetry break in a radial arc constrains the derivative of the enclosed mass and therefore the radial arc systems provide very tight constraints on the shape of the mass density profile. However, the radial critical line disappears when the total mass density profile becomes steeper then $`r^2`$. Therefore a radial arc selected sample may possibly be biased toward flatter mass profiles. For this reason we introduced the tangential arc only systems as a control sample.

A joint lensing and dynamical analysis is performed, fitting a family of two component mass models to the data (see Sand et al. 2003 for details). Specifically, the dark matter mass component is parametrized as a generalized NFW profile (Navarro, Frenk & White 1996,1997; Moore et al. 1998), i.e. the dark matter density goes as $`r^\beta `$ at small radii and $`r^3`$ at large radii. Numerical simulations predict $`\beta `$ in the range 1-1.5 (hereafter, respectively, NFW and Moore slopes), although numerical issues are still being debated (see Sand et al. 2003 and references therein).

Figure 3 shows the posterior probability density for $`\beta `$ for the radial (left) and tangential (right) arc samples. The radial arc sample indicates generally flat inner slopes, the average slope being inconsistent with the CDM “cusps” at more than 99.99% CL. However, intrinsic scatter is detected and individual systems can be as steep as NFW (RXJ1133). The tangential arc systems also confirm flatter slopes than $`\beta =1`$, indicating that the sample with radial arcs is unbiased.

The implications of this discrepancy could be profound. Either the CDM-only simulations are insufficiently accurate and/or contain insufficient physics to describe faithfully the inner regions of clusters. For example, baryons could play an important dynamical role driving energy and angular momentum out of the cluster core through mechanisms such as dynamical friction (e.g. El-Zant et al. 2003). Alternatively, the DM could be partially self-interacting, or manifest some interaction with the baryons (Spergel & Steinhardt 2000). Either outcome would be very exciting. On the one hand, numerical simulations are being developed which will permit the realistic inclusion of baryons. Finding mechanisms that satisfy our observational constraints will be invaluable in understanding the complex physics of star formation and dissipative processes. And of course, there is the possibility that there is some fundamental flaw in CDM which will necessitate considering more exotic scenarios, like self-interacting DM.

We are currently looking to expand our sample, drawing from the candidate radial arc systems identified from the HST-WFPC2 archive (Sand et al. 2004). This would improve our determination of the mean of $`\beta `$ and also provide a first measure of the intrinsic scatter, which is essential for any meaningful comparison with simulations, especially those that include baryons.

## 4. Acknowledgments

TT thanks the organizers for this pleasant and exciting meeting. TT thanks Eric Agol, Stefano Borgani, Amr El-Zant, Raul Jimenez, Masataka Fukugita, Jean-Paul Kneib, Ben Moore, Joel Primack, Paul Schechter, Jerry Sellwood and Simon White for stimulating conversations, during and around the Sydney Meeting. TT gratefully acknowledges support from an AAS travel grant and from HST proposals AR-09222, AR-09527, AR-09960, provided by NASA through a grant from STScI, which is operated by AURA, Incorporated, under NASA contract NAS5-26555.

## References

Freedman et al. 2001, ApJ, 553, 47

El-Zant, A. et al. 2003, ApJ, submitted, astro-ph/0309412

Gerhard, O., Kronawitter, A., Saglia, R. P., & Bender, R. 2001, AJ, 121, 1936

Gebhardt, K. et al. 2003, ApJ, in press, astro-ph/0307242

Koopmans, L.V.E. & Treu, T. 2002, ApJ, 568, L5

Koopmans, L.V.E. & Treu, T. 2003, ApJ, 583, 606

Koopmans, L.V.E., Treu, T., Fassnacht, C.D., Blandford, R.D. & Surpi G. 2003, ApJ, 599, in press

Moore, B., Governato, F., Quinn, T., Stadel, J. & Lake, G. 1998, ApJ, 499, L5

Navarro, J., Frenk, C. S., & White S. D. M 1997, ApJ, 490, 493

Sand, D.J., Treu, T. & Ellis R.S. 2002, ApJ, 574, L129

Sand, D.J., Treu, T., Smith, G.P. & Ellis, R.S. 2003, ApJ, submitted, astro-ph/0309465

Treu, T. & Koopmans, L.V.E. 2002a, ApJ, 575, 87

Treu, T. & Koopmans, L.V.E. 2002b, MNRAS, 337, L6

Treu, T. & Koopmans, L.V.E. 2003, MNRAS, 343, L29

Treu, T., Stiavelli, M., Casertano, S., Møller, P. & Bertin 2002, ApJ, 564, L13

van Dokkum, P.G. & Ellis, R.S. 2003, ApJ, 592, L53

Warren, S.J., Hewett, P.C., Lewis, G.F., Møller, P., Iovino, A., Shaver, P.A. 1996, MNRAS, 278, 139

Zwicky, F. 1937, ApJ, 82, 217