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

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF o 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).& COPY; 2023 Elsevier B.V. All rights reserved.

Automated summary

We demonstrate that polynomial-size constant-rank linear decision trees (LDTs) can be transformed into polynomial-size depth-2 threshold circuits LTF o LTF. An intermediate structure is polynomial-size decision lists that refer to a conjunction of a fixed number of linear threshold functions (LTFs); we prove that these are equivalent to polynomial-size exact linear decision lists (ELDLs), which query precise threshold functions (ELTFs).