Arrow Research search

Author name cluster

Mingji Xia

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

13 papers
2 author rows

Possible papers

13

FOCS Conference 2017 Conference Paper

Variable-Version Lovász Local Lemma: Beyond Shearer's Bound

  • Kun He 0011
  • Liang Li
  • Xingwu Liu
  • Yuyi Wang 0001
  • Mingji Xia

A tight criterion under which the abstract version Lovász Local Lemma (abstract-LLL) holds was given by Shearer [41] decades ago. However, little is known about that of the variable version LLL (variable-LLL) where events are generated by independent random variables, though variable- LLL naturally models and is enough for almost all applications of LLL. We introduce a necessary and sufficient criterion for variable-LLL, in terms of the probabilities of the events and the event-variable graph specifying the dependency among the events. Based on this new criterion, we obtain boundaries for two families of event-variable graphs, namely, cyclic and treelike bigraphs. These are the first two non-trivial cases where the variable-LLL boundary is fully determined. As a byproduct, we also provide a universal constructive method to find a set of events whose union has the maximum probability, given the probability vector and the event-variable graph. Though it is #P-hard in general to determine variable- LLL boundaries, we can to some extent decide whether a gap exists between a variable-LLL boundary and the corresponding abstract-LLL boundary. In particular, we show that the gap existence can be decided without solving Shearer’s conditions or checking our variable-LLL criterion. Equipped with this powerful theorem, we show that there is no gap if the base graph of the event-variable graph is a tree, while gap appears if the base graph has an induced cycle of length at least 4. The problem is almost completely solved except when the base graph has only 3-cliques, in which case we also get partial solutions. A set of reduction rules are established that facilitate to infer gap existence of a event-variable graph from known ones. As an application, various event-variable graphs, in particular combinatorial ones, are shown to be gapful/gapless.

Details

STOC Conference 2016 Conference Paper

Base collapse of holographic algorithms

  • Mingji Xia

A holographic algorithm solves a problem in a domain of size n , by reducing it to counting perfect matchings in planar graphs. It may simulate a n -value variable by a bunch of t matchgate bits, which has 2 t values. The transformation in the simulation can be expressed as a n × 2 t matrix M , called the base of the holographic algorithm. We wonder whether more matchgate bits bring us more powerful holographic algorithms. In another word, whether we can solve the same original problem, with a collapsed base of size n × 2 r , where r < t .

Details

FOCS Conference 2015 Conference Paper

Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k

  • Radu Curticapean
  • Mingji Xia

We identify and study relevant structural parameters for the problem PerfMatch of counting perfect matchings in a given input graph C. These generalize the well-known tractable planar case, and they include the genus of C, its apex number (the minimum number of vertices whose removal renders C planar), and its Hadwiger number (the size of a largest clique minor). To study these parameters, we first introduce the notion of combined matchgates, a general technique that bridges parameterized counting problems and the theory of so-called Holants and matchgates: Using combined matchgates, we can simulate certain nonexisting gadgets F as linear combinations of L = O(1) existing gadgets. If a graph C features k occurrences of F, we can then reduce C to t k graphs that feature only existing gadgets, thus enabling parameterized reductions. As applications of this technique, we simplify known 4 g n O(1) time algorithms for PerfMatch on graphs of genus g. Orthogonally to this, we show #W[1]-hardness of the permanent on k-apex graphs, implying its ⊕W[1]-hardness under the Hadwiger number. Additionally, we rule out n o(k/ log k) time algorithms under the counting exponential-time hypothesis #ETH. Finally, we use combined matchgates to prove $W[1]-hardness of evaluating the permanent modulo 2k, complementing an O(n 4k-3 ) time algorithm by Valiant and answering an open question of Bjϋrklund. We also obtain a lower bound of n Ω(k/ log k) under the parity version $ETH of the exponential-time hypothesis.

Details

SODA Conference 2011 Conference Paper

Dichotomy for Holant* Problems of Boolean Domain

  • Jin-Yi Cai
  • Pinyan Lu
  • Mingji Xia

Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant*( F ), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique and indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i. e. , a (non-zero) vector whose inner product with itself is zero.

Details

FOCS Conference 2010 Conference Paper

Holographic Algorithms with Matchgates Capture Precisely Tractable Planar_#CSP

  • Jin-Yi Cai
  • Pinyan Lu
  • Mingji Xia

Valiant introduced match gate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, match gate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs, and can be arbitrary real-valued symmetric functions. We prove that, every problem in this class belongs to precisely three categories: (1) those which are tractable (i. e. , polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but ractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.

Details

STOC Conference 2009 Conference Paper

Holant problems and counting CSP

  • Jin-Yi Cai
  • Pinyan Lu
  • Mingji Xia

We propose and explore a novel alternative framework to study the complexity of counting problems, called Holant Problems. Compared to counting Constrained Satisfaction Problems (CSP), it is a refinement with a more explicit role for the function constraints. Both graph homomorphism and CSP can be viewed as special cases of Holant Problems. We prove complexity dichotomy theorems in this framework. Because the framework is more stringent, previous dichotomy theorems for CSP problems no longer apply. Indeed, we discover surprising tractable subclasses of counting problems, which could not have been easily specified in the CSP framework. The main technical tool we use and develop is holographic reductions. Another technical tool used in combination with holographic reductions is polynomial interpolations. The study of Holant Problems led us to discover and prove a complexity dichotomy theorem for the most general form of Boolean CSP where every constraint function takes values in the complex number field {C}.

Details

FOCS Conference 2008 Conference Paper

Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness

  • Jin-Yi Cai
  • Pinyan Lu
  • Mingji Xia

We propose a new method to prove complexity dichotomy theorems. First we introduce Fibonacci gates which provide a new class of polynomial time holographic algorithms. Then we develop holographic reductions. We show that holographic reductions followed by interpolations provide a uniform strategy to prove #P-hardness.

Details