On the public citation graph

A Time-Space Tradeoff for Sorting on a General Sequential Model of Computation

0 signed · 129 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.1063/1.3034322openalex-snapshot

An Introduction to Probability Theory and Its Applications, Vol. 2

inferredcites →https://doi.org/10.1145/321958.321962openalex-snapshot

Shifting Graphs and Their Applications

What points at this work

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

inferred← citeshttps://doi.org/10.1006/jcom.1998.0498openalex-snapshot

Trade-offs between Communication Throughput and Parallel Time

inferred← citeshttps://doi.org/10.1006/jcom.1999.0526openalex-snapshot

Time-Space Tradeoffs in Algebraic Complexity Theory

inferred← citeshttps://doi.org/10.1006/jcss.2001.1778openalex-snapshot

Time–Space Tradeoffs for Branching Programs

inferred← citeshttps://doi.org/10.1006/jcss.2002.1821openalex-snapshot

Determinism versus Nondeterminism for Linear Time RAMs with Memory Restrictions

inferred← citeshttps://doi.org/10.1007/11535218_3openalex-snapshot

Pebbling and Proofs of Work

inferred← citeshttps://doi.org/10.1007/11753728_20openalex-snapshot

Incremental Branching Programs

inferred← citeshttps://doi.org/10.1007/3-540-16078-7_89openalex-snapshot

A time-space tradeoff for element distinctness

inferred← citeshttps://doi.org/10.1007/3-540-44985-x_38openalex-snapshot

I/O-Space Trade-Offs

inferred← citeshttps://doi.org/10.1007/3-540-48686-0_32openalex-snapshot

Multi-party Finite Computations

inferred← citeshttps://doi.org/10.1007/3-540-54458-5_49openalex-snapshot

Lower bounds for deterministic and nondeterministic branching programs

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-1-4612-4478-3_8openalex-snapshot

Applications of Kolmogorov Complexity in the Theory of Computation

inferred← citeshttps://doi.org/10.1007/978-1-4939-2864-4_586openalex-snapshot

Memory-Constrained Algorithms

inferred← citeshttps://doi.org/10.1007/978-3-030-45721-1_15openalex-snapshot

Tight Time-Space Lower Bounds for Finding Multiple Collision Pairs and Their Applications

inferred← citeshttps://doi.org/10.1007/978-3-030-83508-8_24openalex-snapshot

Strictly In-Place Algorithms for Permuting and Inverting Permutations

inferred← citeshttps://doi.org/10.1007/978-3-031-34347-6_30openalex-snapshot

Sorting and Ranking of Self-Delimiting Numbers with Applications to Tree Isomorphism

inferred← citeshttps://doi.org/10.1007/978-3-319-21840-3_40openalex-snapshot

Time-Space Trade-offs for Triangulations and Voronoi Diagrams

inferred← citeshttps://doi.org/10.1007/978-3-319-40509-4_1openalex-snapshot

Distributed Scheduling of Enhanced Beacons for IEEE802.15.4-TSCH Body Area Networks

inferred← citeshttps://doi.org/10.1007/978-3-319-62389-4_1openalex-snapshot

A Time-Space Trade-Off for Triangulations of Points in the Plane

inferred← citeshttps://doi.org/10.1007/978-3-319-71069-3_24openalex-snapshot

Time-Space Complexity Advantages for Quantum Computing

inferred← citeshttps://doi.org/10.1007/978-3-322-80139-5_2openalex-snapshot

Weitere Maschinenmodelle

inferred← citeshttps://doi.org/10.1007/978-3-322-80139-5_5openalex-snapshot

Zeit- versus Platzkomplexität

inferred← citeshttps://doi.org/10.1007/978-3-540-30577-4_33openalex-snapshot

Lower Bounds on the OBDD Size of Graphs of Some Popular Functions

inferred← citeshttps://doi.org/10.1007/978-3-540-72504-6_11openalex-snapshot

Finding a Duplicate and a Missing Item in a Stream

inferred← citeshttps://doi.org/10.1007/978-3-642-03816-7_16openalex-snapshot

Branching Programs for Tree Evaluation

inferred← citeshttps://doi.org/10.1007/978-3-642-27848-8_586-1openalex-snapshot

Memory-Constrained Algorithms

inferred← citeshttps://doi.org/10.1007/978-3-642-40273-9_9openalex-snapshot

Computing (and Life) Is All about Tradeoffs

inferred← citeshttps://doi.org/10.1007/978-3-642-45030-3_38openalex-snapshot

Faster, Space-Efficient Selection Algorithms in Read-Only Memory for Integers

inferred← citeshttps://doi.org/10.1007/978-3-662-44777-2_50openalex-snapshot

Sublinear Space Algorithms for the Longest Common Substring Problem

inferred← citeshttps://doi.org/10.1007/978-3-662-47672-7_9openalex-snapshot

Finding the Median (Obliviously) with Bounded Space

inferred← citeshttps://doi.org/10.1007/bf01200404openalex-snapshot

On lower bounds for read-k-times branching programs

inferred← citeshttps://doi.org/10.1007/bf01704903openalex-snapshot

On time versus space III

inferred← citeshttps://doi.org/10.1007/bf02835833openalex-snapshot

On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?

inferred← citeshttps://doi.org/10.1007/s00224-007-9049-yopenalex-snapshot

Incremental Branching Programs

inferred← citeshttps://doi.org/10.1007/s00224-018-09908-6openalex-snapshot

Space-Efficient Algorithms for Longest Increasing Subsequence

inferred← citeshttps://doi.org/10.1007/s00453-021-00826-7openalex-snapshot

Approximation in (Poly-) Logarithmic Space

inferred← citeshttps://doi.org/10.1007/s00454-006-1275-6openalex-snapshot

Multi-Pass Geometric Algorithms

inferred← citeshttps://doi.org/10.1016/0020-0190(94)00094-8openalex-snapshot

Time–space tradeoffs for integer multiplication on various types of input oblivious sequential machines

inferred← citeshttps://doi.org/10.1016/0022-0000(84)90029-1openalex-snapshot

Time-space tradeoffs for matrix multiplication and the discrete fourier transform on any general sequential random-access computer

inferred← citeshttps://doi.org/10.1016/0022-0000(87)90002-xopenalex-snapshot

Upper bounds for time-space trade-offs in sorting and selection

inferred← citeshttps://doi.org/10.1016/0022-0000(88)90002-5openalex-snapshot

Meanders and their applications in lower bounds arguments

inferred← citeshttps://doi.org/10.1016/0022-0000(91)90014-vopenalex-snapshot

Time-space tradeoffs for algebraic problems on general sequential machines

inferred← citeshttps://doi.org/10.1016/0022-0000(92)90028-hopenalex-snapshot

Trade-offs between communication and space

inferred← citeshttps://doi.org/10.1016/0022-0000(92)90046-lopenalex-snapshot

Lower bounds on the length of universal traversal sequences

inferred← citeshttps://doi.org/10.1016/0304-3975(86)90150-7openalex-snapshot

Two time-space tradeoffs for element distinctness

inferred← citeshttps://doi.org/10.1016/0304-3975(93)90257-topenalex-snapshot

The computational complexity of universal hashing

inferred← citeshttps://doi.org/10.1016/0304-3975(93)90352-topenalex-snapshot

Time-space tradeoffs for set operations

inferred← citeshttps://doi.org/10.1016/0890-5401(91)90017-vopenalex-snapshot

Oracle branching programs and Logspace versus P

inferred← citeshttps://doi.org/10.1016/0890-5401(91)90039-5openalex-snapshot

On oblivious branching programs of linear length

inferred← citeshttps://doi.org/10.1016/j.comgeo.2017.01.001openalex-snapshot

Time–space trade-offs for triangulations and Voronoi diagrams

inferred← citeshttps://doi.org/10.1016/j.ejor.2017.10.021openalex-snapshot

Bi-criteria optimization of decision trees with applications to data analysis

inferred← citeshttps://doi.org/10.1016/j.jcss.2003.09.002openalex-snapshot

Graph properties checkable in linear time in the number of vertices

inferred← citeshttps://doi.org/10.1016/j.jcss.2021.07.004openalex-snapshot

Frameworks for designing in-place graph algorithms

inferred← citeshttps://doi.org/10.1016/j.tcs.2015.03.042openalex-snapshot

Finding median in read-only memory on integer input

inferred← citeshttps://doi.org/10.1016/j.tcs.2025.115358openalex-snapshot

Sorting and ranking of self-delimiting numbers with applications to outerplanar graph isomorphism

inferred← citeshttps://doi.org/10.1051/ita:2005025openalex-snapshot

Efficient simulation of synchronous systems by multi-speed systems

inferred← citeshttps://doi.org/10.1109/focs.2009.49openalex-snapshot

Choice-Memory Tradeoff in Allocations

inferred← citeshttps://doi.org/10.1109/focs.2013.39openalex-snapshot

Element Distinctness, Frequency Moments, and Sliding Windows

inferred← citeshttps://doi.org/10.1109/fscs.1990.89561openalex-snapshot

A time-space tradeoff for Boolean matrix multiplication

inferred← citeshttps://doi.org/10.1109/fscs.1990.89562openalex-snapshot

Communication-space tradeoffs for unrestricted protocols

inferred← citeshttps://doi.org/10.1109/infcom.2002.1019325openalex-snapshot

