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$$.

The purpose of this post is only to sketch the proof (and its novel idea) in an easy-to-understand way. For more details, please refer to the original paper.

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

## Prologue

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

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