text:
# Effect of external magnetic field on electron spin dephasing induced by hyperfine interaction in quantum dots

## Abstract

We investigate the influence of an external magnetic field on spin phase relaxation of single electrons in semiconductor quantum dots induced by the hyperfine interaction. The basic decay mechanism is attributed to the dispersion of local effective nuclear fields over the ensemble of quantum dots. The characteristics of electron spin dephasing is analyzed by taking an average over the nuclear spin distribution. We find that the dephasing rate can be estimated as a spin precession frequency caused primarily by the mean value of the local nuclear magnetic field. Furthermore, it is shown that the hyperfine interaction does not fully depolarize electron spin. The loss of initial spin polarization during the dephasing process depends strongly on the external magnetic field, leading to the possibility of effective suppression of this mechanism.

The spin state of an electron confined in a semiconductor quantum dot (QD) is considered one of the most promising candidates for realizing the basic building block (i.e., qubit) of a quantum information system. Since the fundamental concept of this new paradigm relies on quantum mechanical entanglement of qubits, it is quite crucial to control spin relaxation processes that destroy the coherence of spin quantum state. So far, most of the attention has been devoted to the relaxation processes that result in irreversible loss of wave function phase due to spin-phonon interaction caused by spin-orbital coupling in solids or hyperfine interaction (HFI) in crystals with non-zero nuclei spin moments (see Refs.  and  as well as the references therein). The common feature of these spin-lattice mechanisms is that their relaxation rates are very small in QDs at low temperatures.

On the other hand, the HFI can be considered as a source of a local magnetic field $`\stackrel{}{H}_{HF}`$ acting on the electron spin that does not disappear at low (or even zero) temperature.  This particularity makes the HFI a potentially dominant mehchanism at sufficiently low temperatures. In typical QDs, a sum of the contributions from a great number of nuclei spins forms this field. Thus, the strength and the direction of the $`\stackrel{}{H}_{HF}`$ are the random variables, which vary from one QD to the next. Obviously, this dispersion can be damaging to quantum computation since electron spin precession occurs with a random phase and frequency. Nevertheless, it appears from a qualitative speculation that the role of $`\stackrel{}{H}_{HF}`$ dispersion diminishes progressively with an increasing strength of the homogeneous external magnetic field $`\stackrel{}{B}`$ applied to the array of QDs.

In this paper, we provide a quantitative analysis of electron spin evolution under the presence of an external magnetic field $`\stackrel{}{B}`$ as well as the local hyperfine field $`\stackrel{}{H}_{HF}`$. Note, that a theory of electron spin relaxation caused by HFI in a QD was recently presented in Ref. . The main interest of Khaetskii et al.  lies on the electron spin decoherence process inside a single QD when the external magnetic field is zero. It also contains a brief discussion of spin dephasing time. On the other hand, the present study concentrates on the important process of electron spin dephasing induced by HFI in an ensemble of QDs and explicitly considers the effect of external magnetic fields.

The Hamiltonian of electron spin $`S`$ in a QD containing $`N`$ nuclear spins $`I_j`$ ($`j=1,\mathrm{},N`$) takes the form ($`\mathrm{}=1`$)

$$=\omega _eS_z+\omega _n\underset{j=1}{\overset{N}{}}I_{jz}+\underset{j=1}{\overset{N}{}}A_j\stackrel{}{S}\underset{j}{\overset{}{I}},$$
(1)
where $`\omega _e`$ and $`\omega _n`$ are electron and nuclear spin splitting in a magnetic field directed along the $`Z`$ axis, $`A_j`$ is a constant of HFI with the $`j`$-th nuclear spin. The Hamiltonian of Eq. (1) is isomorphic to that, which was introduced to describe the bound magnetic polaron in diluted magnetic semiconductors. Most particularities of optical spectroscopy as well as the thermodynamics of bound magnetic polaron were successfully described by a model where differences in constants of spin-spin interaction were ignored.  By analogy with this model, we describe the dynamics of electron spin by Hamiltonian with a single effective constant $`A`$ of HFI. This allows one to express the Hamiltonian in terms of the total nuclear spin moment $`\stackrel{}{F}=_{j=1}^N\stackrel{}{I}`$:

$$=\omega _eS_Z+\omega _nF_z+A\stackrel{}{S}\stackrel{}{F}.$$
(2)
Even with such a reduced Hamiltonian, the corresponding equations for the motions of electron and nuclear spins are quite complex,

$$\frac{d}{dt}\stackrel{}{S}=\stackrel{}{B}_e\times \stackrel{}{S}+A\stackrel{}{F}\times \stackrel{}{S};$$
(3)
$$\frac{d}{dt}\stackrel{}{F}=\stackrel{}{B}_n\times \stackrel{}{F}+A\stackrel{}{S}\times \stackrel{}{F}.$$
(4)
where $`\stackrel{}{B}_e=\{0,0,\omega _e\}`$ and $`\stackrel{}{B}_n=\{0,0,\omega _n\}`$ are in units of energy. Assuming that the flip-flop processes are unimportant for the problem we consider, the $`\mathrm{\Psi }`$-function of the Hamiltonian given in Eq. (2) can be factorized with respect to electron and nuclear spins. This means that $`\stackrel{}{F}\times \stackrel{}{S}=\left[\stackrel{}{F}\times \stackrel{}{S}\right]`$, and Eqs. (3) and (4) present the closed system of equations with respect to $`S_\alpha `$ and $`F_\alpha `$ ($`\alpha =x`$, $`y`$, $`z`$).

