@inproceedings{M-Characterizing-Arithmetic-Circuit-Classes-By-Constraint-Satisfaction-Problems,
Title = {Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems},
Author = {Stefan Mengel},
Booktitle = {In Proceedings of ICALP 2011},
Pages = {700-711},
Year = {2011},
Volume = {6755},
Publisher = {Springer},
Series = {Lecture Notes in Computer Science},
Abstract = {We explore the expressivity of constraint satisfaction problems (CSPs) in the arithmetic circuit model. While CSPs are known to yield VNP-complete polynomials in the general case, we show that for different restrictions of the structure of the CSPs we get characterizations of different arithmetic circuit classes. In particular we give the first natural non-circuit characterization of VP, the class of polynomial families efficiently computable by arithmetic circuits.},
Url = {http://www3.math.tu-berlin.de/algebra/work/cspfull.pdf},
Reviewed = {True}
}