Also at ]School of Physics and Electronic Science, Guizhou Education
University, 115 Gaoxin Road, Guiyang 550018, China

# Analytical Model for Gaussian Disorder Traps in Organic Thin-Film Transistor

Qiusong Chen  [  Department of Materials Science, Fudan University, Shanghai
200433, China  Juan E. Sanchez  DEVSIM LLC, PO Box 50096, Austin, TX 78763,
USA  Dong Lin  College of Information Engineering, Jimei University, Xiamen
361021, China  Yanlian Lei  School of Physical Science and Technology,
Southwest University, Chongqing 400715, China  Guodong Zhu<EMAIL_ADDRESS>Department of Materials Science, Fudan University, Shanghai 200433, China

###### Abstract

Structural defects and chemical impurities exist in organic semiconductors
acting as trap centers for the excited states. This work presents a novel
analytical model to calculate the trapping and detrapping rates between two
Gaussian density of states. Miller-Abrahams rate and Fermi–Dirac statistics
are employed in this model. The introduction of effective filled and empty
sites for correlated bands greatly simplifies the expression of recombination
rate. A technology computer-aided design simulator-DEVSIM was used to simulate
the donor-like traps in an organic semiconductor DPP-DTT based thin-film
transistor, showing good agreement with the measured transfer characteristic.

##  I Introduction

Organic semiconductors are a class of promising materials for high-efficiency
[1], low-cost [2], flexible [3], and multi-functional [4] electronic devices.
The trap states induced by the chemical impurities and structural defects in
organic semiconductors play a critical role in electric performance.

For example, chemical impurities have been doped in host materials as guest
molecules to improve the electroluminescence in light-emitting diodes [5, 6]
and to enhance the light absorption efficiency in dye sensitized solar cells
[7, 8]. Other reports directly utilized the physics of trap states to build
memories and sensors [9, 10, 11].

However, the applications of organic semiconducting materials in different
areas are restricted by the trap states for the following two reasons: 1) the
traps can serve as unintentional recombination centers in light-emitting
diodes and solar cells [12, 13], 2) carrier transport is also localized by
chemical impurities and structural defects, resulting in carrier mobilities
far below the theoretical prediction [14, 15]. The study of trap related
mechanisms is therefore crucial in extracting theoretical performance limits
of organic semiconductors. Still many questions and challenges need to be
addressed before engineering high-performance electronic devices.

In order to clarify the underlying mechanisms of trap related physics, several
numerical methods have been proposed. The simplest approach included several
discrete energy depths for traps, assuming that the trapping and detrapping
rates are standard first order deferential equations with time[16, 17].
However, the trap states in organic semiconductors are dominated by continuous
energy distributions [18, 11]. Several works employed Gaussian distribution of
exponential functions for trap levels to analyze the field-induced detrapping
and thermal aging effects in organic semiconductors [19, 17, 20]. These works
were mostly based on the master equation approach or Monte Carlo
simulation[21, 19]. However, both approaches are time-consuming methods for
device simulation [19]. Hence, a more efficient and versatile approach is
desired to explore the trap related kinetics.

In this study, we demonstrate a new method to analyze the charge generation
(trapping) and recombination (detrapping) rate between two Gaussian density of
states (DOS), by combining the Fermi–Dirac statistics with Miller-Abrahams
equation [22] Two variables of effective filled site (EFS) and effective empty
site (EES) are defined in the expression of detrapping rate to simplify the
algorithm complexity. Then, this method is applied to the understanding of the
highest occupied molecular orbit (HOMO) and the donor-like trap (DLT) states
in a Poly[2,5-(2-octyldodecyl)-3,6-diketopyrrolopyrrole-
alt-5,5-(2,5-di(thien-2-yl)thieno [3,2-b]thiophene)] (DPP-DTT) [23] based
organic thin-film transistor(OTFT). The simulated results demonstrated by a
technology computer-aided design (TCAD) platform of DEVSIM [24] show good
agreement with the measured transfer characteristic. This model can also be
applied to other types of traps in organic electronic materials, such as
acceptor-like traps.

##  II Modeling

In both organic and inorganic materials, the energetic distribution of trap
states is typically approximated by a Gaussian function with a standard
energetic deviation or an exponential function with a modified characteristic
temperature [11, 25, 20, 26, 18]. The Gaussian function is a better choice to
describe the limited nature of trap density.

Because of the less crystallized structure in organic materials, the energetic
disorder of conductive bands in organic semiconductors are typically also
given by Gaussian DOS [27]. Unlike the inorganic crystalline structure, there
is no clear boundary between the allowed band and the forbidden band [28].
Boltzmann statistics is therefore not a proper approximation for the states in
amorphous organic semiconductors [28] and Fermi–Dirac statistics should be
employed to calculate the average number in a single-particle state [29].

The charge transition model, including trapping and detrapping, between
various energy levels in organic semiconductors must be treated differently
from inorganic crystals. In the following context, we employ Gaussian DOS to
describe energy statistics for both of HOMO and DLT , and then use Miller-
Arbrhams rate and Fermi–Dirac statistics to describe the charge transition
between these two energy levels.

###  II.1 The Gaussian DOS for HOMO and DLT

Figure 1: The diagrams of filling states in Gaussian DOS for HOMO and DLT

The Gaussian DOS for HOMO ($g_{H}$) of organic materials is as follows :

$g_{H}(E_{H},E_{Hc},\sigma_{H})=\frac{N_{H}}{\sigma_{H}\sqrt{2\pi}}\exp(-\frac{(E_{H}-E_{Hc})^{2}}{2\sigma_{H}^{2}})$
(1)

where ${E_{H}}$ is an energy level of a specific state in HOMO. $N_{H}$,
$\sigma_{H}$, and $E_{Hc}$ are the total density, the distribution width, and
energy center of HOMO DOS, respectively. In the following content, we will use
$g_{H}(E_{H})$ as a shorthand for $g_{H}(E_{H},E_{Hc},\sigma_{H})$.

The black solid curve in Fig. 1(a) represents the Gaussian distribution for
HOMO DOS and the empty sites in it. In addition, a hole is defined to be the
remaining delocalized positive charge after an electron escapes form a HOMO
site, whose density is:

$p=\int_{-\infty}^{\infty}g_{H}(E_{H},E_{Hc},\sigma_{H})(1-f(E_{H},E_{f}))dE_{H}$
(2)

in which $f(E,E_{f})$ is Fermi–Dirac statistics and it reads:

$f(E,E_{f})=\frac{1}{e^{\frac{(E-E_{f})}{k_{B}T}}+1}$ (3)

where $E_{f}$, $k_{B}$, $T$ are Fermi energy level, Boltzmann’s constant, and
the absolute temperature, respectively.

It should be noted that, only in the equilibrium state, different bands in the
system share the same Fermi level. Otherwise, in the non-equilibrium state,
every band has its own Fermi level to describe the overall occupation of the
sites [30]. In such condition, this energy level is termed as quasi Fermi
level. As the trapping and detrapping processes typically occur in a non-
equilibrium state, we should use quasi Fermi level of different bands in the
following context, i.e. $E_{Hf}$ for HOMO and $E_{Df}$ for DLT.

The trapped charges consist of both donor-like and acceptor like states across
the forbidden energy gap [31]. Then, the DOS for deep-level DLT is in the same
manner of Gaussian distribution:

$g_{D}(E_{D},E_{Dc},\sigma_{D})=\frac{N_{D}}{\sigma_{D}\sqrt{2\pi}}\exp(-\frac{(E_{D}-E_{Dc})^{2}}{2\sigma_{D}^{2}})$
(4)

where ${E_{D}}$ is an energy level of a specific state in DLT. $N_{D}$,
$\sigma_{D}$, and $E_{Dc}$ are the total density, the distribution width, and
energy center of DLT DOS, respectively. In the following content, we will use
$g_{D}(E_{D})$ as a shorthand for $g_{D}(E_{D},E_{Dc},\sigma_{D})$.

The black solid curve in Fig. 1(b) represents the Gaussian distribution for
DLT and the empty sites in it. Since the DLT site is neutral if occupied by an
electron and positively charged if empty, the density of trapped charge
corresponds to the empty sites. Then the trap density reads:

$p_{D}=\int_{-\infty}^{\infty}g_{D}(E_{D},E_{Dc},\sigma_{D})(1-f(E_{D},E_{Df}))dE_{D}$
(5)

###  II.2 Miller-Abrahams Equation

To describe the transition rate of electrons from one site with energy level
of $E_{i}$ to another site with $E_{j}$ , we employ Miller-Abrahams rate [22,
19], which reads:

$v_{ij}=v_{0}\exp(-2\frac{R_{ij}}{a_{i}}-\frac{E_{j}-E_{i}+|E_{j}-E_{i}|}{2k_{B}T})$
(6)

where $v_{0}$ is attempt frequency, $a_{i}$ is the localization scale of
initial state, $R_{ij}$ is the distance between both states.

###  II.3 Trapping Process

