No. 46 · Monday 16 November 2026 · 75 papers
For every fixed \(d \ge 2\), explicit depth-\(d\) formulas need superpolynomial-size semantic depth-\(d\) \(AC^0[2]\)-Frege refutations. Semantic depth-3 and depth-4 polynomial calculus over \(\mathbb{F}_2\) also receive exponential and superpolynomial lower bounds, which settles the Res(log) question for the weak pigeonhole principle.
Read · PDF · covering 9–15 November 2026
No. 45 · Monday 9 November 2026 · 132 papers
For every fixed \(k\) there is an \(\varepsilon_k > 0\) such that \(k\)-hypercliques in an \(n\)-vertex \((k-1)\)-uniform hypergraph can be counted in \(O(n^{k-\varepsilon_k})\) time, unconditionally; as corollaries, Max-\(k\)SAT runs in \(2^{(1-\varepsilon)n}\cdot\mathrm{poly}(m,n)\) time and length-\(k\) arithmetic progressions are detected in \(n^{2-\varepsilon}\) time, with \(\varepsilon\) depending on \(k\).
Read · PDF · covering 2–8 November 2026
No. 44 · Monday 2 November 2026 · 85 papers
Two analyses of the claimed October 2026 refutations of ETH find that the subexponential #3-SAT bounds certify no speed-up over brute force for any bounded-density input that could ever be written down, cut one algorithm's crossover point to about \(2^{420}\) clauses at clause density one, and observe that the Sparse Max-3-SAT Hypothesis falls too; a third paper, an AI-assisted exposition, explains how the counting procedure works.
Read · PDF · covering 26 October – 1 November 2026
No. 43 · Monday 26 October 2026 · 61 papers
Mishra and Santhanam prove that every Boolean circuit over the full binary basis \(B_2\) computing a certain explicit function in \(\mathrm{P}\) needs at least \(4n-O(\log n)\) gates, up from the \(3.5n-o(n)\) in the paper's own earlier version.
Read · PDF · covering 19–25 October 2026