Catalytic space enables exact multi-pass algorithms for frequency moments F_k and induced subgraph counting using O(k log m) clean space, while single-pass catalytic algorithms add no power.
hub Canonical reference
Tight pair query lower bounds for matching and earth mover’s distance
Canonical reference. 100% of citing Pith papers cite this work as background.
23
Pith papers citing it
Background
100% of classified citations
hub tools
citation-role summary
background 6
citation-polarity summary
years
2026 23roles
background 5polarities
background 5representative citing papers
Protocol learns k-local Lindbladians to ε accuracy with Õ(n^{2k}/ε²) samples and projects to valid generators; improves to log n under sparsity assumptions.
First deterministic sublogarithmic-round spanner and APSP algorithms in linear, sublinear, and near-linear MPC plus Congested Clique via derandomized hitting sets.
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
Every proper minor-closed graph class admits an optimal (1+o(1)) log n bit adjacency labeling scheme.
The one-way communication complexity of reporting k-edit occurrences (including the edit sequences) is Θ(n/m · k log(m|Σ|/k)) bits for 0 < k < m < n/2.
Polynomial-time algorithms for the Polynomial Freiman-Ruzsa theorem and equivalent formulations over F_2^n, based on an optimized quadratic Goldreich-Levin procedure.
Randomized communication complexity of Point-Line Incidence is Theta(log n), the first constant support-rank example with super-constant complexity.
New deterministic and randomized algorithms achieve near-linear-time constant-factor approximations for k-center and (k,z)-clustering on graphs, resolving an open problem of Abboud et al.
Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.
Approximating the quantum value of tilted XOR games to constant precision is RE-complete, implying binary nonlocal games are RE-hard to approximate.
First O(n^{2-1/(2h-2)} polylog n) algorithm for diameter and eccentricity in real-weighted K_h-minor-free digraphs via randomized search-to-decision reduction on VC-dimension.
Separating modules of support-degree k equate to O(k)-subgraph counts, those of symmetric circuit size n^Θ(k) equate to Θ(k)-WL, and their multiplicities equate to differing automorphism cycle indices.
Any n-qubit QC Hamiltonian sparsifies to Õ(n/ε²) terms preserving all state energies within 1±ε using invariant subspace decomposition and the Alon-Kozma operator inequality.
Chain of Thought risk decomposes into oracle-trajectory benefit and trajectory-mismatch cost, with stability determining bounded, linear, or exponential error growth.
Introduces SCDL as a calibration measure that is fully actionable for full swap regret and testable with nearly optimal sample error while satisfying continuity and consistency.
An adaptive algorithm for bilateral trade achieves Õ(T^{3/4} + C log T) regret against the best budget-balanced price distribution in perturbed markets while retaining Õ(T^{3/4}) worst-case regret.
Planarizing gadgets do not exist for the recognition problem of (k, l)-tight graphs.
A router that decomposes uncertainty to flexibly route queries between cheap models and oracles while providing regret bounds and supporting abstention in classification tasks with multiple annotations.
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
A local selection rule based on a fractional solution of the expected instance preserves the expected maximum matching size under sufficient spread and yields near-optimal global matchings with small local budgets on ride-hailing data.
Finding a matrix of rank n to the o(1/log log n) in a subspace of n by n matrices over F_{2^r} promised to contain a rank-1 matrix is hard, assuming NP has no subexponential algorithms.
Generative models learn rules before memorizing data, creating an innovation window whose width depends on dataset size and rule complexity, observed in both diffusion and autoregressive architectures.
citing papers explorer
-
Computing over Data Streams using Catalytic Space
Catalytic space enables exact multi-pass algorithms for frequency moments F_k and induced subgraph counting using O(k log m) clean space, while single-pass catalytic algorithms add no power.
-
Robust Structure Learning of $k$-local Lindbladians
Protocol learns k-local Lindbladians to ε accuracy with Õ(n^{2k}/ε²) samples and projects to valid generators; improves to log n under sparsity assumptions.
-
Deterministic Distance Approximation in MPC via Improved Hitting Sets
First deterministic sublogarithmic-round spanner and APSP algorithms in linear, sublinear, and near-linear MPC plus Congested Clique via derandomized hitting sets.
-
Online Steiner Forest with Recourse
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
-
Adjacency labelling for proper minor-closed graph classes
Every proper minor-closed graph class admits an optimal (1+o(1)) log n bit adjacency labeling scheme.
-
The Communication Complexity of Pattern Matching with Edits Revisited
The one-way communication complexity of reporting k-edit occurrences (including the edit sequences) is Θ(n/m · k log(m|Σ|/k)) bits for 0 < k < m < n/2.
-
An algorithmic Polynomial Freiman-Ruzsa theorem
Polynomial-time algorithms for the Polynomial Freiman-Ruzsa theorem and equivalent formulations over F_2^n, based on an optimized quadratic Goldreich-Levin procedure.
-
No Constant-Cost Protocol for Point--Line Incidence
Randomized communication complexity of Point-Line Incidence is Theta(log n), the first constant support-rank example with super-constant complexity.
-
Faster Randomized and Deterministic k-Clustering on Graphs
New deterministic and randomized algorithms achieve near-linear-time constant-factor approximations for k-center and (k,z)-clustering on graphs, resolving an open problem of Abboud et al.
-
Gap-Majority Lemmas in Communication Complexity
Computing GapMAJ∘fⁿ requires n·(I−O(1)) bits of information, making GapMAJ the third outer gadget with a strong composition theorem in two-player communication.
-
XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games
Approximating the quantum value of tilted XOR games to constant precision is RE-complete, implying binary nonlocal games are RE-hard to approximate.
-
Real-weighted Diameter and Eccentricity of Minor-free and Bounded VC-dimension Graphs in Truly Subquadratic Time
First O(n^{2-1/(2h-2)} polylog n) algorithm for diameter and eccentricity in real-weighted K_h-minor-free digraphs via randomized search-to-decision reduction on VC-dimension.
-
Graph Isomorphism and Representation Theory
Separating modules of support-degree k equate to O(k)-subgraph counts, those of symmetric circuit size n^Θ(k) equate to Θ(k)-WL, and their multiplicities equate to differing automorphism cycle indices.
-
Quantum Cut Sparsifiers
Any n-qubit QC Hamiltonian sparsifies to Õ(n/ε²) terms preserving all state energies within 1±ε using invariant subspace decomposition and the Alon-Kozma operator inequality.
-
On the Cost and Benefit of Chain of Thought: A Learning-Theoretic Perspective
Chain of Thought risk decomposes into oracle-trajectory benefit and trajectory-mismatch cost, with stability determining bounded, linear, or exponential error growth.
-
Testable and Actionable Calibration for Full Swap Regret
Introduces SCDL as a calibration measure that is fully actionable for full swap regret and testable with nearly optimal sample error while satisfying continuity and consistency.
-
Regret Minimization in Bilateral Trade With Perturbed Markets
An adaptive algorithm for bilateral trade achieves Õ(T^{3/4} + C log T) regret against the best budget-balanced price distribution in perturbed markets while retaining Õ(T^{3/4}) worst-case regret.
-
Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
Planarizing gadgets do not exist for the recognition problem of (k, l)-tight graphs.
-
Flexible Routing via Uncertainty Decomposition
A router that decomposes uncertainty to flexibly route queries between cheap models and oracles while providing regret bounds and supporting abstention in classification tasks with multiple annotations.
-
Robust Graph Isomorphism, Quadratic Assignment and VC Dimension
Additive εn²-approximation for graph edit distance on VC-dimension-d graphs in n^{O(d/ε²)} time, with extensions to quadratic assignment problems and a Weisfeiler-Leman dimension bound for robust graph isomorphism.
-
Stochastic Matching via Local Sparsification
A local selection rule based on a fractional solution of the expected instance preserves the expected maximum matching size under sufficient spread and yields near-optimal global matchings with small local budgets on ride-hailing data.
-
Strong Inapproximability for a Promise Rank Problem
Finding a matrix of rank n to the o(1/log log n) in a subspace of n by n matrices over F_{2^r} promised to contain a rank-1 matrix is hard, assuming NP has no subexponential algorithms.
-
The two clocks and the innovation window: When and how generative models learn rules
Generative models learn rules before memorizing data, creating an innovation window whose width depends on dataset size and rule complexity, observed in both diffusion and autoregressive architectures.