ITCS Workshop

This paper studies the online scheduling problem of minimizing the total flow time for $n$ jobs arriving online on $m$ identical machines. While the problem is well understood in the preemptive setting, prior work often asserts that preemption or resource augmentation is necessary, based on the $\Omega(n)$ lower bound shown by Kellerer, Tautenhahn, and Woeginger (SICOMP 1999) for deterministic non-preemptive algorithms in the single-machine case. However, this lower bound applies only to deterministic algorithms in the single-machine case and leaves several fundamental questions unanswered: What is the best deterministic competitive ratio when $m > 1$? Can randomness improve performance in the non-preemptive setting? We address both questions. We present a deterministic non-preemptive algorithm with a competitive ratio of $O(n/m^2 + \sqrt{n/m} \log m)$ and prove that this is nearly tight with a lower bound of $\Omega(n/m^2 + \sqrt{n/m})$. Additionally, we provide a randomized non-preemptive algorithm with a competitive ratio of $O(\sqrt{n/m})$ and prove its tightness, surpassing the $\Omega(n)$ bound in the $m = 1$ case. We also consider the intermediate model of kill-and-restart, where interrupted jobs must restart from scratch. For $m = 1$, we prove an $\Omega(n / \log n)$ lower bound. Interestingly, the situation changes drastically once $m \geq 2$: we develop a deterministic $O(\sqrt{n/m})$-competitive algorithm, which is tight even among randomized algorithms. Since our algorithms run in polynomial time, they improve the best-known offline approximation ratio from $O(\sqrt{n/m} \log(n/m))$ to $O(\sqrt{n/m})$.

Yuhao zhang is an Associate Professor of John Hopcroft Center for Computer Science at Shanghai Jiao Tong University since 2021, working in the field of theoretical computer science. He obtained his Ph.D. (2016~2020) from the Department of Computer Science at the University of Hong Kong, supervised by Dr. Zhiyi Huang. Before that, he got his B.E. from the College of Computer Science and Technology at Zhejiang University (2012~2016). During his undergraduate study, he started to be interested in theoretical computer science when he joined the research group of Prof. Guochuan Zhang. His research focuses on Online Algorithms and Approximation Algorithms. He is dedicated to designing algorithms with provable guarantees for real-world applications and advancing general mathematical frameworks for analyzing their performance.

The rapid advancements in machine learning have been driven by increasingly large datasets and growing computational power. Developing optimization algorithms that scale effectively with data size and the number of computing machines is critical but fraught with challenges, including computational bottlenecks and communication overhead. Additionally, large-scale stochastic optimization processes are inherently vulnerable to adversaries, such as corrupted training samples or compromised machines, which can significantly degrade model performance without robust safeguards. In this talk, I will delve into the dual challenges of efficiency and robustness in large-scale machine learning problems and present our recent work in addressing these issues, including novel approaches to scalable and resilient optimization.

​​Lie He​​ is an Assistant Professor in the School of Computing and Artificial Intelligence at Shanghai University of Finance and Economics (SUFE). He received his bachelor's degree from the University of Science and Technology of China (USTC), as well as an master's and doctoral degree in Computer Science from the École Polytechnique Fédérale de Lausanne (EPFL), Switzerland, advised by Prof. Martin Jaggi. His research centers on ​​efficient large-scale stochastic optimization​​ with ​​robustness guarantees against training-time adversaries​​ and uncertainty quantifications.

The existence of outliers presents formidable challenges for many machine learning problems, including clustering, subspace embedding, and low-rank approximation. In this work, we consider robust coresets for all the above machine learning problems, which reduce the input dataset into a small subset, thus providing a scalable and robust solution. We design a general framework to construct a robust coreset for any machine learning problem that admits a bounded total sensitivity and vanilla coreset. Our coreset is near-optimal for subspace embedding. Our experimental results show that our coresets outperform the uniform sampling benchmark on real-world data sets. This is a joint work with Chansophea Wathanak In, Yi Li, and David Woodruff.

Xuan Wu is a research fellow in Nanyang Technological University, working with Yi Li. He earns his Ph.D from Johns Hopkins Universitiy, adviced by Vladimir Braverman. Before working in NTU, he has worked as a full time researcher in Huawei, headed by Pinyan Lu. Xuan Wu's research focuses on sparsification for machine learning problem, in particular coresets for clustering.