For the trapping process, the electron jumps from a neutral DLT site to an
empty HOMO site. Here, we assume that all states of DLT are higher than HOMO,
because Gaussian distributed DLT are deep-level bands [31]. Then by
integrating the transition rates of all electrons in DLT to all empty site in
HOMO, we can get the total rate of trapping. Fig. 2 exhibits this process.
Hence, the overall trapping rate reads:

$\displaystyle k_{T}=\iint_{-\infty}^{\infty}$ $\displaystyle
v_{DH}g_{D}(E_{D})f(E_{D},E_{Df})$ (7) $\displaystyle
g_{H}(E_{H})(1-f(E_{H},E_{Hf}))dE_{D}dE_{H}$

where $E_{D},E_{H}$ are two energy sites located on DLT and HOMO,
respectively. $v_{DH}$ is Miller-Abrahams rate for electron transition form
site of $E_{D}$ to $E_{H}$. It reads :

$v_{DH}=v_{0}\exp(-2\alpha_{D}R_{DH})$ (8)

where $\alpha_{D}$ is the inverse localization scale of DLT site, $R_{DH}$ is
the average distance from HOMO sites to DLT sites.

Figure 2: The diagrams of electron’s trapping process from the neutral sites
in DLT to the empty sites in HOMO. $p$ and $n_{H}$ are the empty sites(holes)
and the filled sites in HOMO DOS. $n_{D}$ and $p_{D}$ denote the filled and
the empty sites in DLT DOS

After separating variables, the above expression can be simplified as:

$k_{T}=v_{DH}n_{D}p$ (9)

in which $n_{D}$ is the filled sites in DLT. It is illustrated as the orange
area in Fig. 2 and reads:

$\displaystyle n_{D}$
$\displaystyle=\int_{-\infty}^{\infty}g_{D}(E_{D},E_{Dc},\sigma_{D})f(E_{D},E_{Df})dE_{D}$
(10) $\displaystyle=N_{D}-p_{D}$

###  II.4 Detrapping Process

For the detrapping process, the electron jumps from a filled HOMO site to an
empty DLT site as indicated by the red solid arrow in Fig. 3. Then by
integrating all electrons in HOMO to all empty sites in DLT, we can get the
total rate of detrapping. So the detrapping rate reads:

$\displaystyle k_{D}=\iint_{-\infty}^{\infty}$ $\displaystyle
v_{HD}g_{H}(E_{H})f(E_{H},E_{Hf})$ (11) $\displaystyle
g_{D}(E_{D})(1-f(E_{D},E_{Df}))dE_{H}dE_{D}$

where $v_{HD}$ is Miller-Abrahams rate for electron’s transition form the site
of $E_{H}$ in HOMO to $E_{D}$ in DLT. $v_{HD}$ reads:

$v_{HD}=v_{0}\exp(-2\frac{R_{DH}}{a_{H}}-\frac{E_{D}-E_{H}}{k_{B}T})$ (12)

where $a_{H}$ is the average localization scale of HOMO site.

Using the following replacement:

$v_{HD0}=v_{0}\exp(-2\alpha_{H}R_{DH})$ (13)

the expression of Eq. (11) can be rewritten as :

$\displaystyle k_{D}=\iint_{-\infty}^{\infty}$ $\displaystyle
v_{HD0}\exp(-\frac{E_{D}-E_{H}}{k_{B}T})g_{H}(E_{H})f(E_{H},E_{Hf})$ (14)
$\displaystyle g_{D}(E_{D})(1-f(E_{D},E_{Df}))dE_{H}dE_{D}$

Figure 3: The diagrams of electron’s detrapping process from HOMO to the empty
sites in DLT. $n_{H}$ is the actual filled sites and $n_{H}^{{}^{\prime}}$ is
the effective filled sites in HOMO. $p_{D}$ is actual empty sites and
$p_{D}^{{}^{\prime}}$ is the effective empty sites in DLT

###  II.5 Effective Empty and Filled Sites

Eq. (14) has one more exponential terms than Eq. (7), but it can still be
simplified by the method of separation of variables. Here, we define two
parameters of $E^{{}^{\prime}}_{Hc}$ and $E^{{}^{\prime}}_{Dc}$ as effective
energy centers for HOMO and DLT DOS, respectively. The expressions of two
effective energy centers are:

$E^{{}^{\prime}}_{Hc}=E_{Hc}+\frac{\sigma_{H}^{2}}{k_{B}T}$ (15)
$E^{{}^{\prime}}_{Dc}=E_{Dc}-\frac{\sigma_{D}^{2}}{k_{B}T}$ (16)

Fig. 3 illustrate the energy shift of $E^{{}^{\prime}}_{Hc}$ and
$E^{{}^{\prime}}_{Dc}$ with respect to $E_{Hc}$ and $E_{Dc}$, respectively. By
introducing effective energy centers for both HOMO and DLT levels, Eq. (14)
can be rewritten as :

$\displaystyle k_{D}=$ $\displaystyle
c_{E}v_{DH0}\iint_{-\infty}^{\infty}g_{H}(E_{H},E^{{}^{\prime}}_{Hc},\sigma_{H})f(E_{H},E_{Hf})$
(17) $\displaystyle
g_{D}(E_{D},E^{{}^{\prime}}_{Dc},\sigma_{D})(1-f(E_{D},E_{Df}))dE_{H}dE_{D}$

in which $c_{E}$ reads:

$c_{E}=\exp(\frac{\sigma_{H}^{2}+\sigma_{D}^{2}}{2k_{B}^{2}T^{2}}+\frac{E_{Hc}-E_{Dc}}{k_{B}T})$
(18)

Compared with Eq. (7), Eq. (17) can also be simplified to a product form like
Eqs. (9):

$k_{D}=c_{E}v_{DH0}n_{H}^{{}^{\prime}}p^{{}^{\prime}}_{D}$ (19)

in which $n_{H}^{{}^{\prime}}$ reads:

$n_{H}^{{}^{\prime}}=\int_{-\infty}^{\infty}g_{H}(E_{H},E^{{}^{\prime}}_{Hc},\sigma_{H})f(E_{H},E_{Hf})dE_{H}$
(20)

and $p^{{}^{\prime}}_{D}$ reads:

$p_{D}^{{}^{\prime}}=\int_{-\infty}^{\infty}g_{D}(E_{D},E^{{}^{\prime}}_{Dc},\sigma_{D})(1-f(E_{D},E_{Df}))dE_{D}$
(21)

Because Eqs. (20) and (21) are similar to Eqs. (10) and (5), respectively, we
define $n_{H}^{{}^{\prime}}$ as EFS for HOMO and $p^{{}^{\prime}}_{D}$ as EES
for DLT.

So far, we used both Fermi-Dirac statistics and Miller-Abrahams equation to
derive the trapping and detrapping rates of DLT in the Gaussian energetic
disorder semiconductors. The calculation complexity caused by the barrier in
the detrapping process was reduced by virtue of introducing EFS and EES for
the correlated bands. Then the detrapping rate is simplified from a
sophisticated integral expression (Eq. (11)) to a concise product form (Eq.
(19)). The black dot arrow in Fig. 3 indicates the simplified detrapping
picture. In the following section, we will analyze the relationship between
different parameters and variables in this model. Then, this model was
employed to simulate a DPP-DTT based transistor with a bottom-gate/ top-
contact configuration.

##  III Data ANALYSIS

###  III.1 Parameters and Variables

Figure 4: (a) Dependencies of $c_{E}$ on barrier height ($E_{Dc}-E_{Hc}$) at
various temperature. All Gaussian widths for these lines are fixed at 0.11 eV.
(b) Dependencies of $c_{E}$ on one band width of Gaussian HOMO or DLT DOS at
various temperature. The barrier height for these curves are set to 0.25 eV.

In the above content, the trapping and detrapping rates are reduced to the
product forms in Eq. (9) and (19). The coefficient $v_{DH}$ for trapping in
Eq. (9) reflects the impacts of orbit localization in DLT and spacial distance
from HOMO to DLT. The other two variables are the filled electrons in DLT
($n_{D}$) and the empty sites in HOMO ($p$). But for the detrapping rate,
there’s an extra coefficient of $c_{E}$ in Eq. (19). Fig. 4 (a) and (b)
present the dependence of $c_{E}$ on the barrier height and the band width of
Gaussian DOS. In Fig. 4 (a), $c_{E}$ shows a dramatically exponential decay
with respect to the barrier height between the Gaussian centers of HOMO and
DLT. This feature intuitively describes the physical role of energy barrier.
However, there are two results to note: ①, most of $c_{E}$ values within the
range shown in Fig. 4 is greater than 1; ② the range of $c_{E}$ decreases with
device temperature for in both Fig. 4 (a) and (b). Both results are
inconsistent with Miller-Abrahams rate in Eq. (6), because the detrapping rate
should be reduced by the energy barrier ($c_{E}<1$) and enhanced with higher
temperature. So, the attenuation effect of the potential barrier on detrapping
process will act more on EES and EFS. in Eq. (19).

