Search Results

Documents authored by Lin, Jiabao

Document
DOI: 10.4230/LIPIcs.ITCS.2021.40
On the Complexity of #CSP^d

Authors: Jiabao Lin

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Counting CSP^d is the counting constraint satisfaction problem (#CSP in short) restricted to the instances where every variable occurs a multiple of d times. This paper revisits tractable structures in #CSP and gives a complexity classification theorem for #CSP^d with algebraic complex weights. The result unifies affine functions (stabilizer states in quantum information theory) and related variants such as the local affine functions, the discovery of which leads to all the recent progress on the complexity of Holant problems. The Holant is a framework that generalizes counting CSP. In the literature on Holant problems, weighted constraints are often expressed as tensors (vectors) such that projections and linear transformations help analyze the structure. This paper gives an example showing that different classes of tensors distinguished by these algebraic operations may share the same closure property under tensor product and contraction.
Cite as

Jiabao Lin. On the Complexity of #CSP^d. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 40:1-40:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lin:LIPIcs.ITCS.2021.40,
  author =	{Lin, Jiabao},
  title =	{{On the Complexity of #CSP^d}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{40:1--40:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.40},
  URN =		{urn:nbn:de:0030-drops-135793},
  doi =		{10.4230/LIPIcs.ITCS.2021.40},
  annote =	{Keywords: Constraint satisfaction problem, counting problems, Holant, complexity dichotomy}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.34
Counting Independent Sets and Colorings on Random Regular Bipartite Graphs

Authors: Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of independent sets on almost every Delta-regular bipartite graph if Delta >= 53. In the weighted case, for all sufficiently large integers Delta and weight parameters lambda = Omega~ (1/(Delta)), we also obtain an FPTAS on almost every Delta-regular bipartite graph. Our technique is based on the recent work of Jenssen, Keevash and Perkins (SODA, 2019) and we also apply it to confirm an open question raised there: For all q >= 3 and sufficiently large integers Delta=Delta(q), there is an FPTAS to count the number of q-colorings on almost every Delta-regular bipartite graph.
Cite as

Chao Liao, Jiabao Lin, Pinyan Lu, and Zhenyu Mao. Counting Independent Sets and Colorings on Random Regular Bipartite Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 34:1-34:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{liao_et_al:LIPIcs.APPROX-RANDOM.2019.34,
  author =	{Liao, Chao and Lin, Jiabao and Lu, Pinyan and Mao, Zhenyu},
  title =	{{Counting Independent Sets and Colorings on Random Regular Bipartite Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{34:1--34:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.34},
  URN =		{urn:nbn:de:0030-drops-112498},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.34},
  annote =	{Keywords: Approximate counting, Polymer model, Hardcore model, Coloring, Random bipartite graphs}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.29
The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights

Authors: Jiabao Lin and Hanpin Wang

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
Holant problem is a general framework to study the computational complexity of counting problems. We prove a complexity dichotomy theorem for Holant problems over the Boolean domain with non-negative weights. It is the first complete Holant dichotomy where constraint functions are not necessarily symmetric. Holant problems are indeed read-twice #CSPs. Intuitively, some #CSPs that are #P-hard become tractable when restricted to read-twice instances. To capture them, we introduce the Block-rank-one condition. It turns out that the condition leads to a clear separation. If a function set F satisfies the condition, then F is of affine type or product type. Otherwise (a) Holant(F) is #P-hard; or (b) every function in F is a tensor product of functions of arity at most 2; or (c) F is transformable to a product type by some real orthogonal matrix. Holographic transformations play an important role in both the hardness proof and the characterization of tractability.
Cite as

Jiabao Lin and Hanpin Wang. The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{lin_et_al:LIPIcs.ICALP.2017.29,
  author =	{Lin, Jiabao and Wang, Hanpin},
  title =	{{The Complexity of Holant Problems over Boolean Domain with Non-Negative Weights}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.29},
  URN =		{urn:nbn:de:0030-drops-73846},
  doi =		{10.4230/LIPIcs.ICALP.2017.29},
  annote =	{Keywords: counting complexity, dichotomy, Holant, #CSP}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact