Inspired by the work of Dubut, Goubault, and Goubault-Larrecq (ICALP 2015) on natural homology, Dubut (RAMiCS 2020) introduces finitary diagrams and studies bisimilarity and diagrammatic path logics for them. To this aim, he defines a fragment of the existential theory of the reals, called the existential theory of invertible matrices (ETIM). Using a PSPACE upper bound for this fragment, he proves that for finitary diagrams, bisimilarity can be decided in EXPSPACE and model checking for diagrammatic path logic in PSPACE. We significantly improve both these bounds and settle the complexity of model checking for finitary diagrams. As our first main result, we show that there is an efficient randomized algorithm for ETIM. Combining this with the previous work by Dubut, we obtain an NEXP upper bound for bisimilarity of finitary diagrams and an NP upper bound for diagrammatic path logic. We also provide a matching NP-hardness proof for the latter. The hardness proof introduces constrained layered poset problems, which may be of independent interest, and connects them to finitary diagrams using Gabriel’s theorem for representations of path quivers. For bisimilarity over finite fields, we further improve the upper bound to PSPACE. In ETIM, we quantify over invertible matrices. We finally ask what happens if we instead quantify over matrices from the special linear group, that is, of determinant one. We show that in this case, the resulting fragment is equivalent to the existential theory of the reals, under a mild generalization of the allowed linear constraints.

Solving polynomial systems is a powerful tool for designing algorithms in optimization and computational algebra. Formally, this problem is called Hilbert’s Nullstellensatz problem \(\textsf{HN}_R\): given multivariate polynomials over some ring \(R\), it asks whether they have a common solution in \(R\). For every ring \(R\), we can also view \(\textsf{HN}_R\) as a parameterized complexity class by taking the downward closure of \(\textsf{HN}_R\) under polynomial-time many-one reductions. In this work, we show that for many important problems from optimization and algebra, formulating them as systems of polynomial equations is optimal, since we can reduce Hilbert’s Nullstellensatz to them. We first consider the Affine Polynomial Projection Problem, which, given two polynomials, asks whether one of them can be transformed into the other by an affine projection of the variables. Kayal (STOC 2012) proved that this problem is \(\textsf{NP}\)-hard. Here, we improve this lower bound by showing that it is as hard as \(\textsf{HN}_F\) for any field \(F\). The second problem is the Sparse Shift Problem, which asks whether for a given polynomial, there is an affine shift that reduces the number of monomials. For integral domains \(R\) that are not fields, Chillara, Grichener, and Shpilka (STACS 2023) showed that this problem is \(\textsf{HN}_R\)-hard. We extend their result to fields: over infinite fields \(F\), where \(\textsf{HN}_F\) is complete for \(\textsf{NP}_F\) (in the BSS model), we show that the Sparse Shift Problem is equivalent to \(\textsf{HN}_F\). Next, we turn to the important case of Hilbert’s Nullstellensatz over the real numbers. Real-stable polynomials have been a successful tool in mathematics and computer science in recent years, from solving the Kadison-Singer problem to improving the approximation performance of the metric TSP. We prove that testing whether a given polynomial is real stable is equivalent to the complement of \(\textsf{HN}_{\mathbb{R}}\), or equivalently, to the universal theory of the reals \(\forall\mathbb{R}\). We show that the same is true for testing convexity and testing hyperbolicity, as well as for testing whether a biquadratic form is nonnegative, completely settling the complexity of all of these problems.

The framework of Pearl's Causal Hierarchy (PCH) formalizes three types of reasoning: probabilistic (i.e. purely observational), interventional, and counterfactual, that reflect the progressive sophistication of human thought regarding causation. We investigate the computational complexity aspects of reasoning in this framework focusing mainly on satisfiability problems expressed in probabilistic and causal languages across the PCH. That is, given a system of formulas in the standard probabilistic and causal languages, does there exist a model satisfying the formulas? Our main contribution is to prove the exact computational complexities showing that languages allowing addition and marginalization (via the summation operator) yield NP^{PP}-, PSPACE-, and NEXP-complete satisfiability problems, depending on the level of the PCH. These are the first results to demonstrate a strictly increasing complexity across the PCH: from probabilistic to causal and counterfactual reasoning. On the other hand, in the case of full languages, i.e.~allowing addition, marginalization, and multiplication, we show that the satisfiability for the counterfactual level remains the same as for the probabilistic and causal levels, solving an open problem in the field.

Marginalization – summing a function over all assignments to a subset of its inputs – is a fundamental computational problem with applications from probabilistic inference to formal verification. Despite its computational hardness in general, there exist many classes of functions (e.g., probabilistic models) for which marginalization remains tractable, and they can all be commonly expressed by arithmetic circuits computing multilinear polynomials. This raises the question, can all functions with polynomial time marginalization algorithms be succinctly expressed by such circuits? We give a negative answer, exhibiting simple functions with tractable marginalization yet no efficient representation by known models, assuming $\\mathsf{FP} \\neq \#\\mathsf{P}$ (an assumption implied by $\\mathsf{P} \\neq \\mathsf{NP}$). To this end, we identify a hierarchy of complexity classes corresponding to stronger forms of marginalization, all of which are efficiently computable on the known circuit models. We conclude with a completeness result, showing that whenever there is an efficient real RAM performing virtual evidence marginalization for a function, then there are small arithmetic circuits for that function’s multilinear representation.

Linear structural causal models (SCMs) are used to analyze the relationships between random variables. Directed edges represent direct causal effects and bidirected edges represent hidden confounders. Generically identifying the causal parameters from observed correlations between the random variables is an open problem in causality. Gupta and Bl\"aser solve the case of SCMs in which the directed edges form a tree by giving a randomized polynomial time algorithm with running time $O(n^6)$. We present an improved algorithm with running time $O(n^3 \log^2 n)$ and demonstrate its feasibility by providing an implementation that outperforms existing state-of-the-art implementations.

Linear structural causal models (SCMs) are used to express and analyze the relationships between random variables. Direct causal effects are represented as directed edges and confounding factors as bidirected edges. Identifying the causal parameters from correlations between the nodes is an open problem in artificial intelligence. In this paper, we study SCMs whose directed component forms a tree. Van der Zander et al. give a PSPACE-algorithm for the identification problem in this case, which is a significant improvement over the general Gröbner basis approach, which has doubly-exponential time complexity in the number of structural parameters. However, they do not show that their algorithm is complete. In this work, we present a randomized polynomial-time algorithm, which solves the identification problem for tree-shaped SCMs. For every structural parameter, our algorithms decides whether it is generically identifiable, generically 2-identifiable, or generically unidentifiable. (No other cases can occur.) In the first two cases, it provides one or two fractional affine square root terms of polynomials (FASTPs) for the corresponding parameter, respectively. In particular, our algorithm is not only polynomial time, but also complete for for tree-shaped SCMs.

Valiant’s famous VP vs. VNP conjecture states that the symbolic permanent polynomial does not have polynomial-size algebraic circuits. However, the best upper bound on the size of the circuits computing the permanent is exponential. Informally, VNP is an exponential sum of VP-circuits. In this paper we study whether, in general, exponential sums (of algebraic circuits) require exponential-size algebraic circuits. We show that the famous Shub-Smale τ-conjecture indeed implies such an exponential lower bound for an exponential sum. Our main tools come from parameterized complexity. Along the way, we also prove an exponential fpt (fixed-parameter tractable) lower bound for the parameterized algebraic complexity class VW⁰_{nb}[𝖯], assuming the same conjecture. VW⁰_{nb}[𝖯] can be thought of as the weighted sums of (unbounded-degree) circuits, where only ± 1 constants are cost-free. To the best of our knowledge, this is the first time the Shub-Smale τ-conjecture has been applied to prove explicit exponential lower bounds. Furthermore, we prove that when this class is fpt, then a variant of the counting hierarchy, namely the linear counting hierarchy collapses. Moreover, if a certain type of parameterized exponential sums is fpt, then integers, as well as polynomials with coefficients being definable in the linear counting hierarchy have subpolynomial τ-complexity. Finally, we characterize a related class VW[𝖥], in terms of permanents, where we consider an exponential sum of algebraic formulas instead of circuits. We show that when we sum over cycle covers that have one long cycle and all other cycles have constant length, then the resulting family of polynomials is complete for VW[𝖥] on certain types of graphs.

