4 Search Results for "Zhang, Xue"

Document
DOI: 10.4230/LIPIcs.SEA.2024.6
Faster Treewidth-Based Approximations for Wiener Index

Authors: Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani

Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)

Abstract
The Wiener index of a graph G is the sum of distances between all pairs of its vertices. It is a widely-used graph property in chemistry, initially introduced to examine the link between boiling points and structural properties of alkanes, which later found notable applications in drug design. Thus, computing or approximating the Wiener index of molecular graphs, i.e. graphs in which every vertex models an atom of a molecule and every edge models a bond, is of significant interest to the computational chemistry community. In this work, we build upon the observation that molecular graphs are sparse and tree-like and focus on developing efficient algorithms parameterized by treewidth to approximate the Wiener index. We present a new randomized approximation algorithm using a combination of tree decompositions and centroid decompositions. Our algorithm approximates the Wiener index within any desired multiplicative factor (1 ± ε) in time O(n ⋅ log n ⋅ k³ + √n ⋅ k/ε²), where n is the number of vertices of the graph and k is the treewidth. This time bound is almost-linear in n. Finally, we provide experimental results over standard benchmark molecules from PubChem and the Protein Data Bank, showcasing the applicability and scalability of our approach on real-world chemical graphs and comparing it with previous methods.
Cite as

Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6,
  author =	{Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra},
  title =	{{Faster Treewidth-Based Approximations for Wiener Index}},
  booktitle =	{22nd International Symposium on Experimental Algorithms (SEA 2024)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-325-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{301},
  editor =	{Liberti, Leo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.6},
  URN =		{urn:nbn:de:0030-drops-203718},
  doi =		{10.4230/LIPIcs.SEA.2024.6},
  annote =	{Keywords: Computational Chemistry, Treewidth, Wiener Index}
}
Document
DOI: 10.4230/LIPIcs.ECOOP.2016.15
Program Tailoring: Slicing by Sequential Criteria

Authors: Yue Li, Tian Tan, Yifei Zhang, and Jingling Xue

Published in: LIPIcs, Volume 56, 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
Protocol and typestate analyses often report some sequences of statements ending at a program point P that needs to be scrutinized, since P may be erroneous or imprecisely analyzed. Program slicing focuses only on the behavior at P by computing a slice of the program affecting the values at P. In this paper, we propose to restrict our attention to the subset of that behavior at P affected by one or several statement sequences, called a sequential criterion (SC). By leveraging the ordering information in a SC, e.g., the temporal order in a few valid/invalid API method invocation sequences, we introduce a new technique, program tailoring, to compute a tailored program that comprises the statements in all possible execution paths passing through at least one sequence in SC in the given order. With a prototyping implementation, Tailor, we show why tailoring is practically useful by conducting two case studies on seven large real-world Java applications. For program debugging and understanding, Tailor can complement program slicing by removing SC-irrelevant statements. For program analysis, Tailor can enable a pointer analysis, which is unscalable to a program, to perform a more focused and therefore potentially scalable analysis to its specific parts containing hard language features such as reflection.
Cite as

