Marcythm

　　在维璟印象城东南门通往 B1 层的下行扶梯上，抬头可见詹记的广告牌。“我念叨詹记的泡芙好久了，该有几年了”，我说，“那就去看看吧。正好走的时候买一盒，看电影的时候吃。”
　　推开 B1 层的大门，环视一圈，詹记的牌子就在视野正中。走上前去，映入眼帘的是一家稍显局促的店面，一应盒装糕点挤在店面外边缘的弧形长柜台上。钻入一排驻足的游客，我的手随着视线在空中游移，最后锁定在一个熟悉的盒子上：标价 ¥18，共 12 个。我伸出手去，嘴里或许念叨着什么，脸上的表情或许是笑容——我已记不清了。
　　一阵莫名涌现的情感袭击了我，眼泪几乎要涌出来。在那盒泡芙上空大约五厘米，许是有一堵透明的墙，让我的手不得寸进。电光石火间我意识到：我所一直惦念的詹记泡芙，或许只是隐约地寄托了某种情感，而我渴望再次接触它所代表的美好。不会有什么牌子的泡芙，能好吃到让我在三年间一有相关见闻就想起它。这世界上也不会再有一盒产于 2021 年 10 月 24 日的詹记泡芙，在一家虽小但并不局促的店面里遇见我，陪我历过古北路上沿途的晚风、路灯和行人，承载一段感情最后回光返照的余晖。
　　那一瞬间我的表情和肢体大概都几近失控。回过神来的时候，那盒被我念叨了三年的詹记泡芙已经被抛在背后。“等吃完饭再来买吧”，我说。大概不会再来了，我想。原来是怀念，而非惦念。怀念的宾语从来只属于过去，而不属于如今仍在的那些人或物。亲手接触一件陈列在回忆殿堂里的艺术品，实在容易让本就是被粘连修补而成的它变成一地碎渣。是以一顶用于保护的玻璃罩子由我亲手加上，半径五厘米。

记于 2024 年 4 月 12 日凌晨。

In this post, we briefly give an overview of the famous “natural proof barrier” [RR94], which explained why it's extremely hard to obtain a circuit lower bound towards the P vs. NP problem.

Introduction

The celebrated natural proof theorem, stated by Razborov and Rudich in [RR94], gives the fundamental limitation of the common proof technique that has the following form:

1. all circuits of size \(s\) do not satisfy some certain property \(\mathcal{P}\) (which is “not simple”, i.e., having a size lower bound \(s\)),
2. the target function \(f\) satisfies the property \(\mathcal{P}\),
3. so \(f\) has the size lower bound \(s\).

In this post, we briefly explain the main idea of [CDKP23], which uses a novel spectral method named "subspace enumeration" to solve the extensively studied task of approximately counting the number of independent sets on a given bipartite graph \(G\).

Today I listened to the excellent talk Tight Space Complexity of the Coin Problem, and some brief notes are recorded here.

Introduction to the Coin Problem

In the talk we will focus on streaming space complexity required to distinguish a bias of \(\delta\) w.p. 2/3 on \(n\) coin tosses. For example, \(O(\log k)\) space can distinguish \(\delta = \Omega(1/k)\) by maintaining a counter with threshold \(k\). This algorithm is optimal within \(O(\log k)\) space if time-invariant, i.e., don't have access to a clock.

The Coin Problem is statistically solvable when \(\delta = \Omega(n^{-0.5})\) by counting, which is optimal for \(\delta = O(n^{-0.5})\) (equivalently, \(\operatorname{poly}(n)\) width is necessary [BGW20]).

今天把博客又修了一遍，终于公式环境什么的也正常了，博客部署也只需要几个文本文件，干净多了。希望从今天起恢复更新，作为个人学术向记录博客。

non-deduced context

Definition

为了方便理解，此处仅讨论如下形式的函数模板: template <typename T> void foo(P t) （此处 P 为可能包含 T 的类型表达式） 即仅有一个模板参数且为类型参数的单参数函数。

