- 1 AHO, A., HOPCROFT, J., AND ULLMAN, J The Design and Analysis of Computer Algorzthms Addison-Wesley, Reading, Mass., 1974. Google Scholar
- 2 BIEBERBACH, L, AND BAUER, G Vorlesungen uber Algebra. B G Teubner Pubhshmg Co, Berhn, 1928.Google Scholar
- 3 CHAITIN, G., AND SCHWARTZ, J.T. A note on Monte Carlo pmnallty tests and algorithmic reformation theory Commun Pure Appl Math. (1978)Google Scholar
- 4 COLLINS, G.E The calculation of muluvanate polynomial resultants. J. A CM 18, 4 (Oct 197 i), 515-532 Google Scholar
- 5 COLLINS, G.E Computer algebra of polynomials and rattonal functions Amer. Math Monthly 80 (1973), 725-753Google Scholar
- 6 DAvxs, P.J. Proof, completeness, transccndentals, and samphng. J. ACM 24, 2 (April 1977), 298-310 Google Scholar
- 7 DUNFORD, N., AND SCHWARTZ, J T Linear Operators, Part II. Wfiey-lntersclence, New York and London, 1963.Google Scholar
- 8 FEKETE, M.uber dte Verteilung der Wurzeln bet Gew~ssen Algebraischen Glelchungen mit Ganzzahligen Koeffiztenten Math. Z. 17 (1927), 228-249.Google Scholar
- 9 FEKETE, M, AND SZEGO, G. On algebratc equations with integer coefficients whose roots belong to a given point set Math. Z. 63 (1955), 158-172Google Scholar
- 10 HEINDEL, L.E. integer anthmetlc algontluns for polynomial real zero determmatton. J. A CM 18, 4 (Oct. 1971), 533-548 Google Scholar
- 11 HERMANN, G. D~e Frage der Endlich Vtelen Schntte m der Theorie der Polynomidealen. Math. Ann. 95 (1926), 736-788Google Scholar
- 12 KAKEYA, S On approximate polynomials Tohoku Math J. 6 (1914), 182-186.Google Scholar
- 13 MARTIN, W A. Determmmg the equivalence of algebratc expressions by hash coding. J. ACM 18, 4 (Oct. 1971), 549-558. Google Scholar
- 14 MO~NCK, R Fast computation of GDC's Proc. 5th Ann ACM Symp on Theory of Computing, 1973, Austin, Texas, pp 42-151 Google Scholar
- 15 OKADA, Y On approximate polynomials with integer co~ffictents only Tohoku Math. Z 23 (1924), 26-35.Google Scholar
- 16 POLYA, G, ANn SZEGO, G Problems and Theorems in Analysis, vol 2 Sprmger-Vedag, New York, 1976.Google Scholar
- 17 RAaIN, M. Probabdtsttc algorithms In Algorithms and Complextty. New D:reclions and Recent Result.~ J.F. Traub, Ed, Academic Press, New York, 1976, pp. 21-39Google Scholar
- 18 SEIDENBERG, A.A new decision method for elementary algebra. Ann. Math. 60 (1954), 365-374.Google Scholar
- 19 TARSKI, A Declston Methodfor Elementary Algebra and Geometry, 2nd ed. University of California Press, Berkeley, Cahf., 1951.Google Scholar
- 20 VAN DER WAERDEN, B.L. Modern Algebra, vols. I, 11. Fredenck Ungar Publishing Co., New York, 1949, 1950.Google Scholar
- 21 VAN DER WAERDEN, B L.Emfuhrung m die Algebralsche Geometne, 2nd ed. Springer Verlag, New York, 1973Google Scholar
Index Terms
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
Recommendations
Characterizing the easy-to-find subgraphs from the viewpoint of polynomial-time algorithms, kernels, and Turing kernels
SODA '15: Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithmsWe study two fundamental problems related to finding subgraphs: (1) given graphs G and H, Subgraph Test asks if H is isomorphic to a subgraph of G, (2) given graphs G, H, and an integer t, Packing asks if G contains t vertex-disjoint subgraphs ...
Polynomial kernels for weighted problems
We use a technique by Frank and Tardos (Combinatorica 1987) to settle an open problem in kernelization.We present a polynomial kernelization for Knapsack parameterized by number of items.The method can be generally used to obtain polynomial kernels for ...
Probabilistic Autoreductions
Proceedings of the 42nd International Conference on SOFSEM 2016: Theory and Practice of Computer Science - Volume 9587We consider autoreducibility of complete sets for the two common types of probabilistic polynomial-time reductions: RP reductions containing one-sided errors on positive input instances only, and BPP reductions containing two-sided errors. Specifically, ...
Comments