Despite the seeming similarity of Eqs. (3) and (4), there is a significant quantitative difference in the effective fields of the nuclei acting on the electron spin $`A\stackrel{}{F}`$ and of the electron $`\frac{1}{2}A_j`$ ($`S=1/2)`$ acting on the nuclei since a large number $`N>>1`$ of nuclear spins are involved in the QD. The latter property with regard to the inequality $`\omega _e>>\omega _n`$ means a large difference in the typical precession periods for electron and nuclei spins. Thus, for a moment, we can consider the time-dependence of $`\stackrel{}{F}`$ that is given in a parametric representation. The corresponding solution of Eq. (3) with respect to $`X(t)S_X`$, $`Y(t)S_Y`$, $`Z(t)S_Z`$ and initial conditions $`X(0)=Y(0)=0`$, $`Z(0)=1/2`$ reads

$$X(t)=\frac{AF_x}{2\mathrm{\Omega }^2}(AF_z+\omega _e)(1\mathrm{cos}\mathrm{\Omega }t)+\frac{AF_y}{2\mathrm{\Omega }}\mathrm{sin}\mathrm{\Omega }t;$$
(5)
$$Y(t)=\frac{AF_y}{2\mathrm{\Omega }^2}(AF_z+\omega _e)(1\mathrm{cos}\mathrm{\Omega }t)\frac{AF_x}{2\mathrm{\Omega }}\mathrm{sin}\mathrm{\Omega }t;$$
(6)
$$Z(t)=\frac{1}{2}\frac{A^2(F^2F_z^2)}{2\mathrm{\Omega }^2}(1\mathrm{cos}\mathrm{\Omega }t).$$
(7)
The frequency of electron spin precession

$$\mathrm{\Omega }=\sqrt{A^2F^2+2AF_z\omega _e+\omega _e^2}$$
(8)
has the simple physical meaning of the Zeeman frequency of electron in the total field $`\stackrel{}{H}_e=\stackrel{}{B}_e+A\stackrel{}{F}`$ composed of external and internal nuclear fields.

Actually, the components of the total nuclear spin moment $`F_\alpha (t)`$, ($`\alpha =x`$, $`y`$, $`z`$) is affected by the external magnetic field $`\stackrel{}{B}_n`$ and the effective field of an electron $`A\stackrel{}{S}`$, which is oscillating with a high frequency $`\mathrm{\Omega }`$ near some mean value $`\overline{A\stackrel{}{S}}`$. This mean value also changes slowly with a typical nuclear frequency $`\mathrm{\Omega }_n\left|\stackrel{}{B}_n\right|+A/2`$. By taking a small interval in time $`\mathrm{\Delta }t`$ ($`<<\mathrm{\Omega }_n^1`$) to be longer than the period of electron beats (i.e., $`\mathrm{\Delta }t>>\mathrm{\Omega }^1`$), one can average over the rapidly oscillating electron contribution in Eq. (4) and arrive at a system of equations with respect to $`F_\alpha =F_\alpha (t)`$:

$$\frac{d}{dt}F_x=\omega _nF_y+A\overline{Y(t)}F_zA\overline{Z(t)}F_y;$$
(9)
$$\frac{d}{dt}F_y=\omega _nF_x+A\overline{Z(t)}F_xA\overline{X(t)}F_z;$$
(10)
$$\frac{d}{dt}F_z=A\overline{X(t)}F_yA\overline{Y(t)}F_x.$$
(11)
Here the bars mean the procedure of setting $`\mathrm{sin}\mathrm{\Omega }t`$ and $`\mathrm{cos}\mathrm{\Omega }t`$ to zero when Eqs. (5)-(7) are substituted into Eqs. (9)-(11).

Clearly, Eqs. (9)-(11) are non-linear. Fortunately, we obtain identically zero for the time-derivative $`\underset{z}{\overset{}{F}}=0`$ that provides conservation of the nuclei spin projection $`F_z`$ on the external magnetic field during the dephasing process described by Eq. (7). Thus, the dispersion of $`F=\left|\stackrel{}{F}\right|`$ and $`F_z`$, caused by the thermal fluctuation in an ensemble of nuclear spins associated with QDs, results in the dephasing of electron spin.

Mathematically, evolution of the spin polarization in an ensemble of QDs can be reduced to the problem of averaging Eq. (7) over the distribution functions for total nuclear spin \[$`P(F)`$\] and for its $`z`$-projection $`\mu F_z`$ \[$`P_z(\mu )`$\]:

$$Z(t)_T=Z(t)P_z(\mu )P(F)𝑑\mu 𝑑F.$$
(12)
The corresponding distribution functions were found in Ref.  (see also Ref. ). In the case of non-saturated nuclear spin polarization, Eq. (12) can be well approximated by the expression

$$Z(t)_T=C_0^{NI}𝑑F_F^F𝑑\mu F\mathrm{exp}(\frac{F^2}{\sigma }\frac{\omega _n\mu }{T})Z(t),$$
(13)
where $`\sigma =\frac{2}{3}I(I+1)N`$ and $`C`$ is a constant. The averaging in Eq. (13) can be performed numerically for different experimental situations. Some examples of these calculations are presented in Fig. 1 for the case of relatively high temperature $`TA\sigma \omega _n/\omega _e`$.

Two important conclusions follow immediately from Eqs. (7) and (13) (see also Fig. 1). First, electron spin dephasing does not fully relax its own initial spin polarization $`Z_0=Z(0)`$. The minimal rest $`Z_{\mathrm{}}=lim_t\mathrm{}Z(t)_T`$ of $`Z_0`$ corresponds to zero magnetic field: $`Z_{\mathrm{}}=\frac{1}{3}Z_0`$. In a strong enough magnetic field ($`B\mathrm{}`$), dephasing will be fully suppressed: $`Z_{\mathrm{}}Z_0`$. Intermediate cases can be traced with high enough accuracy if we substitute high-temperature approximations for the average values of $`\mu `$ and $`\mu ^2`$ in Eq. (13): $`\mu _T\frac{1}{3}F^2\frac{\omega _n}{T}=\frac{\sigma \omega _n}{2T}`$ and $`\mu ^2_T\frac{1}{3}F^2=\frac{\sigma }{2}`$. A more detailed approximation is of no interest since it corresponds to saturation of nuclear spin polarization along electron spin polarization that results in insignificant dephasing. The final result reads

$$Z_{\mathrm{}}=\frac{\sigma (\frac{1}{2}A^2+A\omega _e\frac{\omega _n}{T})+\omega _e^2}{\sigma (\frac{3}{2}A^2+A\omega _e\frac{\omega _n}{T})+\omega _e^2}Z_0.$$
(14)
The second conclusion is that dispersion of Zeeman frequency $`\mathrm{\Omega }`$ controls the electron dephasing rate. Hence, instead of calculating $`Z(t)_T`$ from Eq. (13), we can find the distribution function for $`\mathrm{\Omega }`$; then, the dephasing rate can be estimated as the width of this distribution. In other words, the dephasing rate can be obtained from the width of electron spin resonance lineshape

$$g(\omega )=\delta (\omega \mathrm{\Omega })P_z(\mu )P(F)𝑑\mu 𝑑F.$$
(15)
Using the definitions in Eqs. (13) and (8) as well as the new integrand variables $`x=F/\sqrt{\sigma }`$, $`y=\mu /\sqrt{\sigma }`$, Eq. (15) can be rewritten as

$$g(\omega )=C^{}\omega e^{\omega ^2\tau _0^2}\mathrm{sinh}\left[(2\omega _e\tau _0+\sqrt{\sigma }\omega _n/T)\omega \tau _0\right].$$
(16)
where $`\tau _0=1/A\sqrt{\sigma }`$. The dephasing rate $`\tau _d^1`$ is expected to be the half width of the $`1/e`$ decay in the maximal intensity of $`g(\omega )`$. Equation (16) predicts a weak dependence of $`\tau _d^1`$ on the parameter $`2\omega _e\tau _0+\sqrt{\sigma }\omega _n/T`$, which is proportional to the external magnetic field:

$$\tau _d^1=\phi (2\omega _e\tau _0+\sqrt{\sigma }\omega _n/T)\tau _0^1,$$
(17)
where the function $`\phi (x)`$ falls into the region between (0.69,1) (see Fig. 2). Thus, by the order of magnitude, $`\tau _d^1\tau _0^1=A\sqrt{\frac{2}{3}I(I+1)N}`$.

At the first glance, it would seem that the efficiency of the phase relaxation increases with the QD volume $`V_0`$ as $`\sqrt{N}=\sqrt{n_iV_0}`$, where $`n_i`$ is the concentration of isotopes with the nuclear spin $`I`$. In actuality, however, we should take into account that the constant of the contact interaction $`A`$ is proportional to the electron spin density at a nuclear site.  As a result, the rate $`\tau _d^1`$ must reveal an inverse dependence on $`\sqrt{V_0}`$.

Let us estimate the HFI constant $`A`$ in terms of ENDOR experimental data in Si:P.  According to the definition,

$$A=\frac{8\pi }{3}g_eg_n\mu _B\mu _n\left|\mathrm{\Psi }\left(\stackrel{}{r}_n\right)\right|^2\eta .$$
(18)
Here $`g_e`$ and $`g_n`$ are electron and nuclear g-factors, $`\mu _B`$ and $`\mu _n=\left(m_e/m_p\right)\mu _B`$ the Bohr and nuclear magnetons, $`m_e`$ and $`m_p`$ the electron and proton masses, $`\left|\mathrm{\Psi }\left(\stackrel{}{r}_n\right)\right|^2`$ is the electron envelope function density at a nuclear lattice site $`\stackrel{}{r}_n`$, and the parameter $`\eta `$ reflects the enhancement of electron density due to the Coulomb singularity at the nuclear core \[see, for details, Ref.  and Eq. (2.78) therein\]. In the case of $`Si^{29}`$, this parameter is $`\eta =186`$.

To find the parameter $`A`$ for QD electrons in natural Si, we can use the Feher’s experimental data  obtained for a shallow donor electron in the presence of $`Si^{29}`$ separated by $`[400]a`$ from the donor centrum ($`4a=5.43\times 10^8cm`$): $`A_{400}/2\pi \mathrm{}=7.72MHz`$. At the same time, the donor electron density $`\left|\mathrm{\Psi }\left(\stackrel{}{r}_{400}\right)\right|^2`$ calculated at this location is $`0.4\times 10^{21}cm^3`$. Then, by utilizing the functional form of Eq. (18) that is proportional to the square of the electron density, the HFI constant A at a nuclear site $`\stackrel{}{r}_n`$ can be expressed as $`A=A_{400}\left|\mathrm{\Psi }\left(\stackrel{}{r}_n\right)\right|^2/\left|\mathrm{\Psi }\left(\stackrel{}{r}_{400}\right)\right|^2`$. If a uniform envelope function is assumed inside the QD, $`\mathrm{\Psi }\left(\stackrel{}{r}_n\right)=1/\sqrt{V_0}`$, one can find $`A/2\pi \mathrm{}`$ = $`1.93kHz`$ with the QD diameter and thickness of $`500\text{Å}`$ and $`50\text{Å}`$, respectively.

Then, in terms of the uniform $`\mathrm{\Psi }`$-function approximation, we can estimate the number of isotopes $`Si^{29}`$ in a QD: $`N`$ = $`xV_0/\mathrm{\Omega }_0`$ = $`2.29\times 10^4`$, where $`x=0.0467`$ is abundance of isotopes $`Si^{29}`$ and $`\mathrm{\Omega }_0=20\text{Å}^3`$ the volume per one $`Si`$ atom. Thus, one can find $`\sigma `$ = $`\frac{2}{3}I(I+1)N`$ = $`1.14\times 10^4`$ and $`\tau _0`$=$`0.54\times 10^6`$ $`s`$.

Let us also consider the final loss of electron polarization after dephasing reaches a saturation at $`t\tau _0`$. According to Eq. (14), the relative loss of initial electron polarization $`Z_0`$ is

$$\frac{Z_0Z_{\mathrm{}}}{Z_0}=\frac{1}{3/2+(1+\epsilon )(\omega _e\tau _0)^2}$$
(19)
where $`\epsilon =\left(\sigma A/T\right)\left(\omega _n/\omega _e\right)`$. The value of $`\sigma A`$ which is independent of electron radius localization and abundance of isotopes $`Si^{29}`$ estimates to be approximately 0.025 K. Thus, with the exception of extremely low temperatures, we expect the parameter $`\epsilon `$ to be small.

We can see that Eq. (19) looks similar to that of Hanle effect  but with the opposite meaning: increasing magnetic field leads to enhancement (not suppression) of spin polarization. It reflects the competition of random field of nuclei, $`H_{HF}=\mathrm{}/g_e\mu _B\tau _0`$ (that is on the order of 0.1-1 G in the case of Si QDs), and the external magnetic field $`B`$. Accordingly, dephasing is not important if $`BH_{HF}`$. It is interesting to note that $`H_{HF}`$ can reach hundred G in QDs composed of III-V semiconductors.

In conclusion, we have considered the influence of an external magnetic field $`\stackrel{}{B}`$ on the electron phase spin relaxation in QDs. The dispersion of nuclear effective local fields $`\stackrel{}{H}_{HF}`$ over the ensemble of the QDs results in electron spin dephasing. The dephasing rate can be estimated as a spin precession frequency caused by field $`\stackrel{}{H}_{HF}`$, so it depends weakly on an external magnetic field $`\stackrel{}{B}`$ provided nuclear spin polarization (or magnetization) is not saturated. On the other hand, reduction of electron spin polarization along $`\stackrel{}{B}`$ during the dephasing process does not lead to full depolarization. If the magnetic field is suitably strong, $`BH_{HF}`$, one can expect an insignificant electron spin depolarization caused by the dephasing process considered.

The result obtained in this study is directly relevant to quantum computing with a large number of qubits (i.e., a large number of QDs containing single electrons). Clearly, random variation in the spin precession frequency and phase across the qubits is deterimental; for example, it can break/negate the initial state preparation in a relatively short time frame of approximately $`\tau _0`$. Special methods must be applied to compensate this distortion. Our work suggests an effective way to suppress the dispersion of random local fields, making QDs a more attractable candidate for quantum computing.

The work performed at North Carolina State University was supported, in part, by the Office of Naval Research and the Defense Advanced Research Projects Agency.


format: text

text:
# Luminosity Function of Morphologically Classified Galaxies in the Sloan Digital Sky Survey

## 1 Introduction

The origin of morphology of galaxies is a long-standing issue, which could provide a key to discerning among models of the formation of galaxies. How galaxy morphology changes as a function of the lookback time is perhaps the prime approach to this problem, and the knowledge of the morphological dependence of the local luminosity function at zero redshift is the baseline. One specific example of the issues is whether the luminosity function of elliptical galaxies obeys the Schechter-type function with a rather flat faint end (e.g., Marzke et al. 1994; Kochanek et al. 2001), or the Gaussian function as inferred by Binggeli, Sandage & Tammann (1988) and more recently by Bernardi et al. (2002a). If the latter is correct, one would envisage galaxy morphology as a bulge-luminosity sequence (Dressler & Sandage 1983; Meisels and Ostriker 1984), which in turn reveals a clue about the formation of elliptical galaxies and bulges.

There are also a number of uses of the morphology-dependent luminosity function (MDLF). We mention only one example: the frequency of gravitational lensing of quasar images is approximately proportional to the luminosity density of early-type galaxies rather than that of all galaxies (Fukugita & Turner 1991). The uncertainty in the MDLF is the largest source of error in predicting the frequency of gravitational lenses, and thus in inferring the cosmological constant from such analyses.

The understanding of the MDLF is significantly poorer than that of the luminosity function for galaxies in general, which has undergone substantial progress in the latest years (Folkes et al. 1999; Blanton et al. 2001) by virtue of large galaxy samples. The traditional way to obtain MDLF is to use morphological classification based on visual inspections of the images (Binggeli et al. 1988; Loveday et al. 1992; Marzke et al. 1994; 1998; Kochanek et al. 2001). Some modern studies attempt to use spectroscopic features to classify galaxies into morphological types (Bromley et al. 1998; Folkes et al. 1999), which makes it possible to analyze large samples. Although a general correlation is known between spectroscopic and Hubble morphologies, the samples derived from the two methods are considerably different. In particular, the classification using spectroscopic features or colours is sensitive to small star formation activities now or in the near past in early-type galaxies, whilst Hubble morphology is insensitive to this process. The problem of automated classification always lies in the difficulty in finding quantitative measures that strongly correlate with the Hubble sequence based on visual inspections. In this paper we derive the MDLF based on visual classifications using a homogeneous bright galaxy sample from Sloan Digital Sky Survey (SDSS; York et al. 2000). The sample we use in this paper is small, but it is based on a homogeneous morphological classification with accurate photometry.

The SDSS conducts both photometric (Gunn et al. 1998; Hogg et al. 2001; Pier et al. 2002) and spectroscopic surveys, and is producing a homogeneous data set, which is suitable to studies of galaxy statistics. The initial survey observations were made in the northern and southern equatorial stripes, and produced a galaxy catalogue to $`r^{}=22.5`$ mag in five colour bands (Fukugita et al. 1996) with a photometric calibration using a new standard star network observed at USNO (Smith et al. 2002). Spectroscopic follow-up is made to 17.8 mag with accurately defined criteria for target selection (Strauss et al. 2002).

Our study is limited to bright galaxies with $`r^{}15.9`$ mag after Galactic extinction correction, since visual classifications sometimes cannot be made confidently beyond this magnitude with the SDSS imaging data. We have classified all galaxies satisfying this magnitude criterion in the northern equatorial stripe. The total number of galaxies in our sample is 1875, of which 1600 have spectroscopic information.

The dominant part of the data we used are already published as an Early Data Release (EDR) (Stoughton et al. 2002). Our present work uses primarily the EDR but supplemented by observations which are not included in EDR to make the sample as complete as possible. Photometry of galaxies in this region is discussed in a galaxy number count paper of Yasuda et al. (2001), and the luminosity function is derived by Blanton et al. (2001), which also discuss spectroscopic details.

## 2 The sample and the morphology classification

The region of the sky we consider is the northern equatorial stripe (SDSS photometry run numbers 752 and 756) for $`145.15^{}\alpha (\mathrm{J2000})235.97^{}`$ and $`|\delta (\mathrm{J2000})|1.27^{}`$, which is included in the EDR sample. The total area is 229.7 square deg. We apply Galactic extinction correction using the extinction map of Schlegel, Finkbeiner & Davis (1998) assuming $`R_r^{}=A_r^{}/E(BV)=2.75`$, and select galaxies with the Petrosian magnitude $`r_{}^{}{}_{P}{}^{}15.9`$ after the correction in the automatically-generated photometric catalogue (Stoughton et al. 2002). We use the extinction-corrected Petrosian magnitude throughout this paper.

The photometric catalogue yields 2418 galaxy candidates with $`r_{}^{}{}_{P}{}^{}15.9`$ if we follow the criteria given in Strauss et al. (2002). This sample still contains number of double stars and shredded galaxies due to deblending failures, which cannot be rejected by the automated algorithm. We obtain after visual inspection of all galaxy candidates 1875 galaxies, of which 1600 (85%) are included in the spectroscopic sample. Spectroscopy was made using 50 plugged plates with additional 41 plates that are centred in the neighbouring stripes. These plates cover 228.1 square deg. The confidence level for the redshift determination is mostly over 99%, but 9 galaxies are given low ($`<85`$%) confidence, which we omit from our sample. We also drop 38 galaxies which either contain multiple galaxies or have poor photometry due to deblending failures. This leaves 1553 galaxies. We note that there are some galaxies which are dropped in the primary galaxy selection in the photometric catalogue (Yasuda et al. 2001; Strauss et al. 2002) due to saturation flags caused by nearby bright stars or to other reasons. We estimate that we have probably missed about $``$88 galaxies in our field from the rate of missed galaxies given in Yasuda et al. So the overall sample completeness is estimated to be 79.5%. For more detailed discussion for the spectroscopic sample, see Blanton et al. (2001).

All galaxies in our sample (1875) are classified into 7 morphological classes, $`T=0`$ (corresponding to E in the Hubble type), 1 (S0), 2 (Sa), 3 (Sb), 4 (Sc), 5 (Sd), and 6 (Im). Morphology classification is carried out by two of us (MF and ON) using the $`g^{}`$ band image of each galaxy displayed on the SAOimage viewer, according to Hubble Atlas of Galaxies (Sandage 1961). We also refer to morphological types given by the Third Reference Catalogue of Bright Galaxies (de Vaucouleurs et al. 1991; RC3), so that our classification closely matches to the traditional scheme, although the RC3 classification, which is based on the photographic material, is occasionally incorrect when galaxies are viewed with the CCD image, with which we can look at the image with different levels of brightness and contrast. We give an index of $`1`$ when we cannot assign a morphological type. The classification by the two independent visual inspections agrees to within $`\mathrm{\Delta }T1.5`$ for most galaxies and a mean (0.5 step in $`T`$) is taken for our final classification.

We reclassify galaxies into three groups of $`T`$, $`0T1.0`$ (E-S0), $`1.5T3`$ (S0/a-Sb), and $`3.5T5`$ (Sbc-Sd). The morphological distributions of the galaxies in the different samples are given in Table 1. The ratio of E-S0:S0/a-Sb:Sbc-Sd:Im $``$ 0.40:0.34:0.24:0.02. This is a somewhat larger fraction of E-S0 compared to the value usually adopted due to our use of $`r^{}`$ colour as the prime passband. For the same reason the fraction of Im galaxies is smaller by a factor of 2-3 than that from $`B`$ selected samples. In this work we do not divide the morphology into further detailed classes considering the uncertainty in visual classification, especially between E and S0 for fainter galaxies. We consider $`T>5`$ galaxies separately, since the spectroscopic target selection is biased against low surface brightness galaxies, and the relatively low quality of photometry for this class of galaxies makes the incompleteness significant; the completeness fraction of Im galaxies as read from Table 1 is only 54%, which is compared with $``$83% for other classes of galaxies. Along with a small Im fraction, our sample for an appropriate redshift range is too small to derive a reliable MDLF for Im galaxies.

## 3 Morphology-Dependent Luminosity Functions

We show in Figure 1 the differential number counts of galaxies. The slope of the counts is slightly steeper than that of the Euclidean value, and is in agreement with previous studies (Yasuda et al. 2001). The counts of spectroscopic galaxies (indicated by the dashed curve) follow those of the photometric sample within one sigma of Poisson statistics, so that the completeness correction for the sample of the present paper does not depend on brightness.

We use the recession velocity with respect to the Galactic Standard of Rest according to RC3. We select galaxies in the redshift range 3000 km s$`{}_{}{}^{1}<cz<36000`$ km s-1. The lower cutoff is imposed to avoid large effects from peculiar velocity flow, and the upper cutoff is practically the limit of our sample. We further impose a cut on apparent magnitude as $`r^{}13.2`$ mag, since very bright galaxies are often dropped from spectroscopic targets. These selections exclude 71 galaxies from our sample, leaving 1482 galaxies used to estimate the MDLF. The redshift distributions of our galaxy sample are shown in Figure 2, where the curves show expectations for a homogeneous universe with the MDLF derived in this paper.

We compute MDLFs for the samples with three methods: maximum-likelihood (ML) (Sandage, Tammann & Yahil 1979), step-wise maximum-likelihood (SWML) (Efstathiou, Ellis & Peterson 1988) and the $`V_{\mathrm{max}}`$ method. We take the step of luminosity to be 0.25 mag for SWML. We adopt $`\mathrm{\Omega }=0.3`$ and $`\lambda =0.7`$ for cosmology, although the maximum redshift of our sample is $`z=0.12`$ and the results hardly depend on the cosmological parameters. The $`K`$ correction is taken from Fukugita, Shimasaku & Ichikawa (1995) with an interpolation with respect to $`g^{}r^{}`$ colour for each galaxy.

The results from the first two methods, ML and SWML, show a good agreement, but those from the $`V_{\mathrm{max}}`$ method differ from the former two in the faint end. This is a well-known effect generally ascribed to inhomogeneous galaxy distributions in the redshift space, as are visible in Figure 2. In Figure 3 we present the MDLF from ML and SWML in the $`r^{}`$ passband, together with the absolute magnitude distribution of galaxies used in the analysis. The ML estimate assumes the Schechter function

$$\varphi (L)dL=\varphi ^{}\left(\frac{L}{L_{}}\right)^\alpha \mathrm{exp}\left[\left(\frac{L}{L_{}}\right)\right]\frac{dL}{L_{}},$$
(1)
and the derived parameters are given in Table 2, where we take the Hubble constant $`h=H_0/100`$ km s-1Mpc-1. Only a crude estimate (with ML) is presented for the luminosity function for Im galaxies, since our sample is too small. We also present the results for the total sample, which includes not only galaxies with $`T=06`$, but also those could not be classified ($`T=1`$). This is a bright-galaxy version of the analysis given by Blanton et al. (2001).

In this table we also give the luminosity densities obtained by integrating (1) over $`L=0`$ to $`\mathrm{}`$. The contours of one and two standard deviation errors calculated from the likelihood functions are shown in $`\alpha M^{}`$ plane in Figure 4. We have also carried out a jack-knife error estimate, by dividing the sample into ten RA bins (width of $``$1.2 hr), in order to study the effect of the sample variance. The best-fit values for the subsamples all fall within the one-sigma ellipse given above, and the variance estimated from the jack-knife method is smaller than the error we quoted. So we adopt one-sigma of the fit for our final error estimate.

We then assign an additional 0.05 mag error from the calibration of photometry (added in quadratures). For more discussion about errors and selection effects, see Blanton et al. (2001). The errors expected from a number of items seen in their analysis are significantly smaller than the statistical error we are concerned with here.

We determine the normalization $`\varphi ^{}`$ of the MDLF following the method of Efstathiou et al. (1988) for each sample of morphologically-classified galaxies. We adopt the region of $`M_r^{}`$ where the sample contains sufficient number of galaxies, dropping too bright ($`M_r^{}<M_r^{}^{}2`$) and faint ($`M_r^{}>M_r^{}^{}+1`$) galaxies and those with high redshifts to avoid strong shot noise effects. We choose the redshift range to be $`0.01z0.075`$, for which the selection function for the total sample is $`0.14`$. The numbers of galaxies used to determine $`\varphi ^{}`$ are given in Table 1 above. In Table 2 we give jack-knife errors for $`\varphi ^{}`$. The normalization significantly varies depending on the cutoff of the redshift range, reflecting the presence of large-scale structure, such as a clump seen between $`z=0.07`$ and 0.08 in Figure 2. The variation of the normalization by varying the upper cutoff between 0.07 and 0.08 is comparable to the jack-knife error we quoted. The normalizations (and errors) are then corrected for the sample incompleteness derived in Table 2 by comparing the spectroscopic sample with good-quality photometry and redshift determinations \[(d) in Table 1\] to the photometric sample \[(a) in Table 1\]. A small difference of areas covered by photometric and spectroscopic surveys is also taken into account. Furthermore, an extra correction factor of (1875+88)/1875=1.05 is multiplied to correct for the incompleteness of the photometric catalogue as discussed in section 2.

We can see following features in our luminosity functions:

(i) The characteristic luminosity and the faint end slope of the total sample are consistent with the parameters derived by Blanton et al. (2001) within 1$``$1.3 sigma. The normalization, however, is significantly lower, corresponding to by 30% in the luminosity density, than that of Blanton et al. This is ascribed to the local deficit of galaxies in the northern equatorial stripe seen for $`r^{}<16`$ mag, and is ascribed to large-scale structure, as discussed in Yasuda et al. (2001). We confirmed that the normalization rapidly approaches that of Blanton et al. when we take the limiting magnitude fainter; with $`r^{}<16.5`$ mag, the luminosity density agrees with that of Blanton et al. within 10%.

(ii) The characteristic luminosity of early-type galaxies is more luminous than that of later-type galaxies by about 0.45 mag. This is consistent with the ‘universal characteristic luminosity’ known for the $`B`$ band (Tammann, Yahil & Sandage 1979), because we expect that $`Br^{}`$ colour differs by 0.4 mag between E and Sb (Fukugita et al. 1995). This implies that the universal characteristic luminosity in the $`B`$ band is an accidental effect.

(iii) The shape of the luminosity function of early-type galaxies is not much different from that of late-type galaxies, although some trend is seen that the number of early-type galaxies slightly declines ($`\alpha 1`$) towards the faint end. This conclusion agrees with Marzke et al. (1994) for the $`B`$ band, and Kochanek et al. (2001) for the $`K`$ band, but does not agree with Loveday et al. (1992), which show an appreciable decline towards the faint end (see Zucca, Pozzetti & Zamorani 1994, which ascribe Loveday et al.’s result to a sample incompleteness). In particular, we do not see a sharp decline of the luminosity function, as inferred in Binggeli et al. (1988) and Bernardi et al. (2002a). The latter authors fit the luminosity function of early-type galaxies selected with photometric and spectroscopic parameters (Bernardi et al. 2002b)111These authors adopted selection criteria based on the concentration index ($`C<0.4`$; see below), the PCA spectral classification index for early-type galaxies, and the de Vaucouleurs- versus exponential-likelihood parameters which are produced from the photometric pipeline. Note that the last parameter correlates very weakly with visual morphology; see Shimasaku et al. 2001. to a Gaussian function with a peak at $`M_r^{}=20.38`$ mag ($`h=1`$): their data go beyond the peak only slightly, and the turn-over is not conclusive. Our luminosity function, which goes down to $``$18.75 mag, does not show any turnover to this magnitude.

(iv) The luminosity function of late-type spirals (Sbc-Sd) does not exhibit an increase ($`\alpha 1`$) towards the faint end. Our late-type spiral galaxy sample shows an even faster decline compared to that of early-type spiral galaxies. We found that the luminosity function derived from $`V_{\mathrm{max}}`$ shows a somewhat faster increase ($`\alpha =1.16`$) compared with those for other types, but this trend is not visible with the MDLF from the ML or SWML methods. We ascribe this larger $`\alpha `$ from the $`V_{\mathrm{max}}`$ method to a local effect of the galaxy distribution, as we mention below. In any case the steepening of the faint end slope does not occur up to the Im type. This might appear to contrast with the conventional belief that late-type galaxies have a steep slope. This is due to our exclusion of very late galaxies ($`T>5`$), and is consistent with Marzke et al. (1994), who found that only the Im luminosity function shows a steep faint end slope.

(vi) The Im type luminosity function shows a steep faint end slope, $`\alpha 1.9`$, consistent with Marzke et al.

It may be worth commenting that the absolute magnitude distributions of early- and late-type spiral galaxies shown in Figure 3 appear to indicate steeper faint end slope for the latter. This is in fact what we have obtained when we use the $`V_{\mathrm{max}}`$ method. This reflects the effect seen in Figure 2 that the morphological composition appears to change as a redshift \[i.e., the frequency of late-type spirals is high in nearby ($`z<0.05`$) sample\]. This effect disappears when we use the likelihood method to calculate the luminosity function under the assumption that it is universal.

For practical uses of the MDLF presented here, the normalization should be multiplied by a factor of 1.29 to correct for the local deficit of galaxies in the northern equatorial stripe in brighter magnitudes.

## 4 Morphological classification with the concentration index

The luminosity function of early-type galaxies we derived does not show a conspicuous decline towards the faint end. One may suspect that that our E and S0 sample may contain increasingly more dwarf ellipticals and spheroidals, which are not separated from their giant counterparts in visual classifications, towards the faint end, and therefore the luminosity function of giant elliptical galaxies might actually decline.

This point may be studied by using a concentration index, since early-type dwarfs usually have galaxy cores significantly softer than those of giant elliptical galaxies (e.g., Kormendy 1986). We define the (inverse) concentration index by the ratio of the two Petrosian radii $`C=r_{50}/r_{90}`$ measured in the $`r^{}`$ band, where $`r_{50}`$ and $`r_{90}`$ are radii which correspond to the apertures that include 50% and 90% of the Petrosian flux. In Figure 5 we plot $`C`$ as a function of absolute magnitudes for E and S0 galaxies. The plot shows that there is no evident trend that fainter early-type galaxies have softer cores; most of the data points fall below $`C<0.34`$, which is a typical value that divides early and late types, down to $``$19 mag.

Shimasaku et al. (2001) report that this $`C`$ parameter shows the strongest correlation with visually-classified morphology among simple photometrically-defined parameters (see also, Doi, Fukugita & Okamura 1993; Abraham et al. 1994; Blanton et al. 2001; Strateva et al. 2001; Bernardi et al. 2002b). We thus separate morphologies into early and late types according as $`C<0.35`$ or $`C>0.35`$, which corresponds to the devision at S0/a. The early-type galaxy sample (706 galaxies) thus defined shows a 82% completeness and is contaminated by late-type galaxies by 18% when we take the visually-classified sample as the reference. The late-type sample (713 galaxies) also shows a 82% completeness and a 18 % contamination from the opposite sample. This choice of $`C`$ minimizes the contamination of the opposite morphologies either way. The analysis is similar to what was already presented by Blanton et al. (2001), with the difference that they have used $`C=0.43`$ (which corresponds to Sb for bright galaxies) to divide the early- and late-type galaxy samples.

Figure 6 shows the MDLF separated according to this $`C`$ index. The parameters of the Schechter function from the ML analysis are given in Table 3 above. The use of a different division at $`C=0.34`$, which is about the division at S0 galaxies, changes the MDLF only slightly. The feature of the luminosity functions is similar to what are derived from the visually-classified sample. The MDLF for early-type galaxies shows a characteristic luminosity brighter than that for late-types, and has a slightly declining faint-end shape while late-type galaxies show a flat faint end. No sharp decline of the luminosity function is visible at least two mag fainter than $`M^{}`$, or at least 2 mag fainter than the peak inferred by Bernardi et al. (2002a).

Our result means that it is unlikely that the visually-classified sample is dominated by dwarf ellipticals that have soft cores in faint magnitudes. The luminosity function of late-type galaxies also shares the features of the visually-classified late-type galaxy sample. This analysis shows that the MDLFs using the concentration index are similar to those with visually-classified samples, although a somewhat smaller difference of characteristic luminosities of the two types represents the $``$20% contamination from the opposite types.

## 5 Conclusions

Our sample is small and we may not be able to extract quantitatively robust parameters, yet we obtain a number of useful conclusions. The most important feature with our analysis is that we have used a homogeneous photometric catalogue with sharply defined selection criteria and a homogeneously morphologically-classified sample based on Hubble morphology of galaxies, rather than a sample classified by indicators using spectroscopic features or colours, which are sensitive to small star formation activities in the present or the near past.

The first conclusion we have obtained is that the shape of the MDLF does not depend too strongly on the Hubble types. The characteristic luminosity of elliptical and S0 galaxies is brighter than that of spiral galaxies in the $`r^{}`$ band. The amount of the difference in brightness is consistent with universal characteristic luminosity in the $`B`$ band, which was found by Tammann et al. (1979). The MDLF of early-type galaxies somewhat declines in the faint end, but does not exhibit a sharp decline, and this is not due to an increasing mixture of dwarf galaxies at least in the magnitude range we are concerned with. The conclusion is unchanged if we use the concentration index as a classifier of early-type galaxies. This indicates that there are many intrinsically faint elliptical galaxies, whose luminosities are fainter than those of bulges in spiral galaxies. The existence of numerous early-type galaxies with a hard core at small luminosities indicates that morphology is unlikely to be a sequence of the bulge luminosity as advocated by Dressler & Sandage (1983), and by Meisels and Ostriker (1984). Our conclusion also justifies the calculation of the strong gravitational lensing frequency of quasars using the standard Schechter function without introducing a cutoff in the luminosity function, which would affect the frequency of sub-arcsecond lensing.

Funding for the creation and distribution of the SDSS Archive has been provided by the Alfred P. Sloan Foundation, the Participating Institutions, the National Aeronautics and Space Administration, the National Science Foundation, the U.S. Department of Energy, the Japanese Monbukagakusho, and the Max Planck Society. The SDSS Web site is http://www.sdss.org/. The SDSS is managed by the Astrophysical Research Consortium (ARC) for the Participating Institutions. The Participating Institutions are The University of Chicago, Fermilab, the Institute for Advanced Study, the Japan Participation Group, The Johns Hopkins University, Los Alamos National Laboratory, the Max-Planck-Institute for Astronomy (MPIA), the Max-Planck-Institute for Astrophysics (MPA), New Mexico State University, University of Pittsburgh, Princeton University, the United States Naval Observatory, and the University of Washington. We would like to thank Sadanori Okamura for useful comments. MF is supported in part by the Grant in Aid of the Japanese Ministry of Education.


text:
# On the Work of Madhu Sudan: the 2002 Nevalinna Prize Winner

## 1. Introduction

Madhu Sudan’s work spans many areas of computer science theory including computational complexity theory, the design of efficient algorithms, algorithmic coding theory, and the theory of program checking and correcting.

Two results of Sudan stand out in the impact they have had on the mathematics of computation. The first work shows a probabilistic characterization of the class NP – those sets for which short and easily checkable proofs of membership exist, and demonstrates consequences of this characterization to classifying the complexity of approximation problems. The second work shows a polynomial time algorithm for list decoding the Reed Solomon error correcting codes.

This short note will be devoted to describing Sudan’s work on probabilistically checkable proofs – the so called PCP theorem and its implications. We refer the reader to  for excellent expositions on Sudan’s breakthrough work on list decoding, and its impact on the study of computational aspects of coding theory as well as the use of coding theory within complexity theory.

Complexity theory is concerned with how many resources such as time and space are required to perform various computational tasks. Computational tasks arise in classical mathematics as well as in the world of computer science and engineering. Examples of what we may call a computational task include finding a proof for a mathematical theorem, automatic verification of the correctness of a given mathematical proof, and designing algorithms for transmitting information reliably through a noisy channel of communication. Defining what is a ‘success’ when solving some of these computational tasks is still a lively and important part of research in this stage of development of complexity theory.

A large body of Sudan’s work, started while he was working on his PhD thesis, addresses the automatic verification of the correctness of mathematical proofs. Many issues come up: how should we encode a mathematical proof so that a computer can verify it, which mathematical statements have proofs which can be quickly verified, and what is the relation between the size of the description of the theorem and the size of its shortest proof which can be quickly verified. The work of Sudan sheds light on all of these questions.

## 2. Efficient proof checking

Let us start with the classic notion of efficiently checkable proofs, which goes back to the early days of computer science in the early seventies when the NP class was defined .

###### Definition 1

The class $`NP`$ consists of those sets $`L\{0,1\}^{}`$ for which there exists polynomial time verification algorithm $`V_L`$ and polynomial $`p`$ such that $`xL`$ if and only if there exists a $`y_x\{0,1\}^{p(|x|)}`$ which makes $`V_L(x,y_x)=TRUE`$. We call $`V_L`$ the NP-verifier for the language $`LNP`$, and $`y_x`$ the NP-witness for $`x`$ in $`L`$.

One example of $`LNP`$ is the set of pairs $`(G,k)`$ where $`k𝐙`$ and $`G`$ is a graph which contain a complete subgraph on $`k`$ vertices – the so called CLIQUE problem. The NP-witness for pair $`(G,k)CLIQUE`$ is the complete subgraph in $`G`$ of size $`k`$. Another example is the set of all logical formulas for which a truth assignment to its Boolean variables exists which makes it true – the SATISFIABILITY problem. The NP-witness for a logical formula $`\varphi `$ is a particular setting of its variables which make the formula satisfiable. Graphs, logical formulas, and truth assignments can all be encoded as binary strings.

## 3. Probabilistic checking of proofs

In the eighties, extensions of the notion of an efficiently verifiable proof were proposed to address issues arising in disciplines involving interactive computation such as cryptography. The extensions incorporate the idea of using randomness in the verification process and allow a negligible probability of error to be present in the verification process. Variants of probabilistic proof systems include interactive proofs , public-coin interactive proofs , computational arguments, CS-proofs , Holographic proofs , multi-prover interactive proofs , memoryless oracles , and probabilistically checkable proofs . The latter three definitions are equivalent to each other although each was introduced under a different name.

By the early nineties probabilistically checkable proofs proofs were generally accepted as the right extension for complexity theoretic investigations. The class PCP of sets for which membership can be checked by ”probabilistically checkable proofs” is defined as follows.

###### Definition 2

Let $`L\{0,1\}^{}`$. For $`L`$ in PCP, there exists a probabilistic polynomial time verification algorithm $`V_L`$

* if $`xL`$, then there exists a $`O_x\{0,1\}^{}`$ such that $`Prob[V_L^{O_x}(x)=TRUE]>1`$
* if $`xL`$, then for all $`O_x\{0,1\}^{}`$, $`Prob[V_L^{O_x}(x)=TRUE]<\frac{1}{2}`$.

The probabilities above are taken over the probabilistic choices of the verification algorithm $`V_L`$. The notation $`V_L^{O_x}`$ means that $`V_L`$ does not receive $`O_x`$ as an input but rather can read individual bits in $`O_x`$ by specifying their locations explicitly. We call $`V_L`$ the PCP-verifier for $`LPCP`$, and $`O_x`$ the PCP-witness for $`x`$ in $`L`$.

A few comments are in order.

For each bit of $`O_x`$ read, we charge $`V_L`$ for the time it takes to write down the address of the bit to be read. The requirement that $`V_L`$ runs in polynomial time implies then that the length of the PCP-witness for $`x`$ is bounded by an exponential in $`|x|`$.

A verifier may make an error and accept incorrectly, but the probability of this event can be made exponentially (in $`|x|`$) small by running a polynomial number of independent executions of $`V_L`$ and accepting only if all executions accept. In light of the above, we argue that probabilistically checkable proofs capture what we want from any efficiently checkable proof system: correct statements are always accepted, incorrect statement are (almost) never accepted, and the verification procedure terminates quickly.

Are probabilistically checkable proofs more powerful than the deterministic NP style proofs? Developments made in a sequence of beautiful papers , finally culminated in the result of Babai et. al.  showing that indeed $`PCP=NEXPTIME`$.111 The class $`NEXPTIME`$ is defined exactly in the same manner as $`NP`$ except that the verifier $`V_L`$ has exponential time and the witness may be exponentially long.  By the separation of the non-deterministic time hierarchy, it is known that $`NP`$ is strictly contained in $`NEXPTIME`$. Thus indeed, the probabilistic checking of proofs is more powerful than the classical deterministic one (at least when the verifier is restricted to polynomial time).

Soon after the power of PCP verifiers was characterized, a finer look was taken at the resources PCP verifiers use. Two important resources in classifying the complexity of language $`L`$ were singled out : the amount of randomness used by the PCP verifier and the number of bits it reads from the PCP-witness (the latter number is referred to as the query size of $`V_L`$).

###### Definition 3

Let $`PCP(r(n),q(n))`$ denote class of sets $`LPCP`$ for which there exists a PCP verifier for $`L`$ which on input $`x\{0,1\}^n`$ uses at most $`O(r(n))`$ random bits and reads at most $`O(q(n))`$ bits of the witness oracle $`O_x`$. 222$`O(g(n)=cf(n)`$ s.t. there exists a constant $`c`$ such that $`g(n)cf(n)`$ for all $`n`$ sufficiently large$`\}`$

Obviously, $`NPPCP(0,_cn^c)`$ as an NP verifier is simply a special case of the PCP verifier which does not use any randomness. Starting with scaling down the result of  it was shown (or at least implied ) in a sequence of improvements  that $`NPPCP(\mathrm{log}n,poly(\mathrm{log}n))`$. These results successively lowered the number of bits that the PCP- verifier needs to read from the PCP-witness, but it seemed essential for the correctness of the verification procedure that this number should be a function which grows with the size of the input.

In the eighties, extensions of the notion of an efficiently verifiable proof were proposed to address issues arising in disciplines involving interactive computation such as cryptography. The extensions incorporate the idea of using randomness in the verification process and allow a negligible probability of error to be present in the verification process. Variants of probabilistic proof systems include interactive proofs , public-coin interactive proofs , computational arguments, CS-proofs , Holographic proofs , multi-prover interactive proofs , memoryless oracles , and probabilistically checkable proofs . The latter three definitions are equivalent to each other although each was introduced under a different name.

By the early nineties probabilistically checkable proofs proofs) were generally accepted as the right extension for complexity theoretic investigations. The class PCP of sets for which membership can be checked by ”probabilistically checkable proofs” is defined as follows.

###### Definition 4

Let $`L\{0,1\}^{}`$. For $`L`$ in PCP, there exists a probabilistic polynomial time verification algorithm $`V_L`$

* if $`xL`$, then there exists a $`O_x\{0,1\}^{}`$ such that $`Prob[V_L^{O_x}(x)=TRUE]>1`$
* if $`xL`$, then for all $`O_x\{0,1\}^{}`$, $`Prob[V_L^{O_x}(x)=TRUE]<\frac{1}{2}`$.

The probabilities above are taken over the probabilistic choices of the verification algorithm $`V_L`$. The notation $`V_L^{O_x}`$ means that $`V_L`$ does not receive $`O_x`$ as an input but rather can read individual bits in $`O_x`$ by specifying their locations explicitly. We call $`V_L`$ the PCP-verifier for $`LPCP`$, and $`O_x`$ the PCP-witness for $`x`$ in $`L`$.

A few comments are in order.

For each bit of $`O_x`$ read, we charge $`V_L`$ for the time it takes to write down the address of the bit to be read. The requirement that $`V_L`$ runs in polynomial time implies then that the length of the PCP-witness for $`x`$ is bounded by an exponential in $`|x|`$.

A verifier may make an error and accept incorrectly, but the probability of this event can be made exponentially (in $`|x|`$) small by running a polynomial number of independent executions of $`V_L`$ and accepting only if all executions accept. In light of the above, we argue that probabilistically checkable proofs capture what we want from any efficiently checkable proof system: correct statements are always accepted, incorrect statement are (almost) never accepted, and the verification procedure terminates quickly.

Are probabilistically checkable proofs more powerful than the deterministic NP style proofs? Developments made in a sequence of beautiful papers , finally culminated in the result of Babai et. al.  showing that indeed $`PCP=NEXPTIME`$.333 The class $`NEXPTIME`$ is defined exactly in the same manner as $`NP`$ except that the verifier $`V_L`$ has exponential time and the witness may be exponentially long.  By the separation of the non-deterministic time hierarchy, it is known that $`NP`$ is strictly contained in $`NEXPTIME`$. Thus indeed, the probabilistic checking of proofs is more powerful than the classical deterministic one (at least when the verifier is restricted to polynomial time).

Soon after the power of PCP verifiers was characterized, a finer look was taken at the resources PCP verifiers use. Two important resources in classifying the complexity of language $`L`$ were singled out : the amount of randomness used by the PCP verifier and the number of bits it reads from the PCP-witness (the latter number is referred to as the query size of $`V_L`$).

###### Definition 5

Let $`PCP(r(n),q(n))`$ denote class of sets $`LPCP`$ for which there exists a PCP verifier for $`L`$ which on input $`x\{0,1\}^n`$ uses at most $`O(r(n))`$ random bits and reads at most $`O(q(n))`$ bits of the witness oracle $`O_x`$. 444$`O(g(n)=cf(n)`$ s.t. there exists a constant $`c`$ such that $`g(n)cf(n)`$ for all $`n`$ sufficiently large$`\}`$

