Speaker: Mingyu Xiao(University of Electronic Science and Technology of China) Host Institute for Interdisciplinary Information Sciences, Tsinghua University Time: 2021-03-22 16:00-2021-03-22 17:00 Address: Tsinghua University FIT1-222 Abstract: Under the hypothesis P != NP, NP-complete problems cannot be solved in polynomial time. Under ETH, the SAT problem (the first NP-complete problem) cannot be solved in sub-exponential […]

Speaker: Long-Tu Yuan (East China Normal University) Time: 13:00 – 14:00 (Time in Beijing) March 18, 2021 (Thursday) Address: Online meeting Host: SCMS （上海数学中心） VooVmeeting: ID: 830 305 307 Password: 121323 Link: https://zoom.com.cn/j/8303053077 Abstract: A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. For a given graph 𝐻, […]

Speaker: Bart Jansen(Eindhoven University of Technology) Time: 5:00 p.m., February 25, 2021(Time in Bergen, GMT+1) 12:00 p.m., February 25, 2021(Time in Beijing, GMT+8) Link: zoom: https://uib.zoom.us/j/4231169675 password: CLIQUE Abstract: We survey polynomial-time sparsification for NP-complete Boolean Constraint Satisfaction Problems (CSPs). The goal in sparsification is to reduce the number of constraints in a problem instance […]