for this workshop
Hereditary discrepancy and factorization norms
at the
American Institute of Mathematics, San Jose, California
organized by
Aleksandar Nikolov and Kunal Talwar
This workshop, sponsored by AIM and the NSF, will be devoted to the application of methods from functional analysis and asymptotic convex geometry to combinatorial discrepancy theory.
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 norm;
- 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 measure.
The workshop will differ from typical conferences in some regards. Participants will be invited to suggest open problems and questions before the workshop begins, and these will be posted on the workshop website. These include specific problems on which there is hope of making some progress during the workshop, as well as more ambitious problems which may influence the future activity of the field. Lectures at the workshop will be focused on familiarizing the participants with the background material leading up to specific problems, and the schedule will include discussion and parallel working sessions.
The deadline to apply for support to participate in this workshop has passed.
For more information email workshops@aimath.org