Efficient periodic scheduling by trees

inferred← citeshttps://doi.org/10.1109/ipdps.2001.925122openalex-snapshot

Communication complexity for asynchronous systems of finite devices

inferred← citeshttps://doi.org/10.1109/isit.2006.262116openalex-snapshot

Minimum Distance of Codes and Their Branching Program Complexity

inferred← citeshttps://doi.org/10.1109/sct.1988.5265openalex-snapshot

Two decades of applied Kolmogorov complexity: in memoriam Andrei Nikolaevich Kolmogorov 1903-87

inferred← citeshttps://doi.org/10.1109/sct.1995.514727openalex-snapshot

On superlinear lower bounds in complexity theory

inferred← citeshttps://doi.org/10.1109/sfcs.1986.31openalex-snapshot

Meanders, Ramsey theory and lower bounds for branching programs

inferred← citeshttps://doi.org/10.1109/sfcs.1986.58openalex-snapshot

Time-space tradeoffs for branching programs contrasted with those for straight-line programs

inferred← citeshttps://doi.org/10.1109/sfcs.1988.21925openalex-snapshot

Near-optimal time-space tradeoff for element distinctness

inferred← citeshttps://doi.org/10.1109/sfcs.1993.366864openalex-snapshot

Time-space lower bounds for directed s-t connectivity on JAG models

inferred← citeshttps://doi.org/10.1109/sfcs.1996.548476openalex-snapshot

New coding techniques for improved bandwidth utilization

inferred← citeshttps://doi.org/10.1109/sfcs.1998.743453openalex-snapshot

Time-space tradeoffs for branching programs

inferred← citeshttps://doi.org/10.1109/sfcs.1998.743455openalex-snapshot

Optimal time-space trade-offs for sorting

inferred← citeshttps://doi.org/10.1109/sfcs.2000.892078openalex-snapshot

Super-linear time-space tradeoff lower bounds for randomized computation

inferred← citeshttps://doi.org/10.1109/sffcs.1999.814578openalex-snapshot

A non-linear time lower bound for Boolean branching programs

inferred← citeshttps://doi.org/10.1109/tit.2005.847727openalex-snapshot

Endcoding Complexity Versus Minimum Distance

inferred← citeshttps://doi.org/10.1137/0216007openalex-snapshot

A Time-Space Tradeoff for Element Distinctness

inferred← citeshttps://doi.org/10.1137/0220017openalex-snapshot

A general Sequential Time-Space Tradeoff for Finding Unique Elements

inferred← citeshttps://doi.org/10.1137/1.9781611974782.77openalex-snapshot

Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma

inferred← citeshttps://doi.org/10.1137/1.9781611977073.67openalex-snapshot

Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions

inferred← citeshttps://doi.org/10.1137/s0097539788148959openalex-snapshot

Near-Optimal Time-Space Tradeoff for Element Distinctness

inferred← citeshttps://doi.org/10.1137/s0097539791196883openalex-snapshot

Communication-Space Tradeoffs for Unrestricted Protocols

inferred← citeshttps://doi.org/10.1137/s0097539795295948openalex-snapshot

Tight Lower Bounds for st -Connectivity on the NNJAG Model

inferred← citeshttps://doi.org/10.1137/s0097539797315884openalex-snapshot

Parallel Sorting with Limited Bandwidth

inferred← citeshttps://doi.org/10.1145/100216.100246openalex-snapshot

The computational complexity of universal hashing

inferred← citeshttps://doi.org/10.1145/1064092.1064121openalex-snapshot

Multi-pass geometric algorithms

inferred← citeshttps://doi.org/10.1145/1283920.1283938openalex-snapshot

An overview of computational complexity

inferred← citeshttps://doi.org/10.1145/1721837.1721842openalex-snapshot

Comparison-based time-space lower bounds for selection

inferred← citeshttps://doi.org/10.1145/195058.195199openalex-snapshot

Trade-offs between communication throughput and parallel time

inferred← citeshttps://doi.org/10.1145/2077336.2077337openalex-snapshot

Pebbles and Branching Programs for Tree Evaluation

inferred← citeshttps://doi.org/10.1145/215399.215431openalex-snapshot

Parallel sorting with limited bandwidth

inferred← citeshttps://doi.org/10.1145/225058.225103openalex-snapshot

A nearly optimal time-space lower bound for directed st -connectivity on the NNJAG model

inferred← citeshttps://doi.org/10.1145/242223.242240openalex-snapshot

Strategic directions in research in theory of computing

inferred← citeshttps://doi.org/10.1145/2422436.2422456openalex-snapshot

Space-bounded communication complexity

inferred← citeshttps://doi.org/10.1145/258533.258673openalex-snapshot

Read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus

inferred← citeshttps://doi.org/10.1145/262301.262310openalex-snapshot

