We consider some restricted arithmetic circuit models for which we know nontrivial lower bounds, and augment their power with help polynomials. More precisely, let $\{h_1,h_2,\ldots,h_m\}$ be an arbitrary but fixed set of $m$ polynomials in the input variables $x_1,x_2,\ldots,x_n$ that are available at the input level for the considered arithmetic circuit model (e.g. depth two arithmetic circuits, noncommutative branching programs or formulas). Can we prove lower bounds for explicit polynomials in such augmented circuit models? We focus on the following cases:
1. We consider noncommutative algebraic branching programs augmented with help polynomials. One approach to proving lower bounds in this model relates it to the remote point problem in the rank metric. For help polynomials with some degree restrictions we show exponential size lower bounds for explicit polynomials. Without the degree restrictions, it turns out that an improved algorithmic upper bound for the remote point problem will yield lower bounds. In the boolean case too, proving lower bounds for constant-depth circuits (augmented with boolean help functions) can be related to improved solutions for the remote point problem in the Hamming metric.
2. We discuss the problem of proving lower bounds for linear circuits
(computing an explicit linear transformation) augmented by linear help
polynomials.
Most of the more recent fast algorithms for matrix multiplication, like Schönhage's Tau-Theorem, Strassen's Laser Method and its generalization by Coppersmith and Winograd, start with an efficient small tensor. Then they take a high power of this tensor and degenerate a matrix multiplication tensor from it. Efficient tensor here means a tensor with low border rank and a "rich" structure which allows the degeneration of a large matrix product. How can we find such good efficient tensors?
The most viable approach seems to look at small powers of existing starting tensors and try to prove that their border rank is strictly smaller than the trivial upper bound. Therefore, it is essential to understand the exact (border) rank of small tensors.
The group-theoretic by Cohn and Umans is somewhat different, since in principle. it allows to construct sequences of groups whose size goes to infinity. But currently, the best upper bounds that we get with this method are achieved by starting with a small group. In this talk, we will demonstrate and discuss methods for understanding the complexity of such small starting structures exactly.
We prove the lower bound 3m^2 - 2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic (occurence) obstructions in the sense of Mulmuley and Sohoni's geometric complexity theory (GCT) program. While this bound is weaker than the one recently obtained by Landsberg and Ottaviani, these are the first significant lower bounds obtained within the GCT program. Behind the proof is an explicit description of the heighest weight vectors f_H in Sym^d \otimes^3 (C^n)^* in terms of combinatorial objects H, called obstruction designs. This description results from analyzing the process of polarization and Schur-Weyl duality. One can view H as a 3-partite, 3-uniform, 2-simple hypergraph.
We state a combinatorial condition for f_H vanishing on all tensors of border rank at most r in terms of the chromatic index of H. A conjecture by Alon and Kim implies that 3/2 *dimension is the best lower bound that can be shown via the chromatic index, showing the limitations of just relying on the chromatic index.
In general, deciding whether f_H equals the zero polynomial is not easy: we show that for a simple family of obstruction designs H_n, this is equivalent to the Alon-Tarsi Conjecture on Latin squares. The Alon-Tarsi Conjecture is also relevant for the permanent versus determinant problem. Kumar showed that this conjecture implies restrictions on the possible candidates for occurences obstructions. This excludes an asymptotic approach to the problem.
(joint work with Christian Ikenmeyer)
We will discuss the surprising link between quantum information and foundational physics questions on the one hand and mathematics and computer science in the other.
We will show how the interplay of foundational questions in entanglement and non-locality give rise to approximation algorithms, solve a 35 year old problem in Banach operator theory and shed some light on the complexity of matrix multiplication.
According to the real tau-conjecture, the number of real roots of a sum of products of sparse polynomials should be polynomially bounded in the size of such an expression. By contrast, the original tau-conjecture of Shub and Smale deals with integer roots of arbitrary straight-line programs, and is known to become false for real rather than integer roots.Both conjectures imply that the permanent is hard to compute for arithmetic circuits. In this talk, I will sketch the proof of this implication for the real tau-conjecture. The two main ingredients are: (i) Reduction to depth 4 for arithmetic circuits. (ii) A connection between the counting hierarchy and arithmetic circuit complexity discovered in a paper by Allender et al. and further explored by B\"urgisser. I will also discuss a tractable case of the conjecture which leads to unconditional lower bounds and polynomial identity testing in a restricted model. Here, the main tool is the Wronskian determinant.
One of the big goals in algebraic complexity is to separate VNP from VNP, another big goal is to separate VNC^1 from VP. Since prominent families in these classes, the determinant and the permanent, are multilinear, an intermediate goal is to separate multilinear versions of these classes. One such goal has been achieved by Ran Raz's landmark result separating multilinear formulas and circuits at polynomial size. The actual separation is in the syntactic multilinear world, and it translates to the multilinear world.
We discuss the question: To what extent does the syntactic multilinear (SM) world reflect the world we are interested in? We describe one anomalous situation where the known containments in the general world are reversed in the SM world: namely, the relationship between formulas and bounded width circuits (both of polynomial size and polynomial degree). We describe another situation where a general-world simulation seems to fails spectacularly in the SM world: namely, transforming formulas to straight-line programs with few registers via the construction of Ben-Or and Cleve.
Talk TBA
Talk TBA
We present several variants of the sunflower conjecture of Erdos and Rado and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and of Cohn et al regarding possible approaches for obtaining fast matrix multiplication algorithms. Specifically, we show that the Erdos-Rado sunflower conjecture (if true) implies a negative answer to the ``no three disjoint equivoluminous subsets'' question of Coppersmith and Winograd; we also formulate a ``multicolored'' sunflower conjecture in Z_3^n and show that (if true) it implies a negative answer to the ``strong USP'' conjecture of Cohn et al (although it does not seem to impact their second conjecture or the viability of the general group-theoretic approach). Joint work with Noga Alon and Chris Uman
We shall discuss connections between PI-algebras (polynomial identity algebras), matrix algebras, tensor-rank and lower bounds on arithmetic proofs.
Based on a joint work with Fu Li
Given an arithmetic circuit C with n inputs over a field F, a natural way to define a Boolean function computed by C is to decide the Boolean output by an equality-test or, in case of an ordered field, a sign-test, when evaluated on a Boolean input x in {0,1}^n. Doing so may lead to interesting connections between algebraic complexity and Boolean complexity. Indeed, Agrawal, Allender and Datta showed that constant depth arithmetic circuits with constants 0 and 1 over an ordered field characterizes the Boolean circuit class TC^0 by equality-tests (and hence also sign tests). In the case of finite fields the Boolean circuit class ACC^0 is similarly characterized by equality-tests.
In this talk we shall consider computing Boolean functions by polynomial threshold functions (PTFs) on general Boolean domains. A typical example of a general Boolean domain is {1,2}^n. We are mainly interested in the length (the number of monomials) of PTFs, with their degree and weight being of secondary interest. Such PTFs can be seen in the above setting of computing Boolean functions using arithmetic circuits, as a very specific case.
We show that PTFs over the {1,2}^n domain are very closely related to depth two threshold circuits, which represent the frontier of circuit lower bounds for threshold circuits. In particular we show that PTFs of polynomial length and polynomial degree compute exactly the functions computed by THR o MAJ circuits. We note that known lower bounds for THR o MAJ circuits extends to the likely larger class of PTFs of polynomial length.
We next exploit this connection to gain a better understanding of threshold circuits. We show that (super-logarithmic) lower bounds for 3-player randomized communication protocols with unbounded error would yield (super-polynomials) size lower bounds for THR o THR circuits; a long-standing open problem.
Finally we discuss structural properties of PTFs. These include relationships between weight and degree of PTFs, and a degree lower bound for PTFs of constant length.
