Algorithms and Logic Group

Category: Seminars

  • Constant Approximating k-Clique is W[1]-hard

    Speaker: Bingkai Lin(Nanjing University) Time: 10:00-11:00 (Time in Beijing) April 20, 2021 (Tuesday) VooVmeeting: ZOOM ID: 467 156 1455 Password: 图灵机被提出的年份（4位） Bilibili Live: http://live.bilibili.com/22528138 Abstract: Deciding whether a graph contains a ‍‍-Clique is a well-known NP‍‍-hard problem. One approach to dealing with NP‍‍-hard problem is approximation algorithm. However, assuming NP P ‍‍, no polynomial time […]

  • An Experimental Study of the Feedback Arc Set Problem

    Speaker: Ziliang Xiong(University of Electronic and Science Technology of China) Time: 10:00-12:00 (Time in Beijing) 14:00-16:00 (Time in Auckland) April 9, 2021 (Friday) VooVmeeting: Link: https://meeting.tencent.com/s/4780kEVEoRgF ID: 381 139 951 Venue: B1-514, Main Building Abstract: Given a digraph, the minimum feedback arc set problem asks to find the smallest arc set whose removal makes the […]

  • Mathematical Principles of Information Sciences, II: Mathematical Theory of Intuitive Reasoning

    Speaker: Angsheng Li(Beihang University) Time: 14:00-15:00 (Time in Beijing) 18:00-19:00 (Time in Auckland) April 9, 2021 (Friday) Venue: B1-501, Main Building Abstract: Started at Hilbert’s 1900 program of axiomatizing mathematics, in 1930s, mathematicians including Gödel proposed the definition of “proof” and established the subject of mathematical logic, and more importantly, Turing 1936 proposed a mathematical […]

  • Mathematical Principles of Information Sciences, I: The Laws of Information

    Speaker: Angsheng Li(Beihang University) Time: 11:00-12:00(Time in Beijing) 15:00-16:00(Time in Auckland) April 8, 2021 (Thursday) Venue: Coffee Beanery (宾诺咖啡) Abstract: Shannon 1945 and 1948 started the mathematical studies of cryptography and of communication, respectively. In 1945,Shannon proposed an information theoretical protocol for data security, leading to the mathematical theory of data security. In 1948, Shannon […]

  • Random sampling in social network auction

    Speaker: Yuchao Song(University of Electronic and Science Technology of China) Time: 10:00AM(Time in Beijing) 3:00PM(Time in Auckland) April 2, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 425 826 163 Password: 1949 Link: https://meeting.tencent.com/s/OWsH2L3tXfss Abstract: We will introuduce the problem of auction design with budget and network structure, that is, auction information can be transmitted by […]

  • Random sampling in auction with budget

    Speaker: Yuchao Song(University of Electronic and Science Technology of China) Time: 10:00AM(Time in Beijing) 3:00PM(Time in Auckland) March 26, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 384 982 466 Password: 1949 Link: https://meeting.tencent.com/s/4UNWqmJBGY2s Abstract: In addition to reviewing the last classical random sampling auctions, we will introuduce the problem of auction with budget which buyers […]

  • How fast can we solve NP-complete problems?

    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 […]

  • Random sampling in auction

    Speaker: Yuchao Song(University of Electronic and Science Technology of China) Time: 10:00AM(Time in Beijing) 3:00PM(Time in Auckland) March 19, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 212 396 556 Password: 1949 Link: https://meeting.tencent.com/s/ZPP7b2ZIpUlL Abstract: Random sampling is a common technique in statistics. It is a common application to obtain the estimation of the overall distribution […]

  • The Anti-Ramsey Number For Paths

    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 𝐻, […]

  • Crowdsourcing Mechanism over Graphs

    Speaker: Shubei Wang (University of Electronic and Science Technology of China) Time: 10:00AM(Time in Beijing) 3:00PM(Time in Auckland) March 12, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 490 679 211 Password: 1936 Link: https://meeting.tencent.com/s/F7AIovMhMkCU Abstract: Crowdsourcing is a sourcing model in which individuals or organizations obtain goods or services, including ideas, voting, micro-tasks and finances, […]