Descriptive complexity for distributed computing with circuits

March 08, 2023 · The Ethereal · 🏛 International Symposium on Mathematical Foundations of Computer Science

🔮 THE ETHEREAL: The Ethereal
Pure theory — exists on a plane beyond code

"No code URL or promise found in abstract"

Evidence collected by the PWNC Scanner

Authors Veeti Ahvonen, Damian Heiman, Lauri Hella, Antti Kuusisto arXiv ID 2303.04735 Category cs.LO: Logic in CS Cross-listed cs.DC Citations 4 Venue International Symposium on Mathematical Foundations of Computer Science Last Checked 5 months ago
Abstract
We consider distributed algorithms in the realistic scenario where distributed message passing is operated via circuits. We show that within this setting, modal substitution calculus MSC captures the expressive power of circuits. The translations between circuits and MSC-programs are linear in both directions. Furthermore, we show that the colouring algorithm based on Cole-Vishkin can be specified via logarithmic size programs.
Community shame:
Not yet rated
📄 View on arXiv 🌐 View on ar5iv 📑 PDF 🎉 Report Code Found
Community Contributions

Found the code? Know the venue? Think something is wrong? Let us know!

📜 Similar Papers

In the same crypt — Logic in CS