On the public citation graph

Separation Between Read-once Oblivious Algebraic Branching Programs (ROABPs) and Multilinear Depth-three Circuits

0 signed · 53 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.
Claim with ORCID
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.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1007/11590156_6openalex-snapshot
Proving Lower Bounds Via Pseudo-random Generators
inferredcites →https://doi.org/10.1007/3-540-09519-5_73openalex-snapshot
Probabilistic algorithms for sparse polynomials
inferredcites →https://doi.org/10.1007/978-3-319-05446-9_5openalex-snapshot
A Selection of Lower Bounds for Arithmetic Circuits
inferredcites →https://doi.org/10.1007/bf01294256openalex-snapshot
Lower bounds on arithmetic circuits via partial derivatives
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-008-0254-0openalex-snapshot
Balancing Syntactically Multilinear Arithmetic Circuits
inferredcites →https://doi.org/10.1007/s00037-009-0270-8openalex-snapshot
Lower Bounds and Separations for Constant Depth Multilinear Circuits
inferredcites →https://doi.org/10.1007/s00037-016-0131-1openalex-snapshot
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
inferredcites →https://doi.org/10.1007/s00224-014-9574-4openalex-snapshot
Lower Bounds for Tropical Circuits and Dynamic Programs
inferredcites →https://doi.org/10.1016/0020-0190(78)90067-4openalex-snapshot
A probabilistic remark on algebraic program testing
inferredcites →https://doi.org/10.1016/0095-8956(85)90092-9openalex-snapshot
λ1, Isoperimetric inequalities for graphs, and superconcentrators
inferredcites →https://doi.org/10.1016/s0022-0000(05)80043-1openalex-snapshot
Hardness vs randomness
inferredcites →https://doi.org/10.1090/s0002-9947-1984-0743744-xopenalex-snapshot
Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
inferredcites →https://doi.org/10.1090/s0273-0979-06-01126-8openalex-snapshot
Expander graphs and their applications
inferredcites →https://doi.org/10.1109/focs.2013.68openalex-snapshot
Arithmetic Circuits: A Chasm at Depth Three
inferredcites →https://doi.org/10.1112/jlms/s1-10.37.26openalex-snapshot
On Representatives of Subsets
inferredcites →https://doi.org/10.1112/jlms/s1-22.2.107openalex-snapshot
The Factorization of Linear Graphs
inferredcites →https://doi.org/10.1137/140975103openalex-snapshot
Hitting-Sets for ROABP and Sum of Set-Multilinear Circuits
inferredcites →https://doi.org/10.1145/1007352.1007353openalex-snapshot
Multi-linear formulas for permanent and determinant are of super-polynomial size
inferredcites →https://doi.org/10.1145/2213977.2214034openalex-snapshot
Separating multilinear branching programs and formulas
inferredcites →https://doi.org/10.1145/2488608.2488649openalex-snapshot
Quasi-polynomial hitting-set for set-depth-Δ formulas
inferredcites →https://doi.org/10.1145/2591796.2591816openalex-snapshot
Hitting sets for multilinear read-once algebraic branching programs, in any order
inferredcites →https://doi.org/10.1145/2591796.2591824openalex-snapshot
Lower bounds for depth 4 formulas computing iterated matrix multiplication
inferredcites →https://doi.org/10.1145/322217.322225openalex-snapshot
Fast Probabilistic Algorithms for Verification of Polynomial Identities
inferredcites →https://doi.org/10.1145/3749740.3749750openalex-snapshot
Completeness Classes in Algebra
inferredcites →https://doi.org/10.1145/800141.804674openalex-snapshot
Testing polynomials which are easy to compute (Extended Abstract)
inferredcites →https://doi.org/10.1561/0400000039openalex-snapshot
Arithmetic Circuits: A Survey of Recent Results and Open Questions
inferredcites →https://doi.org/10.1561/0400000043openalex-snapshot
Partial Derivatives in Arithmetic Complexity and Beyond
inferredcites →https://doi.org/10.4086/toc.2006.v002a006openalex-snapshot
inferredcites →https://doi.org/10.5555/1957995.1957999openalex-snapshot
Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

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-319-94776-1_58openalex-snapshot
Lower Bounds for Special Cases of Syntactic Multilinear ABPs
inferred← citeshttps://doi.org/10.1007/s00037-016-0141-zopenalex-snapshot
Deterministic Identity Testing for Sum of Read-Once Oblivious Arithmetic Branching Programs
inferred← citeshttps://doi.org/10.1007/s00037-021-00209-yopenalex-snapshot
Blackbox identity testing for sum of special ROABPs and its border class
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.1109/focs.2018.00092openalex-snapshot
A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits
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/18m1191567openalex-snapshot
Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications
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/3170709openalex-snapshot
Identity Testing and Lower Bounds for Read- k Oblivious Algebraic Branching Programs
inferred← citeshttps://doi.org/10.1145/3611094openalex-snapshot
Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits
inferred← citeshttps://doi.org/10.1145/3665800openalex-snapshot
Hitting Sets for Orbits of Circuit Classes and Polynomial Families
inferred← citeshttps://doi.org/10.1145/3717823.3718146openalex-snapshot
Characterizing and Testing Principal Minor Equivalence of Matrices
inferred← citeshttps://doi.org/10.4086/toc.2017.v013a002openalex-snapshot
inferred← citeshttps://doi.org/10.4086/toc.2018.v014a016openalex-snapshot
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.29openalex-snapshot
Identity Testing for Constant-Width, and Commutative, Read-Once Oblivious ABPs
inferred← citeshttps://doi.org/10.4230/lipics.ccc.2016.30openalex-snapshot
Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs
inferred← citeshttps://doi.org/10.48550/arxiv.1701.01717openalex-snapshot
Towards an algebraic natural proofs barrier via polynomial identity testing
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.06819openalex-snapshot
Lower Bounds of Algebraic Branching Programs and Layerization
inferred← citeshttps://doi.org/10.48550/arxiv.2010.01385openalex-snapshot
Limitations of Sums of Bounded-Read Formulas
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.