Show simple item record

dc.contributor.authorDawar, Anujen
dc.contributor.authorWilsenach, Gregoryen
dc.contributor.editorCzumaj, Aen
dc.contributor.editorDawar, Aen
dc.contributor.editorMerelli, Een
dc.date.accessioned2020-08-11T23:30:39Z
dc.date.available2020-08-11T23:30:39Z
dc.date.issued2020en
dc.identifier.isbn978-3-95977-138-2en
dc.identifier.issn1868-8969
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/309008
dc.description.abstractWe 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.
dc.publisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
dc.rightsAttribution 4.0 International
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/
dc.titleSymmetric Arithmetic Circuits.en
dc.typeConference Object
prism.endingPage36:1
prism.publicationDate2020en
prism.publicationNameICALPen
prism.publicationName47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference).en
prism.startingPage36:1
prism.volume168en
dc.identifier.doi10.17863/CAM.56098
dcterms.dateAccepted2020-04-28en
rioxxterms.versionVoR
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2020en
dc.contributor.orcidDawar, Anuj [0000-0003-4014-8248]
rioxxterms.typeConference Paper/Proceeding/Abstracten
pubs.funder-project-idEPSRC (EP/S03238X/1)
dc.identifier.urlhttp://www.informatik.uni-trier.de/~ley/db/conf/icalp/icalp2020.htmlen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

Attribution 4.0 International
Except where otherwise noted, this item's licence is described as Attribution 4.0 International