नई ग्राफ विघटन और संयोजनात्मक बूलियन मैट्रिक्स गुणन एल्गोरिदम

हम बुनियादी बूलियन मैट्रिक्स गुणन (BMM) समस्या पर पुनर्विचार करते हैं। 50 साल पहले बीजगणितीय तेज मैट्रिक्स गुणन के आविष्कार के साथ यह भी ज्ञात हुआ कि BMM को वास्तव में उपक्यूबिक O(nω) समय में हल किया जा सकता है, जहां ω<3; ω को 2 के करीब लाने के लिए काफी प्रयास किए गए हैं। तब से, एक समानांतर कार्य लाइन ने अपेक्षाकृत तेज संयोजनात्मक एल्गोरिदम खोजने की कोशिश की है लेकिन सीमित सफलता के साथ। प्रारंभिक O(n3)-समय एल्गोरिदम को पहले एक log2n कारक द्वारा Arlazarov et al.; RAS'70 द्वारा सुधारित किया गया; फिर log2.25n द्वारा Bansal और Williams; FOCS'09, फिर log3n द्वारा Chan; SODA'15, और अंततः log4n द्वारा Yu; ICALP'15 द्वारा।