Figure 5: (a) Dependencies of $n^{{}^{\prime}}_{H}$ on $n_{H}$ of various band
width for Gaussian HOMO DOS at $300K$. (b) Dependencies of
$p_{D}^{{}^{\prime}}$ on $p_{D}$ for various band width of Gaussian DLT DOS at
$300K$. The total density for HOMO and DLT DOS are $1.2\times 10^{21}cm^{-3}$
and $1.0\times 10^{19}cm^{-3}$, respectively.

Fig. 5 presents the dependence of EES and EFS on the actual charge density of
$n_{H}$ in HOMO and $p_{D}$ in DLT, respectively. These data are obtained by
Paasch’s method about the Gauss–Fermi integral [27]. It can be observed from
Fig. 5 (a) that the $n^{{}^{\prime}}_{H}$ relationship with the $n_{H}$
asymptotically reaches a slope equal to 1 in the log-log plot for small
densities. And, the $p^{{}^{\prime}}_{D}$ relationship with the $p_{D}$
presents the same manner. In this region, the values of $n^{{}^{\prime}}_{H}$
and $p^{{}^{\prime}}_{D}$ are $5\sim 15$ orders of magnitude smaller than
$n_{H}$ and $p_{D}$ , respectively. The magnitude of difference increases with
the Gaussian DOS widths, because the energy shift of $E^{{}^{\prime}}_{Hc}$
and $E^{{}^{\prime}}_{Dc}$ increases with these two widths in Eqs. (15) and
(16). However, these magnitude differences decrease when $n_{H}$ and $p_{D}$
become saturated. So the slop of these curves becomes very steep in these
regions in both Fig. 5 (a) and (b). Such phenomenon reflects the saturation
characteristic of the Gaussian distribution. Take the Gaussian HOMO DOS as
example, the quasi Fermi level is the only variable of EFS’ expression in Eq.
(21). So, while the actual filled sites in HOMO DOS are saturated, the raised
effective energy center of $E^{{}^{\prime}}_{Hc}$ makes EFS increase
obviously.

###  III.2 TCAD Simulation for OTFT

In organic semiconductors, the surface trap density is more prominent than the
bulk trap density. A device with active region on the surface is therefore an
appropriate application to validate this method. And OTFT meats this criteria,
because the conductive channel is located in the interface area of
semiconductors.

In the following content, we demonstrate our model in a TCAD simulation of an
OTFT device with the bottom-gate/top-contact configuration. The simulation
parameters and device dimensions are listed in Table 1. The DEVSIM [24] TCAD
simulator was employed to realize a finite volume method (FVM) analysis. The
typical TCAD approach of drift-diffusion model solves three equations:

#### The Poisson equation:

$-\nabla(\varepsilon_{r}\varepsilon_{0}\nabla\psi)=e\cdot(p-n+p_{D})$ (22)

where $\psi$ is electrical potential, $\varepsilon_{0}$ is the permittivity of
vacuum, $\varepsilon_{r}$ is the relative permittivity of the organic
material, and $e$ is the elementary charge.

#### Hole Continuity Equation:

$\frac{\partial p}{\partial t}=\nabla(p\mu_{p}\nabla\psi+D_{p}\nabla p)+G_{p}$
(23)

where $\mu_{p}$, $D_{p}$ and $G_{p}$ are the mobility, diffusion coefficient
and net generation rate for holes, respectively.

#### Electron Continuity Equation:

$\frac{\partial n}{\partial t}=\nabla(-n\mu_{n}\nabla\psi+D_{n}\nabla
n)+G_{n}$ (24)

where $\mu_{n}$, $D_{n}$ and $G_{p}$ are the mobility, diffusion coefficient
and net generation rate of electrons, respectively.

To calculate the variance of DLT density over time, an extra equation for the
net generation rate of DLT is solved simultaneously with the above three
equations. The net generation rate of DLT reads:

$\frac{\partial q_{D}}{\partial t}=k_{T}-k_{D}$ (25)

Table 1:  The parameters used to simulate the DPP-DTT based OTFT if not explicitly stated elsewhere.  Model | Symbol | Value | Unit
---|---|---|---
Device temperature | $T$ | $300$ | K
Total density for HOMO [32] | $N_{H}$ | $1.2\times 10^{21}$ | cm-3
HOMO DOS width [29, 30] | $\sigma_{H}$ | 0.13 | eV
HOMO DOS center [33] | $E_{Hc}$ | -5.2 | eV
LUMO DOS center [33] |  | -3.5 | ev
Total density for DLT [11] | $N_{Ds}$ | $1.0\times 10^{13}$ | cm-2
DLT DOS width | $\sigma_{D}$ | 0.11 | eV
DLT DOS center | $E_{Dc}$ | 3.81 | eV
Trap thickness | $d_{D}$ | 3 | nm
Average distance between |  |  |
HOMO and DLT | $R_{DH}$ | 5 | nm
Localization length |  |  |
for HOMO and DLT[19] | $a_{i}$ | 0.5 | nm
Attempt frequency[19] | $v_{0}$ | 1 | s-1
DPP-DTT thickness |  | 40 | nm
Insulator’s thickness |  | 300 | nm
OTFT channel length |  | 100 |  $\mu$m
Relative permittivity |  |  |
for DPP-DTT | $\varepsilon_{r\\_Semi}$ | 4 |
Relative permittivity |  |  |
for Insulator SiO2 | $\varepsilon_{r\\_SiO_{2}}$ | 3.9 |
Thermionic emission velocity |  |  |
at source and drain [34] |  | $10^{7}$ | cm/s

As our method is based on the bulk density of DLT, we convert the total
surface trap density to the total bulk density through an exponential decay
relationship with depth:

$N_{D}=\frac{N_{Ds}}{d_{D}}\exp(-\frac{x}{d_{D}})$ (26)

where $x$ is the depth from the insulator-semiconductor interface to the
semiconducting layer, $d_{D}$ is the characteristic thickness of DLT. The
values for these parameters are listed in Table 1. Integrating Eq. (26) on the
depth in semiconductor layer, the sum of bulk density is consistent with
surface density.

Here, we assume there is only one kind of trap. So, in Eq. (22), the total
charges in Poisson’s equation include three parts: holes, electrons and DLT.
As the organic OTFT works in the accumulation regime for on-state and
depletion regime for off-state, we take only the electron’s transition between
HOMO and DLT in consideration. Then, we can get the following two results:

$G_{p}=-(k_{T}-k_{D})$ (27) $G_{n}=0$ (28)

For the carriers transport, we use the macroscopic conductivity model for
holes [35, 15] and Poole–Frenkel model for electrons [31]. Then, a typical
model for Schottky contacts is considered on source and drain [36]. The
thermionic emission velocity for holes and electrons is listed in Table. 1.
The initial equilibrium was solved while $k_{T}$ equal to $k_{D}$.

##  IV Experiment and Simulation Results

Figure 6: (a) Schematic of the OTFT structure and layer composition. (b)The
simulated DLT charge density versus gate bias. (c) The comparison of transfer
characteristic between simulated and measured results. The arrows in (b) and
(c) denote the sweeping direction of gate bias.

To examine our method, we fabricated a bottom-gate/ top-contact OTFT by using
DPP-DTT as active layer. Fig. 6 (a) demonstrates the device structure. The
architecture details are listed in Table. 1. The DPP-DTT is an excellent
p-type organic semiconductor material with high carrier mobility and stable
chemical structure [23]. Its energy levels are listed in Table. 1. For the
fabrication procedure, we first deposited its 5mg/ml chlorobenzene solution
via spin-coating on a octyltrichlorosilane (OTS-8) treated Si/SiO2 substrate.
Then, 100nm gold layers were thermal evaporated using a shadow mask as source
and drain electrodes. The electrical measurements for this OTFT was carried
out by a Keithley 4200 semiconductor analyzer in atmosphere. The source
contact was grounded and the drain bias was set to -15 V. The gate bias was
first swept forwardly from 50 V to -100 V, then swept back to 50 V. The
sweeping speed of gate bias was 10 V/s.

Both measured and simulated results are showed in Fig. 6 (b) and (c). All of
simulation parameters are listed in Table 1. In Fig. 6(b), the DLT charges
increase while the device is driven to hole accumulation regime with enough
negative gate bias. But as a nonequilibrium process, the trap concentration
did not synchronize with the gate bias. The maximum point for DLT charges
occurs around -60 V while sweeping the gate bias back to 50V. Fig. 6(c)
presented the simulated and measured transfer characteristic curves. Due to
the accumulation of trapped DLT charges, the drain current in backward scan is
smaller than that in forward scan. So, the Transfer curves present an anti-
clockwise hysteresis loop and the threshold voltage shifts about -16 V in the
backward scan.

##  V Conclusion and Future Work

