Cited By
View all- Idziak PKawałek PKrzaczkowski JWeiß A(2024)Equation Satisfiability in Solvable GroupsTheory of Computing Systems10.1007/s00224-022-10082-z68:4(740-757)Online publication date: 1-Aug-2024
Complexity of Modular Circuits
Article No.: 32, Pages 1 - 11
Abstract
We study how the complexity of modular circuits computing AND depends on the depth of the circuits and the prime factorization of the modulus they use. In particular our construction of subexponential circuits of depth 2 for AND helps us to classify (modulo Exponential Time Hypothesis) modular circuits with respect to the complexity of their satisfiability. We also study a precise correlation between this complexity and the sizes of modular circuits realizing AND. In particular we use the superlinear lower bound from [10] to check satisfiability of CC0 circuits in probabilistic 2O(n/ε(n)) time, where ε is some extremely slowly increasing function. Moreover we show that AND can be computed by a polynomial size modular circuit of depth 2 (with O(log n) random bits) providing a probabilistic computational model that can not be derandomized.
We apply our methods to determine (modulo ETH) the complexity of solving equations over groups of symmetries of regular polygons with an odd number of sides. These groups form a paradigm for some of the remaining cases in characterizing finite groups with respect to the complexity of their equation solving.
References
[1]
[1] David A. Mix Barrington, Richard Beigel and Steven Rudich. 1994. Representing boolean functions as polynomials modulo composite numbers. Computational Complexity, 4, 4 (Dec. 1994), 367–382.
[2]
[2] David A. Mix Barrington, Howard Straubing and Denis Thérien. 1990. Non-uniform automata over groups. Information and Computation, 89, 2 (Dec. 1990), 109–132.
[3]
[3] Richard Beigel and Jun Tarui. 1991. On ACC. In Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science (FOCS ’91), October 1-4, 1991, San Juan, Puerto Rico, IEEE, 783–-792. https://doi.org/10.1109/SFCS.1991.185449.
[4]
[4] Stanley Burris and John Lawrence. 2005. Results on the equivalence problem for finite groups. Algebra Universalis, 52 (Feb. 2005), 495–500.
[5]
[5] Chris Calabro, Russell Impagliazzo and Ramamohan Paturi. 2009. The Complexity of Satisfiability of Small Depth Circuits. In Proceedings of the 4th International Workshop on Parameterized and Exact Computation (IWPEC’09), September 10-11, 2009, Copenhagen, Denmark, Lecture Notes in Computer Science, 5917, Springer, Berlin, Heidelberg, 75–-85.
[6]
[6] Hervé Caussinus. 1996. A Note on a Theorem of Barrington, Straubing and Thérien. Information Processing Letters, 58, 1 (Apr. 1996), 31–33.
[7]
[7] Vince Grolmusz and Gábor Tardos. 2000. Lower bounds for (MODp-MODm) circuits. SIAM Journal of Computing, 29, 4 (2000), 1209–1222.
[8]
[8] Vince Grolmusz. 2001. A Degree-Decreasing Lemma for (MOD-q - MOD-p) Circuits. Discrete Mathematics and Theoretical Computer Science, 4, 2 (Jan. 2001), 247–254.
[9]
[9] Brynmor Chapman and R. Ryan Williams. 2022. Smaller ACC0 Circuits for Symmetric Functions. In Proceedings of the 13th Innovations in Theoretical Computer Science Conference (ITCS 2022) January 11-13, 2023, Cambridge, Massachusetts, LIPIcs, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Article 38, 19 pages. https://doi.org/10.4230/LIPIcs.ITCS.2022.38.
[10]
[10] Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlak, Denis Therien. 2006. Lower bounds for circuits with MODm gates. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), Oktober 21-24, 2006 Berkeley, California, IEEE, 709–-718. https:://doi.org/10.1109/FOCS.2006.46
[11]
[11] Attila Földvári and Gábor Horváth. 2020. The complexity of the equation solvability and equivalence problems over finite groups. International Journal of Algebra and Computation, 30, 3 (May 2020), 1–17.
[12]
[12] Mikael Goldmann and Alexander Russell. 1999. The complexity of solving equations over finite groups. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC’99), May 4-6, 1999, Atlanta, Georgia, IEEE, 80–86. https://doi.org/10.1109/CCC.1999.766266
[13]
[13] Kristoffer Arnsfelt Hansen. 2008. Constant width planar branching programs characterize ACC0 in quasipolynomial size. In Proceedings of the 23rd Annual IEEE Conference on Computational Complexity (CCC’08), June 23-26, 2008, College Park, Maryland, IEEE, 92–-99. https://doi.org/10.1109/CCC.2008.30
[14]
[14] Kristoffer Arnsfelt Hansen and Michal Koucký. 2009. A New Characterization of ACC0 and Probabilistic CC0. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC’09), July 15-18, 2009, Paris, France, IEEE, 27–34. https://doi.org/10.1109/CCC.2009.15
[15]
[15] Gábor Horváth. 2011. The complexity of the equivalence and equation solvability problems over nilpotent rings and groups. Algebra Universalis, 66 (Dec. 2011), 391–-403.
[16]
[16] Gábor Horváth. 2015. The complexity of the equivalence and equation solvability problems over meta-Abelian groups. Journal of Algebra433 (Jul. 2015), 208–230.
[17]
[17] Gábor Horváth and Csaba Szabó. 2006. The complexity of checking identities over finite groups. Internat. J. Algebra Comput., 16, 5 (Oct. 2006), 931-939.
[18]
[18] Paweł M. Idziak, Piotr Kawałek and Jacek Krzaczkowski. 2018. Expressive power, satisfiability and equivalence of circuits over nilpotent algebras. In Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS’18), August 27–31, 2018, Liverpool, UK, LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Article 17, 15 pages. https://doi.org/10.4230/LIPIcs.MFCS.2018.17
[19]
[19] Paweł M. Idziak, Piotr Kawałek and Jacek Krzaczkowski. 2020. Intermediate Problems in Modular Circuits Satisfiability. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’20), July 8–11, 2020, Saarbrücken, Germany, ACM, 578-–590. https://doi.org/10.1145/3373718.3394780
[20]
[20] Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski and Armin Weiß. 2020. Equation satisfiability in solvable groups. To appear in Theory of Computing Systems. arXiv:2010.11788. Retrieved from https://arxiv.org/abs/2010.11788.
[21]
[21] Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski and Armin Weiß. 2022. Satisfiability problems for finite groups. In Proceedings of the 49th International Colloquium on Automata, Languages and Programming (ICALP’22), July 4-8, 2022, Paris, France, LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Article 133, 20 pages. https://doi.org/10.4230/LIPIcs.ICALP.2022.133
[22]
[22] Paweł M. Idziak and Jacek Krzaczkowski. 2022. Satisfiability in MultiValued Circuits. SIAM Journal on Computing, 51, 3 (2022), 337-378. version: In Proceedings of 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS’18), July 9–12, 2018, Oxford, UK, ACM, 550–558. https://doi.org/10.1145/3209108.3209173.
[23]
[23] Russell Impagliazzoa, Ramamohan Paturia and Francis Zaneb. 2001. Which problems have strongly exponential complexity, J. Comput. Syst. Sci. 63, 4 (Dec. 2001), 512–530.
[24]
[24] Piotr Kawałek, Michael Kompatscher and Jacek Krzaczkowski. 2019. Circuit equivalence in 2-nilpotent algebras. arXiv:1909.12256. Retrieved from https://arxiv.org/abs/1909.12256.
[25]
[25] Michael Kompatscher. 2021. CSAT and CEQV for nilpotent Maltsev algebras of Fitting length > 2. arXiv:2105.00689. Retrieved from https://arxiv.org/abs/2105.00689.
[26]
[26] Howard Straubing and Denis Thérien. 2006. A note on MODp–MODm circuits. Theory of Computing Systems, 39 (Sep. 2006), 699–706.
[27]
[27] A. Weiß. 2020 Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis. In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP’20), July 8-11, 2020, Saarbrücken, Germany, LIPIcs, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Article 102, 19 pages. https://doi.org/10.4230/LIPIcs.ICALP.2020.102
Recommendations
Intermediate problems in modular circuits satisfiability
LICS '20: Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer ScienceIn [15] a generalization of Boolean circuits to arbitrary finite algebras had been introduced and applied to sketch P versus NP-complete borderline for circuits satisfiability over algebras from congruence modular varieties. However the problem for ...
Tree Realizations of Iterative Circuits
It is shown how any combinational function that can be described by a flow table or equivalently is realizable in iterative form can be realized in tree form. The propagation delay is then proportional to the logarithm of n, the number of inputs, while ...
On the complexity of circuit satisfiability
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computingIn this paper, we are concerned with the exponential complexity of the Circuit Satisfiability (CktSat) problem and more generally with the exponential complexity of NP-complete problems. Over the past 15 years or so, researchers have obtained a number ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 August 2022
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Polish National Science Centre
Conference
LICS '22
Sponsor:
LICS '22: 37th Annual ACM/IEEE Symposium on Logic in Computer Science
August 2 - 5, 2022
Haifa, Israel
Acceptance Rates
Overall Acceptance Rate 215 of 622 submissions, 35%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 83Total Downloads
- Downloads (Last 12 months)32
- Downloads (Last 6 weeks)5
Reflects downloads up to 30 Sep 2024
Other Metrics
Citations
Cited By
View all- Idziak PKawałek PKrzaczkowski JWeiß A(2024)Equation Satisfiability in Solvable GroupsTheory of Computing Systems10.1007/s00224-022-10082-z68:4(740-757)Online publication date: 1-Aug-2024
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format