Kolmogorov complexity as a combinatorial tool

May 15, 2024 · The Ethereal · 🏛 Conference on Computability in Europe

🔮 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 Alexander Shen arXiv ID 2405.09304 Category cs.DM: Discrete Mathematics Cross-listed cs.IT, math.CO Citations 0 Venue Conference on Computability in Europe Last Checked 5 months ago
Abstract
Kolmogorov complexity is often used as a convenient language for counting and/or probabilistic existence proofs. However, there are some applications where Kolmogorov complexity is used in a more subtle way. We provide one (somehow) surprising example where an existence of a winning strategy in a natural combinatorial game is proven (and no direct proof is known).
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 — Discrete Mathematics