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