Obviously, $`NPPCP(0,_cn^c)`$ as an NP verifier is simply a special case of the PCP verifier which does not use any randomness. Starting with scaling down the result of  it was shown (or at least implied ) in a sequence of improvements  that $`NPPCP(\mathrm{log}n,poly(\mathrm{log}n))`$. These results successively lowered the number of bits that the PCP verifier needs to read from the PCP-witness, but it seemed essential for the correctness of the verification procedure that this number should be a function which grows with the size of the input.

## 4. The PCP theorem

In a breakthrough, which has since become known as the PCP theorem, Sudan and his co-authors characterized the class $`NP`$ exactly in terms of $`PCP`$. They showed that $`NP`$ contains exactly those languages in which a $`PCP`$-verifier can verify membership using only a constant query size and using logarithmic (in the instance size) number of coins. More over, there exists a polynomial time procedure to transform an $`NP`$-witness of $`x`$ in $`L`$ into a PCP-witness of $`x`$ in $`L`$.

###### Theorem 6

 $`NP=PCP(\mathrm{log}n,1)`$

On an intuitive level, the PCP theorem says that there exist a probabilistic verifier for proofs of mathematical assertions which can look only at a constant number of bit positions at the proof and yet with some positive probability catch any mistake made in a fallacious argument.

The proof of the PCP theorem is deep, beautiful, and quite complex. It brings together ideas from algebra, error correcting codes, probabilistic computation, and program testing.

Although the PCP theorem establishes a complexity result, its proof is algorithmic in nature, as it is a transformation of an NP-witness and a deterministic NP-verifier for $`LNP`$ into a PCP-witness and an PCP-verifier for $`L`$. As such it uses methods from the design of computer algorithms and the design of error correcting codes. Several excellent expositions of the proof appeared .

In a very strong sense, the act of transforming an NP witness into a PCP witness is similar to transforming a message into an error correcting code word. The analogy being that a code word is an encoding of a message which enables error detection in spite of noise injected by an adversary, and a PCP witness is an encoding of a proof which enables detection with high probability of an error in spite the best efforts to hide it made by a cheating pretend-to-be prover.

Yet, the act of classic decoding of a code word is very different than the act of checking the correctness of a PCP witness . Whereas in error correcting codes one attempts to recover the entire original message from the corrupted code word if too much noise has not occurred; here we only want to verify that the PCP-witness is a proper encoding of a valid NP-witness (of the same fact) which would have convinced an NP-verifier to accept. It suffices to read only a constant number of bit positions to achieve the latter task, whereas the decoding task depends on reading the entire code word.

One of the subsequent contributions of Sudan, involves constructing a new type of locally testable codes . Locally testable codes are error-correcting codes for which error detection can be made with probability proportional to the distance of the non-codeword from the code, based on reading only a constant number of (random) symbols from the received word. A related concept is that of locally decodable codes  which are error correcting codes which may enable recovery of part of the message (rather than the entire message) by reading only part of the corrupted code word.

