Document Open Access Logo

Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371)

Authors Markus Bläser, Valentine Kabanets, Ronen Shaltiel, Jacobo Torán and all authors of the abstracts in this report



PDF
Thumbnail PDF

File

DagRep.12.9.41.pdf
  • Filesize: 2.25 MB
  • 19 pages

Document Identifiers

Author Details

Markus Bläser
  • Universität des Saarlandes - Saarbrücken, DE
Valentine Kabanets
  • Simon Fraser University - Burnaby, CA
Ronen Shaltiel
  • University of Haifa, IL
Jacobo Torán
  • Universität Ulm, DE
and all authors of the abstracts in this report

Cite AsGet BibTex

Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán. Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). In Dagstuhl Reports, Volume 12, Issue 9, pp. 41-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/DagRep.12.9.41

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 2237 "Algebraic and Analytic Methods in Computational Complexity". Computational Complexity is concerned with the resources that are required for algorithms to detect properties of combinatorial objects and structures. It has often proven true that the best way to argue about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Beside algebraic methods, analytic methods have been used for quite some time in theoretical computer science. These methods can also be used to solve algebraic problems as show by many recent examples in the areas of derandomization, coding theory or circuit lower bounds. These new directions were in the focus of the Dagstuhl Seminar and reflect the developments in the field since the previous Dagstuhl Seminar 18391. This Dagstuhl Seminar brought together researchers who are using a diverse array of algebraic and analytic methods in a variety of settings. Researchers in these areas are relying on ever more sophisticated and specialized mathematics and this seminar played a role in educating a diverse community about the latest new techniques, spurring further progress.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
  • Theory of computation → Circuit complexity
  • Theory of computation → Problems, reductions and completeness
  • Theory of computation
Keywords
  • (de-)randomization
  • algebra
  • circuits
  • coding
  • computational complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail