-
11-24
2026
激励的代价：面向策略性参与者的在线线性规划
时 间：11:00-12:30, Nov 24, 2026 (Tue)地 点：RM 1-312, FIT Building内容：在线线性规划（online LP）是在线算法中的经典问题：共 T 轮，每轮到达若干请求，各自有价值和多维的资源消耗。算法必须立即决定服务哪个，并在长期资源约束下最大化总价值。经典的 primal-dual 方法把对偶变量当资源的“影子价格”，随消耗及时调整，在价值如实且已知时做到最优 regret。然而在 GPU 分配等场景中，请求的价值只有提交者自己知...
-
10-15
2026
Every layer counts: Worst-case depth hierarchy for shallow quantum circuits
时 间：14:30-16:30, Oct 15, 2026 (Thu)地 点：RM S527, MMW Building内容：Circuit depth is a fundamental proxy for computational time. As has long been studied in the classical field, a similar question central in quantum complexity is: Does each additional layer of gates really increase computational power? We answer this question in the affirmative within the quantum complexity class $\math...
-
10-09
2026
High-rate qLDPC processors
时 间：11:00-12:00, Oct 9, 2026 (Fri)地 点：RM S527, MMW Building or Venue: https://caltech.zoom.us/j/87834027070 (password: BB1984)内容：Despite significant progress on quantum low-density parity-check (qLDPC) codes, building qLDPC processors that are high-rate, high-throughput, hardware-friendly, and fast-to-decode remains a challenge. In this work, we introduce mitten codes, a family of ...
-
09-24
2026
Quantum Computing and Quantum Advantage
时 间：11:00-12:00, Sep 24, 2026 (Thu)地 点：RM 1-202, FIT Building内容：Quantum computers have the potential to solve problems that are intractable for classical computers. However, building a universal, fault-tolerant quantum computer remains a significant technological challenge. Before fully fledged quantum computers become available, a more immediate question is what can be achieved wi...
-
09-16
2026
Towards a Doubly Efficient IP = PSPACE
时 间：16:00-17:00, Sep 16, 2026 (Wed)地 点：RM 1-222, FIT Building内容：We show that every language in PSPACE that is decidable by a Turing machine in time T(n)=n^{O(log n)} admits a doubly efficient interactive proof system: the prover runs in time polynomial in T(n), and the verifier runs in time polynomial in n. This extends the best previously known regime for such proof systems from T...
-
09-16
2026
BitGC: Garbled Circuits with 1 Bit per Gate
时 间：10:00-11:00, Sep 14, 2026 (Mon)地 点：RM 1-222, FIT Building内容：This talk introduces BitGC, a computationally efficient construction for rate-one garbling based on Ring-LWE with key-dependent-message security. The garbling consists of an SWHE-encrypted seed and one bit of stitching information per gate. Its computation requires homomorphically expanding the seed using a low-depth P...