Tag - Complexity theory

Yuval Filmus: Structure of Boolean Almost Low Degree Functions on the Biased Cube

28th July, 2023

The FKN theorem states that if a Boolean function on the Boolean cube is close to degree 1, then it is close to a dictator. Similarly, the Kindler-Safra theorem states that if a Boolean function on the Boolean cube is close to degree d, then it is close to a junta.

The picture becomes more interesting when we study functions on the p-biased Boolean cube. If a Boolean function is 𝜀-close to degree 1, then (up to negation) it is O(𝜀)-close to a maximum of O(√𝜀/p+1) coordinates, and so O(√𝜀+p)-close to a constant function. A similar statement holds for functions close to degree d, but the corresponding structure is more complicated.Another setting we might discuss is functions on the symmetric group. If a Boolean function is 𝜀-close to degree 1, then it is O(√𝜀)-close to a dictator (suitably defined), and O(𝜀)-close (up to negation) to a union of “mostly disjoint” cosets. A similar statement should hold for degree d, where the function ought to be close to a (suitably defined) decision tree of depth poly(d).

Mika Göös: Top-Down Lower Bounds for Depth-Four Circuits

24th July, 2023

We present a top-down lower-bound method for depth-4 boolean circuits. In particular, we give a new proof of the well-known result that the parity function requires depth-4 circuits of size exponential in n1/3. Our proof is an application of robust sunflowers and block unpredictability.

Greta Panova: Computational complexity in algebraic combinatorics II

8th April, 2023

Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives on their own and brought us some beautiful formulas and combinatorial interpretations.

The flagship hook-length formula counts the number of standard Young tableaux, which also give the dimension of the irreducible Specht modules of the symmetric group. The elegant Littlewood-Richardson rule gives the multiplicities of irreducible GL-modules in the tensor products of GL-modules. Such formulas and rules have inspired large areas of study and development beyond Algebra and Combinatorics, becoming applicable to Integrable Probability and Statistical Mechanics, and Computational Complexity Theory.

We will see what lies beyond the reach of such nice product formulas and combinatorial interpretations and enter the realm of Computational Complexity Theory, which can formally explain the beauty we see and the difficulties we encounter in finding further formulas and "combinatorial interpretations". In the opposite direction, the 85 year old open problem on Kronecker coefficients of the symmetric group lead to the disproof of the wishful approach of Geometric Complexity Theory (GCT) towards the resolution of the algebraic P vs NP Millennium problem, the VP vs VNP problem. In order to make GCT work and establish computational complexity lower bounds, we need to understand representation-theoretic multiplicities in further detail, possibly asymptotically.

Greta Panova: Computational complexity in algebraic combinatorics I

8th April, 2023

Algebraic Combinatorics originated in Algebra and Representation Theory, studying their discrete objects and integral quantities via combinatorial methods which have since developed independent and self-contained lives on their own and brought us some beautiful formulas and combinatorial interpretations.

The flagship hook-length formula counts the number of standard Young tableaux, which also give the dimension of the irreducible Specht modules of the symmetric group. The elegant Littlewood-Richardson rule gives the multiplicities of irreducible GL-modules in the tensor products of GL-modules. Such formulas and rules have inspired large areas of study and development beyond Algebra and Combinatorics, becoming applicable to Integrable Probability and Statistical Mechanics, and Computational Complexity Theory.

We will see what lies beyond the reach of such nice product formulas and combinatorial interpretations and enter the realm of Computational Complexity Theory, which can formally explain the beauty we see and the difficulties we encounter in finding further formulas and "combinatorial interpretations". In the opposite direction, the 85 year old open problem on Kronecker coefficients of the symmetric group lead to the disproof of the wishful approach of Geometric Complexity Theory (GCT) towards the resolution of the algebraic P vs NP Millennium problem, the VP vs VNP problem. In order to make GCT work and establish computational complexity lower bounds, we need to understand representation-theoretic multiplicities in further detail, possibly asymptotically.

Harm Derksen: Orbit Problems

31st March, 2023

