📊 statistics

Dimension Reduction via Sum-of-Squares and Improved Clustering Algorithms for Non-Spherical Mixtures

यह शोध पत्र एक नवीन सम-वर्ग (sum-of-squares) आधारित आयामी न्यूनीकरण तकनीक प्रस्तुत करता है जो गैर-गोलाकार गॉसियन मिश्रणों के कुशल क्लस्टरिंग को सक्षम बनाता है, जो पिछले अत्याधुनिक तरीकों की तुलना में काफी बेहतर नमूना और समय जटिलता के साथ, ऐसे वितरणों के एक व्यापक वर्ग के लिए ज्ञात सांख्यिकीय क्वेरी और सम-वर्ग निचली सीमाओं को प्रभावी ढंग से दरकिनार करता है।

मूल लेखक: Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer

प्रकाशित 2026-06-02

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

CC BY 4.0

मूल लेखक: Prashanti Anderson, Mitali Bafna, Rares-Darius Buhai, Pravesh K. Kothari, David Steurer

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

कल्पना कीजिए कि आप एक जासूस हैं जो मेल के एक विशाल, अराजक और मिले-जुले ढेर को छाँटने की कोशिश कर रहे हैं। कुछ पत्र "कंपनी A" के हैं, कुछ "कंपनी B" के, और कुछ "कंपनी C" के हैं। हालाँकि, यहाँ दो बड़ी समस्याएँ हैं:

आकृतियाँ अजीब हैं: कंपनी A के पत्र केवल बेतरतीब ढंग से बिखरे हुए नहीं हैं; वे लंबे, पतले सिगार की तरह खींचे हुए हैं। कंपनी B के पत्र पैनकेक की तरह चपटे हैं। कंपनी C के पत्र ऊबड़-खाबड़ चट्टानों की तरह हैं। सांख्यिकी (statistics) की दुनिया में, इन्हें "नॉन-स्फेरिकल गॉसियन मिक्सचर" (non-spherical Gaussian mixtures) कहा जाता है।
शोर (Noise): किसी ने इसमें बहुत सारा बेकार मेल (आउटलेयर्स) मिला दिया है और सब कुछ इतना मिला दिया है कि आप आसानी से पहचान नहीं पा रहे कि कौन सा ढेर किसका है।

दशकों तक, इन अजीब आकृतियों वाले ढेरों को छाँटने के लिए जो सबसे अच्छे उपकरण उपलब्ध थे, वे धीमे और अनाड़ी थे। यदि डेटा उच्च-आयामी स्थान (high-dimensional space) में होता (सोचिए एक ऐसा कमरा जिसमें 3 आयामों के बजाय हजारों आयाम हों), तो इन कंपनियों की संख्या बढ़ने के साथ इन्हें छाँटने में लगने वाला समय तेजी से (exponentially) बढ़ जाता था। यह एक सुई को घास के ढेर में खोजने जैसा था, लेकिन हर नई कंपनी के साथ वह घास का ढेर बड़ा होता जा रहा था।

यह शोध पत्र एक नया, चतुर शॉर्टकट पेश करता है जो खेल बदल देता है।

पुराना तरीका: "पैरेलल पैनकेक्स" (समानांतर पैनकेक्स) की समस्या

पहले, इन अजीब आकार के ढेरों को छाँटने के लिए, एल्गोरिदम को हर संभव कोण से डेटा को देखना पड़ता था, जिसमें बहुत अधिक कंप्यूटिंग शक्ति और डेटा की आवश्यकता होती थी। इस कठिनाई को अक्सर "पैरेलल पैनकेक्स" उपमा से समझाया गया है: कल्पना कीजिए कि कई पतले पैनकेक्स (1D मिश्रण) को एक के ऊपर एक रखा गया है। यदि उन्हें बिल्कुल सही तरीके से रखा जाए, तो वे बाहर से बिल्कुल एक मानक, गोल गेंद (एक मानक गॉसियन) की तरह दिखते हैं, जिससे बिना गहराई में विवरण देखे उनके बीच अंतर करना असंभव हो जाता है।

