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.
Induced Cycles and Paths Are Harder Than You Think , booktitle =
9 Pith papers cite this work. Polarity classification is still indexing.
9
Pith papers citing it
citation-role summary
background 2
method 1
citation-polarity summary
years
2026 9representative citing papers
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.
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 achieves near-linear time approximate generalized Sinkhorn for geodesic optimal transport on bounded-genus graphs by combining separator-based decompositions with Fourier and low-displacement-rank matrix-vector multiplications.
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.
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.
citing papers explorer
-
Dynamic Rank, Basis, and Matching
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 Complexity Separations for Dense and Sparse Graphs
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 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.
-
Backdoor Channels Hidden in Latent Space: Cryptographic Undetectability in Modern Neural Networks
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.
-
When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
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.
-
Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs
GenusSink achieves near-linear time approximate generalized Sinkhorn for geodesic optimal transport on bounded-genus graphs by combining separator-based decompositions with Fourier and low-displacement-rank matrix-vector multiplications.
-
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.
-
Implicit representations via the polynomial method
Semialgebraic graphs admit O(n^{1-2/(d+1)+ε})-bit adjacency labels via polynomial partitioning; semilinear graphs need only O(log n) bits.
-
Differentially Private Modeling of Disease Transmission within Human Contact Networks
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.