## 5. PCP and hardness of approximation

The intellectual appeal of the PCP theorem statement is obvious. What is much less obvious and what has been the main impact of the PCP theorem is its usefulness in proving NP hardness of many approximate versions of combinatorial optimization problems. A task which alluded the theoretical computer science community for over twenty years.

Shortly after the class $`NP`$ and the companion notion of an $`NP`$-complete and NP-hard problems555 A set is $`𝒩𝒫`$-hard if any efficient algorithm for it, can be used to efficiently decide every other set in $`𝒩𝒫`$. An NP set which is NP-hard is called NP-complete. By definition, every $`𝒩𝒫`$-complete language is as hard to compute as any other.  were introduced, Karp illustrated its great relevance to combinatorial optimization problems in his 1974 paper , He showed that a wide collection of optimization problems ( including the minimum travelling salesman problem in a graph, integer programming, minimum graph coloring and maximum graph clique suitably reformulated as language membership problems) are NP-complete. Proving that a problem is NP-complete is generally taken to mean that they are intrinsically intractable as otherwise $`NP=P`$.

In practice this means there is no point in wasting time trying to devise efficient algorithms for NP-complete problems, as none exists (again if $`NPP`$). Still these problems do come up in applications all the time, and need to be addressed. The question is, how? Several methods for dealing with NP-completeness arose in the last 20 years.

