Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR23-012 | 16th February 2023 19:39

Linear threshold functions in decision lists, decision trees, and depth-2 circuits

RSS-Feed

Abstract:

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF$\circ$LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs); we show that these are equivalent to polynomial-size exact linear decision lists (ELDLs) i.e. decision lists querying exact threshold functions (ELTFs).



ISSN 1433-8092 | Imprint