Testing Polynomial Identities with Fewer Random Bits
Can You Fool a Polynomial without Rolling Dice?
(Sprache: Englisch)
Testing if a multivariate polynomial given as an arithmetic circuit is identically zero is a fundamental problem in the theory of computation. It has been studied by computer scientists and mathematicians for about thirty years. From early on, there have...
Leider schon ausverkauft
versandkostenfrei
Buch (Kartoniert)
50.40 €
- Lastschrift, Kreditkarte, Paypal, Rechnung
- Kostenlose Rücksendung
Produktdetails
Produktinformationen zu „Testing Polynomial Identities with Fewer Random Bits “
Klappentext zu „Testing Polynomial Identities with Fewer Random Bits “
Testing if a multivariate polynomial given as an arithmetic circuit is identically zero is a fundamental problem in the theory of computation. It has been studied by computer scientists and mathematicians for about thirty years. From early on, there have been efficient randomized algorithms solving the problem. However, designing efficient algorithms that use fewer or no random bits at all has turned into a notorious open problem over the years. By now, it is understood that a deterministic algorithm for general arithmetic circuits would have major consequences in theoretical computer science. To approach this goal, it is worthwhile to understand the randomness complexity of polynomial identity testing in restricted models. In this book, we consider some natural and well-studied models in which we obtain new results.
Autoren-Porträt von Moritz Hardt
Hardt, MoritzMoritz received a Master\'s degree in Computer Science from Saarland University in 2007. His senior year he spent abroad as a research scholar in the Computer Science Department at Carnegie Mellon University. Currently, Moritz is a PhD student in Computer Science at Princeton University with a keen interest in complexity theory, algorithms and cryptography.
Bibliographische Angaben
- Autor: Moritz Hardt
- 2008, 52 Seiten, Maße: 15 x 22 cm, Kartoniert (TB), Englisch
- Verlag: VDM Verlag Dr. Müller e.K.
- ISBN-10: 3639025423
- ISBN-13: 9783639025422
Sprache:
Englisch
Kommentar zu "Testing Polynomial Identities with Fewer Random Bits"
Schreiben Sie einen Kommentar zu "Testing Polynomial Identities with Fewer Random Bits".
Kommentar verfassen