One technique is to devise algorithms which provably work efficiently for particular input distribution on the instances (“average” instances ) of the NP-complete problems. It is not clear however how to determine whether your application produces such input distribution.

Another direction has been to devise approximation algorithms. We say that an approximation algorithm $`\alpha `$-approximates a maximization problem if, for every instance, it provably guarantees a solution of value which is at least $`\frac{1}{\alpha }`$ of the value of an optimal solution; an approximation algorithm is said to $`\alpha `$-approximate a minimization problem if it guarantees a solution of value at most $`\alpha `$ of the value of an optimal solution.

Devising approximation algorithms has been an active research area for twenty years, still for many NP-hard problems success has been illusive whereas for others good approximation factors were achievable. There has been no theoretical explanation of this state of affairs. Attempting to prove that approximating the solution to NP-hard problems is in itself NP-hard were not successful.

The PCP theorems of Sudan and others, starting with the work of Feige et. al. , has completely revolutionized this state of affairs. It is now possible using the PCP characterization of NP to prove that approximating many optimization problems each for different approximation factors is in itself NP-hard. The mysteries of why it is not only hard to solve optimization problems exactly but also approximately, and why different NP-hard problems behave differently with respect to approximation have been resolved.

The connection between bounding the randomness and query complexity of PCP-verifiers for NP languages and proving the NP hardness of approximation was established in  for the Max-CLIQUE problem (defined below). It seemed at first like an isolated example. The great impact of Sudan et. al.’s  theorem was in showing this was not the case. They showed that proving characterization of NP as $`PCP(logn,1)`$ implies the NP hardness of approximation for a collection of NP-complete problems including Max-3-SAT, Max-VERTEX COVER, and others (as well as improving the Max-CLIQUE hardness factor).

The basic idea is the following: A PCP type theorem provides a natural(?) optimization problem which cannot be efficiently approximated by any factor better than 2 as follows. Fix a PCP-verifier $`V_L`$ for an $`NP`$ language $`L`$ and an $`x`$. Any candidate PCP-witness $`O_x`$ for $`x`$ defines an acceptance probability of $`V_L^{O_x}(x)`$. The gap of $`1/2`$ in the maximum acceptance probability for $`xL`$ versus $`xL`$ (which exists by the definition of $`PCP`$) implies that it is NP-hard to 2-approximate the maximum acceptance probability of $`V_L`$. In other words, the existence of a polynomial time algorithm to 2-approximate the acceptance probability of $`x`$ by $`V_L`$ would imply that $`NP=P`$.

For different optimization problems, showing hardness of approximation is done by demonstrating reductions  from variants of the above optimization problem. These reductions are far more complex than reductions showing NP-hardness for exact problems as one needs to address the difference in in-approximability factors of problems being reduced to each other.

Moreover, these new NP-hardness results have brought on a surge of new research in the algorithmic community as well. New approximation algorithms have been designed which at times have risen to the task of meeting from above the approximation factors which were proved using PCP theorems to be best possible (unless $`NP=P`$) . This has brought on a meeting of two communities of researchers: the algorithm designers and complexity theorists. The former may take the failure of the latter to prove NP hardness of approximating a problem within a particular approximation factor as indication of what factor is feasible and vice versa.

This radical advance is best illustrated by way of a few examples. Finding the exact optimal solution to all of the following problems is $`𝒩𝒫`$-complete. Naive approximation algorithms existed for a long time, which no one could improve. They yield completely different approximation factors. For some of these problems we now have essentially found optimal approximation problem. Any further advancement will imply that $`NP`$ problems are efficiently solvable.

Max-CLIQUE: Given a finite graph on $`n`$ vertices, find the size of the largest complete subgraph. A single vertex solution is within factor $`n`$ of optimal. More elaborate algorithms give factor $`n^{.999}`$. This problem was the first one to be proved hard to approximate using PCP type theorem . It is now known that achieving a factor of $`n^{1ϵ}`$ is $`𝒩𝒫`$-hard for every $`ϵ>0`$ .

Max-3-SAT: Given a logical formula in conjunctive normal form with $`n`$ variables where there is at most 3 literals per clause, determine the maximal number of clauses which can be satisfied simultaneously by a single truth assignment. A simple probabilistic algorithm satisfies $`\frac{1}{2}`$ of the clauses. It is now known  that achieving a factor $`7/8ϵ`$ for $`ϵ>0`$ approximation factor is $`NP`$-hard even if the formula is satisfiable. At the same time  has shown an algorithm which matches the $`7/8`$ approximation factor when the formula is satisfiable.

Min-Set Cover: Given a collection of subsets of a given finite universe of size $`n`$, determine the size of the smallest subcollection that covers every element in the universe. A simply greedy algorithm, choosing the subsets which maximizes the coverage of as many yet uncovered elements as possible, yields a factor $`\mathrm{ln}n`$ from optimal. It is now known that approximation by a factor of $`(1ϵ)\mathrm{ln}n`$ is $`𝒩𝒫`$-hard for every $`ϵ>0`$ .

We point the reader to a collection of papers and expositions by Sudan himself  on these works as well as exciting further developments.

Madhu Sudan

Associate Professor of Electrical Engineering and Computer Science, MIT

| 1987 | B.Tech. in Computer Science, Indian Institute of Technology at New Delhi |
| --- | --- |
| 1992 | Ph.D. in Computer Science, University of California at Berkeley |
| 1992–1997 | Research Staff Member, IBM Thomas J. Watson |
|  | Research Center Mathematical Sciences Department |
| 1997 | Associate Professor, Department of Electrical Engineering and Computer Science at Massachussetts Institute of Technology |

Areas of Special Interests

Theoretical Computer Science, Algorithms, Computational Complexity, Optimization, Coding Theory.

M. Sudan (left) and S. Goldwasser