High-dimensional Expansion of Product Codes is Stronger than Robust and Agreement Testability

• URL: http://arxiv.org/abs/2308.02889v1
• Date: Sat, 5 Aug 2023 14:13:25 GMT
• Title: High-dimensional Expansion of Product Codes is Stronger than Robust and Agreement Testability
• Authors: Gleb Kalachev
• Abstract summary: We show that robust testability for product of many codes with linear distance is equivalent to agreement testability. We provide an example of product of three codes with linear distance which is robustly testable but not product expanding.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the coboundary expansion property of product codes called product expansion, which played a key role in all recent constructions of good qLDPC codes. It was shown before that this property is equivalent to robust testability and agreement testability for products of two codes with linear distance. First, we show that robust testability for product of many codes with linear distance is equivalent to agreement testability. Second, we provide an example of product of three codes with linear distance which is robustly testable but not product expanding.

Related papers

• Maximally Extendable Product Codes are Good Coboundary Expanders [4.604003661048267]
  We investigate the coboundary expansion property of product codes called product expansion. In this paper, we prove that the collection of random codes over a sufficiently large field has good product expansion.
  arXiv  Detail & Related papers  (2025-01-02T18:56:01Z)
• List Decodable Quantum LDPC Codes [49.2205789216734]
  We give a construction of Quantum Low-Density Parity Check (QLDPC) codes with near-optimal rate-distance tradeoff. We get efficiently list decodable QLDPC codes with unique decoders.
  arXiv  Detail & Related papers  (2024-11-06T23:08:55Z)
• Quantum LDPC Codes of Almost Linear Distance via Homological Products [23.22566380210149]
  We present new constructions of quantum codes of linear or close-to-linear distance and dimension with low-weight stabilizers. Our results help address the natural question: When do homological products preserve good code distance?
  arXiv  Detail & Related papers  (2024-11-06T03:53:10Z)
• Codev-Bench: How Do LLMs Understand Developer-Centric Code Completion? [60.84912551069379]
  We present the Code-Development Benchmark (Codev-Bench), a fine-grained, real-world, repository-level, and developer-centric evaluation framework. Codev-Agent is an agent-based system that automates repository crawling, constructs execution environments, extracts dynamic calling chains from existing unit tests, and generates new test samples to avoid data leakage.
  arXiv  Detail & Related papers  (2024-10-02T09:11:10Z)
• HexaCoder: Secure Code Generation via Oracle-Guided Synthetic Training Data [60.75578581719921]
  Large language models (LLMs) have shown great potential for automatic code generation. Recent studies highlight that many LLM-generated code contains serious security vulnerabilities. We introduce HexaCoder, a novel approach to enhance the ability of LLMs to generate secure codes.
  arXiv  Detail & Related papers  (2024-09-10T12:01:43Z)
• Determining the upper bound of code distance of quantum stabilizer codes through Monte Carlo method based on fully decoupled belief propagation [19.39678519027849]
  In this paper, employing the idea of Monte Carlo method, we propose the algorithm of determining the upper bound of code distance of QSCs. Our algorithm shows high precision - the upper bound of code distance determined by the algorithm of a variety of QSCs whose code distance is known is consistent with actual code distance.
  arXiv  Detail & Related papers  (2024-02-09T15:40:55Z)
• StepCoder: Improve Code Generation with Reinforcement Learning from Compiler Feedback [58.20547418182074]
  We introduce StepCoder, a novel framework for code generation, consisting of two main components. CCCS addresses the exploration challenge by breaking the long sequences code generation task into a Curriculum of Code Completion Subtasks. FGO only optimize the model by masking the unexecuted code segments to provide Fine-Grained Optimization. Our method improves the ability to explore the output space and outperforms state-of-the-art approaches in corresponding benchmarks.
  arXiv  Detail & Related papers  (2024-02-02T13:14:31Z)
• Classical product code constructions for quantum Calderbank-Shor-Steane codes [1.4699455652461726]
  We introduce a new product code construction which is a natural generalisation of classical product codes to quantum codes. We show that built-in redundancies in the parity checks result in so-called meta-checks which can be exploited to correct syndrome read-out errors.
  arXiv  Detail & Related papers  (2022-09-27T15:48:37Z)
• Finding the disjointness of stabilizer codes is NP-complete [77.34726150561087]
  We show that the problem of calculating the $c-disjointness, or even approximating it to within a constant multiplicative factor, is NP-complete. We provide bounds on the disjointness for various code families, including the CSS codes,$d codes and hypergraph codes. Our results indicate that finding fault-tolerant logical gates for generic quantum error-correcting codes is a computationally challenging task.
  arXiv  Detail & Related papers  (2021-08-10T15:00:20Z)
• Disentangle Your Dense Object Detector [82.22771433419727]
  Deep learning-based dense object detectors have achieved great success in the past few years and have been applied to numerous multimedia applications such as video understanding. However, the current training pipeline for dense detectors is compromised to lots of conjunctions that may not hold. We propose Disentangled Dense Object Detector (DDOD), in which simple and effective disentanglement mechanisms are designed and integrated into the current state-of-the-art detectors.
  arXiv  Detail & Related papers  (2021-07-07T00:52:16Z)
• Quantum XYZ Product Codes [0.3222802562733786]
  We study a three-fold variant of the hypergraph product code construction, differing from the standard homological product of three classical codes. When instantiated with 3 classical LDPC codes, this "XYZ product" yields a non CSS quantum LDPC code which might display a large minimum distance.
  arXiv  Detail & Related papers  (2020-11-19T09:50:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.