4 papers · 1 filter
Observations on Symmetric Circuits
Christian Engels
We study symmetric arithmetic circuits and improve on lower bounds given by Dawar and Wilsenach (ArXiv 2020). Their result showed an exponential lower bound of the permanent comput…
Lower Bounds of Algebraic Branching Programs and Layerization
Christian Engels
In this paper we improve the lower bound of Chatterjee et al.\ (ECCC 2019) to an lower bound for unlayered Algebraic Branching Programs. We also study the impact layerizat…
Parameterized Valiant's Classes
Markus Blaeser, Christian Engels
We define a theory of parameterized algebraic complexity classes in analogy to parameterized Boolean counting classes. We define the classes VFPT and VW[t], which mirror the Boolea…
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
Suryajith Chillara, Christian Engels, Nutan Limaye +1
We study the size blow-up that is necessary to convert an algebraic circuit of product-depth to one of product-depth in the multilinear setting. We show that for every po…