On depth-3 circuits and covering number: an explicit counter-example

10/15/2022
by   Lianna Hambardzumyan, et al.
0

We give a simple construction of n× n Boolean matrices with Ω(n^4/3) zero entries that are free of 2 × 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset