Establishes Ω(n/ε²) query lower bounds for approximating correlation clustering cost and partitions under memory constraints in adjacency-matrix and general graph models.
hub Canonical reference
Induced Cycles and Paths Are Harder Than You Think , booktitle =
Canonical reference. 80% of citing Pith papers cite this work as background.
19
Pith papers citing it
Background
80% of classified citations
hub tools
citation-role summary
background 4
method 1
citation-polarity summary
representative citing papers
The first dynamic algorithms for matrix rank and related objects achieve update times scaling with rank r, specifically Õ(r^1.405) per entry update and Õ(r^1.528 + z) per column update, extending to dynamic maximum matching.
Streaming max-cut requires Ω(n) space for dense graphs but Ω(n log(ε² n)/ε²) space for graphs with Θ(n/ε²) edges when outputting the cut, with matching upper bounds for dense case and similar separations for densest subgraph.
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.
A cut-preserving sparsifier constructed from approximate max-flow enables faster all-pairs minimum-cut algorithms in unweighted graphs across cut-query, dynamic, and streaming models.
Regularity in hypergraphs is fine-grained equivalent to the general case for clique detection, enabling a complete classification of k-sparse Boolean CSP optimization complexity by constraint degree: linear for d≤1, clique-equivalent for d=2, and exhaustive-search for d≥3 under 3-uniform hyperclique
Backdoors can be realized as statistically natural latent directions in modern neural networks, achieving high attack success with negligible clean accuracy loss and resisting existing defenses.
Sparsity helps for k-independent set only below certain density thresholds, with new algorithms achieving O(min(n^{ωk/3} + m^{k/3}, n^k)) time and conditional lower bounds showing brute-force necessity above thresholds for many binary constraint families.
GenusSink delivers near-linear-time approximate generalized Sinkhorn algorithms for bounded-genus graphs via separator decompositions, computational geometry, and fast matrix-vector multiplies with generalized distance matrices.
Rigorous security proofs for variable-length QKD, phase-error bounding with imperfect detectors, marginal-constrained entropy accumulation, and authentication reductions place practical QKD on firmer mathematical ground.
Semialgebraic graphs admit O(n^{1-2/(d+1)+ε})-bit adjacency labels via polynomial partitioning; semilinear graphs need only O(log n) bits.
Connectivity-preserving important separators of size at most k number 2^{O(k log k)} and can be enumerated in the same bound, yielding 2^{O(k log k)} FPT time for constant-class Node Multiway Cut-Uncut.
Incremental (1-ε)-approximate s-t max-flow algorithm achieving Õ(m + n F*/ε) total update time, first with polylog amortized updates for dense graphs.
First practical algorithm for expander hierarchies used to build a normalized-cut solver that beats state-of-the-art quality on large real-world graphs.
A GNN trained on bipartite alignment graphs between references and LLM generations reports state-of-the-art hallucination detection across four datasets, beating prior methods and GPT-4o.
Establishes n^{1-ε}-hardness of approximation for dichromatic number and acyclic number on tournaments, plus polynomial-time approximations for ℓ-dicolorable digraphs and special dense cases.
A differentially private pipeline using node-level DP summaries to fit ERGMs or SBMs, generate synthetic networks, and simulate SIS disease spread on ARTNet sexual contact data produces incidence, prevalence, and intervention effect sizes close to non-private versions.
1D translation-invariant Gibbs states at positive temperature exhibit superexponential decay of Belavkin-Staszewski conditional mutual information, enabling efficient learning from local measurements and tensor network approximations.
A topical review unifying statistical mechanics, tensor network, and AI approaches to approximate maximum likelihood decoding for quantum error correction codes.
citing papers explorer
-
Rigorous Security Proofs for Practical Quantum Key Distribution
Rigorous security proofs for variable-length QKD, phase-error bounding with imperfect detectors, marginal-constrained entropy accumulation, and authentication reductions place practical QKD on firmer mathematical ground.