\Delta Seminar on Logic, Philosophy, and Computer Science

This is the webpage for the [math]\displaystyle{ \Delta }[/math] Workshop on Logic, Philosophy, and Computer Science.

The Inauguration Workshop

• Time: 2015年10月10日
• Place: 南京大学 仙林校区 计算机系楼2楼 233报告厅
• Local host: 南京大学 数学系 喻良 教授 (yuliaing.nju@gmail.com)，南京大学 计算机系 尹一通 副教授 (yinyt@nju.edu.cn)

• 居住在新纪元酒店的参会人员请于10月10日早8:15集合，统一乘车前往南大仙林校区。

Schedule

Time	Speaker	Title and Abstract
9:30-10:15	琚凤魁（北京师范大学）	Title: A Process Modality in Trace Semantics Abstract: In dynamic logic, actions are usually interpreted as sets of binary tuples. This interpretation lets us describe the input and output states of performing actions very well. There is another way to view actions: they are sets of finite state sequences, called traces. This interpretation makes it possible to talk about what happens during performance of actions. This paper considers four action constructors: composition, intersection, union and iteration; it introduces a process modality and studies its expressive power intensively.
10:15-11:00	孙晓明（中科院计算所）	Title: Progress on the sensitivity conjecture of Boolean functions Abstract: The sensitivity conjecture of Nisan and Szegedy asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of Boolean functions. Despite major advances in analysis of Boolean functions in the past decade, the problem remains wide open with no positive result toward the conjecture since the work of Kenyon and Kutin from 2004. In this talk I will survey some recently progress we made toward this conjecture. We prove tighter upper bounds for various complexity measures in terms of sensitivity. More precisely, we show that [math]\displaystyle{ \mathrm{deg}(f)^{1-o(1)} = O(2^s(f)) }[/math] and [math]\displaystyle{ C(f) \le 2^{s(f)-1} s(f) }[/math]; these in turn imply various corollaries regarding the relation between sensitivity and other complexity measures, such as block sensitivity, via known results. The gap between sensitivity and other complexity measures remains exponential but these results are the first improvement for this difficult problem that has been achieved in a decade. I will also discuss the sensitivity complexity of some special functions, for example graph properties.
coffee break
11:30-12:15	康孝军（吉林大学）	Title: Reverse Mathematics and its Significance Abstract: Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Actually, reverse mathematics can be regarded as a partial realizations of Hilbert's program. After briefly review Reverse mathematics and some important results of it, we show the philosophical significance and influence of reverse mathematics from the perspective of pragmatism.
lunch
14:15-15:00	何家亮（四川大学）	Title: Comparison game on Borel ideal Abstract: In this talk, we will consider some properties about a Wadge-like game which called Comparison game. We prove that the Comparison game is coherent with Wadge game on a subclass of Borel ideals. Thus answer some questions of M. Hrusak and D. M. Alcantara.
15:00-15:45	张驰豪（上海交通大学）	Title: Canonical Paths for Markov Chain Monte Carlo: from Art to Science Abstract: Markov Chain Monte Carlo (MCMC) is a widely used algorithm design scheme for counting problems. Canonical paths is one of the most important tools for proving the efficiency of the MCMC based algorithms and has been successfully applied in the analysis of many approximate counting algorithms. In this talk, I will demostrate the general idea behind this technique and introduce a new formulation of canonical paths for a class of combinatorial problems. The formulation is based on our new characterization of canonical paths in terms of linear equations. As applications, we obtain fully polynomial-time approximate schemes (FPRAS) for a number of counting problems, including the generalization of matchings and edges covers in graphs.
coffee break
16:15-17:00	姚宁远（复旦大学）	Title: On minimal flows, definably amenable groups, and o-minimality Abstract: We study definably amenable groups in NIP theories, focusing on the problem raised by L. Newelski of whether weakly generic types coincide with almost periodic types, equivalently whether the union of minimal subflows of a suitable type space is closed. We give fairly denitive results in the o-minimal context, including a counterexample.