Document Open Access Logo

On Some Recent Advances in Algebraic Complexity (Invited Talk)

Author Amir Shpilka

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2020.6.pdf
  • Filesize: 203 kB
  • 1 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • Algebraic Complexity
  • Arithmetic Circuits
  • Polynomial Identity Testing

Metrics

Abstract

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.

Cite As Get BibTex

Amir Shpilka. On Some Recent Advances in Algebraic Complexity (Invited Talk). In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, p. 6:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSTTCS.2020.6

Author Details

Amir Shpilka
  • School of Computer Science, Tel Aviv University, Israel

Funding

  • Shpilka, Amir: Supported by the Israel Science Foundation (grant number 514/20) and by the Len Blavatnik and the Blavatnik Family foundation-
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact