7 Search Results for "Wilsenach, Gregory"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.46
Symmetric Algebraic Circuits and Homomorphism Polynomials

Authors: Anuj Dawar, Benedikt Pago, and Tim Seppelt

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The central open question of algebraic complexity is whether VP ≠ VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic circuits. For symmetric algebraic circuits, this has been confirmed by Dawar and Wilsenach (2020), who showed exponential lower bounds on the size of symmetric circuits for the permanent. In this work, we set out to develop a more general symmetric algebraic complexity theory. Our main result is that a family of symmetric polynomials admits small symmetric circuits if and only if they can be written as a linear combination of homomorphism counting polynomials of graphs of bounded treewidth. We also establish a relationship between the symmetric complexity of subgraph counting polynomials and the vertex cover number of the pattern graph. As a concrete example, we examine the symmetric complexity of immanant families (a generalisation of the determinant and permanent) and show that a known conditional dichotomy due to Curticapean (2021) holds unconditionally in the symmetric setting.
Cite as

Anuj Dawar, Benedikt Pago, and Tim Seppelt. Symmetric Algebraic Circuits and Homomorphism Polynomials. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 46:1-46:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.ITCS.2026.46,
  author =	{Dawar, Anuj and Pago, Benedikt and Seppelt, Tim},
  title =	{{Symmetric Algebraic Circuits and Homomorphism Polynomials}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.46},
  URN =		{urn:nbn:de:0030-drops-253330},
  doi =		{10.4230/LIPIcs.ITCS.2026.46},
  annote =	{Keywords: algebraic complexity, finite model theory, symmetric circuits, homomorphism counting, graph homomorphism, treewidth, counting width, first-order logic with counting quantifiers}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.40
Symmetric Proofs in the Ideal Proof System

Authors: Anuj Dawar, Erich Grädel, Leon Kullmann, and Benedikt Pago

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We consider the Ideal Proof System (IPS) introduced by Grochow and Pitassi and pose the question of which tautologies admit symmetric proofs, and of what complexity. The symmetry requirement in proofs is inspired by recent work establishing lower bounds in other symmetric models of computation. We link the existence of symmetric IPS proofs to the expressive power of logics such as fixed-point logic with counting and Choiceless Polynomial Time, specifically regarding the graph isomorphism problem. We identify relationships and tradeoffs between the symmetry of proofs and other parameters of IPS proofs such as size, degree and linearity. We study these on a number of standard families of tautologies from proof complexity and finite model theory such as the pigeonhole principle, the subset sum problem and the Cai-Fürer-Immerman graphs, exhibiting non-trivial upper bounds on the size of symmetric IPS proofs.
Cite as