Strategic directions in research in theory of computing

inferred← citeshttps://doi.org/10.1145/301250.301424openalex-snapshot

Determinism versus non-determinism for linear time RAMs (extended abstract)

inferred← citeshttps://doi.org/10.1145/301308.301316openalex-snapshot

Optimal and efficient clock synchronization under drifting clocks

inferred← citeshttps://doi.org/10.1145/3168005openalex-snapshot

Selection and Sorting in the “Restore” Model

inferred← citeshttps://doi.org/10.1145/3230651openalex-snapshot

Deterministic Parallel Algorithms for Fooling Polylogarithmic Juntas and the Lovász Local Lemma

inferred← citeshttps://doi.org/10.1145/358141.358144openalex-snapshot

An overview of computational complexity

inferred← citeshttps://doi.org/10.1145/3618260.3649700openalex-snapshot

Quantum Time-Space Tradeoffs for Matrix Problems

inferred← citeshttps://doi.org/10.1145/3728715openalex-snapshot

Cumulative Memory Lower Bounds for Randomized and Quantum Computation

inferred← citeshttps://doi.org/10.1145/636865.636867openalex-snapshot

Time-space trade-off lower bounds for randomized computation of decision problems

inferred← citeshttps://doi.org/10.1145/65780.65782openalex-snapshot

Figures of merit

inferred← citeshttps://doi.org/10.1145/73007.73026openalex-snapshot

A general sequential time-space tradeoff for finding unique elements

inferred← citeshttps://doi.org/10.1145/73007.73028openalex-snapshot

Tradeoffs between communication and space

inferred← citeshttps://doi.org/10.1145/73007.73061openalex-snapshot

Lower bounds on the length of universal traversal sequences

inferred← citeshttps://doi.org/10.1145/780542.780553openalex-snapshot

Quantum time-space tradeoffs for sorting

inferred← citeshttps://doi.org/10.1145/780542.780571openalex-snapshot

Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions

inferred← citeshttps://doi.org/10.1145/780551.780553openalex-snapshot

Quantum time-space tradeoffs for sorting

inferred← citeshttps://doi.org/10.1214/09-aap656openalex-snapshot

Choice-memory tradeoff in allocations

inferred← citeshttps://doi.org/10.17169/refubium-361openalex-snapshot

Improved Time-Space Trade-Offs for Computing Voronoi Diagrams

inferred← citeshttps://doi.org/10.22215/etd/2008-06498openalex-snapshot

Data stream algorithms

inferred← citeshttps://doi.org/10.4230/lipics.fsttcs.2009.2311openalex-snapshot

Fractional Pebbling and Thrifty Branching Programs

inferred← citeshttps://doi.org/10.4230/lipics.isaac.2023.12openalex-snapshot

Substring Complexity in Sublinear Space

inferred← citeshttps://doi.org/10.4230/lipics.itcs.2022.40openalex-snapshot

The Space Complexity of Sampling

inferred← citeshttps://doi.org/10.4230/lipics.itcs.2024.99openalex-snapshot

Randomized vs. Deterministic Separation in Time-Space Tradeoffs of Multi-Output Functions

inferred← citeshttps://doi.org/10.48550/arxiv.1005.2642openalex-snapshot

Pebbles and Branching Programs for Tree Evaluation

inferred← citeshttps://doi.org/10.48550/arxiv.1212.4372openalex-snapshot

Sliding Windows with Limited Storage

inferred← citeshttps://doi.org/10.48550/arxiv.1505.00090openalex-snapshot

Finding the Median (Obliviously) with Bounded Space

inferred← citeshttps://doi.org/10.48550/arxiv.1507.01346openalex-snapshot

Time-space tradeoffs for two-way finite automata

inferred← citeshttps://doi.org/10.48550/arxiv.cs/0608085openalex-snapshot

A Quadratic Time-Space Tradeoff for Unrestricted Deterministic Decision Branching Programs

inferred← citeshttps://doi.org/10.5555/1496770.1496787openalex-snapshot

Comparison-based time-space lower bounds for selection

inferred← citeshttps://doi.org/10.5555/545381.545383openalex-snapshot

Optimal time-space trade-offs for non-comparison-based sorting

inferred← citeshttps://doi.org/10.7146/brics.v5i10.19282openalex-snapshot

Optimal Time-Space Trade-Offs for Sorting

inferred← citeshttps://doi.org/10.7146/brics.v7i11.20138openalex-snapshot

On Ajtai’s Lower Bound Technique for R-way Branching Programs and the Hamming Distance Problem

inferred← citeshttps://doi.org/10.7146/brics.v8i2.20456openalex-snapshot

Optimal Time-Space Trade-Offs for Non-Comparison-Based Sorting

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.