Zhang et al. (ICML 2021, PLMR 139, pp. 12447–12457) introduced probabilistic generating circuits (PGCs) as a probabilistic model to unify probabilistic circuits (PCs) and determinantal point processes (DPPs). At a first glance, PGCs store a distribution in a very different way, they compute the probability generating polynomial instead of the probability mass function and it seems that this is the main reason why PGCs are more powerful than PCs or DPPs. However, PGCs also allow for negative weights, whereas classical PCs assume that all weights are nonnegative. One main insight of this work is that the negative weights are the cause for the power of PGCs and not the different representation. PGCs are PCs in disguise: we show how to transform any PGC on binary variables into a PC with negative weights with only polynomial blowup. PGCs were defined by Zhang et al. only for binary random variables. As our second main result, we show that there is a good reason for this: we prove that PGCs for categorical variables with larger image size do not support tractable marginalization unless NP=P. On the other hand, we show that we can model categorical variables with larger image size as PC with negative weights computing set-multilinear polynomials. These allow for tractable marginalization. In this sense, PCs with negative weights strictly subsume PGCs.

Learning the unknown causal parameters of a linear structural causal model is a fundamental task in causal analysis. The task, known as the problem of identification, asks to estimate the parameters of the model from a combination of assumptions on the graphical structure of the model and observational data, represented as a non-causal covariance matrix. In this paper, we give a new sound and complete algorithm for generic identification which runs in polynomial space. By a standard simulation result, namely $\mathsf{PSPACE} \subseteq \mathsf{EXP}$, this algorithm has exponential running time which vastly improves the state-of-the-art double exponential time method using a Gröbner basis approach. The paper also presents evidence that parameter identification is computationally hard in general. In particular, we prove, that the task asking whether, for a given feasible correlation matrix, there are exactly one or two or more parameter sets explaining the observed matrix, is hard for $\forall \mathbb{R}$, the co-class of the existential theory of the reals. In particular, this problem is $\mathsf{coNP}$-hard. To our best knowledge, this is the first hardness result for some notion of identifiability.

This special issue contains 7 articles which are based on extended abstracts presented at the 38th Symposium on Theoretical Aspects of Computer Science (STACS).The conference was held online, due to Covid pandemic, organised in Saarbrücken by Saarland University from March 16 to March 19, 2021.The extended abstracts were chosen among the top papers of those which were selected for presentation in a highly competitive peer-review process (after which only 56 papers out of 228 submissions were accepted, putting STACS among the most competitive conferences in Theoretical Computer Science).Compared with the original conference papers, the articles have been extended with a description of the context, full proofs, and additional results.They underwent a rigorous reviewing process, following the TOCS journal standards, completely independent from the selection process of STACS 2021.The topics of the chosen papers cover various areas of Theoretical Computer Science, that is, algorithmic graph theory, linear dynamical systems, parameterized complexity analysis, automata theory, complexity theory, algorithmic group theory, and distributed algorithms.In what follows, we briefly describe the contributions of the papers, ordered alphabetically by author names.In the article "The Complexity of the Distributed Constraint Satisfaction Problem", Silvia Butti and Víctor Dalmau study the distributed variant of the constraint satisfaction problem on a synchronous, anonymous network from a complexity point of view.They show that the problem is decidable in polynomial time if and only if the template is a set of relations invariant under symmetric polymorphisms of all arities.The Minimum Circuit Size Problem MCSP w.r.t. to some size bound s is the problem of deciding whether the minimum circuit size of a given Boolean function on n inputs is at most s(n).Recent works in meta-complexity exhibited "hardness magnifi-B

Probabilistic modeling is a central task in machine learning. Probabilistic models should be tractable, i.e., allowing tractable probabilistic inference, but also efficient, i.e., being able to represent a large set of probability distributions. Zhang et al. (ICML 2021) recently proposed a new model, probabilistic generating circuits. They raised the question whether every strongly Rayleigh distribution can be efficiently represented by such circuits. We prove that this question has a negative answer, there are strongly Rayleigh distributions that cannot be represented by polynomial-sized probabilistic generating circuits, assuming a widely accepted complexity theoretic conjecture.

We study formal languages which are capable of fully expressing quantitative probabilistic reasoning and do-calculus reasoning for causal effects, from a computational complexity perspective. We focus on satisfiability problems whose instance formulas allow expressing many tasks in probabilistic and causal inference. The main contribution of this work is establishing the exact computational complexity of these satisfiability problems. We introduce a new natural complexity class, named succ∃R, which can be viewed as a succinct variant of the well-studied class ∃R, and show that these problems are complete for succ∃R. Our results imply even stronger limitations on the use of algorithmic methods for reasoning about probabilities and causality than previous state-of-the-art results that rely only on the NP- or ∃R-completeness of the satisfiability problems for some restricted languages.

Linear structural equation models represent direct causal effects as directed edges and confounding factors as bidirected edges. An open problem is to identify the causal parameters from correlations between the nodes. We investigate models, whose directed component forms a tree, and show that there, besides classical instrumental variables, missing cycles of bidirected edges can be used to identify the model. They can yield systems of quadratic equations that we explicitly solve to obtain one or two solutions for the causal parameters of adjacent directed edges. We show how multiple missing cycles can be combined to obtain a unique solution. This results in an algorithm that can identify instances that previously required approaches based on Gröbner bases, which have doubly-exponential time complexity in the number of structural parameters.

We consider the orbit closure containment problem, which, for a given vector and a group orbit, asks if the vector is contained in the closure of the group orbit. Recently, many algorithmic problems related to orbit closures have proved to be quite useful in giving polynomial time algorithms for special cases of the polynomial identity testing problem and several non-convex optimization problems. Answering a question posed by Wigderson, we show that the algorithmic problem corresponding to the orbit closure containment problem is NP-hard. We show this by establishing a computational equivalence between the solvability of homogeneous quadratic equations and a homogeneous version of the matrix completion problem, while showing that the latter is an instance of the orbit closure containment problem. Secondly, we consider the notion of slice rank of tensors, which was recently introduced by Tao, and has subsequently been used for breakthroughs in several combinatorial problems like capsets, sunflower free sets, tri-colored sum-free sets, and progression-free sets. We show that the corresponding algorithmic problem, which can also be phrased as a problem about union of orbit closures, is also NP-hard, hence answering an open question by Bürgisser, Garg, Oliveira, Walter, and Wigderson. We show this by using a connection between the slice rank and the size of a minimum vertex cover of a hypergraph revealed by Tao and Sawin.

We give a randomized polynomial time algorithm for polynomial identity testing for the class of n-variate poynomials of degree bounded by d over a field 𝔽, in the blackbox setting. Our algorithm works for every field 𝔽 with | 𝔽 | ≥ d+1, and uses only d log n + log (1/ ε) + O(d log log n) random bits to achieve a success probability 1 - ε for some ε > 0. In the low degree regime that is d ≪ n, it hits the information theoretic lower bound and differs from it only in the lower order terms. Previous best known algorithms achieve the number of random bits (Guruswami-Xing, CCC'14 and Bshouty, ITCS'14) that are constant factor away from our bound. Like Bshouty, we use Sidon sets for our algorithm. However, we use a new construction of Sidon sets to achieve the improved bound. We also collect two simple constructions of hitting sets with information theoretically optimal size against the class of n-variate, degree d polynomials. Our contribution is that we give new, very simple proofs for both the constructions.

Nisan showed in 1991 that the width of a smallest noncommutative single-(source,sink) algebraic branching program (ABP) to compute a noncommutative polynomial is given by the ranks of specific matrices. This means that the set of noncommutative polynomials with ABP width complexity at most k is Zariski-closed, an important property in geometric complexity theory. It follows that approximations cannot help to reduce the required ABP width. It was mentioned by Forbes that this result would probably break when going from single-(source,sink) ABPs to trace ABPs. We prove that this is correct. Moreover, we study the commutative monotone setting and prove a result similar to Nisan, but concerning the analytic closure. We observe the same behavior here: The set of polynomials with ABP width complexity at most k is closed for single-(source,sink) ABPs and not closed for trace ABPs. The proofs reveal an intriguing connection between tangent spaces and the vector space of flows on the ABP. We close with additional observations on VQP and the closure of VNP which allows us to establish a separation between the two classes.

We define a theory of parameterized algebraic complexity classes in analogy to parameterized Boolean counting classes. We define the classes VFPT and VW[t], which mirror the Boolean counting classes #FPT and #W[t], and define appropriate reductions and completeness notions. Our main contribution is the VW[1]-completeness proof of the parameterized clique family. This proof is far more complicated than in the Boolean world. It requires some new concepts like composition theorems for bounded exponential sums and Boolean-arithmetic formulas. In addition, we also look at two polynomials linked to the permanent with vastly different parameterized complexity.

We present a deterministic polynomial time approximation scheme (PTAS) for computing the algebraic rank of a set of bounded degree polynomials. The notion of algebraic rank naturally generalizes the notion of rank in linear algebra, i.e., instead of considering only the linear dependencies, we also consider higher degree algebraic dependencies among the input polynomials. More specifically, we give an algorithm that takes as input a set of polynomials with degrees bounded by d, and a rational number ∊ > 0 and runs in time , where M(n) is the time required to compute the rank of an n × n matrix (with field entries), and finally outputs a number r, such that r is at least (1 – ∊) times the algebraic rank of f. Our key contribution is a new technique which allows us to achieve the higher degree generalization of the results by Bläser, Jindal, Pandey (CCC’17) who gave a deterministic PTAS for computing the rank of a matrix with homogeneous linear entries. It is known that a deterministic algorithm for exactly computing the rank in the linear case is already equivalent to the celebrated Polynomial Identity Testing (PIT) problem which itself would imply circuit complexity lower bounds (Kabanets, Impagliazzo, STOC’03). Such a higher degree generalization is already known to a much stronger extent in the non-commutative world, where the more general case in which the entries of the matrix are given by polysized formulas reduces to the case where the entries are given by linear polynomials using Higman's trick, and in the latter case, one can also compute the exact rank in polynomial time (Garg, Gurvits, Oliviera, Wigderson, FOCS’16, Ivanyos, Qiao, Subrahmanyam, ITCS’17). Higman's trick only preserves the co-rank, hence it cannot be used to reduce the problem of rank approximation to the case when the matrix entries are linear polynomials. Thus our work can also be seen as a step towards bridging the knowledge gap between the non-commutative world and the commutative world.

Algebraic natural proofs were recently introduced by Forbes, Shpilka and Volk (Proc. of the 49th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 653–664, 2017) and independently by Grochow, Kumar, Saks and Saraf (CoRR, abs/1701.01717, 2017) as an attempt to transfer Razborov and Rudich’s famous barrier result (J. Comput. Syst. Sci., 55(1): 24–35, 1997) for Boolean circuit complexity to algebraic complexity theory. Razborov and Rudich’s barrier result relies on a widely believed assumption, namely, the existence of pseudo-random generators. Unfortunately, there is no known analogous theory of pseudo-randomness in the algebraic setting. Therefore, Forbes et al. use a concept called succinct hitting sets instead. This assumption is related to polynomial identity testing, but it is currently not clear how plausible this assumption is. Forbes et al. are only able to construct succinct hitting sets against rather weak models of arithmetic circuits.