Given a group G and two vectors v and w in a representation V, one can ask: do v and w lie in the same orbit? This is what we call the orbit problem. For the action of GLn on m-tuples of n × n matrices, the orbit problem translates to the module isomorphism problem for which there is a known polynomial time algorithm. In joint work with Visu Makam, we also gave a polynomial time algorithm for deciding whether the orbit closures of v and w intersect. We also have similar results for the left-right action of SLn × SLn on the space of m-tuples of matrices. These results are related to interesting problems in algebraic complexity theory, such as non-commutative rational identity testing. The graph isomorphism problem can also formulated as an orbit problem. No polynomial time algorithm for the graph isomorphism problem is known. I will discuss an algorithm for the graph isomorphism problem that is more powerful than the higher-dimensional Weisfeiler-Leman algorithm when it comes to distinguishing pairs of non-isomorphic graphs in polynomial time. (This algorithm could potentially be polynomial time, but we will not make such a bold claim.)

Nitin Saxena: Demystifying the border of depth-3 algebraic circuits

30th March, 2023

Border (or approximative) complexity of polynomials plays an integral role in GCT approach to P!=NP. This raises an important open question: can a border circuit be efficiently debordered (i.e. convert from approximative to exact)? Or, could the approximation involve exponential-precision which may not be efficiently simulable? Circuits of depth 3 or 4, are a good testing ground for this question.

Kumar (ToCT'20) proved the universal power of the border of top-fanin-2 depth-3 circuits. We recently solved some of the related open questions. In this talk we will outline our result: border of bounded-top-fanin depth-3 circuits is relatively easy- it can be computed by a polynomial-size algebraic branching program (ABP). Our de-bordering paradigm has many applications, especially in identity testing and lower bounds.

Youming Qiao: Some algebraic algorithms and complexity classes inspired by connections between graphs and matrix spaces

30th March, 2023

Linear spaces of matrices, or matrix spaces, appear naturally in the study of polynomial identity testing and group isomorphism. In this talk, we examine connections between graphs and matrix spaces, the first of which goes back to the works of Tutte, Edmonds, and Lovász. These connections provide a useful viewpoint on some algebraic algorithms and complexity classes, such as algorithms for the non-commutative rank problem and the group isomorphism problem, and the Tensor-Isomorphism complexity class. Such connections also lead to new questions in algebraic complexity, such as testing whether a matrix space contains only nilpotent matrices.

Shubhangi Saraf: Near-Optimal Lower Bounds for Set-Multilinear Formulas

29th March, 2023

The seminal work of Raz (J. ACM 2013) as well as the recent breakthrough results by Limaye, Srinivasan, and Tavenas (FOCS 2021, STOC 2022) have demonstrated a potential avenue for obtaining lower bounds for general algebraic formulas, via strong enough lower bounds for set-multilinear formulas.

In this talk, along with discussing the impact of these work and several others in the literature, I will discuss some new results in this area, namely strong and near-optimal lower bounds for set-multilinear circuits/formulas in the constant (or low) depth setting, as well as the unbounded depth setting.

Alhussein Fawzi: Discovering matrix multiplication algorithms with deep reinforcement learning

28th March, 2023

Improving the efficiency of algorithms for fundamental computational tasks such as matrix multiplication can have widespread impact, as it affects the overall speed of a large amount of computations. In this talk I will present AlphaTensor, our reinforcement learning agent based on AlphaZero for discovering efficient and provably correct algorithms for the multiplication of matrices. Using this approach, we find new algorithms outperforming the best ranks for many matrix sizes. I will describe how to formulate this problem as a single-player game, and the key machine learning ingredients that enable tackling difficult mathematical problems using reinforcement learning.

Sebastién Tavenas: Approaching Lower Bounds for Algebraic Formulas

27th March, 2023

This talk will present recent advances in obtaining better lower bounds for algebraic formulas. We will discuss a parallelization technique that achieves logarithmic depth in the degree for small homogeneous formulas, which reduces the problem of obtaining lower bounds for general homogeneous formulas to that of small depth formulas. We will also explore how superpolynomial lower bounds can be obtained in the low-degree and low-depth regime by applying the partial derivative method to certain lopsided set-multilinear polynomials. These lower bounds will continue to be superpolynomial for formulas of depth at most O(log(log(d))). Finally, we will show that the best lower bound we can prove for set-multilinear formulas of product-depth D can be characterized in terms of the combinatorial properties of a specific multi-set W of size d, referred to as the "depth-D tree bias" of W.