We consider the problem of private information retrieval from MDS-coded databases with $T$ colluding servers, $U$ robust servers, and $B$ Byzantine servers, referred to as U-B-MDS-TPIR. In the U-B-MDS-TPIR setting, $M$ files are stored across $N$ servers, and in this paper each file is independently encoded using an $(N,K)$ GRS code. We characterize the capacity among linear, full support-rank U-B-MDS-TPIR schemes as $C=\frac{N-U-2B}{N-U}(1+\frac{K+T-1}{N-U-2B}+\cdots+(\frac{K+T-1}{N-U-2B})^{M-1})^{-1}$ when $N-U-2B\ge KT$. When $K=1$ or $T=1$, the same expression gives the capacity without the linearity and full support-rank restrictions. We further extend the construction to the retrieval of $P$ out of $M$ files. For $P \ge \frac{M}{2}$, the resulting multi-file scheme achieves capacity when $K=1$ or $T=1$.
Yanli Wang, Yanlin Wang Sun Yat-Sen University, Bowen Zhang, Yiwei Zhang, Daya Guo, Jiachi Chen, Hongyu Zhang Chongqing University, Zibin Zheng Sun Yat-sen University
Code Large Language Models face critical Time-To-First-Token (TTFT) latency challenges when handling long code completion due to the quadratic complexity (O(n^2)) of attention mechanisms. While existing sparse attention methods attempt to address this issue, they suffer from three key limitations: (1) general sparse patterns cause excessive accuracy degradation without considering code structure, (2) code-specific methods achieve only logical sparsity without actual computational speedup, and (3) limited adaptation to complex scenarios such as repository-level completion. We propose SabreCoder, a training-free Structure-aware block-sparse attention mechanism that bridges the gap between logical and computational sparsity. SabreCoder parses code into semantic chunks, constructs chunk-level sparse patterns through dependency analysis and similarity matching, and maps them to GPU-friendly block-sparse formats. Extensive experiments on LCC and CrossCodeEval benchmarks demonstrate that SabreCoder reduces TTFT by 45-55% while maintaining accuracy within 3% of dense attention.
尚无 AI 解读，展示原文摘要
cs.CL
Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · 2026 · 正式发表