Tata Institute of Fundamental Research
Packing, Combinatorial Macbeath Regions and Semi-algebraic Set Systems
STCS Seminar
Speaker:
Arijit Ghosh (Indian Statistical Institute
ACM Unit
203 Barrackpore Trunk Road
Kolkata 700108)
Organiser:
Kavitha Telikepalli
Date:
Wednesday, 26 Jul 2017, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
The packing lemma of Haussler (J. of Comb. Theory, Ser. A, 1995) states that given a set system with bounded VC dimension, if every pair of sets in the set system have 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. (Disc. & Compt. Geom., 2016) and Mustafa (Disc. & Compt. Geom., 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 J. on Computing, 2016) and Dutta et al. (Disc. & Comput. Geom., 2016).
Improved bounds on combinatorial Macbeath regions, or Mnets, providing a combinatorial analogue to Macbeath regions in convex geometry (Ann. of Math., 1952).
This resolves the main open problem in Mustafa and Ray (Disc & Comput. Geom., 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. (J. of the Euro. Math. Soc., to appear). Besides using the packing lemma and a
combinatorial construction, our proofs combine tools from polynomial partitioning of Guth and Katz (Ann. of Math., 2014) and the probabilistic method.
| Speaker: | Arijit Ghosh (Indian Statistical Institute ACM Unit 203 Barrackpore Trunk Road Kolkata 700108) |
| Organiser: | Kavitha Telikepalli |
| Date: | Wednesday, 26 Jul 2017, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
The packing lemma of Haussler (J. of Comb. Theory, Ser. A, 1995) states that given a set system with bounded VC dimension, if every pair of sets in the set system have 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. (Disc. & Compt. Geom., 2016) and Mustafa (Disc. & Compt. Geom., 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 J. on Computing, 2016) and Dutta et al. (Disc. & Comput. Geom., 2016).
Improved bounds on combinatorial Macbeath regions, or Mnets, providing a combinatorial analogue to Macbeath regions in convex geometry (Ann. of Math., 1952).
This resolves the main open problem in Mustafa and Ray (Disc & Comput. Geom., 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. (J. of the Euro. Math. Soc., to appear). Besides using the packing lemma and a
combinatorial construction, our proofs combine tools from polynomial partitioning of Guth and Katz (Ann. of Math., 2014) and the probabilistic method.
An optimal lower bound for shallow packings, thus settling the open question in Ezra (SIAM J. on Computing, 2016) and Dutta et al. (Disc. & Comput. Geom., 2016).
Improved bounds on combinatorial Macbeath regions, or Mnets, providing a combinatorial analogue to Macbeath regions in convex geometry (Ann. of Math., 1952).
This resolves the main open problem in Mustafa and Ray (Disc & Comput. Geom., 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. (J. of the Euro. Math. Soc., to appear). Besides using the packing lemma and a
combinatorial construction, our proofs combine tools from polynomial partitioning of Guth and Katz (Ann. of Math., 2014) and the probabilistic method.