
We give a fully polynomialtime randomized approximation scheme (FPRAS) for
the allterminal network reliability problem, which is to determine the
probability that, in a undirected graph, assuming each edge fails
independently, the remaining graph is still connected. Our main contribution is
to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014),
that the expected running time of the "clusterpopping" algorithm in
bidirected graphs is bounded by a polynomial in the size of the input.

Approximate counting via correlation decay is the core algorithmic technique
used in the sharp delineation of the computational phase transition that arises
in the approximation of the partition function of antiferromagnetic twospin
models.
Previous analyses of correlationdecay algorithms implicitly depended on the
occurrence of strong spatial mixing (SSM). This means that one uses worstcase
analysis of the recursive procedure that creates the subinstances. We develop
a new analysis method that is more refined than the worstcase analysis. We
take the shape of instances in the computation tree into consideration and
amortise against certain "bad" instances that are created as the recursion
proceeds. This enables us to show correlation decay and to obtain an FPTAS even
when SSM fails.
We apply our technique to the problem of approximately counting independent
sets in hypergraphs with degree upperbound Delta and with a lower bound k on
the arity of hyperedges. Liu and Lin gave an FPTAS for k>=2 and Delta<=5 (lack
of SSM was the obstacle preventing this algorithm from being generalised to
Delta=6). Our technique gives a tight result for Delta=6, showing that there is
an FPTAS for k>=3 and Delta<=6. The best previouslyknown approximation scheme
for Delta=6 is the Markovchain simulation based FPRAS of Bordewich, Dyer and
Karpinski, which only works for k>=8.
Our technique also applies for larger values of k, giving an FPTAS for
k>=Delta. This bound is not substantially stronger than existing randomised
results in the literature. Nevertheless, it gives the first deterministic
approximation scheme in this regime. Moreover, unlike existing results, it
leads to an FPTAS for counting dominating sets in regular graphs with
sufficiently large degree.
We further demonstrate that approximately counting independent sets in
hypergraphs is NPhard even within the uniqueness regime.

We propose a new algorithmic framework, called "partial rejection sampling",
to draw samples exactly from a product distribution, conditioned on none of a
number of bad events occurring. Our framework builds (perhaps surprising) new
connections between the variable framework of the Lov\'asz Local Lemma and some
classical sampling algorithms such as the "cyclepopping" algorithm for rooted
spanning trees. Among other applications, we discover new algorithms to sample
satisfying assignments of kCNF formulas with bounded variable occurrences.

We give fully polynomialtime approximation schemes (FPTAS) for the partition
function of ferromagnetic 2spin systems in certain parameter regimes. The
threshold we obtain is almost tight up to an integrality gap. Our technique is
based on the correlation decay framework. The main technical contribution is a
new potential function, with which we establish a new kind of spatial mixing.

Carbon nitride compounds have emerged recently as a prominent member of 2D
materials beyond graphene. The experimental realizations of 2D graphitic carbon
nitride gC$_3$N$_4$, nitrogenated holey grahpene C$_2$N, polyaniline C$_3$N
have shown their promising potential in energy and environmental applications.
In this work, we predict a new type of carbon nitride network with a C$_9$N$_4$
stoichiometry from first principle calculations. Unlike common CN compounds
and covalent organic frameworks (COFs), which are typically insulating,
surprisingly C$_9$N$_4$ is found to be a 2D nodalline semimetal (NLSM). The
nodal line in C$_9$N$_4$ forms a closed ring centered at $\Gamma$ point, which
originates from the pz orbitals of both C and N. The linear crossing happens
right at Fermi level contributed by two sets of dispersive Kagome and Dirac
bands, which is robust due to negligible spinorbitalcoupling (SOC) in C and
N. Besides, it is revealed that the formation of nodal ring is of accidental
band degeneracy in nature induced by the chemical potential difference of C and
N, as validated by a single orbital tightbinding model, rather than protected
by crystal inplane mirror symmetry or band topology. Interestingly, a new
structure of nodal line, i.e., nodalcylinder, is found in momentum space for
AAstacking C$_9$N$_4$. Our results imply possible functionalization for a
novel metalfree CN covalent network with interesting semimetallic properties.

We present a perfect simulation of the hard disks model via the partial
rejection sampling method. Provided the density of disks is not too high, the
method produces exact samples in $O(\log n)$ rounds, where $n$ is the expected
number of disks. The method extends easily to the hard spheres model in $d>2$
dimensions.

Holographic algorithms introduced by Valiant are composed of two ingredients:
matchgates, which are gadgets realizing local constraint functions by weighted
planar perfect matchings, and holographic reductions, which show equivalences
among problems with different descriptions via certain basis transformations.
In this paper, we replace matchgates in the paradigm above by the affine type
and the product type constraint functions, which are known to be tractable in
general (not necessarily planar) graphs. More specifically, we present
polynomialtime algorithms to decide if a given counting problem has a
holographic reduction to another problem defined by the affine or producttype
functions. Our algorithms also find a holographic transformation when one
exists. We further present polynomialtime algorithms of the same decision and
search problems for symmetric functions, where the complexity is measured in
terms of the (exponentially more) succinct representations. The algorithm for
the symmetric case also shows that the recent dichotomy theorem for Holant
problems with symmetric constraints is efficiently decidable. Our proof
techniques are mainly algebraic, e.g., using stabilizers and orbits of group
actions.

We prove a complexity dichotomy theorem for Holant problems over an arbitrary
set of complexvalued symmetric constraint functions F on Boolean variables.
This extends and unifies all previous dichotomies for Holant problems on
symmetric constraint functions (taking values without a finite modulus). We
define and characterize all symmetric vanishing signatures. They turned out to
be essential to the complete classification of Holant problems. The dichotomy
theorem has an explicit tractability criterion expressible in terms of
holographic transformations. A Holant problem defined by a set of constraint
functions F is solvable in polynomial time if it satisfies this tractability
criterion, and is #Phard otherwise. The tractability criterion can be
intuitively stated as follows: A set F is tractable if (1) every function in F
has arity at most two, or (2) F is transformable to an affine type, or (3) F is
transformable to a product type, or (4) F is vanishing, combined with the right
type of binary functions, or (5) F belongs to a special category of vanishing
type Fibonacci gates. The proof of this theorem utilizes many previous
dichotomy theorems on Holant problems and Boolean #CSP. Holographic
transformations play an indispensable role as both a proof technique and in the
statement of the tractability criterion.

For Markov chain Monte Carlo methods, one of the greatest discrepancies
between theory and system is the scan order  while most theoretical
development on the mixing time analysis deals with random updates, realworld
systems are implemented with systematic scans. We bridge this gap for models
that exhibit a bipartite structure, including, most notably, the
Restricted/Deep Boltzmann Machine. The de facto implementation for these models
scans variables in a layerwise fashion. We show that the Gibbs sampler with a
layerwise alternating scan order has its relaxation time (in terms of epochs)
no larger than that of a randomupdate Gibbs sampler (in terms of variable
updates). We also construct examples to show that this bound is asymptotically
tight. Through standard inequalities, our result also implies a comparison on
the mixing times.

We show that the Clifford gates and stabilizer circuits in the quantum
computing literature, which admit efficient classical simulation, are
equivalent to affine signatures under a unitary condition. The latter is a
known class of tractable functions under the Holant framework.

It is known that the Bloch brane is generated by an odd scalar field $\phi$
and an even one $\chi$. In order to localize a bulk fermion on the Bloch brane,
the coupling between the fermion and scalars should be introduced. { There are
two localization mechanisms in the literature, the Yukawa coupling $\eta
\bar{\Psi} F_1(\phi,\chi) \Psi$ and nonYukawa coupling $\lambda \bar \Psi
\Gamma^M \partial_M F_2(\phi,\chi) \gamma^5 \Psi $. The Yukawa coupling has
been considered.} In this paper, we consider { both couplings between the
fermion and the scalars with $F_1=\chi^m\phi^{2p+1}$ and
$F_2=\chi^n\phi^{2q}$}, and investigate the localization and spectrum structure
of the fermion on the Bloch brane. { It is found that the} lefthanded fermion
zero mode can be localized on the Bloch brane under some conditions, and the
effective potentials have { rich} structure and may be volcanolike, finite
square welllike, and infinite potentials. As a result, the spectrum { consists
of} a series of resonant KaluzaKlein fermions, finite or infinite numbers of
bound KaluzaKlein fermions. { Especially, we find a new feature of the
introduction of both couplings: the spectrum for the case of finite square
welllike potentials contains discrete quasilocalized and localized massive KK
modes simultaneously.

We study the complexity of approximately evaluating the Ising and Tutte
partition functions with complex parameters. Our results are partly motivated
by the study of the quantum complexity classes BQP and IQP. Recent results show
how to encode quantum computations as evaluations of classical partition
functions. These results rely on interesting and deep results about quantum
computation in order to obtain hardness results about the difficulty of
(classically) evaluating the partition functions for certain fixed parameters.
The motivation for this paper is to study more comprehensively the complexity
of (classically) approximating the Ising and Tutte partition functions with
complex parameters. Partition functions are combinatorial in nature and
quantifying their approximation complexity does not require a detailed
understanding of quantum computation. Using combinatorial arguments, we give
the first full classification of the complexity of multiplicatively
approximating the norm and additively approximating the argument of the Ising
partition function for complex edge interactions (as well as of approximating
the partition function according to a natural complex metric). We also study
the norm approximation problem in the presence of external fields, for which we
give a complete dichotomy when the parameters are roots of unity. Previous
results were known just for a few such points, and we strengthen these results
from BQPhardness to #Phardness. Moreover, we show that computing the sign of
the Tutte polynomial is #Phard at certain points related to the simulation of
BQP. Using our classifications, we then revisit the connections to quantum
computation, drawing conclusions that are a little different from (and
incomparable to) ones in the quantum literature, but along similar lines.

We show that the mixing time of Glauber (single edge update) dynamics for the
random cluster model at $q=2$ is bounded by a polynomial in the size of the
underlying graph. As a consequence, the SwendsenWang algorithm for the
ferromagnetic Ising model at any temperature has the same polynomial mixing
time bound.

In this paper, we investigate the problem of localization and the Hodge
duality for a $q$form field on a $p$brane with codimension one. By a general
KaluzaKlein (KK) decomposition without gauge fixing, we obtain two
Schr\"{o}dingerlike equations for two types of KK modes of the bulk $q$form
field, which determine the localization and mass spectra of these KK modes. It
is found that there are two types of zero modes (the $0$level modes): a
$q$form zero mode and a $(q1)$form one, which cannot be localized on the
brane at the same time. For the $n$level KK modes, there are two interacting
KK modes, a massive $q$form KK mode and a massless $(q1)$form one. By
analyzing gauge invariance of the effective action and choosing a gauge
condition, the $n$level massive $q$form KK mode decouples from the $n$level
massless $(q1)$form one. It is also found that the Hodge duality in the bulk
naturally becomes two dualities on the brane. The first one is the Hodge
duality between a $q$form zero mode and a $(pq1)$form one, or between a
$(q1)$form zero mode and a $(pq)$form one. The second duality is between
two group KK modes: one is an $n$level massive $q$form KK mode with mass
$m_n$ and an $n$level massless $(q1)$form mode; another is an $n$level
$(pq)$form one with the same mass $m_n$ and an $n$level massless
$(pq1)$form mode. Because of the dualities, the effective field theories on
the brane for the KK modes of the two dual bulk form fields are physically
equivalent.

Counting independent sets on bipartite graphs (#BIS) is considered a
canonical counting problem of intermediate approximation complexity. It is
conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to
approximate. We study #BIS in the general framework of twostate spin systems
on bipartite graphs. We define two notions, nearlyindependent phasecorrelated
spins and unary symmetry breaking. We prove that it is #BIShard to approximate
the partition function of any 2spin system on bipartite graphs supporting
these two notions. As a consequence, we classify the complexity of
approximating the partition function of antiferromagnetic 2spin systems on
boundeddegree bipartite graphs.

We prove a complexity dichotomy for complexweighted Holant problems with an
arbitrary set of symmetric constraint functions on Boolean variables. This
dichotomy is specifically to answer the question: Is the FKT algorithm under a
holographic transformation a \emph{universal} strategy to obtain
polynomialtime algorithms for problems over planar graphs that are intractable
in general? This dichotomy is a culmination of previous ones, including those
for Spin Systems, Holant, and #CSP. A recurring theme has been that a
holographic reduction to FKT is a universal strategy. Surprisingly, for planar
Holant, we discover new planar tractable problems that are not expressible by a
holographic reduction to FKT.
In previous work, an important tool was a dichotomy for #CSP^d, which denotes
#CSP where every variable appears a multiple of d times. However its proof
violates planarity. We prove a dichotomy for planar #CSP^2. We apply this
planar #CSP^2 dichotomy in the proof of the planar Holant dichotomy.
As a special case of our new planar tractable problems, counting perfect
matchings (#PM) over kuniform hypergraphs is polynomialtime computable when
the incidence graph is planar and k >= 5. The same problem is #Phard when k=3
or k=4, which is also a consequence of our dichotomy. When k=2, it becomes #PM
over planar graphs and is tractable again. More generally, over hypergraphs
with specified hyperedge sizes and the same planarity assumption, #PM is
polynomialtime computable if the greatest common divisor of all hyperedge
sizes is at least 5.

Localization of a spin$1/2$ fermion on the braneworld is an important and
interesting problem. It is well known that a fivedimensional free massless
fermion $\Psi$ minimally coupled to gravity cannot be localized on the
RandallSundrum braneworld. In order to trap such a fermion, the coupling
between the fermion and bulk scalar fields should be introduced. In this paper,
localization and quasilocalization of a bulk fermion on the thick braneworld
generated by two scalar fields (a kink scalar $\phi$ and a dilaton scalar
$\pi$) are investigated. Two types of couplings between the fermion and two
scalars are considered. One coupling is the usual Yukawa coupling
$\eta\bar{\Psi}\phi\Psi$ between the fermion and kink scalar, another one is
$\lambda\bar{\Psi}\Gamma^{M}\partial_{M}\pi\gamma^{5}\Psi$ between the fermion
and dilaton scalar. The leftchiral fermion zero mode can be localized on the
brane, and both the left and rightchiral fermion massive KaluzaKlein modes
may be localized or quasilocalized. Hence the fourdimensional massless
leftchiral fermion and massive Dirac fermions, whose lifetime is infinite or
finite, can be obtained on the brane.

In this paper, we investigate localization of a free massless $q$form bulk
field on thin and thick $AdS_{p+1}$ branes with codimension one. It is found
that the zero mode of the $q$form field with $q>(p+2)/2$ can be localized on
the thin negative tension brane, which is different from the flat brane case
given in [JHEP 10 (2012) 060]. For the thick $AdS_{p+1}$ branes, the $q$form
field with $q>(p+2)/2$ also has a localized zero mode under some conditions.
Furthermore, we find that there are massive bound KK modes of the $q$form
field, which are localized on this type $p$branes.

We show that an effective version of Siegel's Theorem on finiteness of
integer solutions and an application of elementary Galois theory are key
ingredients in a complexity classification of some Holant problems. These
Holant problems, denoted by Holant(f), are defined by a symmetric ternary
function f that is invariant under any permutation of the k >= 3 domain
elements. We prove that Holant(f) exhibits a complexity dichotomy. This
dichotomy holds even when restricted to planar graphs. A special case of this
result is that counting edge kcolorings is #Phard over planar 3regular
graphs for k >= 3. In fact, we prove that counting edge kcolorings is #Phard
over planar rregular graphs for all k >= r >= 3. The problem is
polynomialtime computable in all other parameter settings. The proof of the
dichotomy theorem for Holant(f) depends on the fact that a specific polynomial
p(x,y) has an explicitly listed finite set of integer solutions, and the
determination of the Galois groups of some specific polynomials. In the
process, we also encounter the Tutte polynomial, medial graphs, Eulerian
partitions, Puiseux series, and a certain lattice condition on the (logarithm
of) the roots of polynomials.

We prove a complexity dichotomy theorem for symmetric complexweighted
Boolean #CSP when the constraint graph of the input must be planar. The
problems that are #Phard over general graphs but tractable over planar graphs
are precisely those with a holographic reduction to matchgates. This
generalizes a theorem of Cai, Lu, and Xia for the case of real weights. We also
obtain a dichotomy theorem for a symmetric arity 4 signature with complex
weights in the planar Holant framework, which we use in the proof of our #CSP
dichotomy. In particular, we reduce the problem of evaluating the Tutte
polynomial of a planar graph at the point (3,3) to counting the number of
Eulerian orientations over planar 4regular graphs to show the latter is
#Phard. This strengthens a theorem by Huang and Lu to the planar setting. Our
proof techniques combine new ideas with refinements and extensions of existing
techniques. These include planar pairings, the recursive unary construction,
the antigadget technique, and pinning in the Hadamard basis.

In this paper we investigate the localization and mass spectra of matter
fields with spin 0, 1 and 1/2 on a geometric thick brane generated by pure 4D
and 5D positive cosmological constants without bulk scalar fields. This model
possesses a 4D cosmological constant that can be made as small as one desires
without finetuning it with the bulk cosmological constant. The RS model is
obtained as an analytic continuation of the flat brane limit of this braneworld
configuration when the Hubble parameter disappears. Within this inflating
braneworld model it is possible to formulate a mechanism for obtaining TeV mass
scales from Planck ones by adding a positive thin brane, where the Standard
Model fields are trapped, at a distance y_2 from the origin, where the Planck
thick brane resides. The brane separation must be of the same order than the
inverse thickness parameter of the model in order for the mechanism to generate
the desired hierarchy. This result is obtained by imposing the recovery of both
the correct 4D gravitational couplings and the actually observed accelerated
expansion of the universe in our de Sitter braneworld. Regarding the
localization of matter in the purely geometric thick braneworld, for spin 0
massless and massive scalar fields as well as for spin 1 vector fields, the
potentials of the KaluzaKlein (KK) modes in thecorresponding Schroedinger
equations are modified PoeschlTeller potentials, which lead to the
localization of the scalar and vector zero modes on the brane as well as to
mass gaps in the mass spectra. We also compute the corrections to Coulomb's law
coming from massive KK vector modes. For spin 1/2 fermions, we introduce the
bulk mass term MF(z)\bar{\Psi}\Psi in the action and show that localization of
the massless leftchiral fermion zero mode is feasible for two mass functions
MF(z) with a finite/infinite number of massive KK bound states.

In this paper, we investigate the localization of the KalbRamond field on
symmetric and asymmetric thick branes, which are generated by a background
scalar field. In order to localize the KalbRamond field, we introduce a
coupling with the background scalar field, and find that there exist some
KaluzaKlein resonant modes. For the case of symmetric brane, we seek the
resonances by using the relative probability method and transfer matrix method,
and obtain the same result for the two methods. For the asymmetric case, we use
the transfer matrix method. We find that the number of resonances will decrease
with the increase of the asymmetry.

We investigate the thermodynamic geometry and phase transition of
KehagiasSfetsos black hole in the deformed HoravaLifshitz gravity with
coupling constant $\lambda=1$. The phase transition in black hole
thermodynamics is thought to be associated with the divergence of the
capacities. And the structures of these divergent points are studied. We also
find that the thermodynamic curvature produced by the Ruppeiner metric is
positive definite for all $r_+ > r_$ and is divergence at $\eta_2=0$
corresponded to the divergent points of $C_{\Phi}$ and $C_T$. These results
suggest that the microstructure of the black hole has an effective repulsive
interaction, which is very similar to the ideal gas of fermions. These may
shine some light on the microstructure of the black hole.

Recently, inspired by Eddington's theory, an alternative gravity called
Eddingtoninspired BornInfeld gravity was proposed by Ba$\tilde{\text{n}}$ados
and Ferreira. It is equivalent to Einstein's general relativity in vacuum, but
deviates from it when matter is included. Interestingly, it seems that the
cosmological singularities are prevented in this theory. Based on the new
theory, we investigate a thick brane model with a scalar field presenting in
the fivedimensional background. A domain wall solution is obtained, and
further, we find that at low energy the fourdimensional Einstein gravity is
recovered on the brane. Moreover, the stability of gravitational perturbations
is ensured in this model.

In this paper, we investigate thick branes with a nonminimally coupled
background scalar field, whose solution is a singlekink or a doublekink. The
effects of the nonminimal coupling constant $\xi$ on the structure of the thick
branes and the localization of gravity, fermions, scalars and vectors are
discussed. It is shown that each brane will split into two subbranes as
increasing the nonminimal coupling constant $\xi$. By investigating the tensor
perturbation equations of gravity and the general covariant Dirac equation of
fermions, we find that both the gravity zero mode and leftchiral fermion zero
mode are localized at the center of the singlekink branes and localized
between the two subbranes generated by the doublekink, which indicates that
the constant $\xi$ does not effect the localization of these zero modes.
However, the zero mode of scalars is localized on each subbrane (for both
singlekink and doublekink branes) when $\xi$ is larger than its critical
value $\xi_0$. The effects of the nonminimal coupling constant $\xi$ on the
resonances of gravity and fermions with finite lifetime on the branes are also
discussed.