On the public citation graph

Raising expectations: automating expected cost analysis with types

https://doi.org/10.1145/3408992
0 signed · 122 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/978-3-030-17465-1_8openalex-snapshot
Tail Probabilities for Randomized Program Runtimes via Martingales for Higher Moments
inferredcites →https://doi.org/10.1007/978-3-319-08867-9_50openalex-snapshot
A Simple and Scalable Static Analysis for Bound Analysis and Amortized Complexity Analysis
inferredcites →https://doi.org/10.1007/978-3-319-12736-1_15openalex-snapshot
Resource Analysis of Complex Programs with Cost Equations
inferredcites →https://doi.org/10.1007/978-3-319-22102-1_21openalex-snapshot
Amortized Complexity Verified
inferredcites →https://doi.org/10.1007/978-3-319-22102-1_9openalex-snapshot
Machine-Checked Verification of the Correctness and Amortized Complexity of an Efficient Union-Find Implementation
inferredcites →https://doi.org/10.1007/978-3-319-40229-1_37openalex-snapshot
Lower Runtime Bounds for Integer Programs
inferredcites →https://doi.org/10.1007/978-3-319-41528-4_1openalex-snapshot
Termination Analysis of Probabilistic Programs Through Positivstellensatz’s
inferredcites →https://doi.org/10.1007/978-3-319-63390-9_4openalex-snapshot
Automated Resource Analysis with Coq Proof Objects
inferredcites →https://doi.org/10.1007/978-3-319-89884-1_7openalex-snapshot
How long, O Bayesian network, will I sample thee?
inferredcites →https://doi.org/10.1007/978-3-642-02658-4_7openalex-snapshot
SPEED: Symbolic Complexity Bound Analysis
inferredcites →https://doi.org/10.1007/978-3-642-05089-3_23openalex-snapshot
“Carbon Credits” for Resource-Bounded Computations Using Amortised Analysis
inferredcites →https://doi.org/10.1007/978-3-642-11957-6_6openalex-snapshot
Amortised Resource Analysis with Separation Logic
inferredcites →https://doi.org/10.1007/978-3-642-17511-4_7openalex-snapshot
ABC: Algebraic Bound Computation for Loops
inferredcites →https://doi.org/10.1007/978-3-642-36742-7_35openalex-snapshot
Deriving Probability Density Functions from Probabilistic Functional Programs
inferredcites →https://doi.org/10.1007/978-3-642-54862-8_10openalex-snapshot
Alternating Runtime and Size Complexity Analysis of Integer Programs
inferredcites →https://doi.org/10.1007/978-3-662-46681-0_6openalex-snapshot
Non-cumulative Resource Analysis
inferredcites →https://doi.org/10.1007/b138392openalex-snapshot
Abstraction, Refinement and Proof for Probabilistic Systems
inferredcites →https://doi.org/10.1007/s10817-013-9277-6openalex-snapshot
Analyzing Innermost Runtime Complexity of Term Rewriting by Dependency Pairs
inferredcites →https://doi.org/10.1016/0022-0000(81)90036-2openalex-snapshot
Semantics of probabilistic programs
inferredcites →https://doi.org/10.1016/0022-1996(83)90017-xopenalex-snapshot
Empirical exchange rate models of the seventies
inferredcites →https://doi.org/10.1016/0304-3975(77)90044-5openalex-snapshot
LCF considered as a programming language
inferredcites →https://doi.org/10.1016/j.entcs.2009.12.008openalex-snapshot
Termination and Cost Analysis with COSTA and its User Interfaces
inferredcites →https://doi.org/10.1017/cbo9780511813658openalex-snapshot
Probability with Martingales
inferredcites →https://doi.org/10.1017/cbo9781139342131openalex-snapshot
Practical Foundations for Programming Languages
inferredcites →https://doi.org/10.1017/cbo9781316576892openalex-snapshot
Practical Foundations for Programming Languages
inferredcites →https://doi.org/10.1023/a:1019916231463openalex-snapshot
Dependent Types for Program Termination Verification
inferredcites →https://doi.org/10.1088/0004-637x/721/2/1014openalex-snapshot
MODELING THE TIME VARIABILITY OF SDSS STRIPE 82 QUASARS AS A DAMPED RANDOM WALK
inferredcites →https://doi.org/10.1098/rsif.2008.0014openalex-snapshot
Random walk models in biology
inferredcites →https://doi.org/10.1109/icse.2009.5070545openalex-snapshot
WISE: Automated test generation for worst-case complexity
inferredcites →https://doi.org/10.1109/lics.2011.22openalex-snapshot
Linear Dependent Types and Relative Completeness
inferredcites →https://doi.org/10.1109/lics.2019.8785725openalex-snapshot
Type-Based Complexity Analysis of Probabilistic Functional Programs
inferredcites →https://doi.org/10.1109/sp.2017.53openalex-snapshot
Verifying and Synthesizing Constant-Resource Implementations with Types
inferredcites →https://doi.org/10.1137/0606031openalex-snapshot
Amortized Computational Complexity
inferredcites →https://doi.org/10.1145/1059816.1059824openalex-snapshot
Abstraction and refinement in probabilistic systems
inferredcites →https://doi.org/10.1145/1168857.1168908openalex-snapshot
A probabilistic pointer analysis for speculative optimizations
inferredcites →https://doi.org/10.1145/1328438.1328457openalex-snapshot
Lightweight semiformal time complexity analysis for purely functional data structures
inferredcites →https://doi.org/10.1145/1411509.1411514openalex-snapshot
Random sampling from a search engine's index
inferredcites →https://doi.org/10.1145/1480881.1480894openalex-snapshot
Formal certification of code-based cryptographic proofs
inferredcites →https://doi.org/10.1145/1706299.1706327openalex-snapshot
Static determination of quantitative resource usage for higher-order programs
inferredcites →https://doi.org/10.1145/1863543.1863568openalex-snapshot
Distance makes the types grow stronger
inferredcites →https://doi.org/10.1145/1925844.1926427openalex-snapshot
Multivariate amortized resource analysis
inferredcites →https://doi.org/10.1145/1926385.1926427openalex-snapshot
Multivariate amortized resource analysis
inferredcites →https://doi.org/10.1145/2103621.2103670openalex-snapshot
Probabilistic relational reasoning for differential privacy
inferredcites →https://doi.org/10.1145/2103621.2103721openalex-snapshot
A type theory for probability density functions
inferredcites →https://doi.org/10.1145/2103656.2103670openalex-snapshot
Probabilistic relational reasoning for differential privacy
inferredcites →https://doi.org/10.1145/2103656.2103721openalex-snapshot
A type theory for probability density functions
inferredcites →https://doi.org/10.1145/231379.231433openalex-snapshot
Data flow frequency analysis
inferredcites →https://doi.org/10.1145/2429069.2429090openalex-snapshot
The geometry of types
inferredcites →https://doi.org/10.1145/2429069.2429113openalex-snapshot
Linear dependent types for differential privacy
inferredcites →https://doi.org/10.1145/2593882.2593900openalex-snapshot
Probabilistic programming
inferredcites →https://doi.org/10.1145/2635868.2635899openalex-snapshot
Statistical symbolic execution with informed sampling
inferredcites →https://doi.org/10.1145/2737924.2737955openalex-snapshot
Compositional certified resource bounds
inferredcites →https://doi.org/10.1145/2784731.2784753openalex-snapshot
Analysing the complexity of functional programs: higher-order meets first-order
inferredcites →https://doi.org/10.1145/2837614.2837639openalex-snapshot
Algorithmic analysis of qualitative and quantitative termination problems for affine probabilistic programs
inferredcites →https://doi.org/10.1145/2858949.2784749openalex-snapshot
Denotational cost semantics for functional languages with inductive types
inferredcites →https://doi.org/10.1145/2884781.2884794openalex-snapshot
Generating performance distributions via probabilistic symbolic execution
inferredcites →https://doi.org/10.1145/2933575.2935317openalex-snapshot
Reasoning about Recursive Probabilistic Programs
inferredcites →https://doi.org/10.1145/2951913.2951942openalex-snapshot
A lambda-calculus foundation for universal probabilistic programming
inferredcites →https://doi.org/10.1145/3009837.3009842openalex-snapshot
Towards automatic resource bound analysis for OCaml
inferredcites →https://doi.org/10.1145/3009837.3009858openalex-snapshot
Relational cost analysis
inferredcites →https://doi.org/10.1145/3062341.3062373openalex-snapshot
Compositional recurrence analysis revisited
inferredcites →https://doi.org/10.1145/3133903openalex-snapshot
TiML: a functional language for practical complexity analysis with invariants
inferredcites →https://doi.org/10.1145/3158124openalex-snapshot
Monadic refinements for relational cost analysis
inferredcites →https://doi.org/10.1145/3192366.3192394openalex-snapshot
Bounded expectations: resource analysis for probabilistic programs
inferredcites →https://doi.org/10.1145/3192366.3192409openalex-snapshot
Probabilistic programming with programmable inference
inferredcites →https://doi.org/10.1145/3213846.3213868openalex-snapshot
Badger: complexity analysis with fuzzing and symbolic execution
inferredcites →https://doi.org/10.1145/325694.325716openalex-snapshot
Resource bound certification
inferredcites →https://doi.org/10.1145/3290326openalex-snapshot
Type-guided worst-case input generation
inferredcites →https://doi.org/10.1145/3290377openalex-snapshot
A separation logic for concurrent randomized programs
inferredcites →https://doi.org/10.1145/3293605openalex-snapshot
Probabilistic Termination by Monadic Affine Sized Typing
inferredcites →https://doi.org/10.1145/3314221.3314581openalex-snapshot
Cost analysis of nondeterministic probabilistic programs
inferredcites →https://doi.org/10.1145/3314221.3314602openalex-snapshot
Resource-guided program synthesis
inferredcites →https://doi.org/10.1145/3371083openalex-snapshot
Recurrence extraction for functional programs through call-by-push-value
inferredcites →https://doi.org/10.1145/3371087openalex-snapshot
Trace types and denotational semantics for sound programmable inference in probabilistic languages
inferredcites →https://doi.org/10.1145/3371104openalex-snapshot
Optimal approximate sampling from discrete probability distributions
inferredcites →https://doi.org/10.1145/3371105openalex-snapshot
Aiming low is harder: induction for lower bounds in probabilistic program verification
inferredcites →https://doi.org/10.1145/604131.604148openalex-snapshot
Static prediction of heap space usage for first-order functional programs
inferredcites →https://doi.org/10.2307/2291440openalex-snapshot
Probability and Measure.
inferredcites →https://doi.org/10.2307/2982048openalex-snapshot
Probability and Measure.
inferredcites →https://doi.org/10.26226/morressier.604907f51a80aac83ca25d6copenalex-snapshot
Exponential Automatic Amortized Resource Analysis
inferredcites →https://doi.org/10.3354/meps158275openalex-snapshot
Using random walk models to simulate the vertical distribution of particles in a turbulent water column
inferredcites →https://doi.org/10.4230/lipics.tlca.2015.241openalex-snapshot
Multivariate Amortised Resource Analysis for Term Rewrite Systems
inferredcites →https://doi.org/10.48550/arxiv.1104.0193openalex-snapshot
Linear Dependent Types and Relative Completeness
inferredcites →https://doi.org/10.48550/arxiv.1301.1299openalex-snapshot
Automated Variational Inference in Probabilistic Programming
inferredcites →https://doi.org/10.48550/arxiv.1302.0973openalex-snapshot
A Combination Framework for Complexity
inferredcites →https://doi.org/10.5860/choice.30-1565openalex-snapshot
Probability with martingales
inferredcites →https://doi.org/10.7551/mitpress/1104.001.0001openalex-snapshot
Advanced Topics in Types and Programming Languages

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-72016-2_14openalex-snapshot
Inferring Expected Runtimes of Probabilistic Integer Programs Using Expected Sizes
inferred← citeshttps://doi.org/10.1007/978-3-031-13188-2_4openalex-snapshot
Automated Expected Amortised Cost Analysis of Probabilistic Data Structures
inferred← citeshttps://doi.org/10.1007/978-3-031-38499-8_20openalex-snapshot
Proving Almost-Sure Innermost Termination of Probabilistic Term Rewriting Using Dependency Pairs
inferred← citeshttps://doi.org/10.1007/978-3-031-57231-9openalex-snapshot
Foundations of Software Science and Computation Structures
inferred← citeshttps://doi.org/10.1007/978-3-031-57231-9_10openalex-snapshot
From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting
inferred← citeshttps://doi.org/10.1007/978-3-031-63498-7_14openalex-snapshot
Control-Flow Refinement for Complexity Analysis of Probabilistic Programs in KoAT (Short Paper)
inferred← citeshttps://doi.org/10.1007/978-3-031-75783-9_14openalex-snapshot
Annotated Dependency Pairs for Full Almost-Sure Termination of Probabilistic Term Rewriting
inferred← citeshttps://doi.org/10.1007/978-3-031-91121-7_1openalex-snapshot
Efficient Synthesis of Tight Polynomial Upper-Bounds for Systems of Conditional Polynomial Recurrences
inferred← citeshttps://doi.org/10.1007/978-3-032-32537-2_5openalex-snapshot
Automated Amortised Analysis of Skew Heaps and Leftist Heaps
inferred← citeshttps://doi.org/10.1007/978-981-97-2300-3_4openalex-snapshot
A Complete Dependency Pair Framework for Almost-Sure Innermost Termination of Probabilistic Term Rewriting
inferred← citeshttps://doi.org/10.1016/j.apal.2023.103341openalex-snapshot
Towards logical foundations for probabilistic computation
inferred← citeshttps://doi.org/10.1016/j.scico.2025.103417openalex-snapshot
The annotated dependency pair framework for almost-sure termination of probabilistic term rewriting
inferred← citeshttps://doi.org/10.1017/s0960129521000487openalex-snapshot
Two decades of automatic amortized resource analysis
inferred← citeshttps://doi.org/10.1109/lics56636.2023.10175720openalex-snapshot
Automatic Amortized Resource Analysis with Regular Recursive Types
inferred← citeshttps://doi.org/10.1145/3453483.3454062openalex-snapshot
Central moment analysis for cost accumulators in probabilistic programs
inferred← citeshttps://doi.org/10.1145/3473581openalex-snapshot
Automatic amortized resource analysis with the Quantum physicist’s method
inferred← citeshttps://doi.org/10.1145/3473592openalex-snapshot
On continuation-passing transformations and expected cost analysis
inferred← citeshttps://doi.org/10.1145/3571259openalex-snapshot
Probabilistic Resource-Aware Session Types
inferred← citeshttps://doi.org/10.1145/3591263openalex-snapshot
Automated Expected Value Analysis of Recursive Programs
inferred← citeshttps://doi.org/10.1145/3649824openalex-snapshot
Quantitative Bounds on Resource Usage of Probabilistic Programs
inferred← citeshttps://doi.org/10.1145/3649839openalex-snapshot
Hopping Proofs of Expectation-Based Properties: Applications to Skiplists and Security Proofs
inferred← citeshttps://doi.org/10.1145/3656380openalex-snapshot
Robust Resource Bounds with Static Analysis and Bayesian Inference
inferred← citeshttps://doi.org/10.1145/3674632openalex-snapshot
Almost-Sure Termination by Guarded Refinement
inferred← citeshttps://doi.org/10.1145/3674635openalex-snapshot
Error Credits: Resourceful Reasoning about Error Bounds for Higher-Order Probabilistic Programs
inferred← citeshttps://doi.org/10.1145/3674662openalex-snapshot
Automated Verification of Higher-Order Probabilistic Programs via a Dependent Refinement Type System
inferred← citeshttps://doi.org/10.1145/3689725openalex-snapshot
A Modal Type Theory of Expected Cost in Higher-Order Probabilistic Programs
inferred← citeshttps://doi.org/10.1145/3689753openalex-snapshot
Tachis: Higher-Order Separation Logic with Credits for Expected Costs
inferred← citeshttps://doi.org/10.1145/3704877openalex-snapshot
Approximate Relational Reasoning for Higher-Order Probabilistic Programs
inferred← citeshttps://doi.org/10.1145/3720424openalex-snapshot
Denotational Foundations for Expected Cost Analysis
inferred← citeshttps://doi.org/10.1145/3729317openalex-snapshot
Probabilistic Refinement Session Types
inferred← citeshttps://doi.org/10.1145/3756907.3756917openalex-snapshot
Dependency Pairs for Expected Innermost Runtime Complexity and Strong Almost-Sure Termination of Probabilistic Term Rewriting
inferred← citeshttps://doi.org/10.1145/3828674openalex-snapshot
Adequacy for Predicate Transformer Semantics
inferred← citeshttps://doi.org/10.1145/3830439.3831276openalex-snapshot
A Cost-Aware Probability Monad for Liquid Haskell
inferred← citeshttps://doi.org/10.26226/morressier.604907f41a80aac83ca25cf4openalex-snapshot
Inferring Expected Runtimes of Probabilistic Integer Programs Using Expected Sizes
inferred← citeshttps://doi.org/10.46298/lmcs-20(4:26)2024openalex-snapshot
Worst-Case Input Generation for Concurrent Programs under Non-Monotone Resource Metrics
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.