LIPIcs.ITCS.2023.33.pdf
- Filesize: 0.81 MB
- 20 pages
Document
Lifting to Parity Decision Trees via Stifling
Authors
-
Part of:
Volume:
14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2023-02-01
Cite As Get BibTex
Arkadev Chattopadhyay, Nikhil S. Mande, Swagato Sanyal, and Suhail Sherif. Lifting to Parity Decision Trees via Stifling. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 33:1-33:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ITCS.2023.33
Abstract
We show that the deterministic decision tree complexity of a (partial) function or relation f lifts to the deterministic parity decision tree (PDT) size complexity of the composed function/relation f∘g as long as the gadget g satisfies a property that we call stifling. We observe that several simple gadgets of constant size, like Indexing on 3 input bits, Inner Product on 4 input bits, Majority on 3 input bits and random functions, satisfy this property. It can be shown that existing randomized communication lifting theorems ([Göös, Pitassi, Watson. SICOMP'20], [Chattopadhyay et al. SICOMP'21]) imply PDT-size lifting. However there are two shortcomings of this approach: first they lift randomized decision tree complexity of f, which could be exponentially smaller than its deterministic counterpart when either f is a partial function or even a total search problem. Second, the size of the gadgets in such lifting theorems are as large as logarithmic in the size of the input to f. Reducing the gadget size to a constant is an important open problem at the frontier of current research. Our result shows that even a random constant-size gadget does enable lifting to PDT size. Further, it also yields the first systematic way of turning lower bounds on the width of tree-like resolution proofs of the unsatisfiability of constant-width CNF formulas to lower bounds on the size of tree-like proofs in the resolution with parity system, i.e., Res(⊕), of the unsatisfiability of closely related constant-width CNF formulas.
Subject Classification
ACM Subject Classification
- Theory of computation → Oracles and decision trees
Keywords
- Decision trees
- parity decision trees
- lifting theorems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Anurag Anshu, Shalev Ben-David, and Srijita Kundu. On query-to-communication lifting for adversary bounds. In 36th Computational Complexity Conference (CCC), volume 200 of LIPIcs, pages 30:1-30:39. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.CCC.2021.30.
- Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-to-communication lifting using low-discrepancy gadgets. SIAM J. Comput., 50(1):171-210, 2021. Earlier version in ICALP'19. URL: https://doi.org/10.1137/19M1310153.
- Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Simulation beats richness: new data-structure lower bounds. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 1013-1020. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188874.
- Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, and Sagnik Mukhopadhyay. Simulation theorems via pseudo-random properties. Comput. Complex., 28(4):617-659, 2019. URL: https://doi.org/10.1007/s00037-019-00190-7.
- Arkadev Chattopadhyay, Nikhil S. Mande, and Suhail Sherif. The log-approximate-rank conjecture is false. J. ACM, 67(4):23:1-23:28, 2020. Earlier version in STOC'19. URL: https://doi.org/10.1145/3396695.
- Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. How limited interaction hinders real communication (and what it means for proof and circuit complexity). In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 295-304. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.40.
- Jeff Edmonds, Steven Rudich, Russell Impagliazzo, and Jirí Sgall. Communication complexity towards lower bounds on circuit depth. In 32nd Annual Symposium on Foundations of Computer Science (FOCS), pages 249-257. IEEE Computer Society, 1991. URL: https://doi.org/10.1109/SFCS.1991.185375.
-
Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov. Monotone circuit lower bounds from resolution. Theory Comput., 16:1-30, 2020. Earlier version in STOC'18.
- Mika Göös, Sajin Koroth, Ian Mertz, and Toniann Pitassi. Automating cutting planes is np-hard. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 68-77. ACM, 2020. URL: https://doi.org/10.1145/3357713.3384248.
- Mika Göös, Toniann Pitassi, and Thomas Watson. Deterministic communication vs. partition number. SIAM J. Comput., 47(6):2435-2450, 2018. Earlier version in FOCS'15. URL: https://doi.org/10.1137/16M1059369.
- Mika Göös, Toniann Pitassi, and Thomas Watson. Query-to-communication lifting for BPP. SIAM J. Comput., 49(4), 2020. Earlier version in FOCS'17. URL: https://doi.org/10.1137/17M115339X.
- Dmitry Itsykson and Dmitry Sokolov. Resolution over linear equations modulo two. Ann. Pure Appl. Log., 171(1), 2020. URL: https://doi.org/10.1016/j.apal.2019.102722.
- Alexander Knop, Shachar Lovett, Sam McGuire, and Weiqiang Yuan. Log-rank and lifting for and-functions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 197-208. ACM, 2021. URL: https://doi.org/10.1145/3406325.3450999.
- Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra. Approximating rectangles by juntas and weakly-exponential lower bounds for LP relaxations of csps. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 590-603. ACM, 2017. URL: https://doi.org/10.1145/3055399.3055438.
- Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. Lifting with sunflowers. In Mark Braverman, editor, 13th Innovations in Theoretical Computer Science Conference (ITCS), volume 215 of LIPIcs, pages 104:1-104:24. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. URL: https://doi.org/10.4230/LIPIcs.ITCS.2022.104.
- Ran Raz and Pierre McKenzie. Separation of the monotone NC hierarchy. Combinatorica, 19(3):403-435, 1999. Earlier version in FOCS'97. URL: https://doi.org/10.1007/s004930050062.
- Ran Raz and Iddo Tzameret. Resolution over linear equations and multilinear proofs. Ann. Pure Appl. Log., 155(3):194-224, 2008. URL: https://doi.org/10.1016/j.apal.2008.04.001.
- Hing Yin Tsang, Chung Hoi Wong, Ning Xie, and Shengyu Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. In Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 658-667. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.76.
- Hing Yin Tsang, Ning Xie, and Shengyu Zhang. Fourier sparsity of GF(2) polynomials. In Proceedings of Computer Science - Theory and Applications - 11th International Computer Science Symposium in Russia (CSR), volume 9691 of Lecture Notes in Computer Science, pages 409-424. Springer, 2016. URL: https://doi.org/10.1007/978-3-319-34171-2_29.