A depth-4 algebraic circuit with top fan-in k and bottom fan-in 2 is a circuit Φ of the form Φ = ∑_{i = 1}^k ∏_{j = 1}^{m_i} Q_{ij}, where the polynomials Q_{ij} ∈ 𝕂[x₁, …, x_n] have degree at most 2. The class of all such circuits is denoted by Σ^k Π Σ Π². We say that the circuit Φ is an identity if it formally computes the zero polynomial. An important parameter of Σ^k Π Σ Π² circuits Φ is their (linear) rank, which is defined as the vector space dimension of the polynomials {Q_{ij}}_{i ∈ [k], j ∈ [m_i]}. We prove that, when the base field 𝕂 is of characteristic zero, the rank of any (simple and minimal) Σ^k Π Σ Π² identity is upper bounded by a function which depends only on the top fan-in k. This result makes progress on [Beecken et al., 2013], being the first work to establish a bound on the rank of such identities that depends only on the top fan-in. Moreover, when combined with [Beecken et al., 2013], our main result yields the first deterministic, polynomial time PIT algorithm for Σ^k Π Σ Π² circuits. One of the key components of our proof of the rank bounds is the derivation of an approximate Hansen-type result, which is interesting in its own right. This result can be seen as an algebraic and higher-dimensional analogue of the approximate Sylvester-Gallai result of [Ai et al., 2014], and a distinct approximate fractional Sylvester-Gallai result than the one from [Garg et al., 2023]. Additionally, we prove a robust version of it, in the spirit of the generalization of Hansen’s theorem by [Boaz Barak et al., 2013]. This paper is an extended abstract of the full version of the paper, which can be found at [Garg et al., 2026].

In this work, we explore a non-linear extension of the classical Sylvester-Gallai configuration. Let 𝕂 be an algebraically closed field of characteristic zero, and let ℱ = {F_1, …, F_m} ⊂ 𝕂[x_1, …, x_N] denote a collection of irreducible homogeneous polynomials of degree at most d, where each F_i is not a scalar multiple of any other F_j for i ≠ j. We define ℱ to be a product Sylvester-Gallai configuration if, for any two distinct polynomials F_i, F_j ∈ ℱ, the following condition is satisfied: ∏_{k≠i, j} F_k ∈ rad (F_i, F_j) . We prove that product Sylvester-Gallai configurations are inherently low dimensional. Specifically, we show that there exists a function λ : ℕ → ℕ, independent of 𝕂, N, and m, such that any product Sylvester-Gallai configuration must satisfy: dim(span_𝕂(ℱ)) ≤ λ(d). This result generalizes the main theorems from (Shpilka 2019, Peleg and Shpilka 2020, Oliveira and Sengupta 2023), and gets us one step closer to a full derandomization of the polynomial identity testing problem for the class of depth 4 circuits with bounded top and bottom fan-in.

We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic polynomials to polynomials of any constant degree. As a consequence of our result, we obtain constant rank bounds for depth-4 circuits with top fanin 3 and constant bottom fan-in which compute the zero polynomial. This settles a stronger form of Conjecture 1 in Gupta (2014) when $\mathrm{k}=3$, for any constant degree bound; additionally this also makes progress on Conjecture 28 in Beecken, Mittmann, and Saxena (Information & Computation, 2013). Our rank bounds, when combined with Theorem 2 in Beecken, Mittmann, and Saxena (Information & Computation, 2013) yield the first deterministic, polynomial time PIT algorithm for these circuits.

A central question in mathematics and computer science is the question of determining whether a given ideal $I$ is prime, which geometrically corresponds to the zero set of $I$, denoted $Z(I)$, being irreducible. The case of principal ideals (i.e., $m=1$) corresponds to the more familiar absolute irreducibility testing of polynomials, where the seminal work of (Kaltofen 1995) yields a randomized, polynomial time algorithm for this problem. However, when $m > 1$, the complexity of the primality testing problem seems much harder. The current best algorithms for this problem are only known to be in EXPSPACE. In this work, we significantly reduce the complexity-theoretic gap for the ideal primality testing problem for the important families of ideals $I$ (namely, radical ideals and equidimensional Cohen-Macaulay ideals). For these classes of ideals, assuming the Generalized Riemann Hypothesis, we show that primality testing lies in $\Sigma_3^p \cap \Pi_3^p$. This significantly improves the upper bound for these classes, approaching their lower bound, as the primality testing problem is coNP-hard for these classes of ideals. Another consequence of our results is that for equidimensional Cohen-Macaulay ideals, we get the first PSPACE algorithm for primality testing, exponentially improving the space and time complexity of prior known algorithms.