We have combined theoretical framework of the trapping and detrapping pictures
in organic semiconductors that comprise two Gaussian DOSs. Through the
introducing of EES for DLT and EFS for HOMO, both trapping and detrapping
expression were reduced to two simple product forms. This model is
demonstrated in a FVM based device simulator. To verify this model, we
fabricated a DPP-DTT based TFT with bottom-gate/ top-contact configuration.
The good agreement of the simulated and experimental results testify the
reasonability of this model. A more detailed analysis on charge trapping is a
subject for further investigation.

## Acknowledgements

This work is granted by the Natural Science Foundation of Guizhou Province
(No. QKHJC-ZK[2021]YB329 and QKHJC-ZK[2021]YB018). We thanks Mr. Wenxuan Qiu
for his language support.

## References

  * Congreve  _et al._ [2013] D. N. Congreve, J. Lee, N. J. Thompson, E. Hontz, S. R. Yost, P. D. Reusswig, M. E. Bahlke, S. Reineke, T. Van Voorhis, and M. A. Baldo, “External quantum efficiency above 100singlet-exciton-fission-based organic photovoltaic cell,” Science 340, 334–337 (2013).
  * Lin  _et al._ [2017] F. J. Lin, C. Guo, W. T. Chuang, C. L. Wang, Q. Wang, H. Liu, C. S. Hsu, and L. Jiang, “Directional solution coating by the chinese brush: A facile approach to improving molecular alignment for high-performance polymer tfts,” Adv Mater 29 (2017), 10.1002/adma.201606987.
  * Zhao  _et al._ [2017] Q. Zhao, H. Wang, Z. Ni, J. Liu, Y. Zhen, X. Zhang, L. Jiang, R. Li, H. Dong, and W. Hu, “Organic ferroelectric-based 1t1t random access memory cell employing a common dielectric layer overcoming the half-selection problem,” Adv Mater 29 (2017), 10.1002/adma.201701907.
  * Pandey and Nunzi [2007] A. K. Pandey and J.-M. Nunzi, “Rubrene/fullerene heterostructures with a half-gap electroluminescence threshold and large photovoltage,” Advanced Materials 19, 3613–3617 (2007).
  * Gross  _et al._ [2000] M. Gross, D. C. Müller, H.-G. Nothofer, U. Scherf, D. Neher, C. Bräuchle, and K. Meerholz, “Improving the performance of doped $\pi$-conjugated polymers for use in organic light-emitting diodes,” Nature 405, 661–665 (2000).
  * Pfeiffer  _et al._ [2003] M. Pfeiffer, K. Leo, X. Zhou, J. Huang, M. Hofmann, A. Werner, and J. Blochwitz-Nimoth, “Doped organic semiconductors: Physics and application in light emitting diodes,” Organic Electronics 4, 89–103 (2003), high Efficiency Light Emitters.
  * Hagfeldt  _et al._ [2010] A. Hagfeldt, G. Boschloo, L. Sun, L. Kloo, and H. Pettersson, “Dye-sensitized solar cells,” Chemical reviews 110, 6595–6663 (2010).
  * Paci  _et al._ [2006] I. Paci, J. C. Johnson, X. Chen, G. Rana, D. Popovic, D. E. David, A. J. Nozik, M. A. Ratner, and J. Michl, “Singlet fission for dye-sensitized solar cells: Can a suitable sensitizer be found?” Journal of the American Chemical Society 128, 16546–16553 (2006).
  * Ya-Chin, Tsu-Jae, and Chenming [2001] K. Ya-Chin, K. Tsu-Jae, and H. Chenming, “Charge-trap memory device fabricated by oxidation of si/sub 1-x/ge/sub x,” IEEE Transactions on Electron Devices 48, 696–700 (2001).
  * Lin, Lee, and Chen [2012] H.-W. Lin, W.-Y. Lee, and W.-C. Chen, “Selenophene-dpp donor–acceptor conjugated polymer for high performance ambipolar field effect transistor and nonvolatile memory applications,” J. Mater. Chem. 22, 2120–2128 (2012).
  * Haneef, Zeidell, and Jurchescu [2020] H. F. Haneef, A. M. Zeidell, and O. D. Jurchescu, “Charge carrier traps in organic semiconductors: a review on the underlying physics and impact on electronic devices,” Journal of Materials Chemistry C 8, 759–787 (2020).
  * Street  _et al._ [2010] R. A. Street, M. Schoendorf, A. Roy, and J. H. Lee, “Interface state recombination in organic solar cells,” Physical Review B 81, 205307 (2010).
  * Zhan  _et al._ [2011] X. Zhan, A. Facchetti, S. Barlow, T. J. Marks, M. A. Ratner, M. R. Wasielewski, and S. R. Marder, “Rylene and related diimides for organic electronics,” Advanced Materials 23, 268–284 (2011).
  * Bouhassoune  _et al._ [2009] M. Bouhassoune, S. L. M. v. Mensfoort, P. A. Bobbert, and R. Coehoorn, “Carrier-density and field-dependent charge-carrier mobility in organic semiconductors with correlated gaussian disorder,” Organic Electronics 10, 437–445 (2009).
  * Coehoorn  _et al._ [2005] R. Coehoorn, W. F. Pasveer, P. A. Bobbert, and M. A. J. Michels, “Charge-carrier concentration dependence of the hopping mobility in organic materials with gaussian disorder,” Physical Review B 72 (2005), 10.1103/PhysRevB.72.155206.
  * Chen and Xu [2009] G. Chen and Z. Xu, “Charge trapping and detrapping in polymeric materials,” Journal of Applied Physics 106 (2009), 10.1063/1.3273491.
  * [17] H. A. Alghamdi, G. Chen, and A. S. Vaughan, “Simulation of the developed electro-thermal aging model based on trapping and detrapping process,”  10.1109/CEIDP.2015.7352125.
  * Nicolai, Mandoc, and Blom [2011] H. T. Nicolai, M. M. Mandoc, and P. W. M. Blom, “Electron traps in semiconducting polymers: Exponential versus gaussian trap distribution,” Physical Review B 83 (2011), 10.1103/PhysRevB.83.195204.
  * Scheb, Zimmermann, and Jungemann [2015] M. Scheb, C. Zimmermann, and C. Jungemann, “Field-induced detrapping in doped organic semiconductors with gaussian disorder and different carrier localizations on host and guest sites,” Physical Review B 92 (2015), 10.1103/PhysRevB.92.104201.
  * Montero and Bisquert [2011] J. M. Montero and J. Bisquert, “Interpretation of trap-limited mobility in space-charge limited current in organic layers with exponential density of traps,” Journal of Applied Physics 110 (2011), 10.1063/1.3622615.
  * Germs  _et al._ [2011] W. C. Germs, J. J. M. van der Holst, S. L. M. van Mensfoort, P. A. Bobbert, and R. Coehoorn, “Modeling of the transient mobility in disordered organic semiconductors with a gaussian density of states,” Physical Review B 84 (2011), 10.1103/PhysRevB.84.165210.
  * Miller and Abrahams [1960] A. Miller and E. Abrahams, “Impurity conduction at low concentrations,” Physical Review 120, 745–755 (1960).
  * Lei  _et al._ [2016] Y. Lei, P. Deng, M. Lin, X. Zheng, F. Zhu, and B. S. Ong, “Enhancing crystalline structural orders of polymer semiconductors for efficient charge transport via polymer-matrix-mediated molecular self-assembly,” Adv Mater 28, 6687–94 (2016).
  * [24] DEVSIM LLC, “DEVSIM TCAD semiconductor device simulator,” https://devsim.org.
  * Kimura  _et al._ [2008] M. Kimura, T. Nakanishi, K. Nomura, T. Kamiya, and H. Hosono, “Trap densities in amorphous-ingazno4 thin-film transistors,” Applied Physics Letters 92 (2008), 10.1063/1.2904704.
  * Xu  _et al._ [2016] H. Xu, W.-J. Zhai, C. Tang, S.-Y. Qiu, R.-L. Liu, Z. Rong, Z.-Q. Pang, B. Jiang, J. Xiao, C. Zhong, B.-X. Mi, Q.-L. Fan, and W. Huang, “Thickness dependence of carrier mobility and the interface trap free energy investigated by impedance spectroscopy in organic semiconductors,” The Journal of Physical Chemistry C 120, 17184–17189 (2016).
  * Paasch and Scheinert [2010] G. Paasch and S. Scheinert, “Charge carrier density of organics with gaussian density of states: Analytical approximation for the gauss–fermi integral,” Journal of Applied Physics 107 (2010), 10.1063/1.3374475.
  * Neamen [2003] D. A. Neamen,  _Semiconductor physics and devices_ (McGraw-Hill higher education, 2003).
  * Oelerich, Huemmer, and Baranovskii [2012] J. O. Oelerich, D. Huemmer, and S. D. Baranovskii, “How to find out the density of states in disordered organic semiconductors,” Phys Rev Lett 108, 226403 (2012).
  * Knapp  _et al._ [2010] E. Knapp, R. Häusermann, H. U. Schwarzenbach, and B. Ruhstaller, “Numerical simulation of charge transport in disordered organic semiconductor devices,” Journal of Applied Physics 108 (2010), 10.1063/1.3475505.
  * Boubaker  _et al._ [2017] A. Boubaker, B. Hafsi, K. Lmimouni, and A. Kalboussi, “A comparative tcad simulations of a p-and n-type organic field effect transistors: field-dependent mobility, bulk and interface traps models,” Journal of Materials Science: Materials in Electronics 28, 7834–7843 (2017).
  * Baranovskii [2018] S. D. Baranovskii, “Mott lecture: Description of charge transport in disordered organic semiconductors: Analytical theories and computer simulations,” physica status solidi (a) 215 (2018), 10.1002/pssa.201700676.
  * Li  _et al._ [2012] J. Li, Y. Zhao, H. S. Tan, Y. Guo, C. A. Di, G. Yu, Y. Liu, M. Lin, S. H. Lim, Y. Zhou, H. Su, and B. S. Ong, “A stable solution-processed polymer semiconductor with record high-mobility for printed transistors,” Sci Rep 2, 754 (2012).
  * Ishibashi [1994] T. Ishibashi, “Chapter 5 - gaas-based and inp-based heterostructure bipolar transistors,” in  _Semiconductors and Semimetals_, Vol. 41, edited by R. A. Kiehl and T. C. L. G. Sollner (Elsevier, 1994) pp. 291–358.
  * Ghittorelli  _et al._ [2017] M. Ghittorelli, T. Lenz, H. Sharifi Dehsari, D. Zhao, K. Asadi, P. W. M. Blom, Z. M. Kovacs-Vajna, D. M. de Leeuw, and F. Torricelli, “Quantum tunnelling and charge accumulation in organic ferroelectric memory diodes,” Nature Communications 8, 15741 (2017).
  * RN1 [2006] “Metal-insulator-semiconductor capacitors,” in  _Physics of Semiconductor Devices_ (2006) pp. 197–240.


