Depth-d Threshold Circuits vs. Depth-(d+1) AND-OR Trees

Hatami, P; Hoza, WM; Tal, A; Tell, R

Hatami, P (通讯作者),Ohio State Univ, Dept Comp Sci & Engn, Columbus, OH 43210 USA.

PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023; (): 895

Abstract

For any n is an element of N and d = o (log log n), we prove that there is a Boolean function F on n bits and a value gamma = 2(-Theta(d)) such that F......

Full Text Link