Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-143 | 26th September 2025 23:22

Alternation Depth of Threshold Decision Lists

RSS-Feed




TR25-143
Authors: Vladimir Podolskii, Morgan Prior
Publication: 7th October 2025 15:28
Downloads: 49
Keywords: 


Abstract:

Linear decision lists are a computational model for Boolean functions built from a sequence of linear threshold function queries. Each query is evaluated in order: if a query returns true, the list outputs the value of the function, and if the answer is false, the process continues to the next query. The size of a linear decision list is the number of queries in it.

Linear decision lists form a natural and nontrivial subclass of depth-2 threshold circuits, the class of circuits that currently marks the frontier of explicit circuit lower bounds. While some techniques exist for proving lower bounds against linear decision lists, they are quite limited, leaving important open problems unresolved. Moreover, for the related model of exact linear decision lists, no strong lower bounds are known.

We initiate the study of alternation depth of decision lists. The alternation depth is defined as the number of alternations in the output values of the decision list within the sequence of its queries.

We show that linear decision lists, with both bounded and unbounded query weights, form fine hierarchies with respect to alternation depth. We establish a similar hierarchy for rectangle decision lists, the model closely related to the communication complexity with $\mathrm{NP}$ oracles. In all settings, we prove strong separations within these hierarchies and between them.

Next, we give a lower bound for an explicit function for exact linear decision lists up to depth $n/\log n$. Such lower bounds were not previously known and do not follow directly from existing methods. We also establish a fine depth hierarchy for exact linear decision lists.

To prove these hierarchy separations, we introduce an iterative technique, used in combination with existing techniques such as fooling sets and the analysis of blocky matrices. For the lower bound on bounded-depth exact linear decision lists, we combine the discrepancy method with an iterative analysis of blocky matrices.



ISSN 1433-8092 | Imprint