Data structures achieve O(log* n) per operation for tree-sum queries on decremental forests using micro-macro decomposition, plus a universally optimal algorithm in the group model.
Improved Distance (Sensitivity) Oracles with Subquadratic Space
6 Pith papers cite this work. Polarity classification is still indexing.
6
Pith papers citing it
citation-role summary
background 1
method 1
citation-polarity summary
years
2026 6verdicts
UNVERDICTED 6representative citing papers
A new algorithm finds a matroid basis in tilde O(n to the 3/7) adaptive rounds via independence oracle.
Explicit families of CNF formulas exist such that tree-like semantic Frege refutations with line size s(n) require superpolynomial length for most formulas in the family, for s(n) in a broad range from nearly quadratic to subexponential in n.
A simpler conditional-expectations derandomization yields (L,f)-RPCs with Õ(f L^{f+o(1)}) covering value and Õ(f^{5/2} L^{o(1)}) query time; a new randomized construction matches an improved lower bound of Õ((L/f)^f L^{o(1)}) when f = o(log L).
Classifies the classical and parameterized complexity of vertex-identification problems to chordal graph subclasses, with an almost complete picture for parameters k and n-k.
A non-interactive time-delayed publicly verifiable scheme for quantum computation compiled from private 2-round protocols via time-lock puzzles and commitments, proven secure in the quantum random oracle model with CRS.
citing papers explorer
-
Fast decremental tree sums in forests
Data structures achieve O(log* n) per operation for tree-sum queries on decremental forests using micro-macro decomposition, plus a universally optimal algorithm in the group model.
-
An $\widetilde{O} (n^{3/7})$ Round Parallel Algorithm for Matroid Bases
A new algorithm finds a matroid basis in tilde O(n to the 3/7) adaptive rounds via independence oracle.
-
Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
Explicit families of CNF formulas exist such that tree-like semantic Frege refutations with line size s(n) require superpolynomial length for most formulas in the family, for s(n) in a broad range from nearly quadratic to subexponential in n.
-
Simpler and Improved Replacement Path Coverings
A simpler conditional-expectations derandomization yields (L,f)-RPCs with Õ(f L^{f+o(1)}) covering value and Õ(f^{5/2} L^{o(1)}) query time; a new randomized construction matches an improved lower bound of Õ((L/f)^f L^{o(1)}) when f = o(log L).
-
Identification to Subclasses of Chordal Graphs
Classifies the classical and parameterized complexity of vertex-identification problems to chordal graph subclasses, with an almost complete picture for parameters k and n-k.
-
Time-Delayed Publicly Verifiable Quantum Computation for Classical Verifiers
A non-interactive time-delayed publicly verifiable scheme for quantum computation compiled from private 2-round protocols via time-lock puzzles and commitments, proven secure in the quantum random oracle model with CRS.