[eas_cs_seminars] 9th May 2017

[Luca Rossi]

Please note that the seminar is starting in 5 mins in MB108.

Best,
Luca

On 9 May 2017 at 10:28, Luca Rossi <l.rossi at aston.ac.uk> wrote:

> Hi all,
>
> This is just a reminder of today's seminar "Introduction to second order
> complexity theory" by Florian Steinberg (http://www.mathematik.tu-darm
> stadt.de/~steinberg/).
>
> The talk will be in MB108 from *11am* to 12.30am.
>
> Best,
> Luca
>
> On 4 May 2017 at 21:11, Luca Rossi <l.rossi at aston.ac.uk> wrote:
>
>> Dear all,
>>
>> Next week our CS seminar series will host Florian Steinberg (
>> http://www.mathematik.tu-darmstadt.de/~steinberg/) who will give a talk
>> titled "Introduction to second order complexity theory". The talk will be
>> held in MB108 from 11am to 12.30am. *Please note the unusual place and
>> time*.
>>
>> Best,
>> Luca
>>
>> Abstract:
>> Classical computability and complexity theory use Turing machines as a
>> foundation for consideration of effectivity (computability) and efficiency
>> (polynomial-time computability) of operations on countable discrete
>> structures. For many applications in engineering it would be desirable to
>> not only compute on countable discrete structures but also to compute on
>> continuous structures like the real numbers. The most common model for
>> computation on the real numbers by digital computers are floating point
>> computations. Modeling real numbers by machine numbers is unsatisfactory
>> from a mathematical point of view as the content of a proof of correctness
>> of a mathematical algorithm is usually completely lost during an
>> implementation. A mathematical rigorous and realistic model for computation
>> on continuous structures is provided by computable analysis. The finite
>> strings as codes for elements of a structure are replaced by total string
>> functions that provide on demand information about the element they encode.
>> Functions between encoded spaces can then be computed by operating on Baire
>> space: The space of all total string functions. Computation on Baire space
>> is done using oracle Turing machines. Intuitively, oracle Turing machines
>> correspond to programs with function calls. It is not a priory clear which
>> of these programs should be considered fast. We introduce the accepted
>> class of polynomial-time computable operators on Baire space, i.e. we
>> specify what programs with function calls should be considered efficient.
>> The definition resembles classical polynomial-time computability very
>> closely (due to work by Kapron and Cook). However, there are some important
>> differences that we investigate in some detail.
>>
>> --
>> Luca Rossi
>>
>> Lecturer in Computer Science
>> School of Engineering and Applied Science
>> Aston University
>> Web: http://www.cs.aston.ac.uk/~rossil/
>> <http://www.cs.bham.ac.uk/~rossil/>
>>
>
>
>
> --
> Luca Rossi
>
> Lecturer in Computer Science
> School of Engineering and Applied Science
> Aston University
> Web: http://www.cs.aston.ac.uk/~rossil/
> <http://www.cs.bham.ac.uk/~rossil/>
>



-- 
Luca Rossi

Lecturer in Computer Science
School of Engineering and Applied Science
Aston University
Web: http://www.cs.aston.ac.uk/~rossil/ <http://www.cs.bham.ac.uk/~rossil/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.aston.ac.uk/pipermail/eas_cs_seminars/attachments/20170509/ba6a2ab5/attachment.html