We propose the first local search algorithm for Euclidean clustering that attains an $O(1)$-approximation in almost-linear time. Specifically, for Euclidean k-Means, our algorithm achieves an $O(c)$-approximation in $\tilde{O}(n^{1 + 1 / c})$ time, for any constant $c \ge 1$, maintaining the same running time as the previous (non-local-search-based) approach [la~Tour and Saulpic, arXiv'2407.11217] while improving the approximation factor from $O(c^{6})$ to $O(c)$. The algorithm generalizes to any metric space with sparse spanners, delivering efficient constant approximation in $\ell_p$ metrics, doubling metrics, Jaccard metrics, etc. This generality derives from our main technical contribution: a local search algorithm on general graphs that obtains an $O(1)$-approximation in almost-linear time. We establish this through a new $1$-swap local search framework featuring a novel swap selection rule. At a high level, this rule ``scores'' every possible swap, based on both its modification to the clustering and its improvement to the clustering objective, and then selects those high-scoring swaps. To implement this, we design a new data structure for maintaining approximate nearest neighbors with amortized guarantees tailored to our framework.

姜少峰博士现任北京大学前沿计算研究中心助理教授，北京大学博雅青年学者。他博士毕业于香港大学，并先后在以色列魏茨曼科学院和芬兰阿尔托大学担任博士后研究员及助理教授。他的研究领域是理论计算机科学，侧重于组合优化问题的大数据算法、近似算法和在线算法。他的多篇研究发表于SICOMP、TALG、STOC、FOCS、SODA等理论计算机科学方向的顶级期刊与会议上。

We give a deterministic $O(m\log^{2/3}n)$-time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition model. This is the first result to break the $O(m+n\log n)$ time bound of Dijkstra's algorithm on sparse graphs, showing that Dijkstra's algorithm is not optimal for SSSP.

Ran Duan received his B.S. degree in Computer Science at Tsinghua University in 2006, and his M.S. and Ph.D. degrees in Theoretical Computer Science at University of Michigan, Ann Arbor (under the instruction of Prof. Seth Pettie). Then he held a postdoctoral researcher position in Max-Planck-Institut für Informatik in Germany until 2014, supported by Alexander von Humboldt fellowship. In Aug 2014, he becomes a faculty member in IIIS. His research interest focuses on graph algorithms, data structures, and computational theory.

The CFI-graphs, named after Cai, Fuerer, and Immerman, are central to the study of the graph isomorphism testing and of first-order logic with counting. They are often colored graphs, and the coloring plays a key role in many of their applications. As usual, it is not hard to remove the coloring by some extra graph gadgets, but at the cost of blowing up the size of the graphs and changing some key parameters of the graphs as well. This might lead to suboptimal combinatorial bounds important to their applications. In this talk, I will give a detailed account of the CFI-graphs, both colored and uncolored, and show they serve the same purposes for most applications. This is joint work with Joerg Flum and Mingjun Liu.

陈翌佳目前是上海交通大学计算机系教授。他在上海交通大学获得软件与理论专业博士、德国弗莱堡大学数学博士。他的主要研究兴趣为计算机与数学的交叉领域，包括逻辑、算法与计算复杂性。

Linear scalarization, i.e., combining all loss functions by a weighted sum, has been the default choice in the literature of multi-task learning (MTL) since its inception. In recent years, there has been a surge of interest in developing Specialized Multi-Task Optimizers (SMTOs) that treat MTL as a multi-objective optimization problem. However, it remains open whether there is a fundamental advantage of SMTOs over scalarization. In this talk, I will revisit scalarization from a theoretical perspective. I will be focusing on linear MTL models and studying whether scalarization is capable of fully exploring the Pareto front. Our findings reveal that, in contrast to recent works that claimed empirical advantages of scalarization, when the model is under-parametrized, scalarization is inherently incapable of full exploration, especially for those Pareto optimal solutions that strike the balanced trade-offs between multiple tasks. I will conclude the talk by briefly discussing the extension of our results to general nonlinear neural networks and our recent work on using online Chebyshev scalarization to controllably steer the search of Pareto optimal solutions.

Dr. Han Zhao is an Assistant Professor of Computer Science at the University of Illinois Urbana-Champaign (UIUC). He is also an Amazon Scholar at Amazon AI. Dr. Zhao earned his Ph.D. degree in machine learning from Carnegie Mellon University. His research interest is centered around trustworthy machine learning, with a focus on algorithmic fairness, robust generalization and model interpretability. He has been named a Kavli Fellow of the National Academy of Sciences and has been selected for the AAAI New Faculty Highlights program. His research has been recognized through a Google Research Scholar Award, an Amazon Research Award, and a Meta Research Award.

Quantum computing is progressing rapidly from theoretical exploration to practical realization. From a cryptographic perspective, the dark side of this "quantum moon" poses potentially catastrophic challenges to classical security assumptions. A straightforward response to quantum threats is to replace classical hardness assumptions with quantum-resistant alternatives. While this approach is sufficient for simple primitives such as standard commitments and encryption schemes, it falls short in more advanced cryptographic tasks—particularly those whose security is defined via simulation. Notable examples include zero-knowledge proofs and secure multi-party computation. This talk will explore the foundational challenges in achieving simulation-based security against quantum adversaries. The goal is to provide a clear and insightful overview of this rapidly evolving area, presenting recent technical advances, as well as major open problems that define the current research frontier.

Xiao Liang's is an Assistant Professor at the Chinese University of Hong Kong. His research interests lie in Cryptography and its intersections with related fields such as Quantum Computing, Computational Complexity Theory, and Computer Security. His work has concentrated on theoretical fundamentals, including Zero-Knowledge Protocols, Secure Multi-Party Computation, Non-Malleability, and Digital Signatures, as well as their practical applications. His research has been published at respected conferences (e.g., FOCS, CRYPTO, and ICALP). Prior to his appointment at CUHK, Xiao Liang served as a postdoctoral fellow at NTT Research, Rice University, and Indiana University Bloomington. He holds a Ph.D. in Computer Science and an M.Sc. in Applied Mathematics from Stony Brook University, and a Bachelor of Economics from Beijing Institute of Technology.

We study the $\textit{average-case deterministic query complexity}$ of boolean functions under a uniform input distribution, denoted by $\avgq(f)$, the minimum average depth of zero-error decision trees that compute a boolean function $f$. This measure has found several applications across diverse fields, yet its understanding is limited. We study boolean functions with fixed weight, where weight is defined as the number of inputs on which the output is $1$. We prove \(\avgq(f) \le \max \{ \log \frac{\wt(f)}{\log n} + O(\log \log \frac{\wt(f)}{\log n}), O(1) \}\) for every $n$-variable boolean function $f$, where $\wt(f)$ denotes the weight. For any $4\log n \le m(n) \le 2^{n-1}$, we prove the upper bound is tight up to an additive logarithmic term for almost all $n$-variable boolean functions with fixed weight $\wt(f) = m(n)$. H{\aa}stad's switching lemma or Rossman's switching lemma [Comput. Complexity Conf. 137, 2019] implies $\avgq(f) \leq n(1 - \frac{1}{O(w)})$ or $\avgq(f) \le n(1 - \frac{1}{O(\log s)})$ for CNF/DNF formulas of width $w$ or size $s$, respectively. We show there exists a DNF formula of width $w$ and size $\lceil 2^w / w \rceil$ such that $\avgq(f) = n (1 - \frac{\log n}{\Theta(w)})$ for any $w \ge 2\log n$.

Yuan Li is an assistant professor at Fudan University. Prior to this, he was a software engineer at Google from 2017 to 2021. He received his BSc in Computer Science from Fudan University in 2011 and his PhD in Computer Science from the University of Chicago in 2017. His research interests include computational complexity and coding theory. He has published papers in conferences and journals such as IEEE Transactions on Information Theory, COCOON, FOCS, SIAM Journal on Computing, Information and Computation, Theoretical Computer Science, and DCC (Designs, Codes and Cryptography).

The sparse LPN problem is closely related to the classical problem of refuting random $k$-CSP and has been widely used in cryptography as the hardness assumption. Different from the standard LPN that samples random vectors in $\mathbf{F}_2^n$, it samples random $k$-sparse vectors. Because the number of $k$-sparse vectors is ${n \choose k}＜n^k$, sparse LPN has learning algorithms in polynomial time when $m>n^{k/2}$. However, much less is known about learning algorithms for a constant $k$ like 3 and $m＜n^{k/2}$ samples, except the Gaussian elimination algorithm and sum-of-squares algorithms. We provide a learning algorithm in $e^{\tilde{O}(\eta \cdot n^{\frac{\delta+1}{2}})}$ time given $\delta \in (0,1)$ and $m=\max\{1,\frac{\eta \cdot n^{\frac{\delta+1}{2}}}{k^2}\} \cdot n^{1+(1-\delta)\cdot \frac{k-1}{2}}$ samples. This improves previous learning algorithms in a wide range of parameters. For example, in the classical setting of $k=3$ and $m=n^{1.4}$ \citep{FKO06,ABW10}, our algorithm would be faster than previous approaches for any $\eta＜n^{-0.7}$. Joint work with Wenxuan Shu (USTC) and Zhaienhe Zhou (USTC).

Xue is a faculty member in USTC. He is broadly interested in theoretical computer science. Specific areas include big data algorithms, learning theory and foundations of machine learning, complexity theory, randomized algorithms and pseudorandomness. Previously, I was a postdoc in the theory group of Northwestern University (in USA) and an assistant professor in George Mason University (in USA). Prior to that, I obtained my PhD in the University of Texas at Austin, under the supervision of David Zuckerman, and my bachelor degree from the Yao class of Tsinghua University.

We revisit the classical problem of designing Budget-Feasible Mechanisms (BFMs) for submodular valuation functions, which has been extensively studied since the seminal paper of Singer [FOCS'10] due to their wide applications in crowdsourcing and social marketing. We propose 𝖳𝗋𝗂𝗉𝗅𝖾𝖤𝖺𝗀𝗅𝖾, a novel algorithmic framework for designing BFMs, based on which we present several simple yet effective BFMs that achieve better approximation ratios than the state-of-the-art work. Moreover, our BFMs are the first in the literature to achieve linear query complexity under the value oracle model while ensuring obvious strategyproofness, making them more practical than the previous BFMs. We conduct extensive experiments to evaluate the empirical performance of our BFMs, and the experimental results demonstrate the superiorities of our approach in terms of efficiency and effectiveness compared to the state-of-the-art BFMs.

Kai Han is currently a professor at the School of Computing and Artificial Intelligence, Shanghai University of Finance and Economics (SUFE). Before joining SUFE, he served as a Distinguished Professor at the School of Computer Science and Technology, Soochow University, and as a professor at the School of Computer Science and Technology, University of Science and Technology of China. His research interests include machine learning, big data processing, algorithmic game theory, and social computing.

We introduce and study the persuasive calibration problem, where a principal aims to provide trustworthy predictions about underlying events to a downstream agent to make desired decisions. We adopt the standard calibration framework that regulates predictions to be unbiased conditional on their own value, and thus, they can reliably be interpreted at the face value by the agent. Allowing a small calibration error budget, we aim to answer the following question: what is and how to compute the optimal predictor under this calibration error budget, especially when there exists incentive misalignment between the principal and the agent? We focus on standard $\ell_t$-norm Expected Calibration Error (ECE) metric. We develop a general framework by viewing predictors as post-processed versions of perfectly calibrated predictors. Using this framework, we first characterize the structure of the optimal predictor. Specifically, when the principal's utility is event-independent and for $\ell_1$-norm ECE, we show: (1) the optimal predictor is over-(resp. under-) confident for high (resp. low) true expected outcomes, while remaining perfectly calibrated in the middle; (2) the miscalibrated predictions exhibit a collinearity structure with the principal's utility function. On the algorithmic side, we provide a FPTAS for computing approximately optimal predictor for general principal utility and general $\ell_t$-norm ECE. Moreover, for the $\ell_1$ and $\ell_\infty$-norm ECE, we provide polynomial-time algorithms that compute the exact optimal predictor.

Yiding Feng is an assistant professor at HKUST IEDA. Previously, he worked as a principal researcher at the University of Chicago Booth School of Business, and a postdoctoral researcher at Microsoft Research New England. He received his Ph.D. from the Department of Computer Science at Northwestern University in 2021, and his BS degree from ACM Honors Class at Shanghai Jiao Tong University in 2016. His research focuses on operations research, economics & computation, and theoretical computer science. He was the recipient of the INFORMS Auctions and Market Design (AMD) Michael H. Rothkopf Junior Researcher Paper Prize (second place), and the APORS Young Researcher Best Paper Award.

Multi-player multi-armed bandit (MP-MAB) has been widely studied owing to its diverse applications across numerous domains. We consider an MP-MAB problem where $N$ players compete for $K$ arms in $T$ rounds. The reward distributions are heterogeneous where each player has a different expected reward for the same arm. When multiple players select the same arm, they collide and obtain zero rewards. In this paper, our target is to find the max-min fairness matching that maximizes the reward of the player who receives the lowest reward. This paper improves the existing max-min regret upper bound of $O(\exp(1/\Delta) + K^3 \log T\log \log T)$. More specifically, our decentralized fair elimination algorithm (DFE) deals with heterogeneity and collision carefully and attains a regret upper bound of $O((N^2+K)\log T / \Delta)$, where $\Delta$ is the minimum reward gap between max-min value and sub-optimal arms. In addition, this paper also provides an $\Omega(\max\{N^2, K\} \log T / \Delta)$ regret lower bound for this problem, which indicates that our algorithm is optimal with respect to key parameters $T, N, K$, and $\Delta$. Additional numerical experiments also show the efficiency and improvement of our algorithms. This work is accepted in ICML 2025.

李帅副教授研究可自主决策适应动态环境的强化学习理论与方法，任上海交通大学约翰·霍普克罗夫特计算机科学中心副主任，迄今共发表学术论文90+篇，包含上海交通大学首篇机器学习理论顶会COLT论文等，其中第一/通讯作者发表CCF-A类论文40+篇，10余项理论提升成果仍保持理论最优。她担任机器学习顶会ICML、NeurIPS、UAI、ACL、IJCAI、AAMAS的领域主席（Area Chair）与高级程序委员会委员（SPC），受邀于群体智能顶级会议AAMAS上给出多智能体在线学习与马尔可夫博弈理论基础的教程（连续两年）和IJCAI上给出多智能体在线学习的教程，主持国自然面上基金、青年基金，参与国自然重大研究计划、科技部2030新一代人工智能重大项目。她曾获得AAAI-IAAI Deployed Application Award、上海市扬帆人才计划、上海徐汇光启人才、谷歌博士奖学金、香港政府外展合作奖、华为火花奖、国际SAT竞赛并行求解赛道铜牌、腾讯优秀导师奖等。

We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetilde{\Theta}(T^{2/3})$ tight bound for Global Budget Balance fixed-price mechanisms with two-bit/one-bit feedback. (ii) For correlated/adversarial values, a near-optimal $\Omega(T^{3/4})$ lower bound for Global Budget Balance fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known $\Omega(T^{5/7})$ lower bound obtained in the work BCCF24 and, up to polylogarithmic factors, matches the $\widetilde{\mathcal{O}}(T^{3 / 4})$ upper bound obtained in the same work. Our work in combination with the previous works CCCFL24mor, CCCFL24jmlr, AFF24, BCCF24 (essentially) gives a thorough understanding of regret minimization for fixed-price bilateral trade. En route, we have developed two technical ingredients that might be of independent interest: (i) A novel algorithmic paradigm, called fractal elimination, to address one-bit feedback and independent values. (ii) A new lower-bound construction with novel proof techniques, to address the Global Budget Balance constraint and correlated values.

Yaonan Jin is a full-time researcher at the Huawei TCS Lab (lead by Pinyan Lu). His research interests encompass Theoretical Computer Science, with an emphasis on Algorithmic Economics. Before joining Huawei, he obtained his PhD from Columbia University in 2023 (advised by Xi Chen and Rocco Servedio). Before that, he obtained his MPhil from Hong Kong University of Science and Technology in 2019 (advised by Qi Qi) and his BEng from Shanghai Jiao Tong University in 2017.