In this paper, we study the following non-linear generalization of the classical Sylvester-Gallai configuration. Let K be an algebraically closed field of characteristic 0 and F={F1,…,Fm} ⊂ K[x1,…,xN] be a set of irreducible homogeneous polynomials of degree at most d such that Fi is not a scalar multiple of Fj for i ≠ j. We say that F is a radical Sylvester-Gallai configuration if for any two distinct Fi,Fj ∈ F, there is k ≠ i,j such that Fk ∈ rad(Fi,Fj). We prove that such radical Sylvester-Gallai configurations must be low dimensional. More precisely, we show that there exists a function λ : ℕ → ℕ, independent of K,N, and m, such that any such configuration F must satisfy

We prove a robust generalization of a Sylvester-Gallai type theorem for quadratic polynomials. More precisely, given a parameter 0 < δ ≤ 1 and a finite collection ℱ of irreducible and pairwise independent polynomials of degree at most 2, we say that ℱ is a (δ, 2)-radical Sylvester-Gallai configuration if for any polynomial F_i ∈ ℱ, there exist δ(|ℱ|-1) polynomials F_j such that |rad (F_i, F_j) ∩ ℱ| ≥ 3, that is, the radical of F_i, F_j contains a third polynomial in the set. We prove that any (δ, 2)-radical Sylvester-Gallai configuration ℱ must be of low dimension: that is dim span_ℂ{ℱ} = poly(1/δ).

We prove that any cubic radical Sylvester-Gallai configuration is constant dimensional. This solves a conjecture of Gupta in degree 3 and generalizes the result from Shpilka, who proved that quadratic radical Sylvester-Gallai configurations are constant dimensional. To prove our Sylvester-Gallai theorem, we develop several new tools combining techniques from algebraic geometry and elimination theory. Among our technical contributions, we prove a structure theorem characterizing non-radical ideals generated by two cubic forms, generalizing previous structure theorems for intersections of two quadrics. Moreover, building upon the groundbreaking work Ananyan and Hochster, we introduce the notion of wide Ananyan-Hochster algebras and show that these algebras allow us to transfer the local conditions of Sylvester-Gallai configurations into global conditions.

We consider the problem of computing succinct encodings of lists of generators for invariant rings for group actions. Mulmuley conjectured that there are always polynomial sized such encodings for invariant rings of SL_n(ℂ)-representations. We provide simple examples that disprove this conjecture (under standard complexity assumptions). We develop a general framework, denoted algebraic circuit search problems, that captures many important problems in algebraic complexity and computational invariant theory. This framework encompasses various proof systems in proof complexity and some of the central problems in invariant theory as exposed by the Geometric Complexity Theory (GCT) program, including the aforementioned problem of computing succinct encodings for generators for invariant rings.

Over the past decade there has been growing interest on characterizing which convex cones over Rn are spectrahedral, that is, are a linear section of the cone of positive semidefinite matrices. This interest is largely motivated by applications in control theory, optimization and combinatorics. One particular class of convex cones of interest is the class of hyperbolicity cones, where the (still open) Generalized Lax Conjecture states that every hyperbolicity cone is spectrahedral. Recent works [1, 2] have established that the hyperbolicity cones of the elementary symmetric polynomials and the homogeneous multivariate matching polynomial are spectrahedral, but the question of whether there exists an efficient spectrahedral representation for such cones remains open. Previous work [11] has provided exponential lower bounds on the spectrahedral representation of non-explicit hyperbolicity cones which are known to be spectrahedral. The current best lower unconditional bounds for explicit cones are the linear lower bounds proved by [7].

