Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > DE MORGAN FORMULA:
Reports tagged with De Morgan Formula:
TR21-002 | 8th January 2021
Pooya Hatami, William Hoza, Avishay Tal, Roei Tell

Fooling Constant-Depth Threshold Circuits

Revisions: 1

We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ ... more >>>




ISSN 1433-8092 | Imprint