(2^j,3^j,5^j,...,pn^j) for j=0,1,2,...,2t-1
where pn is the n'th prime and t is the number of terms of the polynomial. To make the method efficient one runs it modulo a sufficiently large prime p. If d is the degree of the polynomial then we need p of size O( d log n ) bits which can be very big.
Another choice is to pick a prime p of a certain form, pick elements w1,w2,...,wn of relatively prime order in GF(p) evaluate at
(w1^j,w2^j,...,wn^j) for j=0,1,2,...,2t-1.
This approach leads to computing discrete logarithms in GF(p) which is feasible because p is constructed so that p-1 has small factors. The advantage of this approach is that the size of the prime p needed is O( n log d ) bits.
For the polynomial GCD problem, however, we have to deal with unlucky evaluation points. They break the point sequence. In the talk we will present some ideas for how to fix the methods. We give some results for the distribution of unlucky evaluation points. We have implemented a multivariate GCD code in Cilk C using the discrete logarithm approach to investigate it's power. We present benchmarks comparing our code with Zippel's GCD algorithm in Maple and the Hensel lifting GCD algorithm in Magma.
This is joint work with Adriano Aarce, Lucas Hu, and Hao Zhuang.
Professor Tony F Chan assumed the presidency of HKUST on 1 September 2009.
Professor Chan’s scientific background is in Mathematics, Computer Science and Engineering. He received his PhD in Computer Science from Stanford University. He taught at Yale University before joining UCLA as Professor of Mathematics in 1986. He was appointed Chair of the Department of Mathematics in 1997 and served as Dean of Physical Sciences from 2001 to 2006. From 2006 to 2009, Professor Chan was Assistant Director of the Mathematical and Physical Sciences Directorate at the U.S. National Science Foundation (NSF).
Professor Chan is an elected member of the US National Academy of Engineering (NAE), a senior member of the Institute of Electrical and Electronic Engineers (IEEE) and an elected fellow of both the Society for Industrial and Applied Mathematics (SIAM) and the American Association for the Advancement of Science. Professor Chan was one of the world’s most cited mathematicians.
Professor Chan is currently a member of the Board of Trustees of the King Abdullah University of Science and Technology (KAUST) in Saudi Arabia, President’s Advisory Council of the Korea Advanced Institute of Science and Technology (KAIST), Scientific Advisory Board of the University of Vienna, and the United States Committee of 100. Professor Chan is also a member of the Advisory Committee on Innovation and Technology of the Hong Kong Government. He was a member of the Selection Committee for the Shaw Prize in Mathematical Sciences in 2012 and 2013.
This thesis compares six WordNet-based methods and two context-based
algorithmic approaches to extract synonyms from two different types of
requirement documents. The eight methods were compared by their recall.
The experiments results showed that the word co-occurrence-based method
achieved the best recall in identifying synonyms of the software
requirements documents. Further experiments showed that setting the
parameters of the word co-occurrence-based method impacts the results
of the experiments as well. The thesis also discusses potential issues
of the word co-occurrence-based method in the design of the
experiments. The document author's personal factors could influence the
experiment results, but this influence can be avoided with careful
Joint work with H. Klaja and T. Ransford.
This talk is based on two joint papers: one with M. Huang and P. Ravi (2013)and the other with P. Ravi (2015).