# TCS Youth Forum TCS Youth Forum 将于2019年10月16日在中科院计算所举办，本次论坛有幸邀请到来自清华大学的金策、武弘勋同学，北京大学的吴克文同学和中科院计算所的蒋佳卿、张智杰同学，分享他们分别在 FOCS、SODA 和 ICALP 等会议上发表的研究成果并交流科研经验和心得。本次论坛将于10月16日上午 9:00 在中科院计算所 4 层 446 会议室举行，非常欢迎感兴趣的老师和同学前来参加。 • 时间：9:00 - 9:40

• 报告题目：Decision List Compression by Mild Randomrestrictions

• 报告人：吴克文，北京大学

• 摘要：A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision lists generalize both CNFs and DNFs, and have been studied both in complexity theory and in learning theory.

The size of a decision list is the number of rules, and its width is the maximal number of variables in a term. We prove that decision lists of small width can always be approximated by decision lists of small size, where we obtain sharp bounds (up to constants). This in particular resolves a conjecture of Gopalan, Meka and Reingold (Computational Complexity, 2013) on DNF sparsification.
An ingredient in our proof is a new random restriction lemma, which allows to analyze how DNFs (and more generally, decision lists) simplify if a small fraction of the variables are fixed. This is in contrast to the more commonly used switching lemma, which requires most of the

variables to be fixed.

• 个人简介：Kewen Wu is an undergraduate in Peking University. He majors in CS, doubles in Math, and is expected to graduate in 2020. He has broad interests in theoretical computer science. • 时间：9:40 - 10:20

• 报告题目：Faster Algorithms for All Pairs Non-decreasing Paths Problem

• 报告人：武弘勋，清华大学

• 摘要：In all pairs non-deceasing path (APNP) problem, one asks for the nondecreasing path between each pair of vertices which minimize the weight of its last edge. The current best upper bound for APNP on weighted digraphs was \tilde{O}(n^{\frac{1}{2}(3+\frac{3-\omega}{\omega +1}+\omega)}) = \tilde{O}(n^2.78) [Duan, Gu, Zhang 2018] where \omega <2.373 is the exponent of time complexity of matrix multiplication [Williams 2012, Le Gall 2014]. We improved it to \tilde{O}(n^{\frac{3+ \omega}{2}}) = \tilde{O}(n^2.686). It matches the current best upper bound of (min, \leq) matrix product [Duan, Pettie 2009] which is a special case of APNP.

• 个人简介：Hongxun Wu is an undergraduate student at Yao class, Tsinghua University. He is broadly interested in theoretical computer science. • 时间：10:20 - 11:00

• 报告题目：Hardness Magnification for all Sparse NP Languages

• 报告人：金策，清华大学

• 摘要：In the Minimum Circuit Size Problem (MCSP[s(m)]), we ask if there is a circuit of size s(m) computing a given truth-table of length n = 2^m. Recently, a surprising phenomenon termed as hardness magnification by [Oliveira and Santhanam, FOCS 2018] was discovered for MCSP[s(m)] and the related problem MKtP of computing time-bounded Kolmogorov complexity. In [Oliveira and Santhanam, FOCS 2018], [Oliveira, Pich, and Santhanam, CCC 2019], and [McKay, Murray, and Williams, STOC 2019], it was shown that minor (n^{1+eps}-style) lower bounds for MCSP[2^o(m)] or MKtP[2^o(m)] would imply breakthrough circuit lower bounds such as NP is not in P/poly, NP is not in NC^1, or EXP is not in P/poly.

We consider the question: What is so special about MCSP and MKtP? Why do they admit this striking phenomenon? One simple property is that all variants of MCSP (and MKtP) considered in prior work are sparse languages. For example, MCSP[s(m)] has 2^{O(s(m))} yes-instances of length n=2^m, so MCSP[2^o(m)] is 2^{n^o(1)}-sparse.

