Talks & Seminars
Title: Packing, combinatorial Macbeath regions, and semi-algebraic set systems
Dr. Arijit Ghosh, ISI Kolkata
Date & Time: January 11, 2018 10:30
Venue: CC 109 Room, 01st Floor, New CSE Bldg.
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 generalised 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: - 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). - 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). - 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. - 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. - 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.
Speaker Profile:
Arijit Ghosh received the Dual Degree (B.Tech and M.Tech) in Computer Science and Engineering form IIT Kharagpur, and PhD in Computer Science from INRIA Sophia Antipolis - Méditerranée. He was a Postdoctoral Researcher in Max Planck Institute for Informatics for 2 years and is currently a Ramanujan Fellow at ISI Kolkata. Broadly his research interests are in Theoretical Computer Science, and currently he is looking into Computational Geometry and Topology, Discrete geometry and applications of Probability Theory in Computer Science and Combinatorics.
List of Talks


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback