• ### A polynomial-time approximation algorithm for all-terminal network reliability(1709.08561)

Feb. 10, 2019 cs.DS
We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal 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 "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input.
• ### Approximation via Correlation Decay when Strong Spatial Mixing Fails(1510.09193)

Feb. 1, 2019 cs.DM, cs.CC
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 anti-ferromagnetic two-spin models. Previous analyses of correlation-decay algorithms implicitly depended on the occurrence of strong spatial mixing (SSM). This means that one uses worst-case analysis of the recursive procedure that creates the sub-instances. We develop a new analysis method that is more refined than the worst-case 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 upper-bound 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 previously-known approximation scheme for Delta=6 is the Markov-chain 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 NP-hard even within the uniqueness regime.
• ### Uniform Sampling through the Lov\'asz Local Lemma(1611.01647)

Jan. 15, 2019 math.CO, math.PR, cs.DS
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 "cycle-popping" algorithm for rooted spanning trees. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.
• ### Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems(1511.00493)

July 5, 2018 cs.DM, cs.DS
We give fully polynomial-time approximation schemes (FPTAS) for the partition function of ferromagnetic 2-spin 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.
• ### Prediction of two-dimensional nodal-line semimetal in a carbon nitride covalent network(1803.06835)

March 19, 2018 cond-mat.mtrl-sci
Carbon nitride compounds have emerged recently as a prominent member of 2D materials beyond graphene. The experimental realizations of 2D graphitic carbon nitride g-C$_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 C-N compounds and covalent organic frameworks (COFs), which are typically insulating, surprisingly C$_9$N$_4$ is found to be a 2D nodal-line 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 spin-orbital-coupling (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 tight-binding model, rather than protected by crystal in-plane mirror symmetry or band topology. Interestingly, a new structure of nodal line, i.e., nodal-cylinder, is found in momentum space for AA-stacking C$_9$N$_4$. Our results imply possible functionalization for a novel metal-free C-N covalent network with interesting semimetallic properties.
• ### Perfect simulation of the Hard Disks Model by Partial Rejection Sampling(1801.07342)

Jan. 22, 2018 math.PR, cs.DS
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 Beyond Matchgates(1307.7430)

Jan. 10, 2018 cs.DS, cs.CC
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 polynomial-time algorithms to decide if a given counting problem has a holographic reduction to another problem defined by the affine or product-type functions. Our algorithms also find a holographic transformation when one exists. We further present polynomial-time 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.
• ### A Complete Dichotomy Rises from the Capture of Vanishing Signatures(1204.6445)

Jan. 10, 2018 cs.CC
We prove a complexity dichotomy theorem for Holant problems over an arbitrary set of complex-valued 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 #P-hard 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.
• ### Layerwise Systematic Scan: Deep Boltzmann Machines and Beyond(1705.05154)

Oct. 9, 2017 cs.DS, cs.LG
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, real-world 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 random-update 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.
• ### Clifford Gates in the Holant Framework(1705.00942)

May 2, 2017 quant-ph, cs.CC
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.
• ### Spectrum Structure of Fermion on Bloch Branes with Two Scalar-fermion Couplings(1510.03345)

Feb. 10, 2017 hep-th, gr-qc
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 non-Yukawa 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} left-handed fermion zero mode can be localized on the Bloch brane under some conditions, and the effective potentials have { rich} structure and may be volcano-like, finite square well-like, and infinite potentials. As a result, the spectrum { consists of} a series of resonant Kaluza-Klein fermions, finite or infinite numbers of bound Kaluza-Klein fermions. { Especially, we find a new feature of the introduction of both couplings: the spectrum for the case of finite square well-like potentials contains discrete quasi-localized and localized massive KK modes simultaneously.
• ### The complexity of approximating complex-valued Ising and Tutte partition functions(1409.5627)

Jan. 22, 2017 quant-ph, cs.CC
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 BQP-hardness to #P-hardness. Moreover, we show that computing the sign of the Tutte polynomial is #P-hard 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.
• ### Random cluster dynamics for the Ising model is rapidly mixing(1605.00139)

April 30, 2016 math.PR, cs.DS
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 Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.
• ### New localization mechanism and Hodge duality for $q-$form field(1502.05456)

March 1, 2016 hep-th
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 Kaluza-Klein (KK) decomposition without gauge fixing, we obtain two Schr\"{o}dinger-like 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 $(q-1)-$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 $(q-1)-$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 $(q-1)-$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 $(p-q-1)-$form one, or between a $(q-1)-$form zero mode and a $(p-q)-$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 $(q-1)-$form mode; another is an $n-$level $(p-q)-$form one with the same mass $m_n$ and an $n-$level massless $(p-q-1)-$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.
• ### #BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Nonuniqueness Region(1311.4451)

Sept. 21, 2015 cs.CC
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 two-state spin systems on bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. As a consequence, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs.
• ### A Holant Dichotomy: Is the FKT Algorithm Universal?(1505.02993)

May 12, 2015 cs.DS, cs.CC
We prove a complexity dichotomy for complex-weighted 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 polynomial-time 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 k-uniform hypergraphs is polynomial-time computable when the incidence graph is planar and k >= 5. The same problem is #P-hard 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 polynomial-time computable if the greatest common divisor of all hyperedge sizes is at least 5.
• ### Localization and quasilocalization of spin-$1/2$ fermion field on two-field thick braneworld(1408.6155)

Aug. 24, 2014 hep-th, hep-ph, gr-qc
Localization of a spin-$1/2$ fermion on the braneworld is an important and interesting problem. It is well known that a five-dimensional free massless fermion $\Psi$ minimally coupled to gravity cannot be localized on the Randall-Sundrum 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 left-chiral fermion zero mode can be localized on the brane, and both the left- and right-chiral fermion massive Kaluza-Klein modes may be localized or quasilocalized. Hence the four-dimensional massless left-chiral fermion and massive Dirac fermions, whose lifetime is infinite or finite, can be obtained on the brane.
• ### Localization of $q-$form fields on $AdS_{p+1}$ branes(1312.2647)

June 13, 2014 hep-th
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.
• ### The Complexity of Counting Edge Colorings and a Dichotomy for Some Higher Domain Holant Problems(1404.4020)

April 15, 2014 cs.CC
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 k-colorings is #P-hard over planar 3-regular graphs for k >= 3. In fact, we prove that counting edge k-colorings is #P-hard over planar r-regular graphs for all k >= r >= 3. The problem is polynomial-time 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.
• ### The Complexity of Planar Boolean #CSP with Complex Weights(1212.2284)

Aug. 6, 2013 cs.DS, cs.CC
We prove a complexity dichotomy theorem for symmetric complex-weighted Boolean #CSP when the constraint graph of the input must be planar. The problems that are #P-hard 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 4-regular graphs to show the latter is #P-hard. 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 anti-gadget technique, and pinning in the Hadamard basis.
• ### Localization of bulk matter fields, the hierarchy problem and corrections to Coulomb's law on a pure de Sitter thick braneworld(1103.2430)

May 20, 2013 hep-th
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 fine-tuning 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 Kaluza--Klein (KK) modes in thecorresponding Schroedinger equations are modified Poeschl-Teller 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 left-chiral fermion zero mode is feasible for two mass functions MF(z) with a finite/infinite number of massive KK bound states.
• ### Resonances of Kalb-Ramond field on symmetric and asymmetric thick branes(1301.3204)

Jan. 15, 2013 hep-th
In this paper, we investigate the localization of the Kalb-Ramond field on symmetric and asymmetric thick branes, which are generated by a background scalar field. In order to localize the Kalb-Ramond field, we introduce a coupling with the background scalar field, and find that there exist some Kaluza-Klein 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.
• ### Thermodynamic Geometry of black hole in the deformed Horava-Lifshitz gravity(1002.1550)

Oct. 13, 2012 hep-th, gr-qc
We investigate the thermodynamic geometry and phase transition of Kehagias-Sfetsos black hole in the deformed Horava-Lifshitz 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.
• ### Domain Wall Brane in Eddington Inspired Born-Infeld Gravity(1203.2349)

June 23, 2012 hep-th, gr-qc
Recently, inspired by Eddington's theory, an alternative gravity called Eddington-inspired Born-Infeld 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 five-dimensional background. A domain wall solution is obtained, and further, we find that at low energy the four-dimensional Einstein gravity is recovered on the brane. Moreover, the stability of gravitational perturbations is ensured in this model.
• ### Thick branes with a nonminimally coupled bulk-scalar field(1106.5216)

June 23, 2012 hep-th, gr-qc
In this paper, we investigate thick branes with a nonminimally coupled background scalar field, whose solution is a single-kink or a double-kink. 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 sub-branes 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 left-chiral fermion zero mode are localized at the center of the single-kink branes and localized between the two sub-branes generated by the double-kink, 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 sub-brane (for both single-kink and double-kink 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.