IJTCS | 特别推荐：女性学者论坛
编者按
首届国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）将于2020年8月17日-21日在线上举行，由北京大学与中国工业与应用数学学会（CSIAM）、中国计算机学会（CCF）、国际计算机学会中国委员会（ACM China Council）联合主办，北京大学前沿计算研究中心承办。
本次大会的主题为“理论计算机科学领域的最新进展与焦点问题”。大会共设7个分论坛，分别对算法博弈论、区块链技术、多智能体强化学习、机器学习理论、量子计算、机器学习与形式化方法和算法与复杂性等领域进行深入探讨。同时，大会特别开设了青年博士论坛、女性学者论坛与本科生科研论坛，荟集海内外知名专家学者，聚焦理论计算机前沿问题。有关信息将持续更新，敬请关注！
本期带来“女性学者论坛”精彩介绍。
“女性学者论坛”介绍
组成人员的多样性对任何一个领域都十分重要。当然每个个体都是特殊的，其特殊性并不能被一个简单类别的标签所抹去。然而，一旦多样性失衡，刻板印象就会产生。而刻板印象很可能将会对没有进入这个领域的个体产生阻碍。如大家觉得幼儿园老师可能女性居多，想成为幼儿园老师的男性就可能会感受到阻力。
理论计算机研究领域也不例外。然而目前来看，中国理论计算机研究领域的女性仍然是少数。其产生的刻板印象将极有可能对女学生的科研方向选择产生影响，甚至她们都很难接触了解到这个领域。本次论坛将邀请四位该领域的女学生（包括本科生和研究生）来介绍她们的学术工作。同时还有一小时的座谈会时间，邀请多位理论领域的女性研究者来讨论理论计算机领域对女性的机遇和挑战。我们尤其还邀请一位理论领域的男性研究者来加入他的视角。希望未来能够促进更多女性了解并加入理论计算机领域。
“女性学者论坛”主席
孔雨晴
北京大学
张家琳
中国科学院计算技术研究所
“女性学者论坛”议程
时间：2020年8月18日
主题座谈会
Opportunities and Challenges for Female Researchers in Theoretical Computer Science
时间：2020年8月18日19:00-20:00
主持人：孔雨晴、张家琳
参与人：陈婧、祁琦、张昭、方奇志、程郁琨、陈翌佳
欢
迎
参
加
“女性学者论坛”报告简介
吴步娇
Optimize the Size and Depth of CNOT Circuits
Abstract
Due to the decoherence of the state-of-the-art physical implementations of quantum computers, and the near-term quantum technologies can only support limited amount of qubits, it is essential to parallelize the quantum circuits with space-depth trade-off. Furthermore, quantum computation is limited to the connection of two qubits in actual physical devices. It is essential to optimize the size and depth of CNOT circuits based on topological superconducting processors.
In this work, we establish an asymptotically optimal space-depth trade-off for the design of CNOT circuits of the logical qubits (CNOT can be operated on any two qubits), we show that this bound is tight by a counting argument. For actual physical qubits, we give an algorithm to optimize the size of CNOT circuits under topological structure, and prove our algorithm is optimal when the graph is regular. In addition, we also consider the optimization of depth of CNOT circuits in d dimensional grid topological structure, by which we can optimize any CNOT circuits to O(n^(1+o(1))/log n)-depth with O(n)-ancillas and d=O(1).
吴怡凡
Optimization of Scoring Rules
Abstract
This paper introduces an objective for optimizing proper scoring rules. The objective is to maximize the increase in payoff of a forecaster who exerts a binary level of effort to refine a posterior belief from a prior belief. In this framework we characterize optimal scoring rules in simple settings, give efficient algorithms for computing optimal scoring rules in complex settings, and identify simple scoring rules that are approximately optimal. In comparison, standard scoring rules in theory and practice – for example, the quadratic rule, scoring rules for the expectation, and scoring rules for multiple tasks that are averages of single-task scoring rules – can be very far from optimal.
巩素宁
A 1/2-approximation Algorithm for Maximizing a Non-monotone Weak-submodular Function on a Bounded Integer Lattice
Abstract
Maximizing non-monotone submodular functions is one of the most important problems in submodular optimization. Let 𝐁=(𝐵1,𝐵2,...,𝐵𝑛) ∈ 𝑍+𝑛 be an integer vector and [𝐁] = {(𝑥1,...,𝑥𝑛)∈𝑍+𝑛∶0≤𝑥𝑘≤𝐵𝑘,∀1≤𝑘≤𝑛} be the set of all non-negative integer vectors not greater than 𝐁. A function 𝑓:[𝐁]→𝑅 is said to be weak-submodular if 𝑓(𝒙+𝛿𝟏𝑘)−𝑓(𝒙)≥𝑓(𝒚+𝛿𝟏𝑘)−𝑓(𝒚) for any 𝑘∈{1,…,𝑛}, any pair of 𝒙,𝒚∈[𝐁] such that 𝒙≤𝒚 and 𝑥𝑘=𝑦𝑘, and any 𝛿∈𝑍+ satisfying 𝒚+𝛿𝟏𝑘∈[𝐁]. Here 𝟏𝑘 is the vector with the 𝑘th component equal to 1 and each of the others equals to 0. In this paper we consider the problem of maximizing a non-monotone and non-negative weak-submodular function on the bounded integer lattice without any constraint. We present a randomized algorithm with an approximation guarantee 1/2 for the problem.
曹 雅
Quantum Composite Control for Nonorthogonal States against Decoherence
Abstract
Quantum feedback control (QFBC) and quantum feedforward control (QFFC) are two of the major techniques for protecting two nonorthogonal qubit states against decoherence. In this paper, we propose a quantum composite control scheme for protecting such states, where QFBC and QFFC are combined. Note that the combination is deliberately devised, other than simply one plus one (i.e., the trivial combination). We show the performance of our scheme is better than that of both the previous control schemes and the trivially combined one for most states and noises in the sense that, for given success probability, our scheme can achieve the biggest fidelity, and for given fidelity, our scheme has the biggest success probability. Furthermore, our scheme can be experimentally implemented with current technologies.
关于IJTCS
简介 → 国际理论计算机联合大会重磅登场
推荐 → 大会特邀报告（一）
推荐 → 大会特邀报告（二）
日程 → 分论坛：算法博弈论
日程 → 分论坛：区块链技术
日程 → 分论坛：多智能体强化学习
日程 → 分论坛：机器学习理论
日程 → 分论坛：量子计算
日程 → 分论坛：机器学习与形式化方法
日程 → 分论坛：算法与复杂性
推荐 → 本科生科研论坛
IJTCS注册信息
本次大会已经正式面向公众开放注册！每位参与者可以选择免费注册以观看线上报告，或是支付一定费用以进一步和讲者就报告内容进行交流，深度参与大会的更多环节。
观看线上报告：免费
完全注册：
（普通）$100 /￥700
（学生）$50 /￥350*
作为参会人参加全部会议，直接在线提问讨论并参与特设互动环节
注册截止：2020年8月15日23:59
点击 ↓↓↓二维码↓↓↓ 跳转注册页面：
*学生注册：网站上注册后需将学生证含有个人信息和学校信息的页拍照发送至IJTCS@pku.edu.cn，邮件主题格式为＂Student Registration + 姓名＂。
大会主席
John Hopcroft
中国科学院外籍院士、北京大学访问讲席教授
林惠民
中国科学院院士、中国科学院软件研究所专家
大会联合主席
邓小铁
北京大学教授
顾问委员会主席
高 文
中国工程院院士、北京大学教授
梅 宏
中国科学院院士、CCF理事长
张平文
中国科学院院士、CSIAM理事长、北京大学教授
组织单位
媒体合作
欢迎注册
大会网站：
https://econcs.pku.edu.cn/ijtcs2020/IJTCS2020.html
注册链接：
https://econcs.pku.edu.cn/ijtcs2020/Registration.htm
联系人
大会赞助、合作等信息，请联系：IJTCS@pku.edu.cn
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点“阅读原文”转免费注册页面