All the True nodes (resp. False nodes and Dummy nodes) in
$G^{\prime\prime}_{\phi}$ can be decoded into the same color.

###### Proof.

The decoding algorithm works as follows. Pick any survived literal block in
$G^{\prime\prime}_{\phi}$. Set the vector of the True node in the literal
block to be $(0,0,1)$. Set the direction in $S^{2}$ that is closest to the
False vector and orthogonal to direction $(0,0,1)$ to be $(1,0,0)$. Since the
True, False and Dummy nodes in the literal block are interconnected by good
edges, the angle between False vector and $(1,0,0)$ together with the angle
between Dummy vector and $(0,1,0)$ are both $O(\frac{1}{\log{n}})$.

Now, by the facts that the distance between any pair of True nodes in
$G^{\prime\prime}_{\phi}$ is $O(\log{n})$, equality gadgets are robust (Lemma
7) and angle on the points in $S^{2}$ is a metric space (in particular, angle
metric satisfies the triangle inequality), if the constant $C$ in Theorem 8 is
small enough, then the angle between any pair of True vectors is at most
$\delta_{p}:=\pi/300$. Denote171717Recall that, by our convention,
$S_{\mathrm{True}}$ is actually the union of two disconnected regions:
$\\{v\in S^{2}:\mathrm{angle}(v,(0,0,1))\leq\delta_{p}\\}\cup\\{v\in
S^{2}:\mathrm{angle}(v,(0,0,-1))\leq\delta_{p}\\}$; that is,
$S_{\mathrm{True}}$ is a small cap centered around the “north pole” plus a
small cap centered around the “south pole”. Similar conventions hold for
$S_{\mathrm{False}}$ and $S_{\mathrm{Dummy}}$ as well.

$S_{\mathrm{True}}=\\{v\in S^{2}:\mathrm{angle}(v,(0,0,1))\leq\delta_{p}\\}$

Then all True vectors in $G^{\prime\prime}_{\phi}$ fall into region
$S_{\mathrm{True}}$. Similarly define $S_{\mathrm{False}}:=\\{v\in
S^{2}:\mathrm{angle}(v,(1,0,0))\leq\delta_{p}\\}$ and
$S_{\mathrm{Dummy}}:=\\{v\in
S^{2}:\mathrm{angle}(v,(0,1,0))\leq\delta_{p}\\}$. Then similar argument shows
that all False (resp. Dummy) vectors in $G^{\prime\prime}_{\phi}$ fall into
region $S_{\mathrm{False}}$ (resp. $S_{\mathrm{Dummy}}$). Finally, since
$S_{\mathrm{True}}$, $S_{\mathrm{False}}$ and $S_{\mathrm{Dummy}}$ are clearly
disjoint, we therefore unambiguously decode all the True nodes, False nodes
and Dummy nodes in $G^{\prime\prime}_{\phi}$. ∎

Note that the proof of Lemma 12 makes it possible to decode a truth assignment
for all $n$ variables that satisfies at least $(1-\epsilon)$ fraction of the
clauses in $\phi$, as we now describe. Since the angle between every pair of
True node vectors is at most $\delta_{p}:=\pi/300$, the assumption of Lemma 8
is satisfied. Therefore, by Lemma 8, at least one of the three literals in
each clause is $\pi/15+\pi/300=21\pi/300$ close to direction $(0,0,1)$.
Moreover, since all the survived copies of the same literal are inter-
connected by an equality gadget, it follows that each of these at most $k$
copies of the literal is $21\pi/300+o(1)<\pi/12$ close to $(0,0,1)$. On the
other hand, since each literal is connected with its negation by a good edge,
its negation is at least $\pi/2-\pi/12-o(1)>\pi/3$ far from $(0,0,1)$.
Therefore, we can decode unambiguously the truth assignment of each variable
as follows: if all the survived copies of $x_{i}$ are $\pi/12$ close to
$(0,0,1)$, assign $x_{i}$ to True; else, if all the survived copies of
$\bar{x}_{i}$ are $\pi/12$ close to $(1,0,0)$, assign $x_{i}$ to False;
otherwise, $x_{i}$ is a free variable and can be assigned truth value
arbitrarily. This completes the proof of Theorem 8. ∎

##  8 The approximation algorithm

Let DiagonalKernel be the algorithm that, given a collection of subsets
$X_{1},X_{2},\ldots,X_{m}\subseteq[N]$, returns the $N\times N$ diagonal
matrix $K$ such that $K_{ii}=\frac{1}{m}\cdot|\\{j:X_{j}\ni i\\}|$ for all
$i\in[N]$. Clearly, DiagonalKernel runs in at most $O(mN)$ time.

######  Theorem 10.

Let $\ell$ be the log likelihood of the DPP defined by the marginal kernel
output by DiagonalKernel on examples $X_{1},X_{2},\ldots,X_{m}$, and let
$\ell^{*}$ be the optimal log likelihood achieved by a DPP kernel on the same
training set. Then
$\ell\leq\left(1+\frac{1}{\log(\frac{m}{a_{max}})}\right)\ell^{*}$, where
$a_{max}:=\max_{i\in[N]}|\\{j:X_{j}\ni i\\}|$ is the maximum element frequency
in examples. It follows immediately that
$\ell\leq(1+\frac{1+o(1)}{\log{N}})\ell^{*}$, when $a_{max}=O(m)/N$. As an
unconditional weaker bound, we always have $\ell\leq(1+(1+\frac{1}{m-1})\log
m)\ell^{*}$.

###### Proof.

Let $\ell$ and $\ell^{*}$ be the log likelihoods of DiagonalKernel kernel and
optimal kernel, respectively. In the following we upper bound the ratio
$\frac{\ell}{\ell^{*}}$.

For each $i\in[N]$, define $a_{i}:=|\\{j:X_{j}\ni i\\}|$ to be the frequency
of element $i$ in the examples. Then $K$ is a diagonal matrix with
$K_{ii}=\frac{a_{i}}{m}$ for each $i\in[N]$. If $\boldsymbol{X}$ is a random
variable distributed according to this diagonal DPP, then $\boldsymbol{X}$ is
distributed as a product distribution of $N$ independent random variables,
with $\Pr[i\in\boldsymbol{X}]=K_{ii}$ for every $i\in[N]$. It follows that,
for every subset example $X_{j}\subseteq[N]$,

$\displaystyle\Pr_{\boldsymbol{X}\sim\mathcal{P}_{K}}[\boldsymbol{X}=X_{j}]$
$\displaystyle=\prod_{i\in X_{j}}K_{ii}\prod_{i\notin
X_{j}}(1-K_{ii})=\prod_{i\in X_{j}}\frac{a_{i}}{m}\prod_{i\notin
X_{j}}\left(1-\frac{a_{i}}{m}\right).$

Since there are exactly $a_{i}$ sets that contain element $i$ and $m-a_{i}$
that do not contain element $i$, the log likelihood of the marginal DPP kernel
$K$ is

