The Oxford Advanced Seminar on Informatic Structures

Introduction to OASIS

Michaelmas 2004

Hilary 2005

Trinity 2005

Michaelmas 2005

Hilary 2006

Trinity 2006

Michaelmas 2006

Hilary 2007

Trinity 2007

Michaelmas 2007

Hilary 2008

Trinity 2008

Michaelmas 2006

NON-CLASSICAL STRUCTURES

Talks are Friday afternoons at 2:00pm in the Fox Room of the Computing Laboratory, except for Georg Gottlob's talk which will be at 4:00pm. The Computing Laboratory is located at the corner of Parks road and Keble road. Abstracts can be found at the bottom of this page. Everyone is welcome!

• Friday 20 October (week 2; 4PM) [Georg Gottlob] (OUCL) Second Order Logic over Finite Structures -- Report on a Research Program

• Friday 27 October (week 3) No OASIS talk this week since there is a [QUOXIC].

• Friday 3 November (week 4; 2PM) [Boris Zilber] (Oxford, Mathematical Institute) Logically perfect structures and quantum geometries

• Friday 24 November (week 7; 2PM) [Stephen Pulman] (OUCL) Comparatives

• Friday 1 December (week 8; 2PM) [Rudiger Schack] (Royal Holloway, London) Quantum random numbers

• Friday 8 December (week 9; 2PM) [Aram Harrow] (University of Bristol) Forget this talk (joint work with Peter Shor)

Georg Gottlob (OUCL): Second Order Logic over Finite Structures -- Report on a Research Program. Abstract: This talk reports about the results achieved so far in the context of a research programme in the intersection of logic, formal language theory, and complexity theory. The aim of this research programme is to classify the complexity of evaluating formulas from different prefix classes of second-order logic over diferent types of finite structures, such as strings, graphs, or arbitrary structures. In particular, we report on classifications of existential second-order logic on graphs.

Stephen Pulman (OUCL): Comparatives (this talk presupposes no linguistics background). Abstract: The literature in formal linguistic semantics contains a wealth of fine grained and detailed analyses of many linguistic phenomena. But very little of this work has found its way into implementations, despite a widespread feeling (among linguists at least) that this can't be very difficult in principle: you just fix a grammar to produce the right logical forms and hook them up to a theorem prover, don't you? In this talk I take a representative analysis of adjectival comparatives and ask what steps one might actually have to go through so as to use this analysis in a realistic setting. I then try to identify some general conclusions that can be drawn from this exercise. I will start with a brief overview of current practice in formal and computational semantics for natural language for a general audience.

Rudiger Schack (Royal Holloway, London): Quantum random numbers. Abstract: In precisely what way are random numbers generated by a quantum device superior to classically generated random numbers? This talk establishes that properties of the generated string such as its algorithmic complexity are not directly relevant to this question, and then shows that any answer to this question must depend on the interpretation of probabilities, and thus on the interpretation of quantum states. Most authors interpret probabilities derived from quantum states as objective. The talk explains why the objectivist approach is unlikely to provide insight into the nature of quantum random numbers. Alternatively, quantum states can be interpreted in a subjectivist way as representing Bayesian degrees of belief. Within the subjectivist approach, one can formulate and prove a theorem that captures in a precise way what is uniquely quantum about quantum random numbers.

Aram Harrow (University of Bristol): Forget this talk (joint work with Peter Shor). Abstract: Erasing correlations and destroying entanglement can be valuable resources for quantum communication. First I'll define coherent erasure as the time reversal of coherent classical communication, and will use this idea to give the first separations of forward and backward communication capacity for unitary gates. Next, I'll give an example---the quantum reverse Shannon theorem---of why it's helpful to be able to coherently destroy entanglement. I'll end with ideas about how to incorporate these new tasks into the traditional resource framework. Based on quant-ph/0511219.