This paper initiates a systematic development of a theory of non-commutative optimization, a setting which greatly extends ordinary (Euclidean) convex optimization. It aims to unify and generalize a growing body of work from the past few years which developed and analyzed algorithms for natural geodesically convex optimization problems on Riemannian manifolds that arise from the symmetries of non-commutative groups. More specifically, these are algorithms to minimize the moment map (a noncommutative notion of the usual gradient), and to test membership in moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity, which quite magically arise from this apriori non-convex, non-linear setting). The importance of understanding this very general setting of geodesic optimization, as these works unveiled and powerfully demonstrate, is that it captures a diverse set of problems, many non-convex, in different areas of CS, math, and physics. Several of them were solved efficiently for the first time using noncommutative methods; the corresponding algorithms also lead to solutions of purely structural problems and to many new connections between disparate fields. In the spirit of standard convex optimization, we develop two general methods in the geodesic setting, a first order and a second order method, which respectively receive first and second order information on the “derivatives” of the function to be optimized. These in particular subsume all past results. The main technical work, again unifying and extending much of the previous work, goes into identifying the key parameters of the underlying group actions which control convergence to the optimum in each of these methods. These non-commutative analogues of “smoothness” in the commutative case are far more complex, and require significant algebraic and analytic machinery (much existing and some newly developed here). Despite this complexity, the way in which these parameters control convergence in both methods is quite simple and elegant. We also bound these parameters in several general cases. Our work points to intriguing open problems and suggests further research directions. We believe that extending this theory, namely understanding geodesic optimization better, is both mathematically and computationally fascinating; it provides a great meeting place for ideas and techniques from several very different research areas, and promises better algorithms for existing and yet unforeseen applications.

