On the public citation graph
Shuffles and Circuits (On Lower Bounds for Modern Parallel Computation)
0 signed · 73 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.1006/jcss.1997.1545openalex-snapshot
The Space Complexity of Approximating the Frequency Moments
inferredcites →https://doi.org/10.1007/978-3-642-24508-4_2openalex-snapshot
Analysis of Boolean Functions
inferredcites →https://doi.org/10.1007/978-3-642-25591-5_39openalex-snapshot
Sorting, Searching, and Simulation in the MapReduce Framework
inferredcites →https://doi.org/10.1007/978-3-642-32820-6_67openalex-snapshot
A Lower Bound Technique for Communication on BSP with Application to the FFT
inferredcites →https://doi.org/10.1007/978-3-642-41527-2_2openalex-snapshot
When Distributed Computation Is Communication Expensive
inferredcites →https://doi.org/10.1007/978-3-662-03927-4openalex-snapshot
Introduction to Circuit Complexity
inferredcites →https://doi.org/10.1007/978-3-662-48653-5_1openalex-snapshot
On the Computational Complexity of MapReduce
inferredcites →https://doi.org/10.1007/bf01137685openalex-snapshot
Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
inferredcites →https://doi.org/10.1007/bf01263419openalex-snapshot
On the degree of boolean functions as real polynomials
inferredcites →https://doi.org/10.1007/bf02579140openalex-snapshot
A topological approach to evasiveness
inferredcites →https://doi.org/10.1007/s00493-010-2485-3openalex-snapshot
An asymptotic bound for the complexity of monotone graph properties
inferredcites →https://doi.org/10.1016/0095-8956(80)90057-xopenalex-snapshot
Further results on the Aanderaa-Rosenberg conjecture
inferredcites →https://doi.org/10.1016/j.tcs.2015.09.029openalex-snapshot
Lessons from the Congested Clique applied to MapReduce
inferredcites →https://doi.org/10.1016/s0022-0000(05)80003-0openalex-snapshot
Exact lower time bounds for computing Boolean functions on CREW PRAMs
inferredcites →https://doi.org/10.1016/s0304-3975(01)00144-xopenalex-snapshot
Complexity measures and decision tree complexity: a survey
inferredcites →https://doi.org/10.1017/cbo9781139814782openalex-snapshot
Analysis of Boolean Functions
inferredcites →https://doi.org/10.1137/0215006openalex-snapshot
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
inferredcites →https://doi.org/10.1137/1.9780898716474openalex-snapshot
Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
inferredcites →https://doi.org/10.1137/120888703openalex-snapshot
A Lower Bound for the Complexity of Monotone Graph Properties
inferredcites →https://doi.org/10.1137/s0097539795294141openalex-snapshot
Communication-Efficient Parallel Sorting
inferredcites →https://doi.org/10.1145/1008299.1008302openalex-snapshot
On the time required to recognize properties of graphs
inferredcites →https://doi.org/10.1145/1824777.1824786openalex-snapshot
On distributing symmetric streaming computations
inferredcites →https://doi.org/10.1145/2020408.2020515openalex-snapshot
Fast clustering using MapReduce
inferredcites →https://doi.org/10.1145/2304576.2304607openalex-snapshot
Space-round tradeoffs for MapReduce computations
inferredcites →https://doi.org/10.1145/237814.237870openalex-snapshot
Communication-efficient parallel sorting (preliminary version)
inferredcites →https://doi.org/10.1145/2463664.2465224openalex-snapshot
Communication steps for parallel query processing
inferredcites →https://doi.org/10.1145/2486159.2486168openalex-snapshot
Fast greedy algorithms in mapreduce and streaming
inferredcites →https://doi.org/10.1145/2591796.2591805openalex-snapshot
Parallel algorithms for geometric graph problems
inferredcites →https://doi.org/10.1145/2611462.2611493openalex-snapshot
On the power of the congested clique model
inferredcites →https://doi.org/10.1145/2746539.2746624openalex-snapshot
Randomized Composable Core-sets for Distributed Submodular Maximization
inferredcites →https://doi.org/10.1145/277651.277681openalex-snapshot
Computational bounds for fundamental problems on general-purpose parallel models
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/3749740.3749753openalex-snapshot
A Bridging Model for Parallel Computation
inferredcites →https://doi.org/10.1145/502090.502097openalex-snapshot
Quantum lower bounds by polynomials
inferredcites →https://doi.org/10.1145/800116.803747openalex-snapshot
A generalization and proof of the Aanderaa-Rosenberg conjecture
inferredcites →https://doi.org/10.14778/2535570.2488334openalex-snapshot
Upper and lower bounds on the cost of a map-reduce computation
inferredcites →https://doi.org/10.21276/ijre.2018.5.5.4openalex-snapshot
MapReduce: Simplified Data Processing on Large Cluster
inferredcites →https://doi.org/10.48550/arxiv.1211.6526openalex-snapshot
Complexity Measures for Map-Reduce, and Comparison to Parallel Computing
inferredcites →https://doi.org/10.48550/arxiv.1304.4636openalex-snapshot
When Distributed Computation is Communication Expensive
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-39951-1_18openalex-snapshot
Strongly Minimal MapReduce Algorithms: A TeraSort Case Study
inferred← citeshttps://doi.org/10.1007/978-3-031-48615-9_4openalex-snapshot
Distributed-Prover Interactive Proofs
inferred← citeshttps://doi.org/10.1007/978-3-031-91736-3_20openalex-snapshot
Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity
inferred← citeshttps://doi.org/10.1007/s00446-021-00418-2openalex-snapshot
Equivalence classes and conditional hardness in massively parallel computations
inferred← citeshttps://doi.org/10.1007/s00446-024-00461-9openalex-snapshot
Component stability in low-space massively parallel computation
inferred← citeshttps://doi.org/10.1007/s00446-025-00477-9openalex-snapshot
Exponential speedup over locality in MPC with optimal memory
inferred← citeshttps://doi.org/10.1007/s00446-025-00479-7openalex-snapshot
Massively parallel computation in a heterogeneous regime
inferred← citeshttps://doi.org/10.1016/j.jpdc.2023.02.010openalex-snapshot
Efficient deterministic MapReduce algorithms for parallelizable problems
inferred← citeshttps://doi.org/10.1016/j.tcs.2026.115912openalex-snapshot
Parallel derandomization for coloring
inferred← citeshttps://doi.org/10.1109/ipdps57955.2024.00098openalex-snapshot
Parallel Derandomization for Coloring*
inferred← citeshttps://doi.org/10.1137/1.9781611975482.99openalex-snapshot
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
inferred← citeshttps://doi.org/10.1137/22m1520177openalex-snapshot
Deterministic Massively Parallel Connectivity
inferred← citeshttps://doi.org/10.1145/3350755.3400230openalex-snapshot
Unconditional Lower Bounds for Adaptive Massively Parallel Computation
inferred← citeshttps://doi.org/10.1145/3350755.3400249openalex-snapshot
Connected Components on a PRAM in Log Diameter Time
inferred← citeshttps://doi.org/10.1145/3350755.3400282openalex-snapshot
Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space
inferred← citeshttps://doi.org/10.1145/3357713.3384303openalex-snapshot
Walking randomly, massively, and efficiently
inferred← citeshttps://doi.org/10.1145/3465084.3467903openalex-snapshot
Component Stability in Low-Space Massively Parallel Computation
inferred← citeshttps://doi.org/10.1145/3519935.3520055openalex-snapshot
Deterministic massively parallel connectivity
inferred← citeshttps://doi.org/10.1145/3558481.3591098openalex-snapshot
Fast Dynamic Programming in Trees in the MPC Model
inferred← citeshttps://doi.org/10.1145/3558481.3591103openalex-snapshot
Adaptive Massively Parallel Connectivity in Optimal Space
inferred← citeshttps://doi.org/10.1145/3626183.3659963openalex-snapshot
Connected Components in Linear Work and Near-Optimal Time
inferred← citeshttps://doi.org/10.1145/3662158.3662770openalex-snapshot
Streaming Graph Algorithms in the Massively Parallel Computation Model
inferred← citeshttps://doi.org/10.1145/3717823.3718194openalex-snapshot
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
inferred← citeshttps://doi.org/10.31274/td-20240617-212openalex-snapshot
Relations between Space-Bounded and Adaptive Massively Parallel Computations
inferred← citeshttps://doi.org/10.4230/lipics.opodis.2019.35openalex-snapshot
Massively Parallel Approximate Distance Sketches
inferred← citeshttps://doi.org/10.48550/arxiv.1912.03042openalex-snapshot
Constructive derandomization of query algorithms
inferred← citeshttps://doi.org/10.48550/arxiv.2001.01146openalex-snapshot
New lower bounds for Massively Parallel Computation from query complexity
inferred← citeshttps://doi.org/10.48550/arxiv.2002.09610openalex-snapshot
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
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.