Too Good to be True? Precisely! The Real Cost of Non-Standard Computation

Add to your list(s) Download to your calendar using vCal

• Ed Blakey (University of Bristol)
• Thursday 02 February 2012, 14:15-15:15
• MR4, Centre for Mathematical Sciences.

If you have a question about this talk, please contact Paul Skrzypczyk.

Certain (unconventional, non-Turing) computers give the illusion of efficiency, whilst being fundamentally impracticable. The illusion stems from the computers’ polynomial time and space complexity, the impracticability from their exponential complexity with respect to computational resources other than time and space (precision, for example, is such a resource). From previous research, we recap a paradigm- and resource-independent framework of computational complexity that dispels this illusion. From immanent research, we mention an application of the framework to Shor’s algorithm (the question here is ‘what is the precision complexity of Shor’s algorithm?’). And from proposed research, we describe an extension of the framework from complexity-theoretic to cryptographic concerns.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR4, Centre for Mathematical Sciences
• bld31

Note that ex-directory lists are not shown.