We prove new barrier results in arithmetic complexity theory, showing severe limitations of natural lifting (aka escalation) techniques. For example, we prove that even optimal rank lower bounds on $k$-tensors cannot yield non-trivial lower bounds on the rank of $d$-tensors, for any constant $d>k$. This significantly extends recent barrier results on the limits of (matrix) rank methods by Efremenko, Garg, Oliveira and Wigderson, which handles the (very important) case $k=2$. Our generalization requires the development of new technical tools and results in algebraic geometry, which are interesting in their own right and possibly applicable elsewhere. The basic issue they probe is the relation between numeric and symbolic rank of tensors, essential in the proofs of previous and current barriers. Our main technical result implies that for every symbolic $k$-tensor (namely one whose entries are polynomials in some set of variables), if the tensor rank is small for every evaluation of the variables, then it is small symbolically. This statement is obvious for $k=2$. To prove an analogous statement for $k>2$ we develop a "numeric to symbolic" transfer of algebraic relations to algebraic functions, somewhat in the spirit of the implicit function theorem. It applies in the general setting of inclusion of images of polynomial maps, in the form appearing in Raz's elusive functions approach to proving VP $\neq$ VNP. We give a toy application showing how our transfer theorem may be useful in pursuing this approach to prove arithmetic complexity lower bounds.

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\operatorname{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($ΣΠΣΠ$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = ω(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas~\cite{T15} for general circuits, and is known to be asymptotically optimal in the exponent when $d < n^ε$ for a small enough constant $ε$. Our upper bound matches the lower bound of $\exp\left({Ω\left(\sqrt{n\log n}\right)}\right)$ proved by Raz and Yehudayoff~\cite{RY09}, and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree. More generally, we show that an $n$-variate polynomial computable by a syntactically multilinear circuit of size $\operatorname{poly}(n)$ can be computed by a syntactically multilinear circuit of product-depth $Δ$ of size at most $\exp\left(O\left(Δ\cdot (n/\log n)^{1/Δ} \cdot \log n\right)\right)$. It follows from the lower bounds of Raz and Yehudayoff (CC 2009) that in general, for constant $Δ$, the exponent in this upper bound is tight and cannot be improved to $o\left(\left(n/\log n\right)^{1/Δ}\cdot \log n\right)$.

We present a polynomial time algorithm to approximately scale tensors of any format to arbitrary prescribed marginals (whenever possible). This unifies and generalizes a sequence of past works on matrix, operator and tensor scaling. Our algorithm provides an efficient weak membership oracle for the associated moment polytopes, an important family of implicitly-defined convex polytopes with exponentially many facets and a wide range of applications. These include the entanglement polytopes from quantum information theory (in particular, we obtain an efficient solution to the notorious one-body quantum marginal problem) and the Kronecker polytopes from representation theory (which capture the asymptotic support of Kronecker coefficients). Our algorithm can be applied to succinct descriptions of the input tensor whenever the marginals can be efficiently computed, as in the important case of matrix product states or tensor-train decompositions, widely used in computational physics and numerical mathematics. Beyond these applications, the algorithm enriches the arsenal of "numerical" methods for classical problems in invariant theory that are significantly faster than "symbolic" methods which explicitly compute invariants or covariants of the relevant action. We stress that (like almost all past algorithms) our convergence rate is polynomial in the approximation parameter; it is an intriguing question to achieve exponential convergence rate, beating symbolic algorithms exponentially, and providing strong membership and separation oracles for the problems above. We strengthen and generalize the alternating minimization approach of previous papers by introducing the theory of highest weight vectors from representation theory into the numerical optimization framework. We show that highest weight vectors are natural potential functions for scaling algorithms and prove new bounds on their evaluations to obtain polynomial-time convergence. Our techniques are general and we believe that they will be instrumental to obtain efficient algorithms for moment polytopes beyond the ones consider here, and more broadly, for other optimization problems possessing natural symmetries.

Alternating minimization heuristics seek to solve a (difficult) global optimization task through iteratively solving a sequence of (much easier) local optimization tasks on different parts (or blocks) of the input parameters. While popular and widely applicable, very few examples of this heuristic are rigorously shown to converge to optimality, and even fewer to do so efficiently. In this paper we present a general framework which is amenable to rigorous analysis, and expose its applicability. Its main feature is that the local optimization domains are each a group of invertible matrices, together naturally acting on tensors, and the optimization problem is minimizing the norm of an input tensor under this joint action. The solution of this optimization problem captures a basic problem in Invariant Theory, called the null-cone problem. This algebraic framework turns out to encompass natural computational problems in combinatorial optimization, algebra, analysis, quantum information theory, and geometric complexity theory. It includes and extends to high dimensions the recent advances on (2-dimensional) operator scaling. Our main result is a fully polynomial time approximation scheme for this general problem, which may be viewed as a multi-dimensional scaling algorithm. This directly leads to progress on some of the problems in the areas above, and a unified view of others. We explain how faster convergence of an algorithm for the same problem will allow resolving central open problems. Our main techniques come from Invariant Theory, and include its rich non-commutative duality theory, and new bounds on the bitsizes of coefficients of invariant polynomials. They enrich the algorithmic toolbox of this very computational field of mathematics, and are directly related to some challenges in geometric complexity theory (GCT).

Arithmetic complexity, the study of the cost of computing polynomials via additions and multiplications, is considered (for many good reasons) simpler to understand than Boolean complexity, namely computing Boolean functions via logical gates. And indeed, we seem to have significantly more lower bound techniques and results in arithmetic complexity than in Boolean complexity. Despite many successes and rapid progress, however, foundational challenges, like proving super-polynomial lower bounds on circuit or formula size for explicit polynomials, or super-linear lower bounds on explicit 3-dimensional tensors, remain elusive. At the same time (and possibly for similar reasons), we have plenty more excuses, in the form of "barrier results" for failing to prove basic lower bounds in Boolean complexity than in arithmetic complexity. Efforts to find barriers to arithmetic lower bound techniques seem harder, and despite some attempts we have no excuses of similar quality for these failures in arithmetic complexity. This paper aims to add to this study. In this paper we address rank methods, which were long recognized as encompassing and abstracting almost all known arithmetic lower bounds to-date, including the most recent impressive successes. Rank methods (under the name of flattenings) are also in wide use in algebraic geometry for proving tensor rank and symmetric tensor rank lower bounds. Our main results are barriers to these methods. In particular, 1. Rank methods cannot prove better than (2^d)*n^(d/2) lower bound on the tensor rank of any d-dimensional tensor of side n. (In particular, they cannot prove super-linear, indeed even >8n tensor rank lower bounds for any 3-dimensional tensors.) 2. Rank methods cannot prove (d+1)n^(d/2) on the Waring rank of any n-variate polynomial of degree d. (In particular, they cannot prove such lower bounds on stronger models, including depth-3 circuits.) The proofs of these bounds use simple linear-algebraic arguments, leveraging connections between the symbolic rank of matrix polynomials and the usual rank of their evaluations. These techniques can perhaps be extended to barriers for other arithmetic models on which progress has halted. To see how these barrier results directly inform the state-of-art in arithmetic complexity we note the following. First, the bounds above nearly match the best explicit bounds we know for these models, hence offer an explanations why the rank methods got stuck there. Second, the bounds above are a far cry (quadratically away) from the true complexity (e.g. of random polynomials) in these models, which if achieved (by any methods), are known to imply super-polynomial formula lower bounds. We also explain the relation of our barrier results to other attempts, and in particular how they significantly differ from the recent attempts to find analogues of "natural proofs" for arithmetic complexity. Finally, we discuss the few arithmetic lower bound approaches which fall outside rank methods, and some natural directions our barriers suggest.

We propose a new second-order method for geodesically convex optimization on the natural hyperbolic metric over positive definite matrices. We apply it to solve the operator scaling problem in time polynomial in the input size and logarithmic in the error. This is an exponential improvement over previous algorithms which were analyzed in the usual Euclidean, "commutative" metric (for which the above problem is not convex). Our method is general and applicable to other settings.

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate R and minimum distance δ of a binary code. The best known tradeoff is the Gilbert-Varshamov bound, and says that for every δ ∈ (0, 1/2), there are codes with minimum distance δ and rate R = RGV(δ) 0 (for a certain simple function RGV(·)). In this paper, we show that the Gilbert-Varshamov bound can be achieved by codes, which support local error-detection and error-correction algorithms. Specifically, we show the following results. 1) Local testing: for all δ ∈ (0, 1/2) and all RGV(δ), there exist codes with length n, rate R, and minimum distance δ that are locally testable with quasipoly log(n) query complexity. 2) Local correction: for all ϵ > 0, for all δGV(δ), there exist codes with length n, rate R, and minimum distance δ that are locally correctable from (δ/2)-o(1) fraction errors with O(nϵ) query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen's random concatenation technique and the best known locally testable codes by Kopparty et al. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami-Sudan-Indyk list decoding strategy for concatenated codes, Alon-Edmonds-Luby distance amplification, and the local list-decodability, local list-recoverability, and local testability of Reed-Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code.

We develop several efficient algorithms for the classical Matrix Scaling problem, which is used in many diverse areas, from preconditioning linear systems to approximation of the permanent. On an input n×n matrix A, this problem asks to find diagonal (scaling) matrices X and Y (if they exist), so that XAY ε-approximates a doubly stochastic matrix, or more generally a matrix with prescribed row and column sums. We address the general scaling problem as well as some important special cases. In particular, if A has m nonzero entries, and if there exist X and Y with polynomially large entries such that XAY is doubly stochastic, then we can solve the problem in total complexity Õ(m + n4/3). This greatly improves on the best known previous results, which were either Õ(n4) or O(mn1/2/ε). Our algorithms are based on tailor-made first and second order techniques, combined with other recent advances in continuous optimization, which may be of independent interest for solving similar problems.

One of the most important open problems in the theory of error-correcting codes is to determine the tradeoff between the rate R and minimum distance δ of a binary code. The best known tradeoff is the Gilbert-Varshamov bound, and says that for every δ ∊ (0,1/2), there are codes with minimum distance δ and rate R = rGV (δ) > 0 (for a certain simple function rGV(·)). In this paper we show that the Gilbert-Varshamov bound can be achieved by codes which support local error-detection and error- correction algorithms. Specifically, we show the following results. 1. Local Testing: For all δ ∊ (0,1/2) and all R < rGV(δ), there exist codes with length n, rate R and minimum distance δ that are locally testable with quasipolylog(n) query complexity. 2. Local Correction: For all ∊ > 0, for all δ < 1/2 sufficiently large, and all R < (1 — ∊)RGV(δ), there exist codes with length n, rate R and minimum distance δ that are locally correctable from fraction errors with O(ne) query complexity. Furthermore, these codes have an efficient randomized construction, and the local testing and local correction algorithms can be made to run in time polynomial in the query complexity. Our results on locally correctable codes also immediately give locally decodable codes with the same parameters. Our local testing result is obtained by combining Thommesen's random concatenation technique and the best known locally testable codes from [KMRS16]. Our local correction result, which is significantly more involved, also uses random concatenation, along with a number of further ideas: the Guruswami-Sudan-Indyk list decoding strategy for concatenated codes, Alon- Edmonds-Luby distance amplification, and the local list-decodability, local list-recoverability and local testability of Reed-Muller codes. Curiously, our final local correction algorithms go via local list-decoding and local testing algorithms; this seems to be the first time local testability is used in the construction of a locally correctable code.

The celebrated Brascamp-Lieb (BL) inequalities [BL76, Lie90], and their reverse form of Barthe [Bar98], are an important mathematical tool, unifying and generalizing numerous in- equalities in analysis, convex geometry and information theory, with many used in computer science. While their structural theory is very well understood, far less is known about computing their main parameters below (which we later define). Prior to this work, the best known algorithms for any of these optimization tasks required at least exponential time. In this work, we give polynomial time algorithms to compute:

Symbolic matrices in non-commuting variables, andthe related structural and algorithmic questions, have a remarkablenumber of diverse origins and motivations. They ariseindependently in (commutative) invariant theory and representationtheory, linear algebra, optimization, linear system theory,quantum information theory, and naturally in non-commutativealgebra.

Kaltofen (Randomness in computation, vol 5, pp 375–412, 1989) proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen’s work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked in Kopparty et al. (2014), and the question of bounding the depth of the circuits computing the factors of a polynomial. We are able to answer these questions in the affirmative for the interesting class of polynomials of bounded individual degrees, which contains polynomials such as the determinant and the permanent. We show that if $${P(x_{1},\ldots,x_{n})}$$ is a polynomial with individual degrees bounded by r that can be computed by a formula of size s and depth d, then any factor $${f(x_{1},\ldots, x_{n})}$$ of $${P(x_{1},\ldots,x_{n})}$$ can be computed by a formula of size $${\textsf{poly}((rn)^{r},s)}$$ and depth d + 5. This partially answers the question above posed in Kopparty et al. (2014), who asked if this result holds without the dependence on r. Our work generalizes the main factorization theorem from Dvir et al. (SIAM J Comput 39(4):1279–1293, 2009), who proved it for the special case when the factors are of the form $${f(x_{1}, \ldots, x_{n}) \equiv x_{n} - g(x_{1}, \ldots, x_{n-1})}$$ . Along the way, we introduce several new technical ideas that could be of independent interest when studying arithmetic circuits (or formulas).

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models. For depth-3 multilinear formulas, of size exp(n^delta), we give a hitting set of size exp(~O(n^(2/3 + 2*delta/3))). This implies a lower bound of exp(~Omega(n^(1/2))) for depth-3 multilinear formulas, for some explicit polynomial. For depth-4 multilinear formulas, of size exp(n^delta), we give a hitting set of size exp(~O(n^(2/3 + 4*delta/3)). This implies a lower bound of exp(~Omega(n^(1/4))) for depth-4 multilinear formulas, for some explicit polynomial. A regular formula consists of alternating layers of +,* gates, where all gates at layer i have the same fan-in. We give a hitting set of size (roughly) exp(n^(1-delta)), for regular depth-d multilinear formulas of size exp(n^delta), where delta = O(1/sqrt(5)^d)). This result implies a lower bound of roughly exp(~Omega(n^(1/sqrt(5)^d))) for such formulas. We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known. Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).