तकनीकी सारांश: कुशल प्लांटेड $k$-XOR के अनुमान के लिए हाइपरग्राफ साइकिल एन्यूमरेशन (Hypergraph Cycle Enumeration)

1. समस्या विवरण (Problem Statement)

यह शोध पत्र प्लांटेड नॉइज़ी $k$-XOR की समस्या को संबोधित करता है, जिसे स्पार्स लर्निंग पैरिटी विद नॉइज़ (LPN) के रूप में भी जाना जाता है। इसका लक्ष्य $m$ नॉइज़ी पैरिटी मापन से एक छिपे हुए बाइनरी वेक्टर $x \in \{\pm 1\}^n$ का पता लगाना और उसे पुनः प्राप्त करना है। प्रत्येक मापन में एक सपोर्ट सेट $S_a \subseteq [n]$ होता है जिसका आकार $k$ है और एक लेबल $b_a$ होता है, जो इस समीकरण से संबंधित है:
$$b_a = \eta_a \prod_{v \in S_a} x_v$$
जहाँ $\eta_a \in \{\pm 1\}$ एक नॉइज़ वेरिएबल है जिसका प्रत्याशा (expectation) $E[\eta_a] = \rho$ है।

• डिटेक्शन (Detection): नुल केस ($\rho=0$, रैंडम डेटा) और प्लांटेड केस ($\rho > 0$) के बीच अंतर करना।
• रिकवरी (Recovery): छिपे हुए वेक्टर $x$ का पुनर्निर्माण करना।

यह समस्या एक सांख्यिकीय-कम्प्यूटेशनल गैप (statistical-computational gap) द्वारा अभिलक्षित है। जबकि $m = \Theta(n)$ क्लॉज़ के साथ सूचना-सैद्धांतिक रिकवरी संभव है, $k \ge 4$ के लिए $m = e^{\Theta(n^{k/2})}$ के थ्रेशोल्ड से नीचे किसी भी ज्ञात बहुपद-समय (polynomial-time) एल्गोरिदम के सफल होने की संभावना नहीं है। मौजूदा कुशल विधियाँ, जैसे कि किकुची पदानुक्रम (Kikuchi hierarchy) और सम-ऑफ-स्क्वेयर्स (Sum-of-Squares - SoS), एक "स्मूथ ट्रेड-ऑफ" प्रदान करती हैं जहाँ कम्प्यूटेशनल डिग्री $\ell$ को बढ़ाने से कम नमूनों के साथ रिकवरी संभव होती है, लेकिन इसके बदले में $n^{O(\ell)}$ रनटाइम और लिफ्टेड स्पेस के आयाम $\binom{n}{\ell}$ के साथ मेमोरी उपयोग बढ़ जाता है।

2. कार्यप्रणाली: हाइपरग्राफ साइकिल एन्यूमरेशन (HCE)

लेखक हाइपरग्राफ साइकिल एन्यूमरेशन (HCE) पेश करते हैं, जो गाऊसी एलिमिनेशन (Gaussian elimination) से प्रेरित एक स्पेक्ट्रल फ्रेमवर्क है। मुख्य विचार $l$ क्लॉज़ के ऐसे सेटों को एकत्रित करना है ताकि उनके सपोर्ट (सिमेट्रिक डिफरेंस) एक विशिष्ट जोड़ी $\{i, j\}$ को छोड़कर बाकी सभी वेरिएबल्स को निरस्त (cancel out) कर दें।

मुख्य तंत्र (Key Mechanisms)

1. इवन कवर्स और विटनेस (Even Covers and Witnesses):
   • एक इवन $l$-कवर $l$ अलग-अलग हाइपरएजेस का एक सेट है जहाँ प्रत्येक वर्टेक्स एक सम संख्या में दिखाई देता है। उनके लेबल्स का गुणनफल प्लांटेड सिग्नल को निरस्त कर देता है, जिससे केवल नॉइज़ बचता है।
   • एक $(i, j)$-विटनेस $l$ क्लॉज़ का एक सेट है जिनका सिमेट्रिक डिफरेंस ठीक $\{i, j\}$ है। उनके लेबल्स का गुणनफल $x_i x_j$ को एक नॉइज़ टर्म के साथ देता है।
