Loading Events

« All Events

  • This event has passed.
:

Martin Ziegler, Quantitative Coding and Complexity Theory of Continuous Data

February 16 Tuesday @ 4:30 PM - 5:30 PM KST

Room B232, IBS (기초과학연구원)

Speaker

Specifying a computational problem requires fixing encodings for input and output: encoding graphs as adjacency matrices, characters as integers, integers as bit strings, and vice versa. For such discrete data, the actual encoding is usually straightforward and/or complexity-theoretically inessential (up to polynomial time, say).

But concerning continuous data, already real numbers naturally suggest various encodings with very different computational properties.

We recall the existing qualitative theory of computably ‘sensible’ encodings of topological spaces; and we newly develop the quantitative theory of complexity-theoretically ‘sensible’ encodings of metric spaces.

Joint work with Donghyun Lim.

Details

Date:
February 16 Tuesday
Time:
4:30 PM - 5:30 PM KST
Event Category:
Event Tags:

Venue

Room B232
IBS (기초과학연구원)

Organizer

Sang-il Oum (엄상일)
View Organizer Website
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.