论文标题
关于深度3电路和覆盖号码：明确的反例
On depth-3 circuits and covering number: an explicit counter-example
论文作者
论文摘要
我们提供了一个简单的构造$ n \ times n $ boolean矩阵，带有$ω（n^{4/3}）$零条目，该条目不含$ 2 \ times 2 $全零子膜，并具有覆盖的数字$ o（\ log log^4（n））$。这种结构为Pudlák，Rödl和Savický的猜想提供了明确的反例，以及研究问题1.33、4.9、11.17的Jukna [布尔功能复杂性]。这些猜想先前使用概率结构被Katz驳斥。
We give a simple construction of $n\times n$ Boolean matrices with $Ω(n^{4/3})$ zero entries that are free of $2 \times 2$ all-zero submatrices and have covering number $O(\log^4(n))$. This construction provides an explicit counterexample to a conjecture of Pudlák, Rödl and Savický and Research Problems 1.33, 4.9, 11.17 of Jukna [Boolean function complexity]. These conjectures were previously refuted by Katz using a probabilistic construction.