पुराने तरीकों ने माना था कि यदि आकृतियाँ पर्याप्त अजीब हैं, तो आपको उन्हें छाँटने के लिए बहुत अधिक समय और डेटा खर्च करना ही होगा।

नया तरीका: "सम-ऑफ-स्क्वायर्स" (Sum-of-Squares) लेंस

लेखकों ने "सम-ऑफ-स्क्वायर्स" (SoS) तकनीक पर आधारित एक नई विधि विकसित की है। इसे एक विशेष चश्मे या लेंस के रूप में सोचें।

पूरे अस्त-व्यस्त कमरे को एक साथ देखने के बजाय, यह लेंस एल्गोरिदम को निम्नलिखित कार्य करने की अनुमति देता है:

"सेपरेशन" दिशाओं को खोजना: यह उन विशिष्ट कोणों (दिशाओं) को खोजता है जहाँ विभिन्न कंपनियों के मेल के ढेर एक-दूसरे से बहुत अलग दिखते हैं। उदाहरण के लिए, यह एक ऐसी दिशा खोज सकता है जहाँ कंपनी A का "सिगार" बहुत लंबा दिखता है, जबकि कंपनी B का "पैनकेक" बहुत चपटा दिखता है।
डेटा को प्रोजेक्ट करना: एक बार जब यह इन विशेष कोणों को खोज लेता है, तो यह उच्च-आयामी डेटा को एक बहुत छोटे, सरल स्थान में प्रोजेक्ट (दबा) देता है (जैसे 3D वस्तु को 2D कागज पर समतल करना)।
सुरागों को सुरक्षित रखना: महत्वपूर्ण बात यह है कि यह दबाने की प्रक्रिया महत्वपूर्ण अंतरों को खोती नहीं है। "सिगार" और "पैनकेक" छोटे स्थान में भी अलग-अलग बने रहते हैं।

दो बड़ी जीत

शोध पत्र दिखाता है कि यह नया लेंस दो विशिष्ट, सामान्य परिदृश्यों के लिए काम करता है:

1. "जीरो-मीन" केस (केंद्रित ढेर)
कल्पना कीजिए कि सभी मेल के ढेर एक ही स्थान (जीरो मीन) के आसपास केंद्रित हैं, लेकिन वे अलग-अलग दिशाओं में खींचे हुए हैं।

पुराना तरीका: इसमें $d^k$ (जहाँ $d$ आयामों की संख्या है और $k$ कंपनियों की संख्या है) के अनुपात में समय लगता था। यदि आपके पास 100 आयाम और 10 कंपनियां होतीं, तो यह असंभव होता।
नया तरीका: इसमें $d^{\text{constant}}$ के अनुपात में समय लगता है। समय आयामों पर निर्भर करता है, लेकिन कंपनियों की संख्या पर घातांकीय (exponential) रूप से नहीं बढ़ता। यह ऐसा है जैसे कहना, "चाहे कितनी भी कंपनियां क्यों न हों, मैं उन्हें लगभग उतने ही समय में छाँट सकता हूँ जितना कि कुछ ही कंपनियों को छाँटने में लगता है।"

2. "आइडेंटिकल कोवेरिएंस" केस (समान आकार, अलग स्थान)
कल्पना कीजिए कि सभी मेल के ढेरों का बिल्कुल एक ही अजीब आकार है (उदाहरण के लिए, सभी खींचे हुए सिगार हैं), लेकिन वे कमरे के अलग-अलग हिस्सों में स्थित हैं।

पुराना तरीका: इसमें भी काफी समय लगता था, लगभग $d^{\text{something related to } k}$ ।
नया तरीका: इसमें समय $d^{\log k}$ के अनुपात में लगता है। यह एक बहुत बड़ा सुधार है। यह एक ऐसे पहाड़ पर चढ़ने के बीच अंतर की तरह है जो अधिक लोग जुड़ने पर और भी खड़ा होता जाता है, बनाम एक ऐसे पहाड़ की तरह जो थोड़ा और खड़ा तो होता है लेकिन फिर भी चढ़ने योग्य है।

यह एक आश्चर्य क्यों है

कंप्यूटर विज्ञान की दुनिया में, कुछ "लोअर बाउंड्स" (lower bounds) होते हैं—गणितीय प्रमाण जो कहते हैं कि, "आप इस समस्या को X समय से तेज़ नहीं हल कर सकते।" इन विशिष्ट प्रकार के मेल छाँटने की समस्याओं के लिए, विशेषज्ञों का मानना था कि "पैरेलल पैनकेक्स" निर्माण यह सिद्ध करता है कि आपको घातांकीय (exponential) समय की आवश्यकता होगी।

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

निचोड़ (The Bottom Line)

यह शोध पत्र एक नए एल्गोरिदम को प्रस्तुत करता है जो एक स्मार्ट फिल्टर की तरह काम करता है। यह शोर को फ़िल्टर करता है और जटिल, उच्च-आयामी डेटा को एक सरल, निम्न-आयामी दृश्य में प्रोजेक्ट करता है जहाँ विभिन्न समूह आसानी से अलग किए जा सकते हैं।

केंद्रित मिश्रणों के लिए: यह उन्हें ऐसे समय में छाँटता है जो समूहों के बढ़ने के साथ विस्फोट नहीं करता।
समान-आकार के मिश्रणों के लिए: यह उन्हें ऐसे समय में छाँटता है जो समूहों के बढ़ने के साथ बहुत धीरे (लॉगारिदमिक रूप से) बढ़ता है।

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

तकनीकी सारांश: गैर-गोलाकार मिश्रणों के लिए सम-वर्ग (Sum-of-Squares) और उन्नत क्लस्टरिंग एल्गोरिदम के माध्यम से आयामी न्यूनीकरण (Dimension Reduction)

1. समस्या विवरण

यह शोध पत्र उच्च-आयामी गाऊसी मिश्रण मॉडल (Gaussian Mixture Models - GMMs) के क्लस्टरिंग की समस्या को संबोधित करता है जहाँ घटक सहप्रसरण (component covariances) मनमाने (गैर-गोलाकार) होते हैं। विशेष रूप से, $k$ $d$ -आयामी गाऊसियनों के एक मिश्रण $P = \sum_{i=1}^k w_i \mathcal{N}(\mu_i, \Sigma_i)$ से प्राप्त $i.i.d.$ नमूनों के दिए जाने पर, लक्ष्य डेटा को इस प्रकार विभाजित करना है कि गलत वर्गीकृत बिंदुओं का अंश छोटा (अधिकतम 1%) हो।

घटकों को टोटल वेरिएशन (TV) दूरी में "सुव्यवस्थित रूप से अलग" (well-separated) माना जाता है, विशेष रूप से $d_{TV}(\mathcal{N}(\mu_i, \Sigma_i), \mathcal{N}(\mu_j, \Sigma_j)) \ge 1 - f(w_{\min})$ , जहाँ $w_{\min}$ न्यूनतम मिश्रण भार (mixing weight) है। लेखक दो विशिष्ट सेटिंग्स पर ध्यान केंद्रित करते हैं:

केंद्रित मिश्रण (Centered Mixtures): सभी घटकों का माध्य शून्य है ( $\mu_i = 0$ ), लेकिन सहप्रसरण $\Sigma_i$ मनमाना है।
समान-सहप्रसरण मिश्रण (Identical-Covariance Mixtures): सभी घटक एक ही अज्ञात सहप्रसरण $\Sigma$ साझा करते हैं, लेकिन उनके माध्य $\mu_i$ भिन्न होते हैं।