$\displaystyle\ell=-\log\left[\prod_{j=1}^{m}\left(\prod_{i\in
X_{j}}\frac{a_{i}}{m}\prod_{i\notin
X_{j}}(1-\frac{a_{i}}{m})\right)\right]=-\log\left[\prod_{i=1}^{N}\left(\frac{a_{i}}{m}\right)^{a_{i}}\left(1-\frac{a_{i}}{m}\right)^{m-a_{i}}\right].$

By Theorem 5, we can assume that the diagonal entries of a kernel $K^{*}$
achieving log likelihood $\ell^{*}$ match those of the diagonal entries of
$K$. Let $\boldsymbol{X}^{*}$ be a random variable distributed according to
such a marginal kernel, then by Lemma 4 (Hadamard’s Inequality) we have

$\displaystyle\Pr_{\boldsymbol{X}^{*}\sim\mathcal{P}_{K^{*}}}[\boldsymbol{X}^{*}=X_{j}]$
$\displaystyle\leq\Pr_{\boldsymbol{X}^{*}\sim\mathcal{P}_{K^{*}}}[X_{j}\subseteq\boldsymbol{X}^{*}]=\det(K^{*}_{X_{j}})$
$\displaystyle\leq\prod_{i\in X_{j}}K^{*}_{ii}=\prod_{i\in
X_{j}}K_{ii}=\prod_{i\in X_{j}}\frac{a_{i}}{m}.$

It follows that

$\ell^{*}\geq-\log\left(\prod_{i=1}^{N}\left(\frac{a_{i}}{m}\right)^{a_{i}}\right).$

We now observe that

$\displaystyle\frac{\ell}{\ell^{*}}$
$\displaystyle\leq\frac{\log\left(\prod_{i=1}^{N}\left(\frac{a_{i}}{m}\right)^{a_{i}}\left(1-\frac{a_{i}}{m}\right)^{m-a_{i}}\right)}{\log\left(\prod_{i=1}^{N}\left(\frac{a_{i}}{m}\right)^{a_{i}}\right)}=1+\dfrac{\log(\prod_{i=1}^{N}\left(1-\frac{a_{i}}{m})^{m-a_{i}}\right)}{\log\left(\prod_{i=1}^{N}\left(\frac{a_{i}}{m}\right)^{a_{i}}\right)}$
$\displaystyle=1+\dfrac{\log\left(\prod_{i=1}^{N}(1-\frac{a_{i}}{m})^{1-\frac{a_{i}}{m}}\right)}{\log\left(\prod_{i=1}^{N}\left(\frac{a_{i}}{m}\right)^{\frac{a_{i}}{m}}\right)}$
$\displaystyle=1+\dfrac{\sum_{i=1}^{N}\log\left((1-\frac{a_{i}}{m})^{1-\frac{a_{i}}{m}}\right)}{\sum_{i=1}^{N}\log\left(\left(\frac{a_{i}}{m}\right)^{\frac{a_{i}}{m}}\right)}.$

For $x\in(0,1)$, let $g(x):=-\log\left((1-x)^{1-x}\right)$ and
$h(x):=-\log\left(x^{x}\right)$, and define

$f(x):=\frac{g(x)}{h(x)}=\dfrac{\log\left((1-x)^{1-x}\right)}{\log\left(x^{x}\right)}=\dfrac{(1-x)\log(1-x)}{x\log
x}.$

Then it is easy to check that, for every $0<x<1$, both $g(x)$ and $h(x)$ and
hence $f(x)$ are positive; moreover, $f(x)$ is an increasing function in $x$ .
Therefore,

$\displaystyle\frac{\ell}{\ell^{*}}$ $\displaystyle\leq
1+\dfrac{\sum_{i=1}^{N}g(\frac{a_{i}}{m})}{\sum_{i=1}^{N}h(\frac{a_{i}}{m})}\leq
1+\max_{i\in[N]}\dfrac{g(\frac{a_{i}}{m})}{h(\frac{a_{i}}{m})}$
$\displaystyle=1+\max_{i\in[N]}\dfrac{\log\left((1-\frac{a_{i}}{m})^{1-\frac{a_{i}}{m}}\right)}{\log\left(\left(\frac{a_{i}}{m}\right)^{\frac{a_{i}}{m}}\right)}$
$\displaystyle=1+f(\frac{a_{max}}{m}).$ (17)

Using the inequality that $(1+x)\log{(1+x)}\geq x$ for all $x>-1$, we get that
$f(x)\leq-\frac{1}{\log x}$ for all $0<x<1$. Thus, when
$\frac{a_{max}}{m}\leq\frac{C}{N}$, the kernel output by DiagonalKernel
satisfies
$\ell\leq(1-\frac{1}{\log(C/N)})\ell^{*}=(1+\frac{1}{\log(N/C)})\ell^{*}$.

When the condition $\frac{a_{max}}{m}\leq\frac{C}{N}$ is not satisfied, in
order to obtain an unconditional upper bound on the log likelihood of
DiagonalKernel , observe that without loss of generality, we may consider only
the cases when $a_{max}\leq m-1$. This is because elements occur in all the
training subsets will be assigned probability $1$ in a maximum likelihood DPP,
hence have $1$ at the diagonal entry and $0$’s at all other off-diagonal
entries. This means that such elements can be “factored out” from the marginal
kernel. Thus, plugging $\frac{a_{max}}{m}=\frac{m-1}{m}$ into (8), we obtain

$\frac{\ell}{\ell^{*}}\leq
1+\frac{\frac{1}{m}\log\frac{1}{m}}{(1-\frac{1}{m})\log(1-\frac{1}{m})}=1+\frac{\log{m}}{(m-1)\log(1+\frac{1}{m-1})}\leq
1+(1+\frac{1}{m-1})\log{m},$

where in the last step we use again the inequality $(1+x)\log(1+x)\geq x$ for
all $x>-1$ (and setting $x=\frac{1}{m-1}$). ∎

Thus this simple algorithm does surprisingly well, unless there are some high
frequent elements that appear in a non-trivial fraction of the training data,
which is often not the case in practice. Further, it’s worth noting that the
training set constructed in our hardness of learning proof also satisfies that
$\frac{a_{max}}{m}\leq\frac{C}{N}$ for some constant $C$.

##  9 Discussion and open problems

In this work, we establish that it is NP-hard to obtain a
$1-O(\frac{1}{\log^{9}N})$-approximation to the maximum log likelihood of
DPPs. We also demonstrate a simple polynomial-time algorithm that achieves
$\frac{1}{(1+o(1))\log{m}}$-approximation. One immediate open problem is to
close this large gap. A natural and plausible approach is to prove the
cardinality-rank conjecture or at least to improve the bound in Theorem 7.
Note that our hardness result does not rule out efficient learning with some
constant factor of approximation: it is still possible that there is a
polynomial-time algorithm that obtains a DPP kernel with a 99%-approximation
to the maximum log likelihood. As observed earlier, we cannot preclude
constant-factor approximations by a better analysis of the constructed hard
instance: the approximation algorithm shows that our hardness result is tight
up to a polynomial factor for the type of subset collections employed in the
proof. Therefore any stronger hardness proof would require constructing a
collection of subsets in which some element appears in a non-trivial fraction
of the subsets.

Our investigation just takes a first stab at understanding the computational
landscape of learning DPPs. In particular, our knowledge for the complexity of
learning DPPs when the data set is indeed generated by an unknown DPP is still
very limited: Can one design efficient algorithms for such a task? Can the DPP
kernel be learned with arbitrary accuracy? And if not, what is the best
approximation factor can such an algorithm achieve? Note that the data here is
no longer a worst-case data set, but only sampled from a worst-case DPP. The
underlying model is thus a semi-random one, and it seems challenging to extend
NP-completeness hardness to such settings; some kind of average-case hardness
is likely to be the best one can hope for. This is essentially the approach
that [BMRU17a] had envisioned when examining the optimization landscape of the
likelihood function for DPP kernels. The convergence of the empirical log-
likelihood function to the true log-likelihood function only holds with high
probability, and so in particular doesn’t carry over to the kinds of worst-
case data sets produced by our reduction. Thus, their conjectured property may
still hold, and may be a route to an efficient algorithm in this setting. On
the other hand, “realizability” is probably a too strong assumption for
practical purposes; DPPs are generally used to model processes featuring
negative association, and it often seems implausible that the data actually
follows a DPP distribution. Therefore, finding more appropriate assumptions is
yet to be explored, and an algorithm for a realizable setting would be a
natural first step along this direction.

As the other side of the coin, it is entirely conceivable that such efficient
algorithms may not exist at all. One may view our main result as proving the
hardness of “agnostic-learning” DPPs, while here the task would be proving
hardness of “PAC-learning” DPPs. Presumably this is more difficult, as PAC-
learning is in general easier than agnostic learning, it is thus harder to
obtain lower bounds in the former setting. In particular, the usual approach
of proving PAC-learning lower bounds involves uniform distributions over some
prescribed collections of subsets. Such distributions are within the scope of
PAC-learning model as it allows arbitrary distributions. By contrast, DPPs are
normally unable to generate the uniform distribution over an arbitrary
collection of subsets. Indeed, we believe that the data set we construct would
be atypical for all DPPs. This is why contrary to the usual representation-
specific hardness theorems in PAC-learning, we believe that an average-case
hardness assumption will be necessary here.

