Heda Chen

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\).