Decision List Compression by Mild Random Restrictions

DOI10.1145/3485007MaRDI QIDQ5056434zbMATH OpenOpenAlexFDO

Authors Shachar Lovett, Kewen Wu, Jiapeng Zhang

Publication date 8 December 2022

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3485007

zbMATH Keywords

decision listsswitching lemmaDNF sparsification

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Decision list compression by mild random restrictions
• Lower bounds for linear decision lists
• Combinatorial bounds for list decoding
• A list-based compact representation for large decision tables management
• On the computational power of Boolean decision lists
• scientific article; zbMATH DE number 2086400
• A Lower Bound on List Size for List Decoding
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Lower bounds on learning decision lists and trees
• Lower bounds on learning decision lists and trees

Cited in

(1)

• DNF sparsification beyond sunflowers

This page was built for publication: Decision List Compression by Mild Random Restrictions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5056434)