Speaker: Avi Wigderson
Title: Permanent & Determinant: non-identical twins
Abstract: The Determinant is undoubtedly the most important polynomial function in mathematics. Its lesser-known sibling, the Permanent, plays very important roles in enumerative combinatorics, statistical and quantum physics, and the theory of computation. In this lecture, I plan to survey some of the many remarkable properties of the permanent, its applications and impact on fundamental computational problems, its similarities to and apparent differences from the determinant, and how these relate to the P vs. NP problem.
This lecture is intended for a general Math & CS audience.
Speaker: Rahul Santhanam
Title:
Abstract:
Speaker: Robert Andrews
Title: Hilbert’s Nullstellensatz is in the Counting Hierarchy
Abstract: We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, lies in the counting hierarchy. More generally, we show that the number of solutions to a system of equations can be computed in polynomial time with oracle access to the counting hierarchy. Our results hold in particular for polynomials with coefficients in either the rational numbers or a finite field. Previously, the best-known bounds on the complexities of these problems were PSPACE and FPSPACE, respectively. Our main technical contribution is the construction of a uniform family of constant-depth arithmetic circuits that compute the multivariate resultant. Joint work with Abhibhav Garg and Éric Schost.
Speaker: Sanyam Agarwal
Title:
Abstract:
Speaker: Pravesh Kothari
Title:
Abstract:
Speaker: Ian Orzel
Title:
Abstract:
Speaker: Pascal Koiran
Title:
Abstract:
Speaker: Jeong-Hoon Ju
Title:
Abstract:
Speaker: Rafael Oliveira
Title: Sylvester-Gallai Configurations, Strong Algebras and Algebraic Complexity
Abstract: In its algebraic formulation, Sylvester-Gallai configurations are one of the simplest and elegant examples of the study of the power and limitations of cancellations in combinatorial algebraic geometry.
Thus, it is natural that questions about Sylvester-Gallai configurations have been studied by combinatorialists, algebraic geometers as well as complexity theorists.
In this talk we survey the connections between Sylvester-Gallai (SG) configurations and algebraic complexity theory, starting from the first connection between SG configurations and the Polynomial Identity Testing (PIT) problem for depth-3 circuits devised by Dvir and Shpilka in 2007, the first polynomial-time algorithm using this approach due to Kayal and Saraf in 2009 and culminating into the intrinsic connection between depth-3 identities and Sylvester-Gallai configurations done by Saxena and Seshadri in 2013.
We also mention connections between robust versions of linear SG configurations and coding theory by Barak, Dvir, Wigderson, and Yehudayoff in 2011, and the reconstruction problem for depth-3 circuits done by Sinha, Saraf, Shringi, and Varadajan.
Once we have established the intimate connection between SG configurations and PIT for depth-3 circuits (the linear case), we survey Gupta's non-linear generalizations of Sylvester-Gallai configurations and their relations to the PIT problem for special classes of depth-4 circuits.
We will then survey recent progress on Gupta's SG conjectures and on deterministic polynomial-time PIT algorithms for depth-4 circuits, both done via the construction of strong algebras and other results from commutative algebra and algebraic geometry.
This talk is based on recent works with Abhibhav Garg, Shir Peleg, Akash Kumar Sengupta, Nir Shalmon and Amir Shpilka.
Speaker: C Ramya
Title:
Abstract:
Speaker: Zeyu Guo
Title:
Abstract:
Speaker: Devansh Shringi
Title:
Abstract:
Speaker: Anuj Dawar
Title:
Abstract:
Speaker: Tim Seppelt
Title:
Abstract:
Speaker: Susanna de Rezende and Kilian Risse
Title:
Abstract:
Speaker: Tuomas Hakoniemi
Title:
Abstract:
Speaker: Prerona Chatterjee
Title:
Abstract:
Speaker: Anakin Dey
Title:
Abstract:
Speaker: Josh Alman
Title: Faster Walsh-Hadamard Transform from Matrix Non-Rigidity
Abstract: The Walsh-Hadamard transform is a simple recursively-defined linear transformation with many applications throughout algorithm design and complexity theory. The folklore "fast Walsh-Hadamard transform" algorithm computes it using only N log N arithmetic operations, which is believed to be optimal up to constant factors. In this talk, I'll give two improved constructions:
- A new algorithm which uses (23/24) N log N + O(N) arithmetic operations, giving the first improvement on the leading constant.
- A new depth-2 linear circuit of size O(N^{1.45}), improving on size O(N^{1.5}) which one gets from the fast Walsh-Hadamard transform approach.
A key idea behind both constructions is to take advantage of the matrix non-rigidty of the Walsh-Hadamard transform. A matrix is called "rigid" if it's impossible to change a "small" number of its entries to make it have "low" rank. L. Valiant showed that if a matrix is rigid, then this implies lower bounds for computing its linear transformation. However, a recent line of work has shown that many matrices of interest, including the Walsh-Hadamard transform, are actually not rigid. Although a formal converse to Valiant's result is not known, we'll make use of non-rigidity in our new constructions.
Finally, I'll discuss recent new barriers against getting further improvements using this approach, including a new lower bound using assumptions from fine-grained complexity theory, and new rigidity lower bounds for the parameters needed to improve these constructions.
Based in part on joint work with Yunfeng Guan, Baitian Li, Jingxun Liang, Ashwin Padaki, and Kevin Rao.
Speaker: Ben Lee Volk
Title: Finding elements of large order
Abstract: We will discuss recent progress on deterministic algorithms that, given an integer N, find an element of large multiplicative order modulo N. Such algorithms played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey (2020, 2021).
Based on a joint work with Ziv Oznovich.
Speaker: Roshan Raj
Title:
Abstract:
Speaker: Prahladh Harsha
Title:
Abstract:
Speaker: Mrinal Kumar
Title: Multivariate polynomial factorization: closure results and algorithms
Abstract: A rich line of research culminating in works of Kaltofen in the 1980s showed that factors of multivariate polynomials with small algebraic circuits and polynomially bounded degree are themselves computable by small algebraic circuits. Furthermore, these works also gave a randomized polynomial-time algorithm to factor such circuits.
Two of the central themes in this line of research since then have been to (i) prove such closure results for more structured classes of circuits, e.g., formulas and constant depth circuits, and (ii) to design efficient deterministic algorithms for multivariate factorization.
In this talk, we will discuss some of these classical results as well as some recent progress on the understanding of these questions for constant-depth algebraic circuits.
Parts of the talk will be based on joint works with Somnath Bhattacharjee, Varun Ramanathan, Shanthanu Rai, Ramprasad Saptharishi, and Shubhangi Saraf.
Speaker: Shanthanu S. Rai
Title: Computing GCD of univariate polynomials in constant parallel time (over any characteristic)
Abstract: The Euclidean algorithm for computing the greatest common divisor (GCD) is arguably the oldest non-trivial algorithm in print. Originally described for integers, it also applies to univariate polynomials. While efficient, the Euclidean algorithm is inherently sequential. Can it be implemented efficiently in parallel for polynomials?
In their seminal work, Andrews and Wigderson answered this affirmatively: they showed that the GCD of two univariate polynomials can be computed in constant parallel time in the arithmetic PRAM model. Equivalently, in algebraic-complexity terms, they proved that the GCD can be computed in (piecewise) algebraic circuits of constant depth and polynomial size. However, their results hold only over fields of characteristic zero and fields of large (polynomially bounded) characteristic.
In this work, we extend their result to all sufficiently large fields, regardless of characteristic. The key ingredient is an analogue of the fundamental theorem of symmetric polynomials for constant-depth algebraic circuits, strengthening a result of Bläser and Jindal for unbounded-depth circuits. Our approach crucially uses the factor closure property of constant-depth circuits, established in our earlier work.
Based on joint work with Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, and Shubhangi Saraf.
Speaker: Magnus Hansen
Title:
Abstract:
Speaker: Théo Fabris
Title:
Abstract:
Speaker: Igor Pak
Title:
Abstract:
Speaker: Julian Dörfler
Title:
Abstract:
Speaker: Pietro Posta
Title: Representation-Theoretic multiplicities and the class #BQ
Abstract: Representation-Theoretic multiplicities, such as Littlewood-Richardson, Kronecker, and plethysm coefficients, are a special case of branching coefficients, counting how many copies of an irreducible representation for a group H appear in an irreducible representation of a different group G. For many of these coefficients, whether you can provide a positive combinatorial interpretation is an important and well-studied open problem within the field of algebraic combinatorics. In this talk, I will explain how this is related to computational complexity and why the quantum complexity equivalent of this problem is much easier to treat.
Speaker: Tuukka Korhonen
Title:
Abstract: