Hereditary discrepancy and factorization norms
February 29 to March 4, 2016
American Institute of Mathematics,
San Jose, California
Aleksandar Nikolov and Kunal Talwar
This workshop will be devoted to the application of
methods from functional analysis and asymptotic convex geometry to combinatorial
Hereditary discrepancy is a combinatorial quantity associated with collections
of sets that has deep connections to uniformity of distributions and a number of
applications to theoretical computer science. Recent work by Nikolov and Talwar
showed that hereditary discrepancy is equivalent, up to logarithmic factors, to
a classical factorization norm from Banach space theory. This led to easier
proofs of classical results, and a much better understanding of the discrepancy
of some natural collections of sets, most prominently sets induced by
axis-aligned boxes in high dimension and by homogeneous arithmetic progressions.
The goal of this workshop is to refine the connections between functional
analysis and convex geometry, on one hand, and combinatorial discrepancy, on the
other, and to explore further the implications of such techniques. Some of our
goals for the workshop are to:
- make the connection between the gamma-2 factorization norm and hereditary
discrepancy fully constructive, for example by developing a constructive proof
of Banaszczyk's bound for the Komlos problem;
- show an analogue of the equivalence between the gamma-2 factorization norm
and hereditary discrepancy for other notions of combinatorial discrepancy, in
particular for the problem of balancing vectors with respect to an arbitrary
- find a geometric quantity, e.g. a different factorization constant, that
approximates hereditary discrepancy more tightly;
- exploit the power of factorization norms for bounding combinatorial
discrepancy, together with classical transference theorems, to give new
constructions of pointsets distributed uniformly relative to an arbitrary
Material from the workshop
A list of participants.
The workshop schedule.
A report on the workshop activities.
A list of open problems.
Papers arising from the workshop: