2024/05/14 by Shohei Satake, Satake, Shohei
Computer Science · #05D10 #11T24 #68R05 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Theory and Algorithms #Information Theory (cs.IT) #Number Theory (math.NT)
paper · pdf · doi:10.48550/arxiv.2405.08608
openalex publication_date 2024/05/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Constructing explicit RIP matrices is an open problem in compressed sensing theory. In particular, it is quite challenging to construct explicit RIP matrices that break the square-root bottleneck. On the other hand, providing explicit 2-source extractors is a fundamental problem in theoretical computer science, cryptography and combinatorics. Nowadays, there are only a few known constructions for explicit 2-source extractors (with negligible errors) that break the half barrier for min-entropy. In this paper, we establish a new connection between RIP matrices breaking the square-root bottleneck and 2-source extractors breaking the half barrier for min-entropy. Here we focus on an RIP matrix (called the Paley ETF) and a 2-source extractor (called the Paley graph extractor), where both are defined from quadratic residues over the finite field of odd prime order p≡ 1 \pmod4. As a main result, we prove that if the Paley ETF breaks the square-root bottleneck, then the Paley graph extractor breaks the half barrier for min-entropy as well. Since it is widely believed that the Paley ETF breaks the square-root bottleneck, our result accordingly provides a new affirmative intuition on the conjecture for the Paley graph extractor by Benny Chor and Oded Goldreich.