इस कार्य से पूर्व, गैर-गोलाकार मिश्रणों के लिए अत्याधुनिक (state-of-the-art) एल्गोरिदम को इन संरचित सेटिंग्स के लिए भी $d^{\Omega(k)}$ की नमूना और समय जटिलता (sample and time complexity) की आवश्यकता थी। यह गोलाकार मिश्रणों के विपरीत था, जिन्हें $d^{O(1)}$ समय में क्लस्टर किया जा सकता है। $d^{\Omega(k)}$ की यह बाधा सांख्यिकीय प्रश्न (Statistical Query - SQ) और सम-वर्ग (Sum-of-Squares - SoS) निचली सीमाओं [DKS17, DKPP24] द्वारा समर्थित थी, जो सुझाव देती थीं कि सामान्य गैर-गोलाकार मिश्रणों के लिए ऐसा खर्च आवश्यक है।

2. कार्यप्रणाली और मुख्य तकनीकी विचार

मुख्य योगदान सम-वर्ग (SoS) पद्धति पर आधारित एक नया आयामी न्यूनीकरण उप-प्रक्रिया (dimension reduction subroutine) है। यह उप-प्रक्रिया इनपुट डेटा के एक निम्न-आयामी प्रक्षेपण (low-dimensional projection) की पहचान करती है जो कम से कम एक जोड़े के बीच अलगाव को संरक्षित करता है, जिससे एल्गोरिदम को आंशिक रूप से डेटा को क्लस्टर करने और पुनरावृत्ति (iterate) करने की अनुमति मिलती है।

2.1 पूर्व कार्य में बाधा

पिछले दृष्टिकोण (जैसे, [BK20, DHKK20]) घटकों को अलग करने के लिए सभी दिशाओं में डेटा के "एंटी-कंसंट्रेशन" (anti-concentration) गुणों को प्रमाणित करने पर निर्भर थे। गैर-गोलाकार मिश्रणों के लिए, इस प्रमाणन हेतु $\Omega(k)$ मोमेंट्स (moments) को मैच करने की आवश्यकता थी, जिससे $d^{\Omega(k)}$ जटिलता उत्पन्न हुई। लेखक देखते हैं कि केंद्रित घटकों या समान सहप्रकारों के लिए विशिष्ट सेटिंग्स में, निचली सीमाओं को सिद्ध करने के लिए उपयोग किए जाने वाले "हार्ड" उदाहरण (पैरेलल पैनकेक्स निर्माण) लागू नहीं होते हैं, क्योंकि ये निर्माण गैर-शून्य माध्य और घातीय रूप से छोटे भारों पर निर्भर करते हैं।

2.2 SoS आयामी न्यूनीकरण दृष्टिकोण

लेखक बिना उच्च-क्रम के मोमेंट्स को मैच किए, "अलगाव की दिशा" (direction of separation) खोजने की एक तकनीक विकसित करते हैं। इस दृष्टिकोण में शामिल हैं:

बाधाओं का निर्धारण (Formulating Constraints): एक इकाई वेक्टर $v$ पर बहुपदीय असमानताओं (polynomial inequalities) का एक तंत्र $A(v)$ बनाना जो "गोलाकार दिशाओं" (वे दिशाएँ जहाँ विचरण/variance 1 के करीब है) या अलगाव के लंबवत दिशाओं को परिभाषित करता है।
- केंद्रित मिश्रणों के लिए: लेखक चौथे मोमेंट टेंसर (fourth moment tensor) का उपयोग करते हैं। वे देखते हैं कि जबकि सममितीकृत (symmetrized) चौथा मोमेंट टेंसर उच्च-रैंक का है और सीधे विघटित करना कठिन है, एक वेक्टर $v$ के "गोलाकार" होने की स्थिति (अर्थात, $v^\top \Sigma_i v \approx 1$ सभी $i$ के लिए) चौथे मोमेंट फॉर्म के हेसियन (Hessian) से जुड़ी एक प्रणाली द्वारा पकड़ी जा सकती है। विशेष रूप से, यदि $\langle M_4, v^{\otimes 4} \rangle \approx 0$ और $\nabla^2_v \langle M_4, v^{\otimes 4} \rangle \approx 0$ , तो $v$ विचलन मैट्रिसेस (deviation matrices) $(\Sigma_i - I)$ के कर्नेल (kernel) के करीब है।
- समान सहप्रकारों के लिए: लेखक [BS23] के एक परिणाम का लाभ उठाते हैं जो दर्शाता है कि समान सहप्रसरण वाला एक मिश्रण मानक गाऊसी वितरण के पहले $O(\log k)$ मोमेंट्स को मैच नहीं कर सकता है। वे उन दिशाओं की पहचान करने के लिए पहले $O(\log k)$ मोमेंट्स पर आधारित बाधाएं निर्मित करते हैं जहाँ विचरण 1 के करीब है।
SoS राउंडिंग (SoS Rounding): बाधाओं का तंत्र $A(v)$ वेक्टर्स के एक सेट को परिभाषित करता है। लेखक एक निम्न-आयामी उप-स्थान (subspace) को पुनः प्राप्त करने के लिए एक SoS राउंडिंग एल्गोरिदम (प्रमेय 4.1 और 4.2) का उपयोग करते हैं जो $A(v)$ के समाधानों को समाहित करता है (या उनके लंबवत होता है)।
- महत्वपूर्ण रूप से, केंद्रित मिश्रणों के लिए आवश्यक SoS प्रमाणों की डिग्री स्थिर (constant) है और समान-सहप्रसरण मिश्रणों के लिए $O(\log k)$ है। यही निम्न डिग्री इस बात का कारण है कि एल्गोरिदम को $d^{\Omega(k)}$ के बजाय $d^{O(1)}$ या $d^{O(\log k)}$ समय में चलने की अनुमति मिलती है।
पुनरावृत्त क्लस्टरिंग (Iterative Clustering): एक बार जब अलगाव की दिशा वाला निम्न-आयामी उप-स्थान मिल जाता है, तो एल्गोरिदम डेटा को प्रोजेक्ट करता है, मिश्रण को दो भागों में विभाजित करने के लिए एक सरल थ्रेशोल्डिंग (thresholding) करता है, और परिणामी उप-समुच्चयों पर पुनरावृत्ति करता है।

3. मुख्य परिणाम

शोध पत्र दो सेटिंग्स के लिए कुशल एल्गोरिदम प्रदान करने वाले दो मुख्य प्रमेय प्रस्तुत करता है।

प्रमेय 1.1: केंद्रित गाऊसी मिश्रण

$k$ केंद्रित गाऊसियनों के एक मिश्रण के लिए जिसका न्यूनतम भार $w_{\min}$ है और युग्मवार TV पृथक्करण है, एक ऐसा एल्गोरिदम मौजूद है जो:

नमूना जटिलता (Sample Complexity): $n \ge \text{poly}(d) \cdot f(w_{\min}^{-1})$ ।
समय जटिलता (Time Complexity): $\text{poly}(d) \cdot f(w_{\min}^{-1})$ ।
गारंटी: एक क्लस्टरिंग आउटपुट देता है जिसमें गलत वर्गीकरण त्रुटि $O(k w_{\min}^{-1} \max\{\epsilon, k^{-k}\})$ है, जहाँ $\epsilon$ आउटलेर्स (outliers) का अंश है।
महत्व: आयाम $d$ पर निर्भरता एक निश्चित बहुपद है, जो $k$ से पूरी तरह स्वतंत्र है। यह उस $d^{\Omega(k)}$ बाधा को तोड़ता है जिसे पहले आवश्यक माना जाता था।

प्रमेय 1.2: समान-सहप्रसरण गाऊसी मिश्रण

$k$ गाऊसियनों के एक मिश्रण के लिए जिसका समान लेकिन अज्ञात सहप्रसरण $\Sigma$ , न्यूनतम भार $w_{\min}$ , और युग्मवार TV पृथक्करण है:

