💻 संगणक विज्ञान

UPP $^{\text{cc}}$ is Not Closed Under Intersection

यह शोध पत्र एक स्पष्ट मैट्रिक्स का निर्माण करके यह सिद्ध करता है कि संचार वर्ग $\mathsf{UPP}^{\mathsf{cc}}$ प्रतिच्छेदन (intersection) के अंतर्गत बंद नहीं है, जिसका निम्न साइन रैंक (sign rank) वाला मैट्रिक्स उसका संयोजन (conjunction) घातीय रूप से उच्च साइन रैंक प्रदर्शित करता है, जो कि रोटेशनल सिमिट्री (rotational symmetry) को बहुपद साइन प्रतिनिधित्व (polynomial sign representations) से जोड़ने वाले फोस्टर की विधि के एक नवीन निरंतर एनालॉग (continuous analog) के माध्यम से स्थापित किया गया परिणाम है।

मूल लेखक: Mark Bun, Mandar Juvekar

प्रकाशित 2026-10-28

📖 9 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Mark Bun, Mandar Juvekar

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

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

द दशकों तक, शोधकर्ताओं ने आश्चर्य किया कि क्या यह शक्तिशाली मॉडल समस्याओं के संयोजन पर अच्छी तरह से व्यवहार करता है। विशेष रूप से, यदि एलिस और बॉब बहुत कम बातचीत के साथ एक पहेली को हल कर सकते हैं, और वे एक दूसरी, समान पहेली को बहुत कम बातचीत के साथ हल कर सकते हैं, तो क्या वे एक संयुक्त पहेली को हल कर सकते हैं—जहाँ उन्हें दोनों को एक साथ हल करना होगा—बिना बहुत अधिक बात किए? सहज रूप से, कोई उम्मीद कर सकता है कि उत्तर 'हाँ' होगा। यदि एक कार्य के लिए खेल के नियम पर्याप्त सरल हैं, तो वे दो कार्यों के लिए भी सरल रहने चाहिए। यह प्रश्न क्षेत्र में एक प्रमुख अनसुलझे रहस्य के रूप में बना रहा, जिसमें कई विशेषज्ञों को संदेह था कि उत्तर 'हाँ' होगा, लेकिन कोई इसे सिद्ध नहीं कर सका।

बोस्टन यूनिवर्सिटी के शोधकर्ताओं की एक टीम ने अब इस प्रश्न को एक निश्चित 'नहीं' के साथ सुलझा लिया है। उन्होंने एक विशिष्ट प्रकार की पहेली का निर्माण किया है जहाँ एलिस और बॉब एक एकल उदाहरण को बहुत कम संचार के साथ हल कर सकते हैं, लेकिन जब उन्हें दो उदाहरणों को एक साथ हल करने के लिए मजबूर किया जाता है, तो उन्हें सूचना के आदान-प्रदान की मात्रा विस्फोट की तरह बढ़ जाती है। यह उछाल केवल थोड़ा सा बड़ा नहीं है; यह घातांकीय (exponentially) रूप से बड़ा है। इसे परिप्रेक्ष्य में रखने के लिए, यदि एक पहेली को हल करने के लिए कुछ शब्दों की आवश्यकता होती है, तो दो पहेलियों को एक साथ हल करने के लिए शब्दों की संख्या इतनी विशाल हो सकती है कि उन्हें बोलने में एक जीवन बीत जाएगा। यह खोज सिद्ध करती है कि इस सख्त मॉडल में न्यूनतम संचार के साथ हल की जाने वाली समस्याओं का वर्ग 'इंटरसेक्शन' (intersection) के तहत बंद नहीं है, जिसका अर्थ है कि दो आसान समस्याओं को मिलाने से अचानक एक अविश्वसनीय रूप से कठिन समस्या बन सकती है।

शोधकर्ता इस निष्कर्ष पर एक ज्यामितीय संस्करण की ओर देखकर पहुँचे। अमूर्त बिट्स के बजाय, उन्होंने कल्पना की कि एलिस और बॉब एक गोले (sphere) पर बिंदु रखे हुए हैं, जो एक गेंद की त्वचा जैसी सतह है। खेल का नियम सरल है: उन्हें यह निर्धारित करना है कि उनके दो बिंदुओं के बीच का कोण तीक्ष्ण (sharp) है या अधिक कोण (obtile/obtuse)। यह एक क्लासिक समस्या है जिसे कम संचार के साथ आसानी से हल किया जा सकता है। शोधकर्ताओं ने फिर पूछा कि क्या होता है यदि एलिस और बॉब को दो जोड़े बिंदु दिए जाते हैं और उन्हें यह निर्धारित करना होता है कि क्या दोनों जोड़े तीक्ष्ण कोण बनाते हैं। उन्होंने पाया कि जबकि एकल जोड़ा आसान है, दोहरा जोड़ा एक ऐसी ज्यामितीय जटिलता पैदा करता है जो संचार लागत को आसमान छूने के लिए मजबूर करती है।

इसे सिद्ध करने के लिए, टीम ने एक ऐसी तकनीक का उपयोग किया जो संचार समस्या को गणितीय फलनों (functions) के आकार के प्रश्न में अनुवादित करती है। उन्होंने गोले को बिंदुओं के संग्रह के रूप में नहीं, बल्कि एक निरंतर सतह के रूप में कल्पित किया जहाँ खेल के नियमों को सुचारू (smooth) बनाया गया है। गोले पर इन नियमों के व्यवहार का अध्ययन करके, उन्होंने एक छिपी हुई बाधा की खोज की। संयुक्त पहेली के नियमों के लिए एक ऐसे फलन की आवश्यकता होती है जो एक बहुत ही विशिष्ट, ऊबड़-खाबड़ तरीके से चिह्न बदलता है, ठीक वैसे ही जैसे किसी कोने पर छाया गिरती है। हालाँकि, गोले की चिकनी, निरंतर प्रकृति ऐसी अत्यधिक बड़ी आकृति के बिना इस ऊबड़-खाबड़ व्यवहार की नकल करने के लिए एक सरल, कम-आयामी आकृति बनाने को असंभव बनाती है।

शोधकर्ताओं ने दिखाया कि संयुक्त पहेली के समाधान को एक सरल ज्यामितीय व्यवस्था का उपयोग करके प्रदर्शित करने का कोई भी प्रयास विफल हो जाएगा, जब तक कि वह व्यवस्था घातांकीय रूप से बड़ी न हो। उन्होंने प्रदर्शित किया कि "मार्जिन" (margin) की त्रुटि—समाधान और निर्णय की सीमा के बीच की दूरी—लुप्तप्राय रूप से छोटी हो जाती है। क्षेत्र की भाषा में, इसका अर्थ है कि समस्या का 'साइन रैंक' (sign rank), जो पहेली का प्रतिनिधित्व करने वाले मैट्रिक्स की जटिलता को मापता है, घातांकीय रूप से बढ़ता है। यह वृद्धि इतनी गंभीर है कि इसे किसी भी कुशल संचार प्रोटोकॉल द्वारा पाटा नहीं जा सकता है।

यह परिणाम केवल एक सैद्धांतिक जिज्ञासा नहीं है; इसके सीखने की सीमाओं और सर्किट डिजाइन के बारे में हमारी समझ पर तत्काल प्रभाव हैं। शोधकर्ताओं ने दिखाया कि उनके निष्कर्षों का तात्पर्य यह है कि कुछ प्रकार के कंप्यूटर सर्किट, जो सरल निर्णय द्वारों (decision gates) की परतों से बने होते हैं, उन्हें दो कार्यों को एक साथ करने के लिए कहा जाने पर घातांकीय रूप से बड़ा होना चाहिए। इसी तरह, मशीन लर्निंग के क्षेत्र में, उनका काम बताता है कि दो सरल ज्यामितिक आकृतियों के प्रतिच्छेदन (intersection) को सीखना मौलिक रूप से कठिन है, और इस कठिनाई को केवल डेटा को बेहतर तरीके से प्रस्तुत करके दूर नहीं किया जा सकता है।

लेख एक संबंधित प्रश्न को भी संबोधित करता है कि क्या संयुक्त समस्या की कठिनाई मूल समस्या की कठिनाई द्वारा सीमित है। लेखक सिद्ध करते हैं कि ऐसा कोई बंधन मौजूद नहीं है। भले ही मूल समस्या सरल हो, संयुक्त समस्या मनमाने ढंग से कठिन हो सकती है। यह उस संभावना को खारिज करता है कि कोई सार्वभौमिक नियम है जो यह सीमित करता है कि एक संयुक्त समस्या मूल समस्या से कितनी अधिक कठिन हो सकती है। शोधकर्ताओं ने पूर्णांक ग्रिड (integer grids) पर परिभाषित फलनों के एक परिवार का उपयोग करके अपना प्रति-उदाहरण (counterexample) निर्मित किया, जिससे पता चलता है कि यह घटना सबसे बुनियादी, असतत (discrete) सेटिंग्स में भी घटित होती है।

इस कार्य के सबसे उल्लेखनीय पहलुओं में से एक निरंतर गोले और असतत ग्रिड के बीच के अंतर को पाटने की विधि है। शोधकर्ताओं ने पहले चिकने गोले पर समस्या को हल किया, जहाँ सममिति (symmetry) के गणित ने उन्हें अंतर्निहित संरचना को स्पष्ट रूप से देखने की अनुमति दी। फिर उन्होंने इस निरंतर समाधान को पूर्णांकों की असतत दुनिया में वापस "राउंड" (round) करने का एक तरीका विकसित किया। यह राउंडिंग प्रक्रिया नाजुक है क्योंकि असतत दुनिया में निर्णय की सीमाएं तीक्ष्ण होती हैं, और राउंडिंग में एक छोटी सी त्रुटि उत्तर को बदल सकती है। टीम ने सिद्ध किया कि उनके निरंतर सीमाएँ इस राउंडिंग प्रक्रिया में जीवित रहने के लिए पर्याप्त मजबूत थीं, जिससे यह सुनिश्चित हुआ कि घातांकीय अंतर असतत समस्याओं के लिए भी सत्य बना रहे।

निष्कर्ष भी सटीक और अनुमानित समाधानों के बीच के अंतर पर प्रकाश डालते हैं। शोधकर्ताओं ने दिखाया कि यदि हम समाधान में त्रुटि की थोड़ी मात्रा की अनुमति देते हैं, तो समस्या को हल करना बहुत आसान हो जाता है। हालाँकि, यदि हम एक सटीक समाधान की मांग करते हैं, तो कठिनाई पूरी शक्ति के साथ वापस आती है। यह अंतर उन एल्गोरिदम की सीमाओं को समझने के लिए महत्वपूर्ण है जिन्हें गलतियाँ करने की अनुमति है बनाम वे जिन्हें पूर्ण होना चाहिए। शोध पत्र उदाहरणों का एक स्पष्ट क्रम प्रदान करता है जहाँ अनुमानित और सटीक कठिनाई के बीच का अंतर घातांकीय है, जो पहले ज्ञात अंतर से बहुत अधिक है।

कंप्यूटर विज्ञान के व्यापक संदर्भ में, यह कार्य इस अंतर्ज्ञान को चुनौती देता है कि जटिलता योगात्मक (additive) होती है। यह दिखाता है कि जब समस्याओं को जोड़ा जाता है, तो जटिलता गुणात्मक (multiplicative), या यहाँ तक कि घातांकीय (exponential) भी हो सकती है। इसके एल्गोरिदम के डिजाइन और गणना की मौलिक सीमाओं को समझने के तरीकों पर प्रभाव हैं। शोधकर्ताओं का प्रमाण कठोर और पूर्ण है, जो इस अंतर के अस्तित्व पर संदेह की कोई गुंजाइश नहीं छोड़ता है। उन्होंने फलनों का एक ठोस परिवार प्रदान किया है जो इस घटना को प्रदर्शित करता है, जिससे यह प्रश्न एक सैद्धांतिक संभावना से एक गणितीय तथ्य में बदल गया है।

