학과 세미나 및 콜로퀴엄

구분 IBS-KAIST 세미나
분류 이산수학
제목 Uniform random expressions lack expressivity
Abstract In computer science, random expressions are commonly used to analyze algorithms, either to study their average complexity, or to generate benchmarks to test them experimentally. In general, these approaches only consider the expressions as purely syntactic trees, and completely ignore their semantics — i.e. the mathematical object represented by the expression. However, two different expressions can be equivalent (for example “0*(x+y)” and “0” represent the same expression, the null expression). Can these redundancies question the relevance of the analyses and tests that do not take into account the semantics of the expressions? I will present how the uniform distribution over syntactic expression becomes completely degenerate when we start taking into account their semantics, in a very simple but common case where there is an absorbing element. If time permits it, I will briefly explain why the BST distribution offers more hope. This is a joint work with Cyril Nicaud and Pablo Rotondo.
일시 2022-10-18 (Tue) / 16:30 ~ 17:30
장소 Room B332, IBS (기초과학연구원)
강연언어 영어
강연자성명 Florent Koechlin
강연자소속 LORIA, INRIA, Nancy, France
강연자홈페이지 https://igm.univ-mlv.fr/~koechlin/
기타정보
초청인 Sang-il Oum
URL https://dimag.ibs.re.kr/event/2022-10-18/
담당자
연락처