नमूना जटिलता: $n \ge d^{O(\log w_{\min}^{-1})} \cdot f(w_{\min}^{-1})$ ।
समय जटिलता: $d^{O(\log^2 w_{\min}^{-1})} \cdot f(w_{\min}^{-1})$ ।
गारंटी: केंद्रित मामले की तरह ही समान गलत वर्गीकरण सीमाएँ।
महत्व: हालांकि केंद्रित मामले की तुलना में $d$ पर निर्भरता थोड़ी अधिक ( $d^{\text{polylog}(k)}$ ) है, फिर भी यह पिछले $d^{\Omega(k)}$ अनुमानों की तुलना में घातीय रूप से बेहतर है।

कोरोलरी: उप-स्थान क्लस्टरिंग (Subspace Clustering)

एक तत्काल अनुप्रयोग के रूप में, लेखक गाऊसीय उप-स्थान क्लस्टरिंग (जहाँ घटक भिन्न उप-स्थानों पर समर्थित होते हैं) के लिए एक आउटलेयर-रोबस्ट एल्गोरिदम प्रदान करते हैं, जिसकी समय और नमूना जटिलता $\text{poly}(d) \cdot f(w_{\min}^{-1})$ है।

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

लेखक दावा करते हैं कि मौजूदा कठोरता परिणामों (hardness results) के संदर्भ में उनके परिणाम आश्चर्यजनक हैं। गैर-गोलाकार मिश्रणों [DKS17, DKPP24] के लिए $d^{\Omega(k)}$ निचली सीमाएँ गैर-शून्य माध्य और घातीय रूप से छोटे भारों वाले "पैरेलल पैनकेक्स" निर्माणों पर आधारित हैं। केंद्रित घटकों या समान सहप्रकारों तक सीमित करके, लेखक यह प्रदर्शित करते हैं कि इन कठोरता बाधाओं को दरकिनार किया जा सकता है।

बाधा को तोड़ना: यह कार्य दिखाता है कि गैर-गोलाकार मिश्रणों के एक "अत्यंत व्यापक वर्ग" (केंद्रित या समान-सहप्रसरण) के लिए, क्लस्टरिंग की लागत को $d^{\Omega(k)}$ से घटाकर $d^{O(1)}$ या $d^{\text{polylog}(k)}$ किया जा सकता है।
पद्धतिगत प्रगति: शोध पत्र एक नई SoS-आधारित आयामी न्यूनीकरण तकनीक पेश करता है जो उच्च-डिग्री मोमेंट मैचिंग की आवश्यकता को समाप्त करती है। पूर्ण संरचना को उच्च-क्रम टेंसरों के माध्यम से पुनः प्राप्त करने के बजाय, यह अलगाव के लिए प्रासंगिक विशिष्ट उप-स्थानों की पहचान करने के लिए निम्न-डिग्री SoS प्रमाणों का उपयोग करता है।
मजबूती (Robustness): एल्गोरिदम स्वाभाविक रूप से आयाम-स्वतंत्र मनमाने आउटलेर्स को सहन करने के लिए विस्तारित होते हैं।

लेखक एक हालिया निचली सीमा [DKK+25] (प्रीप्रिंट के बाद की) को स्वीकार करते हैं जो समान-सहप्रसरण मामले के लिए $d^{\Omega(\log k)}$ SQ निचली सीमा दिखाती है। यह पुष्टि करता है कि जबकि $d^{\Omega(k)}$ बाधा टूट गई है, समान-सहप्रसरण मामले के लिए $d^{O(1)}$ बाधा को SQ मॉडल में $d^{O(1)}$ में नहीं सुधारा जा सकता है, जो केंद्रित और समान-सहप्रसरण सेटिंग्स के बीच एक अलगाव को रेखांकित करता है।

संक्षेप में, यह शोध पत्र गैर-गोलाकार गाऊसी मिश्रणों (शून्य माध्य या समान सहप्रसरण वाले) के क्लस्टरिंग के लिए पहले कुशल एल्गोरिदम प्रदान करता है जो आयाम $d$ में बहुपद समय (एक स्थिर या पॉयलीलॉग घांक के साथ) में चलते हैं, जो पिछले $d^{\Omega(k)}$ अत्याधुनिक (state-of-the-art) से काफी बेहतर है।