5 citations · 5 across the 3 of their papers we have counts for
8 papers · 1 filter
Complexity Classes Arising from Circuits over Finite Algebraic Structures
Piotr Kawałek, Jacek Krzaczkowski
Most classical results in circuit complexity theory concern circuits over the Boolean domain. Besides their simplicity and the ease of comparing different languages, the actual arc…
Nonuniform Deterministic Finite Automata over finite algebraic structures
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski
Nonuniform Deterministic Finite Automata (NUDFA) over monoids were invented by Barrington to study boundaries of nonuniform constant-memory computation. Later, results on these aut…
Violating Constant Degree Hypothesis Requires Breaking Symmetry
Piotr Kawałek, Armin Weiß
The Constant Degree Hypothesis was introduced by Barrington et. al. (1990) to study some extensions of -groups by nilpotent groups and the power of these groups in a certain com…
Complexity of Modular Circuits
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski
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 constructi…
Equation satisfiability in solvable groups
Paweł Idziak, Piotr Kawałek, Jacek Krzaczkowski +1
The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell (2002) where they showed that this problem is in poly…
Even faster algorithms for CSAT over~supernilpotent algebras
Piotr Kawałek, Jacek Krzaczkowski
In this paper two algorithms solving circuit satisfiability problem over supernilpotent algebras are presented. The first one is deterministic and is faster than fastest previous a…
Intermediate problems in modular circuits satisfiability
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski
In arXiv:1710.08163 a generalization of Boolean circuits to arbitrary finite algebras had been introduced and applied to sketch P versus NP-complete borderline for circuits satisfi…
Circuit equivalence in 2-nilpotent algebras
Piotr Kawałek, Michael Kompatscher, Jacek Krzaczkowski
The circuit equivalence problem of a finite algebra is the computational problem of deciding whether two circuits over define the same function or not. This…