A general algebraic formalism for the mathematical modeling of physical systems is sketched. This formalism is sufficiently general to encompass classical and quantum-mechanical models. It is then explained in which way quantum theory differs in an essential way from classical theory and what it is that quantum theory tells us about Nature when suitable experiments are made. Some of the seemingly confusing aspects of quantum theory are highlighted, and it is explained why they actually should not confuse us.
In this talk we will discuss information complexity -- a measure of the amount of information Alice and Bob need to exchange to solve a problem over distributed inputs. We will present an information-theoretically optimal protocol for computing the AND of two bits distributed between Alice and Bob. We prove that the information complexity of AND is ~1.4923 bits. We use the optimal protocol and its properties to obtain tight bounds for the Disjointness problem, showing that the randomized communication complexity of Disjointness on n bits is ~0.4827n ± o(n).
For all practical purposes, the Micali-Vazirani algorithm, discovered in 1980, is still the most efficient known maximum matching algorithm (for very dense graphs, slight asymptotic improvement can be obtained using fast matrix multiplication). However, this has remained a ``black box" result for the last 32 years. We hope to change this with the help of a recent paper giving a simpler proof and exposition of the algorithm:
The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the existence of proofs that can be verified by reading a very small part of the proof. Since the discovery of the theorem, there has been a considerable work on improving the theorem in terms of the length of the proofs, culminating in the construction of PCPs of quasi-linear length, by Ben-Sasson and Sudan (SICOMP 38(2)) and Dinur (J. ACM 54(3)).
We consider Galois cohomology groups over function fields F of curves that are defined over a complete discretely valued field.
Motivated by work of Kato and others for n=3, we show that local-global principles hold for
H^n(F, Z/mZ(n-1)) for all n>1.
In the case n=1, a local-global principle need not hold. Instead, we will see that the obstruction to a local-global principle for H^1(F,G), a Tate-Shafarevich set, can be described explicitly for many (not necessarily abelian) linear algebraic groups G.