2026-08-04T20:49:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13247 2024-03-06T10:51:55Z ddc:004 open_access

On Some Recent Advances in Algebraic Complexity (Invited Talk) Shpilka, Amir Algebraic Complexity Arithmetic Circuits Polynomial Identity Testing Algebraic complexity is the field studying the intrinsic difficulty of algebraic problems in an algebraic model of computation, most notably arithmetic circuits. It is a very natural model of computation that attracted a large amount of research in the last few decades, partially due to its simplicity and elegance, but mostly because of its importance. Being a more structured model than Boolean circuits, one could hope that the fundamental problems of theoretical computer science, such as separating P from NP, deciding whether P = BPP and more, will be easier to solve for arithmetic circuits. In this talk I will give the basic definitions, explain the main questions and how they relate to their Boolean counterparts, and discuss what I view as promising approaches to tackling the most fundamental problems in the field. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Amir Shpilka 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.6 urn:nbn:de:0030-drops-132472 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.6 eng https://creativecommons.org/licenses/by/3.0/legalcode