UNIVERSITY OF HERTFORDSHIRE
COMPUTER SCIENCE RESEARCH COLLOQUIUM
presents
"Functions and Polynomials from the Computational
Point of View"
Gabor Horvath
(Algorithms Group, University of Hertfordshire)
October 3rd, 2007 (Wednesday)
Lecture Theatre E350
Hatfield, College Lane Campus
3 - 4 pm
Coffee/tea and biscuits will be available.
[Catering Permitting]
Everyone is Welcome to Attend
[Space Permitting]
Abstract:
Nowadays, computers are playing larger and larger role in scientific
research. This is especially true in mathematics where one often wants
to perform calculations or computations with a machine. In my research
I investigate the interaction of algebra and computer science. I
examine the connection of functions and polynomials calculating them
over certain algebraic structures (where a "polynomial" is an
expression built up by variables, constants and basic operations).
Computers are based on the 2 element Boolean algebra (using the NOT,
AND, OR logical operations). The Boolean algebra has the interesting
property that every function has a polynomial realization (functional
completeness), that is the reason for the computational completeness of
computers. It is not the only such algebraic structure, though. I
am especially in interested how a function can be calculated by polynomials
over these other functionally complete algebras.
My research area has three natural aspects:
1. Finding polynomials for functions: For a given function find a short
realizing polynomial which calculates the exact function.
2. Finding functions for polynomials: For two given polynomials decide
whether they realize the same function (equivalence problem)
3. Finding if polynomials agree somewhere: For two given polynomials
decide whether they attain the same value for some substitution
(equation solvability problem).
I am especially interested in the length of realizing polynomials and
computational complexity of the equivalence and the equation
solvability problems. I mostly considered these problems for finite
groups.
--------------------------------------------------
Hertfordshire Computer Science Research Colloquium
http://homepages.feis.herts.ac.uk/~nehaniv/colloq