-
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, […]
-
Computation, Randomness and Dimensionality
Speaker: George Barmpalias (Chinese Academy of Sciences) Time: 11:00AM(Time in Beijing) 4:00PM(Time in Auckland) March 11, 2021 (Thursday) Address: Online meeting VooVmeeting: ID: 222 489 953 Password: 202103 Link: https://meeting.tencent.com/s/OgG2rzHAiky1 Abstract: Randomness is a precious resource in computation and modeling, where access to a random source with specific properties is needed. Transforming one type of […]
-
Network Protection
Speaker: Binglin Tao (University of Electronic and Science Technology of China) Time: 10:00AM(Time in Beijing) 3:00PM(Time in Auckland) March 5, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 159 906 783 Password: 1936 Link: https://meeting.tencent.com/s/YcCZ2nwdpBoj Abstract: Communication systems and infrastructures become more critical in our daily life. Damages to physical links or nodes affect all transmission […]
-
Algebraic Sparsification for Decision and Maximization Constraint Satisfaction Problems
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 […]
-
Approximate Strategyproof Mechanisms Design for Facility Location Games
Speaker: Mengfan Ma(University of Electronic Science and Technology of China) Time: 9:00AM(Time in Beijing) 2:00PM(Time in Auckland) February 5, 2021 (Friday) Address: Online meeting VooVmeeting: ID: 349 933 612 Password: 1936 Link: https://meeting.tencent.com/s/xvmzXgslf53A Abstract: In the basic settings of facility location games, agents are located on the real line and public facilities are to be […]
-
Seminars on Extremal Graph Theory and Ramsey Theory in 2021
-
A simple deterministic pseudopolynomial time algorithms for subset sum
Speaker: Chao Xu(The Voleon Group) Time: 11:00AM(Time in Beijing) 4:00PM(Time in Auckland) January 6, 2021 (Wednesday) VooVmeeting ID：360572001 Password: 1936 Link: https://meeting.tencent.com/s/Hu6RyhQq2MPc Abstract: Given a set of n positive integers and a target integer t, the subset sum problem asks if there exists a subset with elements sum to t. Bellman (1956) found a dynamic […]