2 Search Results for "Wang, Ji"

Document
DOI: 10.4230/LIPIcs.CP.2021.57
Making Rigorous Linear Programming Practical for Program Analysis

Authors: Tengbin Wang, Liqian Chen, Taoqing Chen, Guangsheng Fan, and Ji Wang

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract
Linear programming is a key technique for analysis and verification of numerical properties in programs, neural networks, etc. In particular, in program analysis based on abstract interpretation, many numerical abstract domains (such as Template Constraint Matrix, constraint-only polyhedra, etc.) are designed on top of linear programming. However, most state-of-the-art linear programming solvers use floating-point arithmetic in their implementations, leading to an approximate result that may be unsound. On the other hand, the solvers implemented using exact arithmetic are too costly. To this end, this paper focuses on advancing rigorous linear programming techniques based on floating-point arithmetic for building sound and efficient program analysis. Particularly, as a supplement to existing techniques, we present a novel rigorous linear programming technique based on Fourier-Mozkin elimination. On this basis, we implement a tool, namely, RlpSolver, combining our technique with existing techniques to lift effectiveness of rigorous linear programming in the scene of analysis and verification. Experimental results show that our technique is complementary to existing techniques, and their combination (RlpSolver) can achieve a better trade-off between cost and precision via heuristic rules.
Cite as

Tengbin Wang, Liqian Chen, Taoqing Chen, Guangsheng Fan, and Ji Wang. Making Rigorous Linear Programming Practical for Program Analysis. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 57:1-57:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.CP.2021.57,
  author =	{Wang, Tengbin and Chen, Liqian and Chen, Taoqing and Fan, Guangsheng and Wang, Ji},
  title =	{{Making Rigorous Linear Programming Practical for Program Analysis}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{57:1--57:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.57},
  URN =		{urn:nbn:de:0030-drops-153486},
  doi =		{10.4230/LIPIcs.CP.2021.57},
  annote =	{Keywords: Linear programming, rigorous linear programming, abstract interpretation, program analysis, Fourier-Mozkin elimination}
}
Document
DOI: 10.4230/LIPIcs.TQC.2013.192
Symmetries of Codeword Stabilized Quantum Codes

Authors: Salman Beigi, Jianxin Chen, Markus Grassl, Zhengfeng Ji, Qiang Wang, and Bei Zeng

Published in: LIPIcs, Volume 22, 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)

Abstract
Symmetry is at the heart of coding theory. Codes with symmetry, especially cyclic codes, play an essential role in both theory and practical applications of classical error-correcting codes. Here we examine symmetry properties for codeword stabilized (CWS) quantum codes, which is the most general framework for constructing quantum error-correcting codes known to date. A CWS code Q can be represented by a self-dual additive code S and a classical code C, i.e., Q=(S,C), however this representation is in general not unique. We show that for any CWS code Q with certain permutation symmetry, one can always find a self-dual additive code S with the same permutation symmetry as Q such that Q=(S,C). As many good CWS codes have been found by starting from a chosen S, this ensures that when trying to find CWS codes with certain permutation symmetry, the choice of S with the same symmetry will suffice. A key step for this result is a new canonical representation for CWS codes, which is given in terms of a unique decomposition as union stabilizer codes. For CWS codes, so far mainly the standard form (G,C) has been considered, where G is a graph state. We analyze the symmetry of the corresponding graph of G, which in general cannot possess the same permutation symmetry as Q. We show that it is indeed the case for the toric code on a square lattice with translational symmetry, even if its encoding graph can be chosen to be translational invariant.
Cite as

Salman Beigi, Jianxin Chen, Markus Grassl, Zhengfeng Ji, Qiang Wang, and Bei Zeng. Symmetries of Codeword Stabilized Quantum Codes. In 8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 22, pp. 192-206, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{beigi_et_al:LIPIcs.TQC.2013.192,
  author =	{Beigi, Salman and Chen, Jianxin and Grassl, Markus and Ji, Zhengfeng and Wang, Qiang and Zeng, Bei},
  title =	{{Symmetries of Codeword Stabilized Quantum Codes}},
  booktitle =	{8th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2013)},
  pages =	{192--206},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-55-2},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{22},
  editor =	{Severini, Simone and Brandao, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2013.192},
  URN =		{urn:nbn:de:0030-drops-43129},
  doi =		{10.4230/LIPIcs.TQC.2013.192},
  annote =	{Keywords: CWS Codes, Union Stabilizer Codes, Permutation Symmetry, Toric Code}
}
  • Refine by Author
  • 1 Beigi, Salman
  • 1 Chen, Jianxin
  • 1 Chen, Liqian
  • 1 Chen, Taoqing
  • 1 Fan, Guangsheng
  • Show More...

  • Refine by Classification
  • 1 Software and its engineering → Formal methods
  • 1 Theory of computation → Linear programming

  • Refine by Keyword
  • 1 CWS Codes
  • 1 Fourier-Mozkin elimination
  • 1 Linear programming
  • 1 Permutation Symmetry
  • 1 Toric Code
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2013
  • 1 2021

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