Witness Complexity of Short Descriptions: A Cryptographic Perspective
यह शोध पत्र "विटनेस कॉम्प्लेक्सिटी" (witness complexity) को एक नए मीट्रिक के रूप में प्रस्तुत करता है जो लघु क्रिप्टोग्राफिक विवरणों के विस्तार या सत्यापन के लिए आवश्यक न्यूनतम समय को मापता है, यह प्रदर्शित करते हुए कि कम विवरण लंबाई (कोलमोगोरोव कॉम्प्लेक्सिटी) कुशल उपयोगिता की गारंटी नहीं देती है और इस समय-लागत अंतराल तथा P और NP जैसे मौलिक जटिलता वर्गों के बीच एक औपचारिक संबंध स्थापित करता है।