\indent In this talk we will prove the following obstruction result to
functors extending the Zariski spectrum: every contravariant functor from rings to sets whose restriction to the full subcategory of commutative rings is isomorphic to Spec must assign the empty set to complex matrix algebras of order at least 3. The proof relies crucially on the Kochen-Specker "no-hidden-variables" theorem of quantum mechanics. We will also discuss a (very) recent generalization of the result due to van den Berg and Heunen.

The talk will give an introduction
to this new branch of compressed sensing.
One has an affine subspace intersect the positive semideinite (PSD)
matrices and wishes to find a smallest rank
matrix therein. This is a highly nonconvex
problem. Minimizing the trace is a convex problem
which often gives the correct answer. There is an
elegant probablistic analysis which applies in some
situations. The talk gives an exposition of this.

\indent Improvements of the obvious lower bounds on the independence number of (hyper)graphs have had impact on problems in discrete geometry, coding theory, number theory and combinatorics. One of the most famous examples is the result of Komlos-Pintz-Szemeredi (1982) on the independence number of 3-uniform hypergraphs which made important progress on the decades old Heilbronn problem. We give a sharp upper bound on the chromatic number of simple k-uniform hypergraphs that implies the above result as well as more general theorems due to Ajtai-Komlos-Pintz-Spencer-Szemeredi, and Duke-Lefmann-Rodl. Our proof technique is inspired by work of Johansson on graph coloring and uses the semi-random or nibble method. This is joint work with Alan Frieze.