Projects
2023 - present, ERC Synergy Grant, Postdoc position,
Polynomial-time Computation: Opening the Blackboxes in Constraint Problems.
2022 - 2025, NCN Preludium grant, Principal Investigator
Modular circuits - algorithms and lower bounds.
2017 - 2023, NCN Maestro grant, PhD position
Numerical and structural invariants in algebra, logic and constraint satisfaction problems.
2021 - 2022, POB SciMat minigrant, Principal Investigator
Applications of modular circuits.
Teaching
TU Wien + private:
2026, Computational Complexity, Lecturer
2023 - present, Semestral/Bachelor/Masters thesis, Tutor
UMCS, Lublin:
2022 - 2023, Formal Languages and Programming Paradigms, Tutor
UJ, Kraków:
2018 - 2022, Algebraic Methods in Computer Science, Tutor
2020 - 2022, Programming Project, Tutor
2018 - 2019, Theory of Programming, Tutor
2018 - 2019, Models of Computation, Tutor
PhD Thesis
Complexity of solving equations in finite algebraic structures, 10/11/2023, defended under the supervision of prof. Paweł Idziak.
Publications per topic (with a short description)
Algorithms for solving algebraic equations
We investigate which sets of operations over a finite domain admit polynomial-time algorithms for satisfiability and equivalence of equations (or circuits) built from those operations. These problems have been studied since the 1980s for finite groups, and even for particular groups—such as S_4 —they remained open for decades. Some authors conjectured a P vs. NP-complete/coNP-complete dichotomy for these classes of problems.
In a series of papers, we give a complete characterization of the tractable cases of the equivalence problem for groups, and an almost complete characterization of satisfiability as well (with some remaining subtleties about how satisfiability should be defined, which we discuss in detail). Strikingly, the specific groups that resisted classification for so long yield NP-intermediate and coNP-intermediate complexities under ETH together with certain circuit lower-bound assumptions, thereby refuting the earlier dichotomy conjectures. Finally, using tools from universal algebra, we extend these results from groups to circuit satisfiability over far more general finite algebraic structures.
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Intermediate problems in modular circuits satisfiability, LICS'20.
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Complexity of Modular Circuits, LICS'22
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Nonuniform Deterministic Finite Automata over finite algebraic structures, ICALP'25
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Armin Weiss, Satisfiability problems for finite groups, ICALP'22
Piotr Kawałek, Michael Kompatscher, Jacek Krzaczkowski, Circuit equivalence in 2-nilpotent algebras, STACS'24
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Satisfiability of Circuits and Equations over Finite Malcev Algebras, STACS'22
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Expressive Power, Satisfiability and Equivalence of Circuits over Nilpotent Algebras, MFCS'18
Piotr Kawałek, Jacek Krzaczkowski, Even faster algorithms for CSAT over supernilpotent algebras, MFCS'20
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Armin Weiss, Equation satisfiability in solvable groups, TOCS'22 (special edition)
Circuit Complexity for the class CC
We study bounded depth circuits built of modulo counting gates, so-called CC-circuits. These circuits seem to exhibit dual behaviour when compered to much better understood AC^0-circuits. It is an open problem whether such circuits can express AND function of arity n in polynomial size, it is one of these important and still unsolved open problems in circuit complexity theory. In our work we propose better constructions of AND, we study some algorithmic meta-problems for such circuits and connect them to circuit lower bounds, we study probabilistic models of computation corresponding to these circuits and improve some of the earlier results in a very simple manner. We provide new circuit lower bounds in symmetry-restricted settings.
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Complexity of Modular Circuits, LICS'22
Piotr Kawałek, Armin Weiss, Violating Constant Degree Hypothesis Requires Breaking Symmetry, STACS'25
Universal Algebraic Circuit Complexity
We propose to study Circuit Complexity classes that arise when arbitrary sets of bounded fan-in gates are allowed over arbitrary (finite) domain. The effective expressive power of such circuits depends only on the polynomial clone of an algebra and thus can be extensively studied with universal algebraic methods. We connect some standard algebraic notions to classical complexity classes. In this view solvable circuits become tightly connected to classical arithmetic circuits, circuits over semi-linear algebras become tightly connected to monotone circuits and many similar correspondences of this kind can be demonstrated.
Piotr Kawałek, Jacek Krzaczkowski, Complexity Classes Arising from Circuits over Finite Algebraic Structures, LICS'26 submission
Paweł M. Idziak, Piotr Kawałek, Jacek Krzaczkowski, Nonuniform Deterministic Finite Automata over finite algebraic structures, ICALP'25
Lectures and talks
Circuit complexity classes from finite algebras, Vienna 2026, AAA
Violating Constant Degree Hypothesis Requires Breaking Symmetry, Aarhus 2025, ICALP
Circuits, Equations and Universal Algebraic Circuit Complexity, Kolfuschg 2024, CWC
Satisfiability of circuits over finite algebras, Siena 2024, Algebra Week
An etude on polynomials over finite rings, Prague 2024, Seminar
Complexity of satisfiability and equivalence problems in finite algebras, Boulder 2024, PALS
Complexity of solving equations in finite algebraic structures, Denton 2024, BLAST
Complexity of solving equations, Vienna 2024, Seminar
Circuit Complexity aspects of solving equations in finite algebraic structures, Tartu 2023, AAA
Polymorphic Diagonalization for proving low-depth circuit lower bounds, Linz 2023, Seminar
A probabilistic approach to solving equations in finite algebraic structures, Pocinho 2023, TCA
Symmetric variants of Constant Degree Hyphothesis, Stuttgart 2023, Seminar
Complexity of Modular Circuits, Haifa 2022, LICS
Modular Circuits of constant depth, Stuttgart 2022, Seminar
Even faster algorithms for CSAT over supernilpotent algebras, Prague 2020, MFCS
Circuits, equations and nilpotent algebras, Dresden 2019, AAA