2. रिकवरी मैट्रिक्स $A^{(l)}$:
   • HCE एक $n \times n$ मैट्रिक्स बनाता है जहाँ प्रविष्टि (entry) $A^{(l)}_{ij}$ सभी $l$-लेवल के $(i, j)$-विटनेस के लेबल उत्पादों का योग है।
   • किकुची विधि के विपरीत, जो $\binom{n}{\ell}$ आयाम के लिफ्टेड स्पेस पर कार्य करती है, HCE इन सभी चेन्स को एक $n \times n$ मैट्रिक्स में संकुचित (compress) कर देता है।
   • इस मैट्रिक्स का अपेक्षित मान (expected value) रैंक-वन सिग्नल $xx^\top$ (प्लस नॉइज़) के समानुपाती होता है, जिससे स्पेक्ट्रल एस्टीमेशन (टॉप आइगेनवेक्टर खोजना) के माध्यम से रिकवरी संभव होती है।
3. एल्गोरिदम कार्यान्वयन:
   • लेखक विटनेस को कुशलतापूर्वक सूचीबद्ध करने के लिए एक मीट-इन-द-मिडल (MITM) रणनीति का उपयोग करते हैं।
   • क्लॉज़ को दो हिस्सों ($\lceil l/2 \rceil$ और $\lfloor l/2 \rfloor$) में विभाजित किया जाता है। एल्गोरिदम सबसेट्स को उनके बाउंड्री (XOR sum) द्वारा हैश करता है और वैध विटनेस बनाने वाले मिलान (matches) की खोज करता है।
   • यह मेमोरी की आवश्यकता को $O(n^2 + m^{\lceil l/2 \rceil})$ तक कम करता है और $\binom{n}{\ell}$ के घातीय मेमोरी विस्फोट (exponential memory blowup) से बचाता है।

3. मुख्य योगदान

• HCE का परिचय: प्लांटेड नॉइजी $k$-XOR के लिए एक पदानुक्रमित एल्गोरिथम दृष्टिकोण, जो किटकुची/SoS विधियों के समान सैंपल-टाइम ट्रेड-ऑफ को बनाए रखता है, लेकिन हर स्तर $l$ पर स्पेक्ट्रल समस्या को $n \times n$ मैट्रिक्स तक सीमित कर देता है।
• सैद्धांतिक गारंटी:
  • डिटेक्शन: सिद्ध किया गया कि HCE प्लांटेड सिग्नल का पता लगा सकता है जब क्लॉज़ डेंसिटी $m/n$ किकुची के समान थ्रेशोल्ड कर्व का पालन करती है: $m/n = e^{\Omega(\rho^{-2}(n/l)^{k/2-1})}$। डिटेक्शन परिणाम सटीक है, इसमें कोई लॉगरिदमिक हानि नहीं है।
  • रिकवरी: कमजोर रिकवरी (weak recovery) गारंटी स्थापित की गई है जहाँ $A^{(l)}$ का टॉप आइगेनवेक्टर $x$ के साथ सह-संबंध (correlate) रखता है। रिकवरी थ्रेशोल्ड पॉलीलॉगारिदमिक कारकों तक किकुची कर्व से मेल खाता है।