We consider the problem of commutative rank computation of a given matrix space. A matrix space is a (linear) subspace of the (linear) space of n x n matrices over a given field. The problem is fundamental, as it generalizes several computational problems from algebra and combinatorics. For instance, checking if the commutative rank of the space is n, subsumes problems such as testing perfect matching in graphs and identity testing of algebraic branching programs. An efficient deterministic computation of the commutative rank is a major open problem, although there is a simple and efficient randomized algorithm for it. Recently, there has been a series of results on computing the non-commutative rank of matrix spaces in deterministic polynomial time. Since the non-commutative rank of any matrix space is at most twice the commutative rank, one immediately gets a deterministic 1/2-approximation algorithm for the computation of the commutative rank. This leads to a natural question of whether this approximation ratio can be improved. In this paper, we answer this question affirmatively. We present a deterministic Polynomial-time approximation scheme (PTAS) for computing the commutative rank of a given matrix space B. More specifically, given a matrix space and a rational number e > 0, we give an algorithm, that runs in time O(n^(4 + 3/e)) and computes a matrix A in the given matrix space B such that the rank of A is at least (1-e) times the commutative rank of B. The algorithm is the natural greedy algorithm. It always takes the first set of k matrices that will increase the rank of the matrix constructed so far until it does not find any improvement, where the size of the set k depends on e.

An important building block in all current asymptotically fast algorithms for matrix multiplication are tensors with low border rank, that is, tensors whose border rank is equal or very close to their size. To find new asymptotically fast algorithms for matrix multiplication, it seems to be important to understand those tensors whose border rank is as small as possible, so called tensors of minimal border rank. We investigate the connection between degenerations of associative algebras and degenerations of their structure tensors in the sense of Strassen. It allows us to describe an open subset of n*n*n tensors of minimal border rank in terms of smoothability of commutative algebras. We describe the smoothable algebra associated to the Coppersmith-Winograd tensor and prove a lower bound for the border rank of the tensor used in the "easy construction" of Coppersmith and Winograd.

We present a deterministic algorithm to interpolate an m-sparse n-variate polynomial which uses poly(n, m, log H, log d) bit operations. Our algorithm works over the integers. Here H is a bound on the magnitude of the coefficient values of the given polynomial. The degree of given polynomial is bounded by d and m is upper bound on number of monomials. This running time is polynomial in the output size. Our algorithm only requires modular black box access to the given polynomial, as introduced in [12]. As an easy consequence, we obtain an algorithm to interpolate polynomials represented by arithmetic circuits.

Euclidean optimization problems such as TSP and minimum-length matching admit fast partitioning algorithms that compute near-optimal solutions on typical instances. In order to explain this performance, we develop a general framework for the application of smoothed analysis to partitioning algorithms for Euclidean optimization problems. Our framework can be used to analyze both the running-time and the approximation ratio of such algorithms. We apply our framework to obtain smoothed analyses of Dyer and Frieze’s partitioning algorithm for Euclidean matching, Karp’s partitioning scheme for the TSP, a heuristic for Steiner trees, and a heuristic for degree-bounded minimum-length spanning trees.

We prove that an associative algebra A has minimal rank if and only if the Alder-Strassen bound is also tight for the multiplicative complexity of A, that is, the multiplicative complexity of A is 2 dim A - tAwhere tAdenotes the number of maximal twosided ideals of A. This generalizes a result by E. Feig who proved this for division algebras. Furthermore, we show that if A is local or superbasic, then every optimal quadratic computation for A is almost bilinear.

We construct a hitting set generator for sparse multivariate polynomials over the reals. The seed length of our generator is O(log^2 (mn/epsilon)) where m is the number of monomials, n is number of variables, and 1 - epsilon is the hitting probability. The generator can be evaluated in time polynomial in log m, n, and log 1/epsilon. This is the first hitting set generator whose seed length is independent of the degree of the polynomial. The seed length of the best generator so far by Klivans and Spielman [STOC 2001] depends logarithmically on the degree. From this, we get a randomized algorithm for testing sparse black box polynomial identities over the reals using O(log^2 (mn/epsilon)) random bits with running time polynomial in log m, n, and log(1/epsilon). We also design a deterministic test with running time ~O(m^3 n^3). Here, the ~O-notation suppresses polylogarithmic factors. The previously best deterministic test by Lipton and Vishnoi [SODA 2003] has a running time that depends polynomially on log delta, where $delta$ is the degree of the black box polynomial.

We consider the two-variable interlace polynomial introduced by Arratia, Bollobas and Sorkin (2004). We develop graph transformations which allow us to derive point-to-point reductions for the interlace polynomial. Exploiting these reductions we obtain new results concerning the computational complexity of evaluating the interlace polynomial at a fixed point. Regarding exact evaluation, we prove that the interlace polynomial is #P-hard to evaluate at every point of the plane, except on one line, where it is trivially polynomial time computable, and four lines, where the complexity is still open. This solves a problem posed by Arratia, Bollobas and Sorkin (2004). In particular, three specializations of the two-variable interlace polynomial, the vertex-nullity interlace polynomial, the vertex-rank interlace polynomial and the independent set polynomial, are almost everywhere #P-hard to evaluate, too. For the independent set polynomial, our reductions allow us to prove that it is even hard to approximate at any point except at 0.

We present a polynomial time factor 0.999 ċ log n approximation algorithm for the asymmetric traveling salesperson problem with triangle inequality.

Let R(A) denote the rank (also called bilinear complexity) of a finite dimensional associative algebra A. A fundamental lower bound for R(A) is the so-called Alder--Strassen bound R(A) \ge 2 \dim A - t, where t is the number of maximal twosided ideals of A. An algebra is called an algebra of minimal rank if the Alder--Strassen bound is tight, i.e., $R(A) = 2 \dim A - t. As the main contribution of this work, we characterize all algebras of minimal rank over arbitrary fields. This finally solves an open problem in algebraic complexity theory; see, for instance, [V. Strassen, Handbook of Theoretical Computer Science, J. van Leeuwen, ed., Elsevier Science, New York, 1990, Vol.\ A, pp. 634--672, section 12, Problem 4] or [P. Bürgisser, M. Clausen, and M. A. Shokrollahi, Algebraic Complexity Theory, Springer, New York, 1997, Problem 17.5].

No abstract available.

Let R(A) denote the rank (also called the bilinear complexity) of a finite-dimensional associative algebra A. A fundamental lower bound for R(A) is the so-called Alder-Strassen (1981) bound: R(A) /spl ges/ 2 dim A-t, where t is the number of maximal two-sided ideals of A. The class of algebras for which the Alder-Strassen bound is sharp, the so-called "algebras of minimal rank", has received wide attention in algebraic complexity theory. We characterize all algebras of minimal rank over perfect fields. This solves an open problem in algebraic complexity theory over perfect fields [as discussed by V. Strassen (1990) and P. Bu/spl uml/rgisser et al. (1997)]. As a by-product, we determine all algebras A of minimal rank with A/rad A /spl cong/ k/sup t/ over arbitrary fields.

We prove a lower bound of 5/2n/sup 2/-3n for the rank of n/spl times/n-matrix multiplication over an arbitrary field. Similar bounds hold for the rank of the multiplication in noncommutative division algebras and for the multiplication of upper triangular matrices.

We study the multiplicative complexity and the rank of the multiplication in the local algebras R/sub m,n/=k[x,y]/(x/sup m+1/,y/sup n+1/) and T/sub n/=k[x,y]/(x/sup n+1/,x/sup n/y,...,y/sup n+1/) of bivariate polynomials. We obtain the lower bounds (21/3-0(1))/spl middot/dim R/sub m,n/, and (2 1/2 -0(1))/spl middot/dim T/sub n/ for the multiplicative complexity of the multiplication in R/sub m,n/ and T/sub n/, respectively. On the other hand, we derive the upper bounds 3/spl middot/dim T/sub n/-2n-2 and 3/spl middot/dim R/sub m.n/-m-n-3 for the rank of the multiplication in T/sub n/ and R/sub m,n/, respectively, provided that the ground field k admits "fast" univariate polynomial multiplication mod x/sup N/-1. Our results are also applicable to arbitrary finite dimensional algebras of truncated bivariate polynomials k[x,y]/I, where the ideal I=(x(d/sub 0/+1),x(d/sub 1/+1)y,...,x(d/sub n/+1)y/sup n/,y/sup n+1/) is described by a degree pattern d/sub 0//spl ges/d/sub 1//spl ges//spl middot//spl middot//spl middot//spl ges/d/sub n//spl ges/0.