- Introduction
- Starting the blog
- Boolean circuits as a model of computation
- The sunflower lemma and \(\Gamma\)-condition
- Room for improvement
- The extension generator theorem (EGT)
- Overview of Paper 1 Ver. 1
- Paper 1 posted on the left tries to prove the sunflower conjecture, however containing a major logic flaw. I’m now working on fixing it hoping to upload its second version soon as there seems to be a way. Paper 2 Ver. 2 proves the k-disjoint-set claim also discussing its background, as covered by Chap 3 and 4 below.
- The split lemma. The main idea. Construction algorithms: (1), (2), (3).
- The two recursive statements: (1), (2), (3) . Step 1 of proving (2.1). An error in Step 1
- Restarting with an error overview. Step 2 of proving (2.1)
- On the combinatorial domain \(2^X\) (Part 1)
- Sparsity of a family
- Proof of the EGT
- Collective \( \Gamma \)-conditions
- Partitioning sets and families
- Three disjoint sets in \({\mathcal F} \) satisfying \( \Gamma( m^{\frac{1}{2}+\epsilon} ) \)
- The push-up lemma
- Main recursive steps
- Generalization to \( k \) sets
- Conclusions and upcoming topics
- On the combinatorial domain \(2^X\) (Part 2)
- EGT and circuit complexity
- Circuit complexity and the P vs NP problem
- Random vertex coloring: the standard method for monotone complexity
- Application of EGT to circuit complexity: overview of Paper 4
- Limit of extension generators
- The Hamming distance between two uniform families
Links for mobile devices