Department Seminar

Title: Packing, combinatorial Macbeath regions, and semi-algebraic set systems
Speaker: Arijit Ghosh (ISI Kolkata)
Details: Mon, 6 Nov, 2017 3:00 PM @ A M Turing Hall
Abstract:: The packing lemma of Haussler (Journal of Combinatorial Theory, Series A, 1995) states that given a set system with bounded VC dimension, if every pair of sets in the set system has large symmetric difference, then the set system cannot contain too many sets. This has turned out to be the technical foundation for many results in combinatorial geometry and discrepancy. Recently it was generalized by Dutta et al. (Discrete & Computational Geometry, 2016) and Mustafa (Discrete & Computational Geometry, 2016) to the shallow packing lemma, applying to set systems as a function of their shallow-cell complexity. We proved the following new results related to packings:
  1. An optimal lower bound for shallow packings, thus settling the open question in Ezra (SIAM Journal on Computing, 2016) and Dutta et al. (Discrete & Computational Geometry, 2016).
  2. Improved bounds on combinatorial Macbeath regions, or Mnets, providing a combinatorial analog to Macbeathregions in convex geometry (Annals of Mathematics, 1952). This resolves the main open problem in Mustafa and Ray (Discrete & Computational Geometry, 2016).
  3. Mnets provide a general, more powerful framework from which the state-of-the-art unweighted Epsilon-net results of Varadarajan (STOC, 2010) and Chan et al. (SODA, 2012) follow immediately.
  4. Our upper bounds on Mnets for general semialgebraic set systems are asymptotically tight. We also give a more precise lower bound in terms of shallow-cell complexity.
  5. Simplifying and generalizing one of the main technical tools in Fox et al. (Journal of the European Mathematical Society, to appear). Besides using the packing lemma and a combinatorial construction, our proofs combine tools from the polynomial partitioning of Guth and Katz (Annals of Mathematics, 2014) and the probabilistic method.


Announcements from Dept.

  • Nov 8, 2024 : CSE Words Meeting (read more)
  • Sep 13, 2024 : CSE Words Meeting (read more)
  • May 13, 2024 : MS-PhD Admissions (Jul 2024) - List of Recommended Candidates (read more)
(View All)
© 2016 - All Rights Reserved - Dept of CSE, IIT Madras
Website Credits