EUVIMEDEUVIMED entdecken
Crossref

Partial Derivatives in Arithmetic Complexity and Beyond

Xi Chen, Neeraj Kayal, Avi Wigderson

Foundations and Trends® in Theoretical Computer Science · 2011

DOI: 10.1561/0400000043 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Foundations and Trends® in Theoretical Computer Science, 2011. Verfasst von Xi Chen und 2 weiteren Autor:innen. Die Arbeit wurde bisher 27-mal zitiert (Crossref) und nennt 90 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

How complex is a given multivariate polynomial? The main point of this survey is that one can learn a great deal about the structure and complexity of polynomials by studying (some of) their partial derivatives. The bulk of the survey shows that partial derivatives provide essential ingredients in proving both upper and lower bounds for computing polynomials by a variety of natural arithmetic models. We will also see applications which go beyond computational complexity, where partial derivatives provide a wealth of structural information about polynomials (including their number of roots, reducibility and internal symmetries), and help us solve various number theoretic, geometric, and combinatorial problems.

Zitieren

APA

Chen, X., Kayal, N., & Wigderson, A. (2011). Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends® in Theoretical Computer Science. https://doi.org/10.1561/0400000043

Vancouver

Chen X, Kayal N, Wigderson A. Partial Derivatives in Arithmetic Complexity and Beyond. Foundations and Trends® in Theoretical Computer Science. 2011. doi:10.1561/0400000043

BibTeX
@article{Chen2011,
  author = {Chen, Xi and Kayal, Neeraj and Wigderson, Avi},
  title = {Partial Derivatives in Arithmetic Complexity and Beyond},
  journal = {Foundations and Trends® in Theoretical Computer Science},
  year = {2011},
  doi = {10.1561/0400000043}
}
Kostenlos starten →