On the public citation graph
Arithmetization: A new method in structural complexity theory
0 signed · 119 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/3-540-50517-2_80openalex-snapshot
Circuit definitions of nondeterministic complexity classes
inferredcites →https://doi.org/10.1007/3-540-52282-4_30openalex-snapshot
Hiding instances in multioracle queries
inferredcites →https://doi.org/10.1007/3-540-52282-4_31openalex-snapshot
Counting classes: Thresholds, parity, mods, and fewness
inferredcites →https://doi.org/10.1007/bf01200056openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1007/bf01200430openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1016/0022-0000(88)90028-1openalex-snapshot
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
inferredcites →https://doi.org/10.1016/0022-0000(89)90020-2openalex-snapshot
Probabilistic complexity classes and lowness
inferredcites →https://doi.org/10.1016/0304-3975(76)90061-xopenalex-snapshot
The polynomial-time hierarchy
inferredcites →https://doi.org/10.1016/0304-3975(79)90044-6openalex-snapshot
The Complexity of Computing the Permanent
inferredcites →https://doi.org/10.1016/0304-3975(86)90135-0openalex-snapshot
NP is as easy as detecting unique solutions
inferredcites →https://doi.org/10.1016/0304-3975(92)90084-sopenalex-snapshot
Counting classes: thresholds, parity, mods, and fewness
inferredcites →https://doi.org/10.1109/fscs.1990.89520openalex-snapshot
Nondeterministic exponential time has two-prover interactive protocols
inferredcites →https://doi.org/10.1109/fscs.1990.89521openalex-snapshot
A characterization of Hash P by arithmetic straight line programs
inferredcites →https://doi.org/10.1109/psct.1987.10319246openalex-snapshot
Probabilistic Complexity Classes and Lowness
inferredcites →https://doi.org/10.1109/sct.1990.113952openalex-snapshot
E-mail and the unexpected power of interaction
inferredcites →https://doi.org/10.1109/sct.1991.160241openalex-snapshot
Gap-definable counting classes
inferredcites →https://doi.org/10.1109/sct.1991.160252openalex-snapshot
On the random-self-reducibility of complete sets
inferredcites →https://doi.org/10.1109/sfcs.1986.47openalex-snapshot
Proofs that yield nothing but their validity and a methodology of cryptographic protocol design
inferredcites →https://doi.org/10.1109/sfcs.1989.63527openalex-snapshot
On the computational power of PP and (+)P
inferredcites →https://doi.org/10.1137/0218012openalex-snapshot
The Knowledge Complexity of Interactive Proof Systems
inferredcites →https://doi.org/10.1137/0221040openalex-snapshot
Circuit Definitions of Nondeterministic Complexity Classes
inferredcites →https://doi.org/10.1142/s0129054191000066openalex-snapshot
#P-COMPLETENESS VIA MANY-ONE REDUCTIONS
inferredcites →https://doi.org/10.1145/100216.100225openalex-snapshot
Self-testing/correcting with applications to numerical problems
inferredcites →https://doi.org/10.1145/103418.103426openalex-snapshot
PP is closed under intersection
inferredcites →https://doi.org/10.1145/146585.146605openalex-snapshot
Algebraic methods for interactive proof systems
inferredcites →https://doi.org/10.1145/22145.22192openalex-snapshot
Trading group theory for randomness
inferredcites →https://doi.org/10.1145/28395.28404openalex-snapshot
Algebraic methods in the theory of lower bounds for Boolean circuit complexity
inferredcites →https://doi.org/10.1145/73007.73015openalex-snapshot
Designing programs that check their work
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1006/inco.1996.0001openalex-snapshot
PP Is Closed under Truth-Table Reductions
inferred← citeshttps://doi.org/10.1006/jcss.2000.1728openalex-snapshot
Computational Arithmetic Geometry
inferred← citeshttps://doi.org/10.1006/jcss.2001.1768openalex-snapshot
Integer Circuit Evaluation Is PSPACE-Complete
inferred← citeshttps://doi.org/10.1006/jcss.2001.1786openalex-snapshot
Spectral Methods for Matrix Rigidity with Applications to Size–Depth Trade-offs and Communication Complexity
inferred← citeshttps://doi.org/10.1007/0-387-23830-1_3openalex-snapshot
Probabilistic Verification and Non-Approximability
inferred← citeshttps://doi.org/10.1007/11821069_61openalex-snapshot
Characterizing Valiant’s Algebraic Complexity Classes
inferred← citeshttps://doi.org/10.1007/3-540-36494-3_47openalex-snapshot
Competing Provers Yield Improved Karp-Lipton Collapse Results
inferred← citeshttps://doi.org/10.1007/3-540-44450-5_13openalex-snapshot
Arithmetic Circuits and Polynomial Replacement Systems
inferred← citeshttps://doi.org/10.1007/3-540-58325-4_175openalex-snapshot
On helping and interactive proof systems
inferred← citeshttps://doi.org/10.1007/3-540-60084-1_74openalex-snapshot
New collapse consequences of NP having small circuits
inferred← citeshttps://doi.org/10.1007/3-540-60178-3_81openalex-snapshot
Computation models and function algebras
inferred← citeshttps://doi.org/10.1007/978-3-030-26954-8_23openalex-snapshot
Scalable Zero Knowledge with No Trusted Setup
inferred← citeshttps://doi.org/10.1007/978-3-319-26850-7_29openalex-snapshot
EPiC: Efficient Privacy-Preserving Counting for MapReduce
inferred← citeshttps://doi.org/10.1007/978-3-642-22953-4_18openalex-snapshot
Succinct Algebraic Branching Programs Characterizing Non-uniform Complexity Classes
inferred← citeshttps://doi.org/10.1007/bf01200056openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferred← citeshttps://doi.org/10.1007/bf01200430openalex-snapshot
Non-deterministic exponential time has two-prover interactive protocols
inferred← citeshttps://doi.org/10.1007/bf01275486openalex-snapshot
BPP has subexponential time simulations unlessEXPTIME has publishable proofs
inferred← citeshttps://doi.org/10.1007/s00037-007-0224-yopenalex-snapshot
Communication vs. Computation
inferred← citeshttps://doi.org/10.1007/s00145-025-09567-0openalex-snapshot
Study of Arithmetization Methods for STARKs
inferred← citeshttps://doi.org/10.1007/s00607-018-0634-5openalex-snapshot
EPiC: efficient privacy-preserving counting for MapReduce
inferred← citeshttps://doi.org/10.1016/0012-365x(94)00112-vopenalex-snapshot
Probabilistically checkable proofs and their consequences for approximation algorithms
inferred← citeshttps://doi.org/10.1016/0196-6774(92)90052-eopenalex-snapshot
The NP-completeness column: An ongoing guide
inferred← citeshttps://doi.org/10.1016/0304-3975(93)90210-kopenalex-snapshot
Interactive proof systems and alternating time—space complexity
inferred← citeshttps://doi.org/10.1016/0304-3975(95)00237-5openalex-snapshot
Recursion theoretic characterizations of complexity classes of counting functions
inferred← citeshttps://doi.org/10.1016/j.ic.2005.01.002openalex-snapshot
Competing provers yield improved Karp–Lipton collapse results
inferred← citeshttps://doi.org/10.1016/j.ic.2020.104627openalex-snapshot
A structured view on weighted counting with relations to counting, quantum computation and applications
inferred← citeshttps://doi.org/10.1016/j.jco.2006.09.006openalex-snapshot
Characterizing Valiant's algebraic complexity classes
inferred← citeshttps://doi.org/10.1016/j.jco.2012.04.005openalex-snapshot
Software Engineering and complexity in effective Algebraic Geometry
inferred← citeshttps://doi.org/10.1016/j.jcss.2013.08.001openalex-snapshot
The complexity of weighted counting for acyclic conjunctive queries
inferred← citeshttps://doi.org/10.1016/j.jisa.2019.102391openalex-snapshot
Order-preserving encryption using approximate common divisors
inferred← citeshttps://doi.org/10.1016/j.tcs.2005.07.032openalex-snapshot
A note on the circuit complexity of PP
inferred← citeshttps://doi.org/10.1016/j.tcs.2015.07.030openalex-snapshot
Shorter arithmetization of nondeterministic computations
inferred← citeshttps://doi.org/10.1016/s0022-0000(05)80024-8openalex-snapshot
Gap-definable counting classes
inferred← citeshttps://doi.org/10.1016/s0049-237x(99)80033-0openalex-snapshot
Computation Models and Function Algebras
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00151-1openalex-snapshot
Approximate evaluations of characteristic polynomials of Boolean functions
inferred← citeshttps://doi.org/10.1016/s0304-3975(00)00159-6openalex-snapshot
A nonadaptive NC checker for permutation group intersection
inferred← citeshttps://doi.org/10.1016/s0304-3975(99)00183-8openalex-snapshot
Cook's versus Valiant's hypothesis
inferred← citeshttps://doi.org/10.1090/conm/270/04379openalex-snapshot
Algebraic geometry over four rings and the frontier to tractability
inferred← citeshttps://doi.org/10.1103/physreve.82.031106openalex-snapshot
Making classical ground-state spin computing fault-tolerant
inferred← citeshttps://doi.org/10.1109/ccc.1997.612316openalex-snapshot
A nonadaptive NC checker for permutation group intersection
inferred← citeshttps://doi.org/10.1109/focs.2016.35openalex-snapshot
Settling the Complexity of Computing Approximate Two-Player Nash Equilibria
inferred← citeshttps://doi.org/10.1109/focs.2018.00021openalex-snapshot
Delegating Computations with (Almost) Minimal Time and Space Overhead
inferred← citeshttps://doi.org/10.1109/sct.1991.160241openalex-snapshot
Gap-definable counting classes
inferred← citeshttps://doi.org/10.1109/sct.1991.160252openalex-snapshot
On the random-self-reducibility of complete sets
inferred← citeshttps://doi.org/10.1109/sct.1991.160263openalex-snapshot
BPP has subexponential time simulations unless EXPTIME has publishable proofs
inferred← citeshttps://doi.org/10.1109/sct.1992.215390openalex-snapshot
Formal power series: an algebraic approach to the GapP and Hash P functions
inferred← citeshttps://doi.org/10.1109/sfcs.1992.267823openalex-snapshot
Proof verification and hardness of approximation problems
inferred← citeshttps://doi.org/10.1109/sfcs.1994.365678openalex-snapshot
Program result-checking: a theory of testing meets a test of theory
inferred← citeshttps://doi.org/10.1109/sfcs.1995.492457openalex-snapshot
Spectral methods for matrix rigidity with applications to size-depth tradeoffs and communication complexity
inferred← citeshttps://doi.org/10.1137/0222061openalex-snapshot
Random-Self-Reducibility of Complete Sets
inferred← citeshttps://doi.org/10.1137/s009753970139207xopenalex-snapshot
Arithmetic Circuits and Polynomial Replacement Systems
inferred← citeshttps://doi.org/10.1137/s0097539793255151openalex-snapshot
Robust Characterizations of Polynomials with Applications to Program Testing
inferred← citeshttps://doi.org/10.1137/s0097539795296206openalex-snapshot
New Collapse Consequences of NP Having Small Circuits
inferred← citeshttps://doi.org/10.1145/103418.103428openalex-snapshot
Checking computations in polylogarithmic time
inferred← citeshttps://doi.org/10.1145/146585.146605openalex-snapshot
Algebraic methods for interactive proof systems
inferred← citeshttps://doi.org/10.1145/268999.269003openalex-snapshot
Software reliability via run-time result-checking
inferred← citeshttps://doi.org/10.1145/278298.278306openalex-snapshot
Proof verification and the hardness of approximation problems
inferred← citeshttps://doi.org/10.1145/3241304openalex-snapshot
Hardness of Approximation Between P and NP
inferred← citeshttps://doi.org/10.1145/3241304.3241306openalex-snapshot
The Frontier of Intractability
inferred← citeshttps://doi.org/10.1145/3241304.3241308openalex-snapshot
Communication complexity of approximate Nash equilibrium
inferred← citeshttps://doi.org/10.1145/3241304.3241310openalex-snapshot
PPAD-hardness of approximation
inferred← citeshttps://doi.org/10.1145/3241304.3241311openalex-snapshot
The generalized circuit problem
inferred← citeshttps://doi.org/10.1145/3241304.3241319openalex-snapshot
VC and Littlestone's dimensions
inferred← citeshttps://doi.org/10.1145/3241304.3241321openalex-snapshot
2-player approximate Nash equilibrium
inferred← citeshttps://doi.org/10.2178/jsl/1230396913openalex-snapshot
A la recherche de la definition de la complexite d'espace pour le calcul des polynomes a la maniere de Valiant
inferred← citeshttps://doi.org/10.48550/arxiv.0912.5340openalex-snapshot
Why so? or Why no? Functional Causality for Explaining Query Answers
inferred← citeshttps://doi.org/10.48550/arxiv.1110.3030openalex-snapshot
Software Engineering and Complexity in Effective Algebraic Geometry
inferred← citeshttps://doi.org/10.48550/arxiv.1110.4201openalex-snapshot
The Complexity of Weighted Counting for Acyclic Conjunctive Queries
inferred← citeshttps://doi.org/10.48550/arxiv.1406.4106openalex-snapshot
Beautiful Structures: An Appreciation of the Contributions of Alan Selman
inferred← citeshttps://doi.org/10.48550/arxiv.math/0301111openalex-snapshot
Dedekind Zeta Functions and the Complexity of Hilbert's Nullstellensatz
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.