On the public citation graph
Multi-linear formulas for permanent and determinant are of super-polynomial size
0 signed · 162 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1007/978-3-662-03338-8openalex-snapshot
Algebraic Complexity Theory
inferredcites →https://doi.org/10.1007/bf01294256openalex-snapshot
Lower bounds on arithmetic circuits via partial derivatives
inferredcites →https://doi.org/10.1007/bf01744302openalex-snapshot
On the depth complexity of formulas
inferredcites →https://doi.org/10.1007/pl00001609openalex-snapshot
Depth-3 arithmetic circuits over fields of characteristic zero
inferredcites →https://doi.org/10.1007/s00037-004-0182-6openalex-snapshot
Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
inferredcites →https://doi.org/10.1007/s00037-005-0188-8openalex-snapshot
Deterministic polynomial identity testing in non-commutative models
inferredcites →https://doi.org/10.1007/s002009900021openalex-snapshot
Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields
inferredcites →https://doi.org/10.1016/0304-3975(76)90083-9openalex-snapshot
A lower bound on the number of additions in monotone computations
inferredcites →https://doi.org/10.1016/0304-3975(80)90060-2openalex-snapshot
Negation can be exponentially powerful
inferredcites →https://doi.org/10.1016/j.jcss.2010.06.013openalex-snapshot
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors
inferredcites →https://doi.org/10.1016/s0747-7171(87)80063-9openalex-snapshot
Feasible arithmetic computations: Valiant's hypothesis
inferredcites →https://doi.org/10.1017/cbo9780511526633.008openalex-snapshot
Why is Boolean Complexity Theory so Difficult?
inferredcites →https://doi.org/10.1109/ccc.2004.11openalex-snapshot
Deterministic polynomial identity testing in non commutative models
inferredcites →https://doi.org/10.1109/ccc.2008.8openalex-snapshot
Lower Bounds and Separations for Constant Depth Multilinear Circuits
inferredcites →https://doi.org/10.1109/focs.2007.6openalex-snapshot
48th Annual IEEE Symposium on Foundations of Computer Science - TOC
inferredcites →https://doi.org/10.1109/sfcs.1995.492458openalex-snapshot
Lower bounds on arithmetic circuits via partial derivatives
inferredcites →https://doi.org/10.1137/0214050openalex-snapshot
A Lower Bound for the Formula Size of Rational Functions
inferredcites →https://doi.org/10.1145/1007352.1007378openalex-snapshot
Multilinear formulas and skepticism of quantum computing
inferredcites →https://doi.org/10.1145/103418.103462openalex-snapshot
Lower bounds for non-commutative computation
inferredcites →https://doi.org/10.1145/276698.276872openalex-snapshot
An exponential lower bound for depth 3 arithmetic circuits
inferredcites →https://doi.org/10.1145/780542.780595openalex-snapshot
Derandomizing polynomial identity tests means proving circuit lower bounds
inferredcites →https://doi.org/10.1146/annurev.cs.03.060188.001533openalex-snapshot
Algebraic Complexity Theory
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/11537311_4openalex-snapshot
On the Incompressibility of Monotone DNFs
inferred← citeshttps://doi.org/10.1007/978-3-030-26176-4_15openalex-snapshot
On Proving Parameterized Size Lower Bounds for Multilinear Algebraic Models
inferred← citeshttps://doi.org/10.1007/978-3-030-79416-3_9openalex-snapshot
Limitations of Sums of Bounded Read Formulas and ABPs
inferred← citeshttps://doi.org/10.1007/978-3-030-86593-1_30openalex-snapshot
On the Hardness of the Determinant: Sum of Regular Set-Multilinear Circuits
inferred← citeshttps://doi.org/10.1007/978-3-031-23101-8_20openalex-snapshot
Lower Bounds for Monotone q-Multilinear Boolean Circuits
inferred← citeshttps://doi.org/10.1007/978-3-319-05446-9_4openalex-snapshot
Algebraic Complexity Classes
inferred← citeshttps://doi.org/10.1007/978-3-319-05446-9_5openalex-snapshot
A Selection of Lower Bounds for Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/978-3-319-32162-2_1openalex-snapshot
$$P\mathop{ =}\limits^{?}NP$$
inferred← citeshttps://doi.org/10.1007/978-3-319-34171-2_19openalex-snapshot
Sums of Read-Once Formulas: How Many Summands Suffice?
inferred← citeshttps://doi.org/10.1007/978-3-319-62389-4_21openalex-snapshot
On Constant Depth Circuits Parameterized by Degree: Identity Testing and Depth Reduction
inferred← citeshttps://doi.org/10.1007/978-3-319-94776-1_58openalex-snapshot
Lower Bounds for Special Cases of Syntactic Multilinear ABPs
inferred← citeshttps://doi.org/10.1007/978-3-540-30538-5_38openalex-snapshot
Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching Require Exponential Size
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_6openalex-snapshot
Diagonal Circuit Identity Testing and Lower Bounds
inferred← citeshttps://doi.org/10.1007/978-3-540-85238-4_37openalex-snapshot
Arithmetic Circuits, Syntactic Multilinearity, and the Limitations of Skew Formulae
inferred← citeshttps://doi.org/10.1007/978-3-642-03351-3_17openalex-snapshot
Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
inferred← citeshttps://doi.org/10.1007/978-3-642-03351-3_18openalex-snapshot
Simulation of Arithmetical Circuits by Branching Programs with Preservation of Constant Width and Syntactic Multilinearity
inferred← citeshttps://doi.org/10.1007/978-3-642-13562-0_7openalex-snapshot
Algebraic Proofs over Noncommutative Formulas
inferred← citeshttps://doi.org/10.1007/978-3-642-14165-2_35openalex-snapshot
On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors
inferred← citeshttps://doi.org/10.1007/978-3-642-14165-2_37openalex-snapshot
Exponential Time Complexity of the Permanent and the Tutte Polynomial
inferred← citeshttps://doi.org/10.1007/978-3-642-39206-1_56openalex-snapshot
Arithmetic Circuit Lower Bounds via MaxRank
inferred← citeshttps://doi.org/10.1007/978-3-662-48054-0_27openalex-snapshot
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
inferred← citeshttps://doi.org/10.1007/978-981-97-2340-9_30openalex-snapshot
Lower Bounds for the Sum of Small-Size Algebraic Branching Programs
inferred← citeshttps://doi.org/10.1007/s00037-008-0246-0openalex-snapshot
The Strength of Multilinear Proofs
inferred← citeshttps://doi.org/10.1007/s00037-008-0254-0openalex-snapshot
Balancing Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/s00037-009-0263-7openalex-snapshot
The Black-Box Query Complexity of Polynomial Summation
inferred← citeshttps://doi.org/10.1007/s00037-009-0270-8openalex-snapshot
Lower Bounds and Separations for Constant Depth Multilinear Circuits
inferred← citeshttps://doi.org/10.1007/s00037-009-0284-2openalex-snapshot
Quadratic Lower Bound for Permanent Vs. Determinant in any Characteristic
inferred← citeshttps://doi.org/10.1007/s00037-011-0007-3openalex-snapshot
Homogeneous Formulas and Symmetric Polynomials
inferred← citeshttps://doi.org/10.1007/s00037-013-0072-xopenalex-snapshot
Resource Trade-offs in Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1007/s00037-015-0103-xopenalex-snapshot
Unifying Known Lower Bounds via Geometric Complexity Theory
inferred← citeshttps://doi.org/10.1007/s00037-015-0105-8openalex-snapshot
Read-once polynomial identity testing
inferred← citeshttps://doi.org/10.1007/s00037-016-0131-1openalex-snapshot
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
inferred← citeshttps://doi.org/10.1007/s00037-018-0171-9openalex-snapshot
Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees
inferred← citeshttps://doi.org/10.1007/s00037-019-00189-0openalex-snapshot
Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
inferred← citeshttps://doi.org/10.1007/s00037-020-00196-6openalex-snapshot
On $$\epsilon$$-sensitive monotone computations
inferred← citeshttps://doi.org/10.1007/s00224-007-2013-zopenalex-snapshot
On the Incompressibility of Monotone DNFs
inferred← citeshttps://doi.org/10.1007/s00224-010-9285-4openalex-snapshot
Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model
inferred← citeshttps://doi.org/10.1007/s00224-010-9308-1openalex-snapshot
Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials
inferred← citeshttps://doi.org/10.1007/s00224-016-9742-9openalex-snapshot
Multi-k-ic Depth Three Circuit Lower Bound
inferred← citeshttps://doi.org/10.1007/s00493-016-3460-4openalex-snapshot
Black-Box Identity Testing of Depth-4 Multilinear Circuits
inferred← citeshttps://doi.org/10.1007/s00493-019-4009-0openalex-snapshot
Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1016/j.apal.2008.04.001openalex-snapshot
Resolution over linear equations and multilinear proofs
inferred← citeshttps://doi.org/10.1016/j.dam.2024.09.023openalex-snapshot
Notes on Boolean read- k and multilinear circuits
inferred← citeshttps://doi.org/10.1016/j.ic.2011.07.004openalex-snapshot
Algebraic proofs over noncommutative formulas
inferred← citeshttps://doi.org/10.1016/j.ipl.2019.105839openalex-snapshot
A note on parameterized polynomial identity testing using hitting set generators
inferred← citeshttps://doi.org/10.1016/j.jcss.2010.06.013openalex-snapshot
Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors
inferred← citeshttps://doi.org/10.1016/j.jpaa.2017.02.008openalex-snapshot
On the complexity of the permanent in various computational models
inferred← citeshttps://doi.org/10.1016/j.tcs.2017.10.019openalex-snapshot
Sums of read-once formulas: How many summands are necessary?
inferred← citeshttps://doi.org/10.1016/j.tcs.2019.10.047openalex-snapshot
Lower bounds for special cases of syntactic multilinear ABPs
inferred← citeshttps://doi.org/10.1016/j.tcs.2025.115214openalex-snapshot
Lower bounds for the sum of small-size algebraic branching programs
inferred← citeshttps://doi.org/10.1070/sm2012v203n10abeh004270openalex-snapshot
A method for deriving lower bounds for the complexity of monotone arithmetic circuits computing real polynomials
inferred← citeshttps://doi.org/10.1090/bull/1880openalex-snapshot
Asymptotic spectra: Theory, applications, and extensions
inferred← citeshttps://doi.org/10.1090/s0894-0347-2011-00694-2openalex-snapshot
Non-commutative circuits and the sum-of-squares problem
inferred← citeshttps://doi.org/10.1109/ccc.2004.11openalex-snapshot
Deterministic polynomial identity testing in non commutative models
inferred← citeshttps://doi.org/10.1109/ccc.2008.8openalex-snapshot
Lower Bounds and Separations for Constant Depth Multilinear Circuits
inferred← citeshttps://doi.org/10.1109/ccc.2009.19openalex-snapshot
A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent
inferred← citeshttps://doi.org/10.1109/ccc.2013.16openalex-snapshot
Approaching the Chasm at Depth Four
inferred← citeshttps://doi.org/10.1109/ccc.2014.35openalex-snapshot
Unifying Known Lower Bounds via Geometric Complexity Theory
inferred← citeshttps://doi.org/10.1109/focs.2004.42openalex-snapshot
Multilinear- NC₁ ≠ Multilinear- NC₂
inferred← citeshttps://doi.org/10.1109/focs.2004.9openalex-snapshot
Algebras with Polynomial Identities and Computing the Determinant
inferred← citeshttps://doi.org/10.1109/focs.2007.13openalex-snapshot
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
inferred← citeshttps://doi.org/10.1109/focs.2007.6openalex-snapshot
48th Annual IEEE Symposium on Foundations of Computer Science - TOC
inferred← citeshttps://doi.org/10.1109/focs.2011.70openalex-snapshot
Efficient Reconstruction of Random Multilinear Formulas
inferred← citeshttps://doi.org/10.1109/focs.2013.34openalex-snapshot
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs
inferred← citeshttps://doi.org/10.1109/focs.2014.15openalex-snapshot
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
inferred← citeshttps://doi.org/10.1109/focs.2015.35openalex-snapshot
Deterministic Divisibility Testing via Shifted Partial Derivatives
inferred← citeshttps://doi.org/10.1109/focs.2015.65openalex-snapshot
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k
inferred← citeshttps://doi.org/10.1109/focs46700.2020.00087openalex-snapshot
Learning sums of powers of low-degree polynomials in the non-degenerate case
inferred← citeshttps://doi.org/10.1109/focs52979.2021.00083openalex-snapshot
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
inferred← citeshttps://doi.org/10.1137/110824516openalex-snapshot
Deterministic Identity Testing of Depth-4 Multilinear Circuits with Bounded Top Fan-in
inferred← citeshttps://doi.org/10.1137/151002423openalex-snapshot
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
inferred← citeshttps://doi.org/10.1142/s1793557114500314openalex-snapshot
Types of depth and formula size
inferred← citeshttps://doi.org/10.1145/1007352.1007378openalex-snapshot
Multilinear formulas and skepticism of quantum computing
inferred← citeshttps://doi.org/10.1145/1060590.1060678openalex-snapshot
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
inferred← citeshttps://doi.org/10.1145/1248377.1248391openalex-snapshot
Optimal sparse matrix dense vector multiplication in the I/O-model
inferred← citeshttps://doi.org/10.1145/1374376.1374446openalex-snapshot
A quadratic lower bound for the permanent and determinant problem over any characteristic ≠ 2
inferred← citeshttps://doi.org/10.1145/1374376.1374479openalex-snapshot
Elusive functions and lower bounds for arithmetic circuits
inferred← citeshttps://doi.org/10.1145/1806689.1806779openalex-snapshot
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
inferred← citeshttps://doi.org/10.1145/1806689.1806780openalex-snapshot
Tensor-rank and lower bounds for arithmetic formulas
inferred← citeshttps://doi.org/10.1145/1806689.1806781openalex-snapshot
Non-commutative circuits and the sum-of-squares problem
inferred← citeshttps://doi.org/10.1145/2213977.2214034openalex-snapshot
Separating multilinear branching programs and formulas
inferred← citeshttps://doi.org/10.1145/2213977.2214035openalex-snapshot
Reconstruction of depth-4 multilinear circuits with top fan-in 2
inferred← citeshttps://doi.org/10.1145/2535928openalex-snapshot
Tensor-Rank and Lower Bounds for Arithmetic Formulas
inferred← citeshttps://doi.org/10.1145/2591796.2591816openalex-snapshot
Hitting sets for multilinear read-once algebraic branching programs, in any order
inferred← citeshttps://doi.org/10.1145/2591796.2591823openalex-snapshot
Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas
inferred← citeshttps://doi.org/10.1145/2591796.2591824openalex-snapshot
Lower bounds for depth 4 formulas computing iterated matrix multiplication
inferred← citeshttps://doi.org/10.1145/2591796.2591847openalex-snapshot
A super-polynomial lower bound for regular arithmetic formulas
inferred← citeshttps://doi.org/10.1145/2635812openalex-snapshot
Exponential Time Complexity of the Permanent and the Tutte Polynomial
inferred← citeshttps://doi.org/10.1145/2897518.2897550openalex-snapshot
On the size of homogeneous and of depth four formulas with low individual degree
inferred← citeshttps://doi.org/10.1145/2898437openalex-snapshot
Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices
inferred← citeshttps://doi.org/10.1145/3055399.3055496openalex-snapshot
Succinct hitting sets and barriers to proving algebraic circuits lower bounds
inferred← citeshttps://doi.org/10.1145/3209663openalex-snapshot
On Algebraic Branching Programs of Small Width
inferred← citeshttps://doi.org/10.1145/3313232openalex-snapshot
Lower bounds for Sum and Sum of Products of Read-once Formulas
inferred← citeshttps://doi.org/10.1145/3369928openalex-snapshot
Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits
inferred← citeshttps://doi.org/10.1145/3519935.3520044openalex-snapshot
Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication
inferred← citeshttps://doi.org/10.1145/3611094openalex-snapshot
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
inferred← citeshttps://doi.org/10.1145/3618260.3649760openalex-snapshot
On the Power of Homogeneous Algebraic Formulas
inferred← citeshttps://doi.org/10.1145/3689957openalex-snapshot
Improved Lower Bound, and Proof Barrier, for Constant Depth Algebraic Circuits
inferred← citeshttps://doi.org/10.1145/3798129.3800779openalex-snapshot
Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
inferred← citeshttps://doi.org/10.1561/0400000039openalex-snapshot
Arithmetic Circuits: A Survey of Recent Results and Open Questions
inferred← citeshttps://doi.org/10.1561/0400000043openalex-snapshot
Partial Derivatives in Arithmetic Complexity and Beyond
inferred← citeshttps://doi.org/10.1561/9781601984814openalex-snapshot
Partial Derivatives in Arithmetic Complexity and Beyond
inferred← citeshttps://doi.org/10.2139/ssrn.4752485openalex-snapshot
On the Hardness of the Determinant: Sum of Regular Set-Multilinear Circuits1
inferred← citeshttps://doi.org/10.23919/date58400.2024.10546633openalex-snapshot
Quantum State Preparation Using an Exact CNOT Synthesis Formulation
inferred← citeshttps://doi.org/10.24963/kr.2021/20openalex-snapshot
A Compilation of Succinctness Results for Arithmetic Circuits
inferred← citeshttps://doi.org/10.4171/022-3/54openalex-snapshot
Pseudorandomness and combinatorial constructions
inferred← citeshttps://doi.org/10.4213/sm7904openalex-snapshot
Об одном методе получения нижних оценок сложности монотонных арифметических схем, вычисляющих действительные многочлены
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2015.304openalex-snapshot
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.32openalex-snapshot
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.33openalex-snapshot
Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity
inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2016.39openalex-snapshot
Limitations of sum of products of Read-Once Polynomials
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2019.53openalex-snapshot
On the Symmetries of and Equivalence Test for Design Polynomials
inferred← citeshttps://doi.org/10.4230/lipics.stacs.2025.53openalex-snapshot
On Read-k Projections of the Determinant
inferred← citeshttps://doi.org/10.48550/arxiv.1309.5668openalex-snapshot
Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order
inferred← citeshttps://doi.org/10.48550/arxiv.1512.04386openalex-snapshot
Read-once polynomials: How many summands suffice?
inferred← citeshttps://doi.org/10.48550/arxiv.1702.05328openalex-snapshot
On algebraic branching programs of small width
inferred← citeshttps://doi.org/10.48550/arxiv.1710.09502openalex-snapshot
Barriers for Rank Methods in Arithmetic Complexity
inferred← citeshttps://doi.org/10.48550/arxiv.1804.08810openalex-snapshot
Lower Bounds for Special Cases of Syntactic Multilinear ABPs
inferred← citeshttps://doi.org/10.48550/arxiv.2007.07496openalex-snapshot
Observations on Symmetric Circuits
inferred← citeshttps://doi.org/10.48550/arxiv.2010.01385openalex-snapshot
Limitations of Sums of Bounded-Read Formulas
inferred← citeshttps://doi.org/10.48550/arxiv.quant-ph/0412143openalex-snapshot
Limits on Efficient Computation in the Physical World
inferred← citeshttps://doi.org/10.48550/arxiv.quant-ph/0507242openalex-snapshot
Are Quantum States Exponentially Long Vectors?
inferred← citeshttps://doi.org/10.70675/10b79942z0379z46a4zbb33z9331f6eae3dbopenalex-snapshot
Des fonctions difficiles en compilation de connaissances : bornes inférieures et applications
inferred← citeshttps://doi.org/10.7282/t35d8qvqopenalex-snapshot
On circuit complexity classes and iterated matrix multiplication
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.