Exploring the Frontiers of Feasible Computation. The project aims to delineate the boundary between feasible and infeasible computational problems. A problem is considered feasible if there is an algorithm to solve it in worst-case time bounded by a polynomial in the input size. This is probably impossible for the important class of NP-complete problems. However, typical examples of NP-complete problems can often be solved in polynomial time, because worst-case problems are rare. The project is ....Exploring the Frontiers of Feasible Computation. The project aims to delineate the boundary between feasible and infeasible computational problems. A problem is considered feasible if there is an algorithm to solve it in worst-case time bounded by a polynomial in the input size. This is probably impossible for the important class of NP-complete problems. However, typical examples of NP-complete problems can often be solved in polynomial time, because worst-case problems are rare. The project is relevant to public-key cryptography, where breaking an encryption scheme should be infeasible, and to many real-life situations where NP-complete problems need to be solved, either exactly or approximately.Read moreRead less
Continued Fractions and Torsion on Hyperelliptic Curves. Scientific advance should not blindly add to our knowledge; a true advance brings insights that collapse different issues into one. Understanding more is to need to remember less. For an important class of examples, this project identifies the study of a fundamental invariant of a quadratic number field, its regulator and hence its class number, with maximum torsion on the Jacobian variety of an hyperelliptic curve. The investigator's meth ....Continued Fractions and Torsion on Hyperelliptic Curves. Scientific advance should not blindly add to our knowledge; a true advance brings insights that collapse different issues into one. Understanding more is to need to remember less. For an important class of examples, this project identifies the study of a fundamental invariant of a quadratic number field, its regulator and hence its class number, with maximum torsion on the Jacobian variety of an hyperelliptic curve. The investigator's methods will surprise some longstanding problems into submission and in particular will lead them to reveal full data on torsion on hyperelliptic curves of low genus.
Read moreRead less