On the public citation graph

Towards optimal simulations of formulas by bounded-width programs

https://doi.org/10.1007/bf01200059
0 signed · 38 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/bfb0030331openalex-snapshot
A lower bound on complexity of branching programs
inferredcites →https://doi.org/10.1016/0022-0000(89)90037-8openalex-snapshot
Bounded-width polynomial-size branching programs recognize exactly those languages in NC1
inferredcites →https://doi.org/10.1109/sfcs.1983.30openalex-snapshot
Lower bounds by probabilistic arguments
inferredcites →https://doi.org/10.1109/sfcs.1989.63536openalex-snapshot
Subquadratic simulations of circuits by branching programs
inferredcites →https://doi.org/10.1145/100216.100251openalex-snapshot
Towards optimal simulations of formulas by bounded-width programs
inferredcites →https://doi.org/10.1145/12130.12131openalex-snapshot
Bounded-width polynomial-size branching programs recognize exactly those languages in NC 1
inferredcites →https://doi.org/10.1145/12130.12134openalex-snapshot
Two lower bounds for branching programs
inferredcites →https://doi.org/10.1145/321812.321815openalex-snapshot
The Parallel Evaluation of General Arithmetic Expressions
inferredcites →https://doi.org/10.1145/3749740.3749750openalex-snapshot
Completeness Classes in Algebra
inferredcites →https://doi.org/10.1145/62212.62215openalex-snapshot
Founding crytpography on oblivious transfer
inferredcites →https://doi.org/10.1145/62212.62236openalex-snapshot
Computing algebraic formulas with a constant number of registers
inferredcites →https://doi.org/10.1145/72981.72995openalex-snapshot
Non-cryptographic fault-tolerant computing in constant number of rounds of interaction
inferredcites →https://doi.org/10.1145/800061.808736openalex-snapshot
Bounds for width two branching programs
inferredcites →https://doi.org/10.1145/800061.808737openalex-snapshot
Multi-party protocols

What points at this work

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

inferred← citeshttps://doi.org/10.1006/jcss.1997.1530openalex-snapshot
Efficient Oblivious Branching Programs for Threshold and Mod Functions
inferred← citeshttps://doi.org/10.1006/jcss.2001.1762openalex-snapshot
Branching Program Size Is Almost Linear in Formula Size
inferred← citeshttps://doi.org/10.1007/11821069_13openalex-snapshot
The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
inferred← citeshttps://doi.org/10.1007/3-540-39200-9_37openalex-snapshot
Efficient Multi-party Computation over Rings
inferred← citeshttps://doi.org/10.1007/3-540-49116-3_5openalex-snapshot
Relating Branching Program Size and Formula Size over the Full Binary Basis
inferred← citeshttps://doi.org/10.1007/3-540-57568-5_251openalex-snapshot
Time space tradeoffs (getting closer to the barrier?)
inferred← citeshttps://doi.org/10.1007/978-3-030-17656-3_1openalex-snapshot
Homomorphic Secret Sharing from Lattices Without FHE
inferred← citeshttps://doi.org/10.1007/978-3-030-62974-8_5openalex-snapshot
Two-Server Verifiable Homomorphic Secret Sharing for High-Degree Polynomials
inferred← citeshttps://doi.org/10.1007/978-3-030-64378-2_13openalex-snapshot
Mr NISC: Multiparty Reusable Non-Interactive Secure Computation
inferred← citeshttps://doi.org/10.1007/978-3-030-77870-5_24openalex-snapshot
The Rise of Paillier: Homomorphic Secret Sharing and Public-Key Silent OT
inferred← citeshttps://doi.org/10.1007/978-3-030-90402-9_6openalex-snapshot
NIKE from Affine Determinant Programs
inferred← citeshttps://doi.org/10.1007/978-3-031-35486-1_12openalex-snapshot
Multi-key Homomorphic Secret Sharing from LWE Without Multi-key HE
inferred← citeshttps://doi.org/10.1007/978-3-662-44371-2_17openalex-snapshot
Faster Bootstrapping with Polynomial Error
inferred← citeshttps://doi.org/10.1007/978-3-662-49896-5_27openalex-snapshot
Post-zeroizing Obfuscation: New Mathematical Tools, and the Case of Evasive Circuits
inferred← citeshttps://doi.org/10.1109/ccc.2000.856733openalex-snapshot
BP(f)=O(L(f)/sup 1+έ/)
inferred← citeshttps://doi.org/10.1137/16m1082007openalex-snapshot
Communication Lower Bounds via Critical Block Sensitivity
inferred← citeshttps://doi.org/10.1145/2488608.2488640openalex-snapshot
Shielding circuits with groups
inferred← citeshttps://doi.org/10.1145/2554797.2554822openalex-snapshot
Iterated group products and leakage resilience against NC1
inferred← citeshttps://doi.org/10.1145/3133956.3134107openalex-snapshot
Homomorphic Secret Sharing
inferred← citeshttps://doi.org/10.1145/3583085openalex-snapshot
Catalytic Branching Programs from Groups and General Protocols
inferred← citeshttps://doi.org/10.17760/d20005081openalex-snapshot
Towards bridging theory and implementation of cryptographic primitives
inferred← citeshttps://doi.org/10.48550/arxiv.1311.2355openalex-snapshot
Communication Lower Bounds via Critical Block Sensitivity
inferred← citeshttps://doi.org/10.48550/arxiv.1312.3193openalex-snapshot
Iterated group products and leakage resilience against NC^1
inferred← citeshttps://doi.org/10.5445/ir/1000035100openalex-snapshot
Complete Primitives for Information-Theoretically Secure Two-Party Computation
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.