We show that there is a hardness magnification phenomenon for all equally-sparse NP languages. Formally, suppose there is an eps > 0 and a language L in NP which is 2^{n^o(1)}-sparse, and L is not in Circuit[n^{1+eps}]. Then NP does not have n^k-size circuits for all k. We prove analogous theorems for De Morgan formulas, B_2-formulas, branching programs, AC^0 and TC^0 circuits, and more: improving the state of the art in NP lower bounds against any of these models by an eps factor in the exponent would already imply NP lower bounds for all fixed polynomials. In fact, in our proofs it is not necessary to prove a (say) n^{1+eps} circuit size lower bound for L: one only has to prove a lower bound against n^{1+eps}-time n^eps-space deterministic algorithms with n^eps advice bits. Such lower bounds are well-known for non-sparse problems.

• 个人简介Ce Jin is a final-year undergraduate in Yao Class, Tsinghua University. He is interested in algorithm design and computational complexity. • 时间：11:10 - 11:50

• 报告题目：Cake Cutting on Graphs: A Discrete and Bounded Proportional Protocol

• 报告人：张智杰，中科院计算所

• 摘要：The classical cake cutting problem studies how to find fair allocations of a heterogeneous and divisible resource among multiple agents. Two of the most commonly studied fairness concepts in cake cutting are proportionality and envy-freeness. It is well known that a proportional allocation among 𝑛 agents can be found efficiently via simple protocols. For envy-freeness, in a recent breakthrough, Aziz and Mackenzie proposed a discrete and bounded envy-free protocol for any number of players. However, the protocol suffers from high multiple-exponential query complexity and it remains open to find simpler and more efficient envy-free protocols. In this paper we consider a variation of the cake cutting problem by assuming an underlying graph over the agents whose edges describe their acquaintance relationships, and agents evaluate their share relatively to those of their neighbors. An allocation is called locally proportional if each agent thinks she receives at least the average value over her neighbors. Local proportionality generalizes proportionality and is in an interesting middle ground between proportionality and envy-freeness: its existence is guaranteed by that of an envy-free allocation, but no simple protocol is known to produce such a locally proportional allocation for general graphs. Previous works showed locally proportional protocols for special classes of graphs, and it is listed in previous papers as an open question to design simple locally proportional protocols for more general classes of graphs. In this paper we completely resolved this open question by presenting a discrete and bounded locally proportional protocol for any given graph. Our protocol has a query complexity of only single exponential, which is significantly smaller than the six towers of 𝑛 query complexity of the envy-free protocol given by Aziz and Mackenzie.

• 个人简介：Zhijie Zhang is currently a third-year graduate student at Institute of Computing Technology, CAS, under supervision of Xiaoming Sun. Previously, he was an undergraduate student at Nankai University. He has broad interest in combinatorial optimization and algorithms. His recent focus includes submodular function maximization and fair allocations. • 时间：11:50 - 12:30

• 报告题目：Optimal Space-Depth Trade-Off of CNOT Circuits in Quantum Logic Synthesis

• 报告人：蒋佳卿，中科院计算所

• 摘要：Due to the decoherence of the state-of-the-art physical implementations of quantum computers, it is essential to parallelize the quantum circuits to reduce their depth. Two decades ago, Moore and Nilsson demonstrated that additional qubits (or ancillae) could be used to design "shallow" parallel circuits for quantum operators. They proved that any n-qubit CNOT circuit could be parallelized to O(log n) depth, with O(n^2) ancillae. However, the nearterm quantum technologies can only support limited amount of qubits, making space-depth trade-off a fundamental research subject for quantum-circuit synthesis. In this work, we establish an asymptotically optimal space-depth tradeoff for the design of CNOT circuits. We prove that for any m ≥ 0, any n-qubit CNOT circuit can be parallelized to O(max{log n, n^2*log(n+m)/(n+m)}) depth, with m ancillae. This bound is tight by a counting argument.

• 个人简介：Jiaqing Jiang received her B.S degree in mathematical science from Nankai University, China, in 2017. The same year she joined Institute of Computing Technology, Chinese Academy of Sciences as a Master student. Her research interests include quantum circuit synthesis and quantum algorithms. Under the guidance of Prof. Xiaoming Sun, Prof. Jialin Zhang and Prof. Guojing Tian, she has published several papers in ACM-SIAM Symposium on Discrete Algorithms, Physical Review A and IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.  