List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier

• URL: http://arxiv.org/abs/2101.11653v1
• Date: Wed, 27 Jan 2021 19:17:33 GMT
• Title: List-Decodable Coded Computing: Breaking the Adversarial Toleration Barrier
• Authors: Mahdi Soleymani, Ramy E. Ali, Hessam Mahdavifar, A. Salman Avestimehr
• Abstract summary: We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. We show how the master node can perform certain carefully designed extra computations in order to obtain the side information. We further propose folded Lagrange coded computing, referred to as folded LCC or FLCC, to incorporate the developed techniques into a specific coded computing setting.
• Score: 24.75623641870649
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of coded computing where a computational task is performed in a distributed fashion in the presence of adversarial workers. We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. More specifically, we leverage list-decoding techniques for folded Reed-Solomon (FRS) codes and propose novel algorithms to recover the correct codeword using side information. In the coded computing setting, we show how the master node can perform certain carefully designed extra computations in order to obtain the side information. This side information will be then utilized to prune the output of list decoder in order to uniquely recover the true outcome. We further propose folded Lagrange coded computing, referred to as folded LCC or FLCC, to incorporate the developed techniques into a specific coded computing setting. Our results show that FLCC outperforms LCC by breaking the barrier on the number of adversaries that can be tolerated. In particular, the corresponding threshold in FLCC is improved by a factor of two compared to that of LCC.

Related papers

• Fast correlated decoding of transversal logical algorithms [67.01652927671279]
  Quantum error correction (QEC) is required for large-scale computation, but incurs a significant resource overhead.<n>Recent advances have shown that by jointly decoding logical qubits in algorithms composed of logical gates, the number of syndrome extraction rounds can be reduced.<n>Here, we reform the problem of decoding circuits by directly decoding relevant logical operator products as they propagate through the circuit.
  arXiv  Detail & Related papers  (2025-05-19T18:00:00Z)
• An Empirical Study on the Effectiveness of Large Language Models for Binary Code Understanding [50.17907898478795]
  This work proposes a benchmark to evaluate the effectiveness of Large Language Models (LLMs) in real-world reverse engineering scenarios. Our evaluations reveal that existing LLMs can understand binary code to a certain extent, thereby improving the efficiency of binary code analysis.
  arXiv  Detail & Related papers  (2025-04-30T17:02:06Z)
• TFHE-Coder: Evaluating LLM-agentic Fully Homomorphic Encryption Code Generation [10.597643264309415]
  Homomorphic Encryption over the torus (TFHE) enables encrypted computation on data without decryption. Despite its potential in privacy preserving machine learning, secure multi party computation, private blockchain transactions, and secure medical diagnostics, its adoption remains limited due to cryptographic complexity and usability challenges. This work establishes the first benchmark for TFHE code generation, demonstrating how LLMs, when augmented with domain-specific feedback, can bridge the expertise gap in FHE code generation.
  arXiv  Detail & Related papers  (2025-03-15T17:57:44Z)
• Decoding Quantum LDPC Codes using Collaborative Check Node Removal [0.0]
  We present a strategy to improve the performance of the iterative decoders based on a collaborative way.<n>We show that an integration of information measurements (IM) for qubits and it's adjacent stabilizer checks, can be exploited to extract far better performing results.
  arXiv  Detail & Related papers  (2025-01-14T11:41:45Z)
• Sifting through the Chaff: On Utilizing Execution Feedback for Ranking the Generated Code Candidates [46.74037090843497]
  Large Language Models (LLMs) are transforming the way developers approach programming by automatically generating code based on natural language descriptions. This paper puts forward RankEF, an innovative approach for code ranking that leverages execution feedback. Experiments on three code generation benchmarks demonstrate that RankEF significantly outperforms the state-of-the-art CodeRanker.
  arXiv  Detail & Related papers  (2024-08-26T01:48:57Z)
• Collective Bit Flipping-Based Decoding of Quantum LDPC Codes [0.6554326244334866]
  We improve both the error correction performance and decoding latency of variable degree-3 (dv-3) QLDPC codes under iterative decoding. Our decoding scheme is based on applying a modified version of bit flipping (BF) decoding, namely two-bit bit flipping (TBF) decoding.
  arXiv  Detail & Related papers  (2024-06-24T18:51:48Z)
• Factor Graph Optimization of Error-Correcting Codes for Belief Propagation Decoding [62.25533750469467]
  Low-Density Parity-Check (LDPC) codes possess several advantages over other families of codes. The proposed approach is shown to outperform the decoding performance of existing popular codes by orders of magnitude.
  arXiv  Detail & Related papers  (2024-06-09T12:08:56Z)
• Learning Linear Block Error Correction Codes [62.25533750469467]
  We propose for the first time a unified encoder-decoder training of binary linear block codes. We also propose a novel Transformer model in which the self-attention masking is performed in a differentiable fashion for the efficient backpropagation of the code gradient.
  arXiv  Detail & Related papers  (2024-05-07T06:47:12Z)
• Estimating the Decoding Failure Rate of Binary Regular Codes Using Iterative Decoding [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder. We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Deep Quantum Error Correction [73.54643419792453]
  Quantum error correction codes (QECC) are a key component for realizing the potential of quantum computing. In this work, we efficiently train novel emphend-to-end deep quantum error decoders. The proposed method demonstrates the power of neural decoders for QECC by achieving state-of-the-art accuracy.
  arXiv  Detail & Related papers  (2023-01-27T08:16:26Z)
• Machine Learning-Aided Efficient Decoding of Reed-Muller Subcodes [59.55193427277134]
  Reed-Muller (RM) codes achieve the capacity of general binary-input memoryless symmetric channels. RM codes only admit limited sets of rates. Efficient decoders are available for RM codes at finite lengths.
  arXiv  Detail & Related papers  (2023-01-16T04:11:14Z)
• Neural Belief Propagation Decoding of Quantum LDPC Codes Using Overcomplete Check Matrices [60.02503434201552]
  We propose to decode QLDPC codes based on a check matrix with redundant rows, generated from linear combinations of the rows in the original check matrix. This approach yields a significant improvement in decoding performance with the additional advantage of very low decoding latency.
  arXiv  Detail & Related papers  (2022-12-20T13:41:27Z)
• Generalized Lagrange Coded Computing: A Flexible Computation-Communication Tradeoff for Resilient, Secure, and Private Computation [11.951700263976777]
  Generalized Lagrange Coded Computing (GLCC) codes are proposed to provide resiliency against stragglers who do not return results in time. LCC codes include the state-of-the-art Lagrange Coded Computing (LCC) codes as a special case.
  arXiv  Detail & Related papers  (2022-04-24T02:48:07Z)
• Analog Lagrange Coded Computing [23.67685616088422]
  A distributed computing scenario is considered, where the computational power of a set of worker nodes is used to perform a certain computation task over a dataset that is dispersed among the workers. LCC, proposed by Yu et al., leverages the well-known Lagrange operations on coded computing. We propose a novel extension of LCC to the analog domain, referred to as analog (ALCC)
  arXiv  Detail & Related papers  (2020-08-19T17:47:37Z)
• perm2vec: Graph Permutation Selection for Decoding of Error Correction Codes using Self-Attention [19.879263834757758]
  We present a data-driven framework for permutation selection, combining domain knowledge with machine learning concepts. This work is the first to leverage the benefits of the neural Transformer networks in physical layer communication systems.
  arXiv  Detail & Related papers  (2020-02-06T15:42: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.