• जटिलता विश्लेषण (Complexity Analysis):
  • दिखाया गया कि मैच किए गए लेवल्स के लिए, HCE और किकुची के अग्रणी रनटाइम एक्सपोनेंट्स (जैसे $k=4$ के लिए) समान हैं, लेकिन HCE एक बहुत छोटे मैट्रिक्स प्रतिनिधित्व का उपयोग करता है।
  • दिखाया गया कि HCE विटनेस सर्च स्टेप के लिए एक सब-क्वाड्रेटिक क्वांटम स्पीडअप प्राप्त करता है, जिसमें टानी के एल्गोरिदम (Tani's algorithm) का उपयोग करके जटिलता को $O(m^{\lceil l/2 \rceil})$ से घटाकर $\tilde{O}(m^{l/3})$ कर दिया जाता है। लेखक स्पष्ट रूप से उल्लेख करते हैं कि यह क्वार्टिक क्वांटम स्पीडअप को खारिज नहीं करता है, जो कि बड़े आकार और उच्च शोर शक्ति के प्रासंगिक क्षेत्र में किकुची विधि के लिए अभी भी मान्य है।
• अनुभवजन्य प्रदर्शन (Empirical Performance):
  • $k=4, 5, 6$ के लिए प्रयोग दिखाते हैं कि HCE समान स्तरों पर किकुची के रिकवरी ओवरलैप से मेल खाता है।
  • महत्वपूर्ण रूप से, HCE अल्ट्रा-स्पार्स रिजीम (ultra-sparse regime) (कम क्लॉज़ डेंसिटी $C$) में काफी अधिक तेज़ और मेमोरी-कुशल है। उदाहरण के लिए, $n=50, k=4$ पर, HCE ने किकुची के $\approx 5.5$ घंटों की तुलना में $\approx 300$ सेकंड में इंस्टेंस हल किए (एक $\sim 60\times$ की गति वृद्धि)।

4. परिणाम और ट्रेड-ऑफ

शोध पत्र उन विशिष्ट क्षेत्रों की पहचान करता है जहाँ HCE और किकुची उत्कृष्ट प्रदर्शन करते हैं:

• अल्ट्रा-स्पार्स रिजीम ($C \ll 1$): HCE बेहतर है। HCE में $l$-क्लॉज़ उत्पादों को सूचीबद्ध करने की लागत कम है क्योंकि बहुत कम उत्पाद जोड़े (pairs) में सिमटते हैं, जबकि किकुची का लिफ्टेड ऑपरेटर डेंसिटी के बावजूद उच्च-आयामी बना रहता है।
• डेंस रिजीम ($C \gtrsim 1$): किकुची अधिक उपयुक्त हो जाता है। जैसे-जैसे $C$ बढ़ता है, HCE में एन्यूमरेशन लागत बढ़ती जाती है, जो अंततः इसके छोटे मैट्रिक्स आकार के लाभ को कम कर देती है।
• विषम $k$ (Odd $k$): HCE विषम $k$ पर सीधे लागू होता है (विशिष्ट पैरिटी हैंडलिंग के साथ), जबकि सिमेट्रिक किकुची अनबैलेंस्ड लिफ्टिंग की आवश्यकता होती है या पैरिटी बाधाओं के कारण कुछ स्तरों पर शून्य हो जाता है।

लेखक नोट करते हैं कि हालांकि HCE किकुची के रिकवरी प्रदर्शन से मेल खाता है, लेकिन यह किकुची के क्वार्टिक क्वांटम स्पीडअप को खारिज नहीं करता है, क्योंकि वह स्पीडअप लिफ्टेड किकुची स्पेस की संरचना पर निर्भर करता जिसे HCE संकुचित कर देता है।

5. महत्व और दावे

यह शोध पत्र HCE को किकुची पदानुक्रम के एक व्यावहारिक और सैद्धांतिक रूप से पुष्ट विकल्प के रूप में प्रस्तुत करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

1. व्यावहारिक दक्षता: यह उन कठिन (स्पार्स) क्षेत्रों में इंस्टेंस को हल करता है जो मेमोरी और रनटाइम बाधाओं के कारण किकुची के लिए वर्तमान में अगम्य हैं।
2. वैचारिक स्पष्टता: यह स्पेक्ट्रल विधियों के लिए एक पारदर्शी "साइकिल एन्यूमरेशन" व्याख्या प्रदान करता है, जो उन्हें सीधे परिमित क्षेत्रों (finite fields) पर गाऊसी एलिमिनेशन से जोड़ता है।
3. स्मूथ ट्रेड-ऑफ: यह पुष्टि करता है कि सैंपल कॉम्प्लेक्सिटी और कम्प्यूटेशनल लागत के बीच स्मूथ ट्रेड-ऑफ एक अंतर्निहित इवन-कवर संरचना का गुण है, जिसे विशाल लिफ्टेड स्पेस के भारी मेमोरी ओवरहेड के बिना प्राप्त किया जा सकता है।

लेखक विनम्रतापूर्वक दावा करते हैं कि HCE एक नया सांख्यिकीय क्षेत्र पेश नहीं करता है या किकुची पर सार्वभौमिक श्रेष्ठता सिद्ध नहीं करता है; बल्कि, यह विशिष्ट पैरामीटर क्षेत्रों (अल्ट्रा-स्पार्स) में एक व्यावहारिक लाभ प्रदान करता है और इन पदानुक्रमों के स्पेक्ट्रल एंडपॉइंट पर एक नया दृष्टिकोण प्रदान करता है। वे इस प्रश्न को खुला छोड़ देते हैं कि क्या उनके रिकवरी बाउंड्स में पॉलीलॉगारिदमिक स्लैक को नॉर्मलाइजेशन के माध्यम से हटाया जा सकता है, और क्या H1C के एन्यूमरेशन स्टेप के लिए इसी तरह का बड़ा क्वांटम स्पीडअप प्राप्त किया जा सकता है।