## Acknowledgments

We thank the anonymous reviewers for carefully reading the manuscript and
providing useful comments and suggestions. B.J. was partially supported by NSF
awards IIS-1908287, IIS-1939677, and CCF-1718380. E.G. was partially supported
by NSF CCF-1910659 and NSF CCF-1910411. N.X. was partially supported by U.S.
Army Research Office (ARO) under award number W911NF1910362.

## References

  * [AC07] Noga Alon and Michael Capalbo.  Finding disjoint paths in expanders deterministically and online.  In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS’07), pages 518–524. IEEE, 2007.
  * [AFAT14] Raja Hafiz Affandi, Emily Fox, Ryan Adams, and Ben Taskar.  Learning the parameters of determinantal point process kernels.  In International Conference on Machine Learning, pages 1224–1232, 2014.
  * [AFT13] Raja Hafiz Affandi, Emily B. Fox, and Ben Taskar.  Approximate inference in continuous determinantal point processes.  In Advances in Neural Information Processing Systems 25, pages 1430–1438, 2013.
  * [AGR16] Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei.  Monte Carlo Markov chain algorithms for sampling strongly Rayleigh distributions and determinantal point processes.  In Conference on Learning Theory, pages 103–115. PMLR, 2016.
  * [AGR+20] Lucas Anquetil, Mike Gartrell, Alain Rakotomamonjy, Ugo Tanielian, and Clément Calauzènes.  Wasserstein learning of determinantal point processes.  arXiv preprint arXiv:2011.09712, 2020.
  * [AKFT13] Raja Hafiz Affandi, Alex Kulesza, Emily Fox, and Ben Taskar.  Nyström approximation for large-scale determinantal processes.  In Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, volume 31 of PMLR, pages 85–98, 2013.
  * [Bar13] Yannick Baraud.  Estimation of the density of a determinantal process.  Confluentes Mathematici, 5(1):3–21, 2013.
  * [BG16] Joshua Brakensiek and Venkatesan Guruswami.  New hardness results for graph and hypergraph colorings.  In 31st Conference on Computational Complexity (CCC 2016), 2016\.
  * [BKS03] Piotr Berman, Marek Karpinski, and Alex D. Scott.  Approximation hardness and satisfiability of bounded occurrence instances of SAT.  Electronic Colloquium in Computational Complexity, TR03-022, 2003\.
  * [BMRU17a] Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, and John Urschel.  Maximum likelihood estimation of determinantal point processes.  arXiv preprint arXiv:1701.06501, 2017.
  * [BMRU17b] Victor-Emmanuel Brunel, Ankur Moitra, Philippe Rigollet, and John Urschel.  Rates of estimation for determinantal point processes.  In Conference on Learning Theory, pages 343–345, 2017.
  * [BOT02] Andrej Bogdanov, Kenji Obata, and Luca Trevisan.  A lower bound for testing $3$-colorability in bounded-degree graphs.  In The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., pages 93–102. IEEE, 2002.
  * [BP93] Robert Burton and Robin Pemantle.  Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances.  The Annals of Probability, pages 1329–1371, 1993.
  * [BR05] Alexei Borodin and Eric M. Rains.  Eynard-Mehta theorem, Schur process, and their Pfaffian analogs.  Journal of statistical physics, 121(3-4):291–317, 2005.
  * [CGGS15] Wei-Lun Chao, Boqing Gong, Kristen Grauman, and Fei Sha.  Large-margin determinantal point processes.  In Proceedings of the Thirty-First Conference on Uncertainty in Artificial Intelligence, pages 191–200, 2015.
  * [CMI09] Ali Civril and Malik Magdon-Ismail.  On selecting a maximum volume sub-matrix of a matrix and related problems.  Theoretical Computer Science, 410(47-49):4801–4811, 2009.
  * [DB18] Christophe Dupuy and Francis Bach.  Learning determinantal point processes in sublinear time.  In International Conference on Artificial Intelligence and Statistics, pages 244–257, 2018.
  * [DCV19] Michał Dereziński, Daniele Calandriello, and Michal Valko.  Exact sampling of determinantal point processes with sublinear time preprocessing.  In Advances in Neural Information Processing Systems 32, 2019.
  * [DLM20] Michal Derezinski, Feynman T. Liang, and Michael W. Mahoney.  Exact expressions for double descent and implicit regularization via surrogate random design.  Advances in Neural Information Processing Systems 33, 2020.
  * [DMR09] Irit Dinur, Elchanan Mossel, and Oded Regev.  Conditional hardness for approximate coloring.  SIAM Journal on Computing, 39(3):843–873, 2009.
  * [DRS09] Shaddin Dughmi, Tim Roughgarden, and Mukund Sundararajan.  Revenue submodularity.  In Proceedings of the 10th ACM conference on Electronic commerce, pages 243–252, 2009.
  * [DW18] Michał Dereziński and Manfred K. Warmuth.  Reverse iterative volume sampling for linear regression.  The Journal of Machine Learning Research, 19(1):853–891, 2018.
  * [Dys62] Freeman J. Dyson.  Statistical theory of the energy levels of complex systems. III.  Journal of Mathematical Physics, 3(1):166–175, 1962.
  * [GAJ20] Khashayar Gatmiry, Maryam Aliakbarpour, and Stefanie Jegelka.  Testing determinantal point processes.  arXiv preprint arXiv:2008.03650, 2020.
  * [GBDK19] Mike Gartrell, Victor-Emmanuel Brunel, Elvis Dohmatob, and Syrine Krichene.  Learning nonsymmetric determinantal point processes.  arXiv preprint arXiv:1905.12962, 2019.
  * [GGR98] Oded Goldreich, Shari Goldwasser, and Dana Ron.  Property testing and its connection to learning and approximation.  Journal of the ACM (JACM), 45(4):653–750, 1998.
  * [GK04] Venkatesan Guruswami and Sanjeev Khanna.  On the hardness of $4$-coloring a $3$-colorable graph.  SIAM Journal on Discrete Mathematics, 18(1):30–40, 2004.
  * [GKFT14] Jennifer A Gillenwater, Alex Kulesza, Emily Fox, and Ben Taskar.  Expectation-maximization for learning determinantal point processes.  Advances in Neural Information Processing Systems, 27:3149–3157, 2014.
  * [GKS05] Carlos Guestrin, Andreas Krause, and Ajit Paul Singh.  Near-optimal sensor placements in Gaussian processes.  In Proceedings of the 22nd international conference on Machine learning, pages 265–272, 2005.
  * [GKT12a] Jennifer Gillenwater, Alex Kulesza, and Ben Taskar.  Discovering diverse and salient threads in document collections.  In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 710–720, 2012.
  * [GKT12b] Jennifer Gillenwater, Alex Kulesza, and Ben Taskar.  Near-optimal map inference for determinantal point processes.  In Advances in Neural Information Processing Systems 24, pages 2744–2752, 2012.
  * [GPK16] Mike Gartrell, Ulrich Paquet, and Noam Koenigstein.  Bayesian low-rank determinantal point processes.  In Proceedings of the 10th ACM Conference on Recommender Systems, pages 349–356, 2016.
  * [GPK17] Mike Gartrell, Ulrich Paquet, and Noam Koenigstein.  Low-rank factorization of determinantal point processes.  In Thirty-First AAAI Conference on Artificial Intelligence, 2017\.
  * [GS12] Venkatesan Guruswami and Ali Kemal Sinop.  Optimal column-based low-rank matrix reconstruction.  In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms, pages 1207–1214. SIAM, 2012.
  * [Hås00] Johan Håstad.  On bounded occurrence constraint satisfaction.  Information Processing Letters, 74(1-2):1–6, 2000.
  * [Hås01] Johan Håstad.  Some optimal inapproximability results.  Journal of the ACM, 48(4):798–859, 2001.
  * [HJ12] Roger A Horn and Charles R Johnson.  Matrix analysis.  Cambridge university press, second edition, 2012.
  * [HKPV06] J. Ben Hough, Manjunath Krishnapur, Yuval Peres, and Bálint Virág.  Determinantal processes and independence.  Probability surveys, 3:206–229, 2006.
  * [HMRW14] Moritz Hardt, Raghu Meka, Prasad Raghavendra, and Benjamin Weitz.  Computational limits for matrix completion.  In Conference on Learning Theory, pages 703–725. PMLR, 2014.
  * [HPS+10] Gerald Haynes, Catherine Park, Amanda Schaeffer, Jordan Webster, and Lon H Mitchell.  Orthogonal vector coloring.  The Electronic Journal of Combinatorics, 17, 2010.
  * [IR08] Ilse C. F. Ipsen and Rizwana Rehman.  Perturbation bounds for determinants and characteristic polynomials.  SIAM Journal on Matrix Analysis and Applications, 30(2):762–776, 2008.
  * [Kan13] Byungkon Kang.  Fast determinantal point process sampling with application to clustering.  In Advances in Neural Information Processing Systems 25, pages 2319–2327, 2013.
  * [KLQ95] Chun-Wa Ko, Jon Lee, and Maurice Queyranne.  An exact algorithm for maximum entropy sampling.  Operations Research, 43(4):684–691, 1995.
  * [KLS00] Sanjeev Khanna, Nathan Linial, and Shmuel Safra.  On the hardness of approximating the chromatic number.  Combinatorica, 20(3):393–415, 2000.
  * [KMS98] David R. Karger, Rajeev Motwani, and Madhu Sudan.  Approximate graph coloring by semidefinite programming.  J. ACM, 45(2):246–265, 1998.
  * [KSG08] Andreas Krause, Ajit Singh, and Carlos Guestrin.  Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies.  Journal of Machine Learning Research, 9(2), 2008.
  * [KT10] Alex Kulesza and Ben Taskar.  Structured determinantal point processes.  Advances in neural information processing systems 23, pages 1171–1179, 2010.
  * [KT11a] Alex Kulesza and Ben Taskar.  $k$-DPPs: fixed-size determinantal point processes.  In Proceedings of the 28th International Conference on International Conference on Machine Learning, pages 1193–1200, 2011.
  * [KT11b] Alex Kulesza and Ben Taskar.  Learning determinantal point processes.  In Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, pages 419–427, 2011.
  * [KT12] Alex Kulesza and Ben Taskar.  Determinantal point processes for machine learning.  Foundations and Trends in Machine Learning, 5(2-3):123–286, 2012\.
  * [Kul12] John A. Kulesza.  Learning with Determinantal Point Processes.  PhD thesis, University of Pennsylvania, 2012.
  * [Lau09] Monique Laurent.  Matrix completion problems.  Encyclopedia of Optimization, 3:221–229, 2009.
  * [LB12] Hui Lin and Jeff Bilmes.  Learning mixtures of submodular shells with application to document summarization.  In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pages 479–490, 2012.
  * [LCYO16] Donghoon Lee, Geonho Cha, Ming-Hsuan Yang, and Songhwai Oh.  Individualness and determinantal point processes for pedestrian detection.  In European Conference on Computer Vision, pages 330–346. Springer, 2016.
  * [LGD20] Claire Launay, Bruno Galerne, and Agnès Desolneux.  Exact sampling of determinantal point processes without eigendecomposition.  Journal of Applied Probability, 57(4):1198–1221, 2020.
  * [LJS16a] Chengtao Li, Stefanie Jegelka, and Suvrit Sra.  Fast DPP sampling for Nyström with application to kernel methods.  In International Conference on Machine Learning, pages 2061–2070. PMLR, 2016.
  * [LJS16b] Chengtao Li, Stefanie Jegelka, and Suvrit Sra.  Fast mixing Markov chains for strongly Rayleigh measures, DPPs, and constrained sampling.  In Advances in Neural Information Processing Systems 29, pages 4195–4203, 2016.
  * [LMR15] Frédéric Lavancier, Jesper Møller, and Ege Rubak.  Determinantal point process models and statistical inference.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 77(4):853–877, 2015.
  * [Lov79] László Lovász.  On the Shannon capacity of a graph.  IEEE Trans. Inf. Theory, 25(1):1–7, 1979.
  * [Lov19] László Lovász.  Graphs and geometry, volume 65.  American Mathematical Soc., 2019.
  * [LPS88] Alexander Lubotzky, Ralph Phillips, and Peter Sarnak.  Ramanujan graphs.  Combinatorica, 8(3):261–277, 1988.
  * [LSS89] L. Lovász, M. Saks, and A. Schrijver.  Orthogonal representations and connectivity of graphs.  Linear Algebra and its Applications, 114-115:439–454, 1989.
  * [LSS00] L. Lovász, M. Saks, and A. Schrijver.  A correction: orthogonal representations and connectivity of graphs.  Linear Algebra and its Applications, 313(1):101–105, 2000.
  * [LV99] László Lovász and Katalin Vesztergombi.  Geometric representations of graphs.  Paul Erdos and his Mathematics, 2, 1999.
  * [Lyo03] Russell Lyons.  Determinantal probability measures.  Publications Mathématiques de l’IHÉS, 98:167–212, 2003\.
  * [Mac75] Odile Macchi.  The coincidence approach to stochastic point processes.  Advances in Applied Probability, 7(1):83–122, 1975.
  * [Mar88] Grigorii Aleksandrovich Margulis.  Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators.  Problemy peredachi informatsii, 24(1):51–60, 1988.
  * [MGS19] Zelda Mariet, Mike Gartrell, and Suvrit Sra.  Learning determinantal point processes by corrective negative sampling.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2251–2260, 2019.
  * [MS15] Zelda Mariet and Suvrit Sra.  Fixed-point algorithms for learning determinantal point processes.  In International Conference on Machine Learning, pages 2389–2397, 2015.
  * [MS16] Zelda E Mariet and Suvrit Sra.  Kronecker determinantal point processes.  Advances in Neural Information Processing Systems, 29:2694–2702, 2016.
  * [Ohs21] Naoto Ohsaka.  Unconstrained map inference, exponentiated determinantal point processes, and exponential inapproximability.  In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130, pages 154–162, 2021.
  * [OR19] Takayuki Osogami and Rudy Raymond.  Determinantal reinforcement learning.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33(1), pages 4659–4666, 2019.
  * [ORG+18] Takayuki Osogami, Rudy Raymond, Akshay Goel, Tomoyuki Shirai, and Takanori Maehara.  Dynamic determinantal point processes.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32(1), 2018.
  * [Pee96] René Peeters.  Orthogonal representations over finite fields and the chromatic number of graphs.  Combinatorica, 16(3):417–431, 1996.
  * [PP89] T.D. Parsons and Tomaž Pisanski.  Vector representations of graphs.  Discrete Mathematics, 78(1):143–154, 1989.
  * [PV88] Leonard Pitt and Leslie G. Valiant.  Computational limitations on learning from examples.  Journal of the ACM (JACM), 35(4):965–984, 1988.
  * [RK15] Patrick Rebeschini and Amin Karbasi.  Fast mixing for discrete point processes.  In Conference on Learning Theory, pages 1480–1500. PMLR, 2015.
  * [RS96] Zeév Rudnick and Peter Sarnak.  Zeros of principal $L$-functions and random matrix theory.  Duke Mathematical Journal, 81(2):269–322, 1996.
  * [SG13] Amar Shah and Zoubin Ghahramani.  Determinantal clustering process-a nonparametric bayesian approach to kernel based semi-supervised clustering.  In Proceedings of the Twenty-Ninth Conference on Uncertainty in Artificial Intelligence, pages 566–575, 2013.
  * [Sos00] Alexander Soshnikov.  Determinantal random point fields.  Russian Mathematical Surveys, 55(5):923, 2000.
  * [SZA13] Jasper Snoek, Richard Zemel, and Ryan Prescott Adams.  A determinantal point process latent variable model for inhibition in neural spiking data.  Advances in Neural Information Processing Systems 25, 2013.
  * [Tre01] Luca Trevisan.  Non-approximability results for optimization problems on bounded degree instances.  In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 453–461, 2001.
  * [UBMR17] John Urschel, Victor-Emmanuel Brunel, Ankur Moitra, and Philippe Rigollet.  Learning determinantal point processes with moments and cycles.  In International Conference on Machine Learning, pages 3511–3520. PMLR, 2017.
  * [XO16] Haotian Xu and Zhijian Ou.  Scalable discovery of audio fingerprint motifs in broadcast streams with determinantal point process based motif clustering.  IEEE/ACM Transactions on Audio, Speech, and Language Processing, 24(5):978–989, 2016.
  * [YFZ+16] Jin-ge Yao, Feifan Fan, Wayne Xin Zhao, Xiaojun Wan, Edward Chang, and Jianguo Xiao.  Tweet timeline generation with determinantal point processes.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30(1), 2016.
  * [YWW+20] Yaodong Yang, Ying Wen, Jun Wang, Liheng Chen, Kun Shao, David Mguni, and Weinan Zhang.  Multi-agent determinantal $q$-learning.  In International Conference on Machine Learning, pages 10757–10766. PMLR, 2020.
  * [ZA12] James Y. Zou and Ryan P. Adams.  Priors for diversity in generative latent variable models.  In Advances in Neural Information Processing Systems 24, pages 2996–3004, 2012.
  * [ZKL+10] Tao Zhou, Zoltán Kuscsik, Jian-Guo Liu, Matúš Medo, Joseph Rushton Wakeling, and Yi-Cheng Zhang.  Solving the apparent diversity-accuracy dilemma of recommender systems.  Proceedings of the National Academy of Sciences, 107(10):4511–4515, 2010.