लेख इस बात पर ध्यान दिलाते हुए समाप्त होता है कि जबकि उनका निर्माण एक महत्वपूर्ण अलगाव (separation) प्राप्त करता है, यह अधिकतम संभव अलगाव नहीं है। अभी भी यह पता लगाने की गुंजाइश है कि क्या इस अंतर को और भी बड़ा बनाया जा सकता है, जो संभावित रूप से एकल और संयुक्त मामलों के बीच के अधिकतम संभव अंतर तक पहुँच सकता है। यह भविष्य के अनुसंधान के लिए द्वार खोलता है ताकि सीमाओं को और आगे बढ़ाया जा सके। यह कार्य अमूर्त कम्प्यूटेशनल समस्याओं को हल करने में ज्यामितीय अंतर्दृष्टि की शक्ति के प्रमाण के रूप में खड़ा है, जो दिखाता है कि कभी-कभी संचार की सीमाओं को समझने का सबसे अच्छा तरीका उस स्थान के आकार को देखना है जिसमें संचार होता है।

तकनीकी सारांश: UPPcc इंटरसेक्शन (Intersection) के अंतर्गत बंद नहीं है

समस्या विवरण
यह शोध पत्र संचार जटिलता (communication complexity) के एक मौलिक खुले प्रश्न को संबोधित करता है: क्या UPPcc (अनबाउंडेड-एरर प्रोबेबिलिस्टिक कम्युनिकेशन कॉम्प्लेक्सिटी) क्लास इंटरसेक्शन के अंतर्गत बंद है। एक फलन (function) $F$ का संबंध UPPcc से तब होता है जब उसे पोलिलॉग (polylogarithmic) संचार का उपयोग करके $1/2$ से अधिक की प्रायिकता के साथ कंप्यूट किया जा सकता है। जबकि इसके समान वर्ग PP को इंटरसेक्शन के अंतर्गत बंद होने के लिए जाना जाता है, UPPcc की स्थिति अनसुलझी रही है। विशेष रूप से, लेखक यह जांचते हैं कि क्या ऐसा कोई फलन $F$ मौजूद है जहाँ $U(F)$ छोटा (पोलिलॉग) हो, लेकिन $U(F \land F)$ काफी बड़ा हो।

इस समस्या का विश्लेषण साइन रैंक (sign rank) के माध्यम से किया गया है। पातुरी और साइमन ने स्थापित किया कि अनबाउंडेड-एरर कम्युनिकेशन कॉम्प्लेक्सिटी $U(F)$ को उसके संचार मैट्रिक्स $A$ के साइन रैंक, जिसे $\text{rank}_{\pm}(A)$ द्वारा दर्शाया जाता है, द्वारा एक एडिटिव कांस्टेंट (additive constant) तक अभिलक्षित किया जा सकता है: $U(F) = \log(\text{rank}_{\pm}(A)) \pm O(1)$ । साइन रैंक उस वास्तविक मैट्रिक्स की न्यूनतम रैंक है जो $A$ के प्रत्येक प्रविष्टि (entry) के चिह्न (sign) के साथ मेल खाती है। लेखक एक स्पष्ट मैट्रिक्स परिवार बनाने का लक्ष्य रखते हैं जहाँ $A \land A$ का साइन रैंक $A$ के साइन रैंक की तुलना में तेजी से (exponentially) बढ़ जाता है।

