Hereditary discrepancy and factorization norms

February 29 to March 4, 2016

at the

American Institute of Mathematics, San Jose, California

organized by

Aleksandar Nikolov and Kunal Talwar

Original Announcement

This workshop 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:

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:

An algorithm for Komlós conjecture matching Banaszczyk's bound
by  Nikhil Bansal, Daniel Dadush, and Shashwat Garg,  57th Annual IEEE Symposium on Foundations of Computer Science–FOCS 2016, 788–799, IEEE Computer Soc., Los Alamitos, CA, 2016.  MR3631042
Algorithmic discrepancy beyond partial coloring
by  Nikhil Bansal and Shashwat Garg
Towards a constructive version of Banaszczyk's vector balancing theorem
by  Daniel Dadush, Shashwat Garg, Shachar Lovett, and Aleksandar Nikolov,  Approximation, randomization, and combinatorial optimization. Algorithms and techniques, Art. No. 28, 12 pp., LIPIcs. Leibniz Int. Proc. Inform., 60, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016  MR3566770