NDLI: Solving polynomial systems (invited talk abstract): a complexity theory viewpoint

Please wait, while we are loading the content...

Representing and handling mathematical concepts by humans and machines (invited talk abstract)

Solving polynomial systems (invited talk abstract): a complexity theory viewpoint

Computation in word-hyperbolic groups (invited talk abstract)

Factorization in Z[x]: the searching phase

Hypergeometric dispersion and the orbit problem

Deciding linear-trigonometric problems

Algorithms for near-rings of non-linear transformations

An improved algorithm for the resolution of singularities

Computing canonical representatives of regular differential ideals

Improved projection for CAD's of $R^{3}$

On accelerated methods to evaluate sums of products of rational numbers

Conditions for exact resultants using the Dixon formulation

Multiprecision floating point addition

Computing the Galois group of a polynomial using linear differential equations

Local quantifier elimination

Integer Smith form via the valence: experience with large sparse matrices from homology

Black box Frobenius decompositions over small fields

A method for deciding whether the Galois group is abelian

Linear differential equations, iterative logarithms and orderings on monomial differential extensions

Constructing endomorphism rings via duals

Bounds on numers of vectors of multiplicities for polynomials which are easy to compute

Fast practical algorithms for the Boolean-product-witness-matrix problem

Advanced notations in mathematica

Pseudofactors of multivariate polynomials

An exact real algebraic arithmetic with equality determination

Fast randomized algorithms for the structure of matrix algebras over finite fields (extended abstract)

An algorithm for the eigenvalue perturbation problem: reduction of a κ-matrix to a Lidskii matrix

Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm

Symbolic parametrization of pipe and canal surfaces

Computing an equidimensional decomposition of an algebraic variety by means of geometric resolutions

Metric invariants of tetrahedra via polynomial elimination

Computing normalizers of permutation groups efficiently using isomorphisms of association schemes

On the design and implementation of Brown's algorithm over the integers and number fields

Solving projective complete intersection faster

Rational solutions of singular linear systems

Some remarks on parallel exponentiation (extended abstract)

Further evaluation of Java for symbolic computation

Matrix structure, polynomial arithmetic, and erasure-resilient encoding/decoding

Determination of maximal symmetry groups of classes of differential equations

Solving systems of linear one-sided equations in integer monoid and group rings

How to check if a finitely generated commutative monoid is a principal ideal commutative monoid

Proper parametrization of surfaces with a rational pencil

Rectangular corner cutting and Sylvester A-resultants

Solving polynomial systems (invited talk abstract): a complexity theory viewpoint

Content Provider	ACM Digital Library
Author	Cucker, Felipe
Abstract	During the last few decades two traditions of computing have grown and grown further apart.Firstly, there is the tradition of discrete computation. It has its roots in work in mathematical logic at the truth of the century involving the decidability of the arithmetic. Abstract computational devices such as the Turing machine and computability concepts such as recursive function are legacies of this tradition.Secondly, there is the long-standing tradition of algorithmics results in algebra and analysis which we will refer to as the numerical tradition. Algorithms such as Gaussian elimination or Newton's method and negative results such as Galois' theorem on the non-solvability by radicals of polynomial equations of degree at least 5 are legacies of this tradition.The arrival of the digital computer set a stage in which both traditions could meet. The need of feasibility in practice for computable functions brought along the need for a complexity theory. But while the discrete tradition was very successful at building such a theory, at the end of the 80's there was little akin to complexity theory within the numerical tradition.This difference in the theoretical foundations for both traditions is apparent in the 1989 SIAM's John von Neumann Lecture given by Steve Smale [4]. The following table is taken from there (below, “Scientific computation” corresponds to the numerical tradition and “Computer Science” to the discrete one). Models of computations are abstract devices designed to model computations in the real world and set a formal framework in which the power and limitations of computation can be rigorously proved. Real world computations, however, depend on too many parameters and the consideration of all of them would make the abstract model too cumbersome and therefore useless. A key question is how does one select a set of features to be considered in the formal model.In this talk we shall try to motivate one such choice (with two main variants) for a model of computation over the real numbers. Then, we shall survey some advances towards the laying of foundations within the numerical tradition as suggested in [4].Some of the work laying these foundations can be traced back some decades, for instance, to the work of Turing [5]. Some other is more recent (e.g. the foundational paper [2]). Two appropriate references for our talk are [1, 3].
File Format	PDF
ISBN	1581132182
DOI	10.1145/345542.345557
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2000-07-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Application of a theory of simulation to models of mobile communication systems (invited talk) (abstract only)

The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)

Invited Talk Abstract

Object-oriented queries over software systems: (abstract of invited talk)

2001 (Invited talk. Abstract only): a statistical odyssey

Operating systems specialization (invited talk) (abstract only): experiences, opportunities and challenges

Fixed Point Computation Problems and Facets of Complexity (Invited Talk)

Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk)

Evaluation opportunities in mechanized theories (invited talk abstract).

Solving polynomial systems (invited talk abstract): a complexity theory viewpoint

Similar Documents

Application of a theory of simulation to models of mobile communication systems (invited talk) (abstract only)

The Polynomial Method in Circuit Complexity Applied to Algorithm Design (Invited Talk)

Invited Talk Abstract

Object-oriented queries over software systems: (abstract of invited talk)

2001 (Invited talk. Abstract only): a statistical odyssey

Operating systems specialization (invited talk) (abstract only): experiences, opportunities and challenges

Fixed Point Computation Problems and Facets of Complexity (Invited Talk)

Examining classical graph-theory problems from the viewpoint of formal-verification methods (invited talk)

Evaluation opportunities in mechanized theories (invited talk abstract).

Solving polynomial systems (invited talk abstract): a complexity theory viewpoint