在我们进行模板参数推导的时候，我们实质上是在做一个类似解方程的过程。对于一个函数调用 foo(a), 它给出了一个类型间的相等关系，即 a 的类型（设为 U）与 P 相同: U = P。要推导出模板参数的类型，就需要对这一方程进行求解。当这一方程可以被解出时，它就被称为一个 deducible context；当这一方程无法被解出时，它就是一个 non-deduced context。用一个例子来说明:

1
2
3
4
5
6
7
8
9
10

template <typename T>
void foo(std::vector<T> a) { }

template <typename T>
T bar(std::type_identity_t<T> b) { return b; }

int main() {
  foo(std::vector<int>{1});
  // bar(1); // error: couldn't infer template argument 'T'
}

在这个例子中，对 foo(std::vector<int>{1}) 进行模板参数推导的时候，我们可以得到方程 std::vector<T> = std::vector<int> (a = {1})，由此解出 T = int 完成推导，这是一个 deducible context；对 bar(1) 进行模板参数推导的时候，我们可以得到方程 std::type_identity<T>::type = int (b = 1)，这是一个无法求解的方程（因为 type_identity 可能有无穷多种特化满足这一方程，无法一一枚举求解），于是会产生编译错误，所以这是一个 non-deduced context。（事实上，在所有的 non-deduced context 中，最常见的一种就是模板参数 T 出现在 :: 的左边。这种方程无法求解的原因可参见上文。）

22.4.18

首先是在研究 split 相关的编译错误时得到的结论: 在变长参数包非尾置参数的时候, 无法显式指定变长参数包之后的参数（而只能依靠 deduction）, 因为编译器无法判断变长参数包到哪里截止。因此测试中应将 split<1, 2, 3, _Tp, _Abi>(data) 修改为 split<1, 2, 3>(data)。（也就是说这并不是一个问题, 而是 by design 如此）

其次是, 对于这样的两个 split 函数（一个是 split into tuple, 一个是 split into array）

1
2
3
4
5
6
7
8
9
10
11
12

// template<size_t... Sizes, class T, class Type>
template<class T, class Type, size_t... Sizes>
  std::enable_if_t<
    ((0 + ... + Sizes) == simd_size_v<T, Type>),
    std::tuple<simd<T, fixed_size<Sizes>>...>
  > split(const simd<T, Type>&) noexcept;

template<class V, class Type>
  std::enable_if_t<
    (simd_size_v<typename V::value_type, Type> % V::size() == 0),
    std::array<V, simd_size_v<typename V::value_type, Type> / V::size()>
  > split(const simd<typename V::value_type, Type>&) noexcept;

Prologue

今天看了 Cornell CS3410 的 Calling Conventions，大概花了两个多小时，但实际上并没有学到很多，更多地是 clarify 了一些以前了解过一点的知识以及一些细节。slide 大概分了三点：Transfer Control, Pass Arguments to/from the Routine, Manage Registers.（slide 上说 there is no one true RISC-V calling convention, 但找到了一个 RV psABI 的文档，不知道咋回事） 先上个总结图（from RV Manual: RISC-V Assembly Programmer’s Handbook）

今天终于下定决心重修了博客。

1. 从之前首页放 log 的模式改为专开一栏放 log，因为之后计划将学习知识后的总结 blog 放在首页（希望能写出来）。
2. 本学期之前的 log 由于某些众所周知的原因全部封存。（当然稍微有点脑洞的话都可以从 url 扒出来就是了）(虽然粗看了一遍感觉其实没什么但还是先封两个月再说)

A Simple Lead-in

1
2
3
4
5
6
7

T *p = /* loop invariant address */
for (init; cond; inc) {
  a = /* loop invariant */;
  c = a + d;
  *p = x;
  outlive = /* loop invariant */;
}

1
2
3
4
5
6
7
8

a = /* loop invariant */; // hoist
T t = *p;
for (init; cond; inc) {
  c = a + d;
  t = x;
}
outlive = /* loop invariant */; // sink
*p = t; // promote memory accesses to scalars

Loop

Dominators

Node \(a\) dominates node \(b\) \((a \operatorname{dom} b)\) in a graph if every path from the entry node to \(b\) goes through \(a\).