Add to Outlook calendar Add to Google calendar

Algebra & Combinatorics Seminar

Title: Closures, Coverings, and Complexity
Speaker: S. Venkitesh (IIT, Bombay)
Date: 26 August 2022
Time: 4 pm
Venue: LH-1, Mathematics Department

The polynomial method is an ever-expanding set of algebraic techniques, which broadly entails capturing combinatorial objects by algebraic means, specifically using polynomials, and then employing algebraic tools to infer their combinatorial features. While several instances of the polynomial method have been part of the combinatorialist’s toolkit for decades, development of this method has received more traction in recent times, owing to several breakthroughs like (i) Dvir’s solution (2009) to the finite-field Kakeya problem, followed by an improvement by Dvir, Kopparty, Saraf, and Sudan (2013), (ii) Guth and Katz (2015) proving a conjecture by Erdös on the distinct distances problem, (iii) solutions to the capset problem by Croot, Lev, and Pach (2017), and Ellenberg and Gijswijt (2017), to name a few.

One of the ways to employ the polynomial method is via the classical algebraic objects – (affine) Zariski closure, (affine) Hilbert function, and Gröbner basis. Owing to their applicability in several areas like computational complexity, combinatorial geometry, and coding theory, an important line of enquiry is to understand these objects for ‘structured’ sets of points in the affine space. In this talk, we will be mainly concerned with Zariski closures of symmetric sets of points in the Boolean cube.

Firstly, we will look at a combinatorial characterization of Zariski closures of all symmetric sets, and its application to some hyperplane and polynomial covering problems for the Boolean cube, over any field of characteristic zero. We will also briefly look at Zariski closures over fields of positive characteristic, although much less is known in this setting. Secondly, we will see a simple illustration of a ‘closure statement’ being used as a technique for proving bounds on the complexity of approximating Boolean functions by polynomials. We will conclude with some open questions on Zariski closures motivated by problems on these two fronts.

Some parts of this talk will be based on the works: https://arxiv.org/abs/2107.10385, https://arxiv.org/abs/2111.05445, https://arxiv.org/abs/1910.02465.


Contact: +91 (80) 2293 2711, +91 (80) 2293 2265 ;     E-mail: chair.math[at]iisc[dot]ac[dot]in
Last updated: 09 Dec 2022