कार्यप्रणाली
लेखक फोस्टर के मेथड (Forster's method) पर केंद्रित एक ज्यामितीय दृष्टिकोण का उपयोग करते हैं, जो साइन रैंक लोअर बाउंड्स को लीनियर अरेंजमेंट्स के औसत मार्जिन (average margin) के ऊपरी बाउंड्स से जोड़ता है। मुख्य तकनीकी रणनीति एक निरंतर-से-विविक्त (continuous-to-discrete) स्थानांतरण है:

निरंतर स्वरूप (Continuous Formulation): लेखक एक निरंतर एनालॉग समस्या को परिभाषित करते हैं, जिसे $\text{CHS}_d \land \text{CHS}_d$ कहा जाता है, जहाँ इनपुट डिस्क्रीट वेक्टर्स के बजाय यूनिट स्फीयर $S^{d-1}$ पर बिंदु होते हैं। इस समस्या के लिए एक लीनियर अरेंजमेंट को फलन $f, g: (S^{d-1})^2 \to \mathbb{R}^r$ द्वारा दर्शाया जाता है।
रोटेशनल सिमेट्राइजेशन (Rotational Symmetrization): वे एक "सिमेट्राइज्ड" फलन $H(s_1, s_2)$ पेश करते हैं, जो इनपुट के निश्चित इनर प्रोडक्ट्स $s_1, s_2$ के दिए जाने पर अरेंजमेंट वेक्टर्स के अपेक्षित इनर प्रोडक्ट को दर्शाता है। फलन $H$ केवल इनपुट्स के इनर प्रोडक्ट्स पर निर्भर करता है, जिससे रोटेशनल सिमेट्री (rotational symmetry) का लाभ उठाया जा सकता है।
एप्रोक्सिमेशन थ्योरी और डेरिवेटिव्स:
- गेनबाकर पॉलिनोमिअल्स (Gegenbauer polynomials) और स्फेरिक हार्मोनिक विश्लेषण का उपयोग करते हुए, वे सिद्ध करते हैं कि $H$ स्मूथ (smooth) है और इसमें $O(d)$ क्रम तक सीमित डेरिवेटिव्स हैं। फलस्वरूप, $H$ को इसके लो-डिग्री टेलर पॉलिनोमिअल्स द्वारा अच्छी तरह से एप्रोक्सिमेट किया जा सकता है।
- वे $H$ की स्मूथनेस और उस आवश्यकता के बीच विरोधाभास का लाभ उठाते हैं जिसके तहत इसे साइन टेस्ट के कंजंक्शन (conjunction) (अर्थात "लोअर-लेफ्ट क्वाड्रेंट" इंडिकेटर $Q_2(s_1, s_2) = \text{sgn}(s_1) \land \text{sgn}(s_2)$ ) का प्रतिनिधित्व करना चाहिए। पॉलिनोमिअल्स मूल बिंदु (origin) के पास $Q_2$ का प्रभावी ढंग से साइन प्रतिनिधित्व नहीं कर सकते।
- यह संभालने के लिए कि अरेंजमेंट निर्णय सीमा (decision boundary) के पास विफल हो सकता है (जहाँ इनर प्रोडक्ट्स शून्य के करीब होते हैं), वे एप्रोक्सिमेशन थ्योरी के परिणामों (विशेष रूप से न्यूमैन और शेरस्टोव के कार्य का विस्तार) का उपयोग करते हैं ताकि यह दिखाया जा सके कि प्रतिबंधित डोमेन पर $Q_2$ के लगभग साइन प्रतिनिधित्व वाले गुणांक (coefficients) यदि डिग्री कम है, तो समान रूप से छोटे होंगे।
औसत मार्जिन बाउंड (Average Margin Bound): $H$ की स्मूथनेस और $Q_2$ का लगभग साइन प्रतिनिधित्व करने वाले पॉलिनोमिअल्स के गुणांक बाउंड्स को जोड़कर, वे सिद्ध करते हैं कि निरंतर समस्या के किसी भी अरेंजमेंट का औसत मार्जिन तेजी से घटता है ( $2^{-\Omega(d)}$ )।
विविक्त स्थानांतरण (Discrete Transfer): वे डिस्क्रीट इंटीजर वेक्टर्स को स्फीयर पर बिंदुओं में मैप करने के लिए एक राउंडिंग प्रक्रिया का निर्माण करते हैं। वे दिखाते हैं कि यदि निरंतर समस्या का औसत मार्जिन तब भी छोटा है जब साइन बाधाओं (constraints) को सीमा के पास शिथिल किया जाता है, तो डिस्क्रीट समस्या (बाउंडेड इंटीजर हाफस्पेस) इस छोटे औसत मार्जिन को विरासत में प्राप्त करती है। फोस्टर के प्रमेय द्वारा, एक छोटा औसत मार्जिन एक बड़े साइन रैंक को इंगित करता है।

मुख्य योगदान और परिणाम
यह शोध पत्र निम्नलिखित मुख्य परिणाम स्थापित करता है:

मुख्य प्रमेय: एक स्पष्ट फलन परिवार $F$ $F$ (विशेष रूप से, बाउंडेड इंटीजर हाफस्पेस $H_{M,d}$ $H_{M, d}$ ) मौजूद है जिससे $U(F) = O(\log n)$ $U (F) = O (lo g n)$ है लेकिन $U(F \land F) = \Omega(\sqrt{n})$ $U (F \land F) = Ω (n)$ है।
- फलन $H_{M,d}$ को इनपुट्स $a, b \in \{-M, \dots, M\}^d$ पर $\text{sgn}(\langle a, b \rangle - 1/2)$ के रूप में परिभाषित किया गया है।
- $M = 2^{\Theta(d)}$ के लिए, इनपुट साइज $n = \Theta(d^2)$ है। $H_{M,d}$ का साइन रैंक $O(d)$ है, जबकि $H_{M,d} \land H_{M,d}$ का साइन रैंक $2^{\Omega(d)} = 2^{\Omega(\sqrt{n})}$ है।
रैंडम वेक्टर्स: यह सेपरेशनेशन (separation) उन मैट्रिसेस के लिए भी मान्य है जो स्फीयर पर रैंडम यूनिट वेक्टर्स से बने हैं, जहाँ इंटरसेक्शन का साइन रैंक उच्च प्रायिकता के साथ मूल मैट्रिक्स की तुलना में तेजी से बढ़ जाता है।
टाइटनेस (Tightness): लेखक इस फलन परिवार के लिए अपने लोअर बाउंड विश्लेषण की इष्टतमता (optimality) प्रदर्शित करते हैं। वे दिखाते हैं कि $H_{M,d} \land H_{M,d}$ का साइन रैंक $2^{O(d + \log M)}$ है, जो $M = 2^{\Theta(d)}$ के लिए लोअर बाउंड से मेल खाता है।

महत्व
यह शोध पत्र इस प्रश्न का एक निश्चित नकारात्मक उत्तर प्रदान करता है कि क्या UPPcc इंटरसेक्शन के अंतर्गत बंद है। यह संचार जटिलता के एक लंबे समय से चले आ रहे खुले प्रश्न को हल करता है।

इस परिणाम का महत्व कई अन्य क्षेत्रों में भी विस्तृत है:

सर्किट कॉम्प्लेक्सिटी: यह दर्शाता है कि थ्रेशोल्ड-ऑफ-मेजॉरिटी (Threshold-of-Majority) सर्किट्स का आकार इंटरसेक्शन के तहत तेजी से बढ़ सकता है। जबकि एक फलन $F$ एक पॉलीनोमियल-साइज़ थ्रेशोल्ड-ऑफ-मेजॉरिटी सर्किट द्वारा कंप्यूट किया जा सकता है, $F \land F$ को $2^{\Omega(\sqrt{n})}$ आकार की आवश्यकता हो सकती है।
लर्निंग थ्योरी: यह स्थापित करता है कि दो हाफस्पेस के इंटरसेक्शन की क्लास की डायमेंशन कॉम्प्लेक्सिटी (dimension complexity) घातीय (exponential) है ( $2^{\Omega(d)}$ )। यह डायमेंशन कॉम्प्लेक्सिटी पर निर्भर करने वाले फ्रेमवर्क्स में हाफस्पेस के इंटरसेक्शन को सीखने के लिए निम्न-आयामी सटीक रिडक्शन (low-dimensional exact reductions) को खारिज करता है।
साइन रैंक बनाम एप्रोक्सिमेट साइन रैंक: परिणाम मैट्रिसेस का एक स्पष्ट परिवार प्रदान करते हैं जो साइन रैंक और एप्रोक्सिमेट साइन रैंक के बीच घातीय अंतर (exponential separation) प्रदर्शित करते हैं। जबकि पिछले कार्यों ने क्वैसी-पॉलीनोमियल (quasipolynomial) सेपरेशन दिखाया था, यह कार्य प्रदर्शित करता है कि यह अंतर घातीय हो सकता है।

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

इसी तरह के और पेपर