Yue Li, Tian Tan, Yifei Zhang, and Jingling Xue. Program Tailoring: Slicing by Sequential Criteria. In 30th European Conference on Object-Oriented Programming (ECOOP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 56, pp. 15:1-15:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ECOOP.2016.15,
  author =	{Li, Yue and Tan, Tian and Zhang, Yifei and Xue, Jingling},
  title =	{{Program Tailoring: Slicing by Sequential Criteria}},
  booktitle =	{30th European Conference on Object-Oriented Programming (ECOOP 2016)},
  pages =	{15:1--15:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-014-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{56},
  editor =	{Krishnamurthi, Shriram and Lerner, Benjamin S.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2016.15},
  URN =		{urn:nbn:de:0030-drops-61092},
  doi =		{10.4230/LIPIcs.ECOOP.2016.15},
  annote =	{Keywords: Program Slicing, Program Analysis, API Protocol Analysis}
}
Document
DOI: 10.4230/DARTS.2.1.8
Program Tailoring: Slicing by Sequential Criteria (Artifact)

Authors: Tian Tan, Yue Li, Yifei Zhang, and Jingling Xue

Published in: DARTS, Volume 2, Issue 1, Special Issue of the 30th European Conference on Object-Oriented Programming (ECOOP 2016)

Abstract
Protocol and typestate analyses often report some sequences of statements ending at a program point P that needs to be scrutinized, since P may be erroneous or imprecisely analyzed. Program slicing focuses only on the behavior at P by computing a slice of the program affecting the values at P. In our companion paper "Program Tailoring: Slicing by Sequential Criteria", we propose to focus on the subset of that behavior at P affected by one or several statement sequences, called a sequential criterion (SC). By leveraging the ordering information in a SC, e.g., the temporal order in a few valid/invalid API method invocation sequences, we introduce a new technique, program tailoring, to compute a tailored program that comprises the statements in all possible execution paths passing through at least one sequence in SC in the given order. This artifact is based on TAILOR, a prototyping implementation of program tailoring, to evaluate the usefulness of TAILOR in practice. The provided package is designed to support repeatability of all the experiments of our companion paper. Specifically, it allows users to reproduce the results for all the three research questions addressed in the evaluation section of our companion paper. In addition, an extensive set of extra results, which are not described in the companion paper, are also included, in order to help users better understand this work.
Cite as

Tian Tan, Yue Li, Yifei Zhang, and Jingling Xue. Program Tailoring: Slicing by Sequential Criteria (Artifact). In Special Issue of the 30th European Conference on Object-Oriented Programming (ECOOP 2016). Dagstuhl Artifacts Series (DARTS), Volume 2, Issue 1, pp. 8:1-8:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{tan_et_al:DARTS.2.1.8,
  author =	{Tan, Tian and Li, Yue and Zhang, Yifei and Xue, Jingling},
  title =	{{Program Tailoring: Slicing by Sequential Criteria (Artifact)}},
  pages =	{8:1--8:3},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2016},
  volume =	{2},
  number =	{1},
  editor =	{Tan, Tian and Li, Yue and Zhang, Yifei and Xue, Jingling},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.2.1.8},
  URN =		{urn:nbn:de:0030-drops-61298},
  doi =		{10.4230/DARTS.2.1.8},
  annote =	{Keywords: Program Slicing, Program Analysis, API Protocol Specification}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.28
Complexity Classification of Two-Qubit Commuting Hamiltonians

Authors: Adam Bouland, Laura Mancinska, and Xue Zhang

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We classify two-qubit commuting Hamiltonians in terms of their computational complexity. Suppose one has a two-qubit commuting Hamiltonian H which one can apply to any pair of qubits, starting in a computational basis state. We prove a dichotomy theorem: either this model is efficiently classically simulable or it allows one to sample from probability distributions which cannot be sampled from classically unless the polynomial hierarchy collapses. Furthermore, the only simulable Hamiltonians are those which fail to generate entanglement. This shows that generic two-qubit commuting Hamiltonians can be used to perform computational tasks which are intractable for classical computers under plausible assumptions. Our proof makes use of new postselection gadgets and Lie theory.
Cite as

Adam Bouland, Laura Mancinska, and Xue Zhang. Complexity Classification of Two-Qubit Commuting Hamiltonians. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 28:1-28:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{bouland_et_al:LIPIcs.CCC.2016.28,
  author =	{Bouland, Adam and Mancinska, Laura and Zhang, Xue},
  title =	{{Complexity Classification of Two-Qubit Commuting Hamiltonians}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{28:1--28:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.28},
  URN =		{urn:nbn:de:0030-drops-58469},
  doi =		{10.4230/LIPIcs.CCC.2016.28},
  annote =	{Keywords: Quantum Computing, Sampling Problems, Commuting Hamiltonians, IQP, Gate Classification Theorems}
}
  • Refine by Author
  • 2 Li, Yue
  • 2 Tan, Tian
  • 2 Xue, Jingling
  • 2 Zhang, Yifei
  • 1 Bouland, Adam
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 2 Program Analysis
  • 2 Program Slicing
  • 1 API Protocol Analysis
  • 1 API Protocol Specification
  • 1 Commuting Hamiltonians
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 3 2016
  • 1 2024

© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact