Streaming and Sketching Complexity of CSPs: A survey

May 05, 2022 · The Ethereal · 🏛 International Colloquium on Automata, Languages and Programming

🔮 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 Madhu Sudan arXiv ID 2205.02744 Category cs.CC: Computational Complexity Cross-listed cs.DS Citations 10 Venue International Colloquium on Automata, Languages and Programming Last Checked 2 months ago
Abstract
In this survey we describe progress over the last decade or so in understanding the complexity of solving constraint satisfaction problems (CSPs) approximately in the streaming and sketching models of computation. After surveying some of the results we give some sketches of the proofs and in particular try to explain why there is a tight dichotomy result for sketching algorithms working in subpolynomial space regime.
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 — Computational Complexity