Search Results

Documents authored by Chen, Shiteng

Document
DOI: 10.4230/LIPIcs.STACS.2024.49
Sub-Exponential Time Lower Bounds for #VC and #Matching on 3-Regular Graphs

Authors: Ying Liu and Shiteng Chen

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
This article focuses on the sub-exponential time lower bounds for two canonical #P-hard problems: counting the vertex covers of a given graph (#VC) and counting the matchings of a given graph (#Matching), under the well-known counting exponential time hypothesis (#ETH). Interpolation is an essential method to build reductions in this article and in the literature. We use the idea of block interpolation to prove that both #VC and #Matching have no 2^{o(N)} time deterministic algorithm, even if the given graph with N vertices is a 3-regular graph. However, when it comes to proving the lower bounds for #VC and #Matching on planar graphs, both block interpolation and polynomial interpolation do not work. We prove that, for any integer N > 0, we can simulate N pairwise linearly independent unary functions by gadgets with only O(log N) size in the context of #VC and #Matching. Then we use log-size gadgets in the polynomial interpolation to prove that planar #VC and planar #Matching have no 2^{o(√{N/(log N)})} time deterministic algorithm. The lower bounds hold even if the given graph with N vertices is a 3-regular graph. Based on a stronger hypothesis, randomized exponential time hypothesis (rETH), we can avoid using interpolation. We prove that if rETH holds, both planar #VC and planar #Matching have no 2^{o(√N)} time randomized algorithm, even that the given graph with N vertices is a planar 3-regular graph. The 2^{Ω(√N)} time lower bounds are tight, since there exist 2^{O(√N)} time algorithms for planar #VC and planar #Matching. We also develop a fine-grained dichotomy for a class of counting problems, symmetric Holant*.
Cite as

Ying Liu and Shiteng Chen. Sub-Exponential Time Lower Bounds for #VC and #Matching on 3-Regular Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 49:1-49:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.STACS.2024.49,
  author =	{Liu, Ying and Chen, Shiteng},
  title =	{{Sub-Exponential Time Lower Bounds for #VC and #Matching on 3-Regular Graphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{49:1--49:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.49},
  URN =		{urn:nbn:de:0030-drops-197593},
  doi =		{10.4230/LIPIcs.STACS.2024.49},
  annote =	{Keywords: computational complexity, planar Holant, polynomial interpolation, rETH, sub-exponential, #ETH, #Matching, #VC}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.8
From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces

Authors: Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
In the 1970’s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017). In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration. (Dedicated to the memory of Ker-I Ko)
Cite as

Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun. From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 8:1-8:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bei_et_al:LIPIcs.ITCS.2020.8,
  author =	{Bei, Xiaohui and Chen, Shiteng and Guan, Ji and Qiao, Youming and Sun, Xiaoming},
  title =	{{From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge Between Graphs and Alternating Matrix Spaces}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{8:1--8:48},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.8},
  URN =		{urn:nbn:de:0030-drops-116932},
  doi =		{10.4230/LIPIcs.ITCS.2020.8},
  annote =	{Keywords: independent set, vertex coloring, graphs, matrix spaces, isotropic subspace}
}
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 Imprint Privacy Contact