Search Results

Documents authored by Kawałek, Piotr

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2025.161
Nonuniform Deterministic Finite Automata over Finite Algebraic Structures

Authors: Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Nonuniform deterministic finite automata (NUDFA) over monoids were invented by Barrington in [Barrington, 1985] to study boundaries of nonuniform constant-memory computation. Later, results on these automata helped to identify interesting classes of groups for which equation satisfiability problem (PolSat) is solvable in (probabilistic) polynomial time [Mikael Goldmann and Alexander Russell, 2002; Idziak et al., 2022]. Based on these results, we present a full characterization of groups, for which the identity checking problem (called PolEqv) has a probabilistic polynomial-time algorithm. We also go beyond groups, and propose how to generalise the notion of NUDFA to arbitrary finite algebraic structures. We study satisfiability of these automata in this more general setting. As a consequence, we present a full description of finite algebras from congruence modular varieties for which testing circuit equivalence CEqv can be solved by a probabilistic polynomial-time procedure. In our proofs we use two computational complexity assumptions: randomized Expotential Time Hypothesis and Constant Degree Hypothesis.
Cite as

Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Nonuniform Deterministic Finite Automata over Finite Algebraic Structures. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 161:1-161:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{idziak_et_al:LIPIcs.ICALP.2025.161,
  author =	{Idziak, Pawe{\l} M. and Kawa{\l}ek, Piotr and Krzaczkowski, Jacek},
  title =	{{Nonuniform Deterministic Finite Automata over Finite Algebraic Structures}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{161:1--161:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l 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.2025.161},
  URN =		{urn:nbn:de:0030-drops-235386},
  doi =		{10.4230/LIPIcs.ICALP.2025.161},
  annote =	{Keywords: program satisfiability, circuit equivalence, identity checking}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.58
Violating Constant Degree Hypothesis Requires Breaking Symmetry

Authors: Piotr Kawałek and Armin Weiß

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
The Constant Degree Hypothesis was introduced by Barrington et. al. [David A. Mix Barrington et al., 1990] to study some extensions of q-groups by nilpotent groups and the power of these groups in a computation model called NuDFA (non-uniform DFA). In its simplest formulation, it establishes exponential lower bounds for MOD_q∘MOD_m∘AND_d circuits computing AND of unbounded arity n (for constant integers d,m and a prime q). While it has been proved in some special cases (including d = 1), it remains wide open in its general form for over 30 years. In this paper we prove that the hypothesis holds when we restrict our attention to symmetric circuits with m being a prime. While we build upon techniques by Grolmusz and Tardos [Vince Grolmusz and Gábor Tardos, 2000], we have to prove a new symmetric version of their Degree Decreasing Lemma and use it to simplify circuits in a symmetry-preserving way. Moreover, to establish the result, we perform a careful analysis of automorphism groups of MOD_m∘AND_d subcircuits and study the periodic behaviour of the computed functions. Our methods also yield lower bounds when d is treated as a function of n. Finally, we present a construction of symmetric MOD_q∘MOD_m∘AND_d circuits that almost matches our lower bound and conclude that a symmetric function f can be computed by symmetric MOD_q∘MOD_p∘AND_d circuits of quasipolynomial size if and only if f has periods of polylogarithmic length of the form p^k q^𝓁.
Cite as

Piotr Kawałek and Armin Weiß. Violating Constant Degree Hypothesis Requires Breaking Symmetry. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 58:1-58:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kawalek_et_al:LIPIcs.STACS.2025.58,
  author =	{Kawa{\l}ek, Piotr and Wei{\ss}, Armin},
  title =	{{Violating Constant Degree Hypothesis Requires Breaking Symmetry}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{58:1--58:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.58},
  URN =		{urn:nbn:de:0030-drops-228837},
  doi =		{10.4230/LIPIcs.STACS.2025.58},
  annote =	{Keywords: Circuit lower bounds, constant degree hypothesis, permutation groups, CC⁰-circuits}
}
Document
DOI: 10.4230/LIPIcs.STACS.2024.45
Circuit Equivalence in 2-Nilpotent Algebras

Authors: Piotr Kawałek, Michael Kompatscher, and Jacek Krzaczkowski

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
The circuit equivalence problem Ceqv(A) of a finite algebra A is the problem of deciding whether two circuits over A compute the same function or not. This problem not only generalises the equivalence problem for Boolean circuits, but is also of interest in universal algebra, as it models the problem of checking identities in A. In this paper we prove that Ceqv(A) ∈ 𝖯, if A is a finite 2-nilpotent algebra from a congruence modular variety.
Cite as

Piotr Kawałek, Michael Kompatscher, and Jacek Krzaczkowski. Circuit Equivalence in 2-Nilpotent Algebras. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 45:1-45:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kawalek_et_al:LIPIcs.STACS.2024.45,
  author =	{Kawa{\l}ek, Piotr and Kompatscher, Michael and Krzaczkowski, Jacek},
  title =	{{Circuit Equivalence in 2-Nilpotent Algebras}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{45:1--45:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.45},
  URN =		{urn:nbn:de:0030-drops-197554},
  doi =		{10.4230/LIPIcs.STACS.2024.45},
  annote =	{Keywords: circuit equivalence, identity checking, nilpotent algebra}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.127
Satisfiability Problems for Finite Groups

Authors: Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Over twenty years ago, Goldmann and Russell initiated the study of the complexity of the equation satisfiability problem (PolSat and the NUDFA program satisfiability problem (ProgramSat) in finite groups. They showed that these problems are in 𝖯 for nilpotent groups while they are NP-complete for non-solvable groups. In this work we completely characterize finite groups for which the problem ProgramSat can be solved in randomized polynomial time under the assumptions of the Randomized Exponential Time Hypothesis and the Constant Degree Hypothesis. We also determine the complexity of PolSat for a wide class of finite groups. As a by-product, we obtain a classification for ListPolSat, a version of PolSat where each variable can be restricted to an arbitrary subset. Finally, we also prove unconditional algorithms for these problems in certain cases.
Cite as

Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, and Armin Weiß. Satisfiability Problems for Finite Groups. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 127:1-127:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{idziak_et_al:LIPIcs.ICALP.2022.127,
  author =	{Idziak, Pawe{\l} M. and Kawa{\l}ek, Piotr and Krzaczkowski, Jacek and Wei{\ss}, Armin},
  title =	{{Satisfiability Problems for Finite Groups}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{127:1--127:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.127},
  URN =		{urn:nbn:de:0030-drops-164685},
  doi =		{10.4230/LIPIcs.ICALP.2022.127},
  annote =	{Keywords: Satisifiability, Solvable groups, ProgramSat, PolSat, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.STACS.2022.37
Satisfiability of Circuits and Equations over Finite Malcev Algebras

Authors: Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We show that the satisfiability of circuits over finite Malcev algebra A is NP-complete or A is nilpotent. This strengthens the result from our earlier paper [Idziak and Krzaczkowski, 2018] where nilpotency has been enforced, however with the use of a stronger assumption that no homomorphic image of A has NP-complete circuits satisfiability. Our methods are moreover strong enough to extend our result of [Idziak et al., 2021] from groups to Malcev algebras. Namely we show that tractability of checking if an equation over such an algebra A has a solution enforces its nice structure: A must have a nilpotent congruence ν such that also the quotient algebra A/ν is nilpotent. Otherwise, if A has no such congruence ν then the Exponential Time Hypothesis yields a quasipolynomial lower bound. Both our results contain important steps towards a full characterization of finite algebras with tractable circuit satisfiability as well as equation satisfiability.
Cite as

Paweł M. Idziak, Piotr Kawałek, and Jacek Krzaczkowski. Satisfiability of Circuits and Equations over Finite Malcev Algebras. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{idziak_et_al:LIPIcs.STACS.2022.37,
  author =	{Idziak, Pawe{\l} M. and Kawa{\l}ek, Piotr and Krzaczkowski, Jacek},
  title =	{{Satisfiability of Circuits and Equations over Finite Malcev Algebras}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{37:1--37:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.37},
  URN =		{urn:nbn:de:0030-drops-158474},
  doi =		{10.4230/LIPIcs.STACS.2022.37},
  annote =	{Keywords: Circuit satisfiability, solving equations, Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.55
Even Faster Algorithms for CSAT Over supernilpotent Algebras

Authors: Piotr Kawałek and Jacek Krzaczkowski

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
Recently, a few papers considering the polynomial equation satisfiability problem and the circuit satisfiability problem over finite supernilpotent algebras from so called congruence modular varieties were published. All the algorithms considered in these papers are quite similar and rely on checking a not too big set of potential solutions. Two of these algorithms achieving the lowest time complexity up to now, were presented in [Aichinger, 2019] (algorithm working for finite supernilpotent algebras) and in [Földvári, 2018] (algorithm working in the group case). In this paper we show a deterministic algorithm of the same type solving the considered problems for finite supernilpotent algebras which has lower computational complexity than the algorithm presented in [Aichinger, 2019] and in most cases even lower than the group case algorithm from [Földvári, 2018]. We also present a linear time Monte Carlo algorithm solving the same problem. This, together with the algorithm for nilpotent but not supernilpotent algebras presented in [Paweł M. Idziak et al., 2020], is the very first attempt to solving the circuit satisfiability problem using probabilistic algorithms.
Cite as

Piotr Kawałek and Jacek Krzaczkowski. Even Faster Algorithms for CSAT Over supernilpotent Algebras. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kawalek_et_al:LIPIcs.MFCS.2020.55,
  author =	{Kawa{\l}ek, Piotr and Krzaczkowski, Jacek},
  title =	{{Even Faster Algorithms for CSAT Over supernilpotent Algebras}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{55:1--55:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.55},
  URN =		{urn:nbn:de:0030-drops-127225},
  doi =		{10.4230/LIPIcs.MFCS.2020.55},
  annote =	{Keywords: circuit satisfiability, solving equations, supernilpotent algebras, satisfiability in groups}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact