Incidence geometry is a part of combinatorics that studies the
intersection patterns of geometric objects. For example, suppose
that we have a set of L lines in the plane. A point is called
r-rich if it lies in r different lines from the set. For a...
olynomials are a special class of functions. They are useful in
many branches of mathematics, often in problems which don't mention
polynomials. We discuss two examples: polynomials in
error-correcting codes and polynomials in geometric
inequalities...
In 2007, Zeev Dvir shocked experts by giving a one-page proof of
the finite field Kakeya problem. The new idea in the proof was to
introduce high degree polynomials into a problem about points and
lines. This idea has led to progress on several...
There are two important measures of the complexity of a boolean
function: the sensitivity and block sensitivity. Whether or not
they are polynomial related remains a major open question. In this
talk I will survey some known results on this...
fundamental theorem in linear algebra is that any real n x d
matrix has a singular value decomposition (SVD). Several important
numerical linear algebra problems can be solved efficiently once
the SVD of an input matrix is computed: e.g. least...
We discuss three areas of algorithmic game theory that have
grappled with intractability. The first is the complexity of
computing game-theoretic equilibria, like Nash equilibria. There is
an urgent need for new ideas on this topic, to enable...