DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.148

Alternation Depth of Threshold Decision Lists

Authors: Vladimir Podolskii and Morgan Prior

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

Linear decision lists are a computational model for Boolean functions. A linear decision list is built from a sequence of linear threshold function queries which are evaluated one by one: 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. Although some techniques for proving lower bounds against linear decision lists exist, 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 with linear threshold queries. The alternation depth is defined as the number of alternations in the sequence of output values of the decision list. We show that linear decision lists, both with bounded and unbounded weights in the threshold queries, form fine hierarchies with respect to alternation depth. A similar hierarchy exists for rectangle decision lists, the model closely related to communication complexity with NP oracles. We prove strong separations within these hierarchies and between them. Next, we give a superpolynomial lower bound for an explicit function for exact linear decision lists of depth below 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 use an iterative technique combined with existing techniques such as fooling sets and the analysis of blocky matrices. For the lower bound on exact linear decision lists, we combine the discrepancy method with an iterative analysis of blocky matrices.

Cite as

Vladimir Podolskii and Morgan Prior. Alternation Depth of Threshold Decision Lists. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 148:1-148:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{podolskii_et_al:LIPIcs.ICALP.2026.148,
  author =	{Podolskii, Vladimir and Prior, Morgan},
  title =	{{Alternation Depth of Threshold Decision Lists}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{148:1--148:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.148},
  URN =		{urn:nbn:de:0030-drops-265373},
  doi =		{10.4230/LIPIcs.ICALP.2026.148},
  annote =	{Keywords: linear decision lists, threshold decision lists, rectangle decision lists, threshold circuits}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2025.37

Communication Complexity of Equality and Error-Correcting Codes

Authors: Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, and Ilya Volkovich

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract

We study the public-coin randomized communication complexity of the equality function. The communication complexity of this function is known to be low when the error probability is constant and the players have access to many random bits. The complexity grows, however, if the allowed error probability and the amount of randomness are restricted. We show that public-coin randomized protocols for equality and error-correcting codes are essentially the same object. That is, given a protocol for equality, we can construct a code, and vice versa. We substantially extend the protocol-implies-code direction: any protocol computing a function with a large fooling set can be converted into an error-correcting code. As a corollary, we show that among functions with a fooling set of size s, equality on log s bits has the least randomized communication complexity, regardless of the restrictions on the error probability and the amount of randomness. Finally, we use the connection to error-correcting codes to analyze the randomized communication complexity of equality for varying restrictions on the error probability and the amount of randomness. In most cases, we provide tight bounds. We pinpoint the setting in which tight bounds are still unknown.

Cite as

Dale Jacobs, John Jeang, Vladimir Podolskii, Morgan Prior, and Ilya Volkovich. Communication Complexity of Equality and Error-Correcting Codes. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 37:1-37:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jacobs_et_al:LIPIcs.FSTTCS.2025.37,
  author =	{Jacobs, Dale and Jeang, John and Podolskii, Vladimir and Prior, Morgan and Volkovich, Ilya},
  title =	{{Communication Complexity of Equality and Error-Correcting Codes}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{37:1--37:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.37},
  URN =		{urn:nbn:de:0030-drops-251175},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.37},
  annote =	{Keywords: communication complexity, randomized communication complexity, error-correcting codes}
}

Search Results

Documents authored by Prior, Morgan

Alternation Depth of Threshold Decision Lists

Abstract

Cite as

Communication Complexity of Equality and Error-Correcting Codes

Abstract

Cite as

Thanks for your feedback!

Could not send message