Anuj Dawar, Erich Grädel, Leon Kullmann, and Benedikt Pago. Symmetric Proofs in the Ideal Proof System. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 40:1-40:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.MFCS.2025.40,
  author =	{Dawar, Anuj and Gr\"{a}del, Erich and Kullmann, Leon and Pago, Benedikt},
  title =	{{Symmetric Proofs in the Ideal Proof System}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{40:1--40:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.40},
  URN =		{urn:nbn:de:0030-drops-241477},
  doi =		{10.4230/LIPIcs.MFCS.2025.40},
  annote =	{Keywords: proof complexity, algebraic complexity, descriptive complexity, symmetric circuits, graph isomorphism}
}
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.ITCS.2022.52
Lower Bounds for Symmetric Circuits for the Determinant

Authors: Anuj Dawar and Gregory Wilsenach

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the determinant and the permanent. The symmetry restriction is that the circuits which take a matrix input are unchanged by a permutation applied simultaneously to the rows and columns of the matrix. Under such restrictions we have polynomial-size circuits for computing the determinant but no subexponential size circuits for the permanent. Here, we consider a more stringent symmetry requirement, namely that the circuits are unchanged by arbitrary even permutations applied separately to rows and columns, and prove an exponential lower bound even for circuits computing the determinant. The result requires substantial new machinery. We develop a general framework for proving lower bounds for symmetric circuits with restricted symmetries, based on a new support theorem and new two-player restricted bijection games. These are applied to the determinant problem with a novel construction of matrices that are bi-adjacency matrices of graphs based on the CFI construction. Our general framework opens the way to exploring a variety of symmetry restrictions and studying trade-offs between symmetry and other resources used by arithmetic circuits.
Cite as

Anuj Dawar and Gregory Wilsenach. Lower Bounds for Symmetric Circuits for the Determinant. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 52:1-52:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.ITCS.2022.52,
  author =	{Dawar, Anuj and Wilsenach, Gregory},
  title =	{{Lower Bounds for Symmetric Circuits for the Determinant}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{52:1--52:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.52},
  URN =		{urn:nbn:de:0030-drops-156480},
  doi =		{10.4230/LIPIcs.ITCS.2022.52},
  annote =	{Keywords: arithmetic circuits, symmetric arithmetic circuits, Boolean circuits, symmetric circuits, permanent, determinant, counting width, Weisfeiler-Leman dimension, Cai-F\"{u}rer-Immerman constructions}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.37
On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism

Authors: Anuj Dawar and Danny Vagnozzi

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
We compare the capabilities of two approaches to approximating graph isomorphism using linear algebraic methods: the invertible map tests (introduced by Dawar and Holm) and proof systems with algebraic rules, namely polynomial calculus, monomial calculus and Nullstellensatz calculus. In the case of fields of characteristic zero, these variants are all essentially equivalent to the Weisfeiler-Leman algorithms. In positive characteristic we show that the distinguishing power of the monomial calculus is no greater than the invertible map method by simulating the former in a fixed-point logic with solvability operators. In turn, we show that the distinctions made by this logic can be implemented in the Nullstellensatz calculus.
Cite as

Anuj Dawar and Danny Vagnozzi. On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.MFCS.2021.37,
  author =	{Dawar, Anuj and Vagnozzi, Danny},
  title =	{{On the Relative Power of Linear Algebraic Approximations of Graph Isomorphism}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.37},
  URN =		{urn:nbn:de:0030-drops-144774},
  doi =		{10.4230/LIPIcs.MFCS.2021.37},
  annote =	{Keywords: Graph isomorphism, proof complexity, invertible map tests}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.36
Symmetric Arithmetic Circuits

Authors: Anuj Dawar and Gregory Wilsenach

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
We introduce symmetric arithmetic circuits, i.e. arithmetic circuits with a natural symmetry restriction. In the context of circuits computing polynomials defined on a matrix of variables, such as the determinant or the permanent, the restriction amounts to requiring that the shape of the circuit is invariant under row and column permutations of the matrix. We establish unconditional, nearly exponential, lower bounds on the size of any symmetric circuit for computing the permanent over any field of characteristic other than 2. In contrast, we show that there are polynomial-size symmetric circuits for computing the determinant over fields of characteristic zero.
Cite as

Anuj Dawar and Gregory Wilsenach. Symmetric Arithmetic Circuits. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.ICALP.2020.36,
  author =	{Dawar, Anuj and Wilsenach, Gregory},
  title =	{{Symmetric Arithmetic Circuits}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.36},
  URN =		{urn:nbn:de:0030-drops-124430},
  doi =		{10.4230/LIPIcs.ICALP.2020.36},
  annote =	{Keywords: arithmetic circuits, symmetric arithmetic circuits, Boolean circuits, symmetric circuits, permanent, determinant, counting width, Weisfeiler-Leman dimension, Cai-F\"{u}rer-Immerman constructions}
}
Document
DOI: 10.4230/LIPIcs.CSL.2018.20
Symmetric Circuits for Rank Logic

Authors: Anuj Dawar and Gregory Wilsenach

Published in: LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)

Abstract
Fixed-point logic with rank (FPR) is an extension of fixed-point logic with counting (FPC) with operators for computing the rank of a matrix over a finite field. The expressive power of FPR properly extends that of FPC and is contained in P, but it is not known if that containment is proper. We give a circuit characterization for FPR in terms of families of symmetric circuits with rank gates, along the lines of that for FPC given by [Anderson and Dawar 2017]. This requires the development of a broad framework of circuits in which the individual gates compute functions that are not symmetric (i.e., invariant under all permutations of their inputs). This framework also necessitates the development of novel techniques to prove the equivalence of circuits and logic. Both the framework and the techniques are of greater generality than the main result.
Cite as

Anuj Dawar and Gregory Wilsenach. Symmetric Circuits for Rank Logic. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 119, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dawar_et_al:LIPIcs.CSL.2018.20,
  author =	{Dawar, Anuj and Wilsenach, Gregory},
  title =	{{Symmetric Circuits for Rank Logic}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic (CSL 2018)},
  pages =	{20:1--20:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Ghica, Dan R. and Jung, Achim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.20},
  URN =		{urn:nbn:de:0030-drops-96870},
  doi =		{10.4230/LIPIcs.CSL.2018.20},
  annote =	{Keywords: fixed-point logic with rank, circuits, symmetric circuits, uniform families of circuits, circuit characterization, circuit framework, finite model theory, descriptive complexity}
}
  • Refine by Type
  • 7 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 2 2025
  • 1 2022
  • 1 2021
  • 1 2020
  • Show More...

  • Refine by Author
  • 6 Dawar, Anuj
  • 3 Wilsenach, Gregory
  • 2 Pago, Benedikt
  • 1 Grädel, Erich
  • 1 Kawałek, Piotr
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Algebraic complexity theory
  • 4 Theory of computation → Circuit complexity
  • 3 Theory of computation → Finite Model Theory
  • 2 Theory of computation → Complexity theory and logic
  • 2 Theory of computation → Proof complexity
  • Show More...

  • Refine by Keyword
  • 5 symmetric circuits
  • 3 counting width
  • 2 Boolean circuits
  • 2 Cai-Fürer-Immerman constructions
  • 2 Weisfeiler-Leman dimension
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact