University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Topological arguments in Kolmogorov complexity

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Topological arguments in Kolmogorov complexity

Download to your calendar using vCal

If you have a question about this talk, please contact Mustapha Amrani .

Semantics and Syntax: A Legacy of Alan Turing

We show how topological arguments (simple facts about non-homotopic mappings) can be used to prove result about Kolmogorov complexity. In particular, we show that for every string x of complexity at least n +c log n one can find a string y such that both conditional complexities C(x|y) and C(y|x) are equal to n+O(1).

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Faculty of Music Colloquia 2025/6 Average on weekdays: 9160.875 kWh Seminar time is 1pm BST in Room FW 11, Willam Gates Hall. Zoom link: https://cl-cam-ac-uk.zoom.us/j/4361570789?pwd=Nkl2T3ZLaTZwRm05bzRTOUUxY3Q4QT09&from=addon

Other talks

External Seminar - Jenn Brophy TBC Semiconductor-based neutron detector development at QMUL Synthesizing Diverse Policies for Multi-Agent Coordination Title to be confirmed Cultural evolution creates language-like structure: from humans to humpback whales and beyond Title TBC
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity