First adversarially robust data structure for c-approximate furthest neighbor search with query time matching the best known oblivious results for many parameter regimes.
hub Canonical reference
51 Shay Solomon, Amitai Uzrad, and Tianyi Zhang
Canonical reference. 80% of citing Pith papers cite this work as background.
20
Pith papers citing it
Background
80% of classified citations
hub tools
citation-role summary
background 4
other 1
citation-polarity summary
representative citing papers
Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
Scalable ROM-PRUs imply a positive resolution to the Aaronson-Kuperberg unitary synthesis problem, with any such algorithm requiring a classical oracle of input length (2-o(1))log d that rules out existing candidates.
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
A randomized algorithm maintains O(Δ / ln Δ) coloring of dynamically changing triangle-free graphs with amortized Δ^{o(1)} log n update time per edge update against an adaptive adversary.
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
Quadtrees and related structures are 2-Presortable, admitting expected O(n sqrt(log n)) algorithms given presorts along both axes.
Modified logarithmic Sobolev inequalities hold for Davies semigroups in 2D Abelian quantum double models at positive temperatures via a Dobrushin-Shlosman condition and verified strong martingale property for conditional expectations.
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.
A technique for enforcing differential privacy in temporal runtime monitoring by analyzing dependencies and injecting noise into specifications while using tree mechanisms to limit accuracy loss.
A generic conversion turns offline local search algorithms into online stochastic combinatorial bandit algorithms with O(log^3 T) approximate regret.
DSQ is W[1]-hard on degeneracy-2 and K_{3,3}-free graphs but FPT parameterized by solution size plus treewidth, FPT on nowhere dense classes, and admits subexponential algorithms on apex-minor-free graphs via bidimensionality.
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone parameters.
O(n log n) algorithm for edge-coloring planar graphs with Delta >= 8 using Delta colors, extending prior O(n log n) result for Delta >= 9 and generalizing to bounded-genus graphs.
Incremental (1-ε)-approximate s-t max-flow algorithm achieving Õ(m + n F*/ε) total update time, first with polylog amortized updates for dense graphs.
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
First experimental study of dynamic greedy set cover algorithms reveals practical tradeoffs in quality and efficiency across real instances.
CBMD decomposes non-Hermitian operators via contour residues to enable optimal-query quantum simulation of first-order dynamics and special functions such as Bessel and Airy evolutions without requiring diagonalizability.
Controlled unitaries can be decontrolled into standard unitaries with random phase, showing they do not help beyond global phase information for a large class of quantum problems.
citing papers explorer
-
Adversarially Robust Approximate Furthest Neighbor
First adversarially robust data structure for c-approximate furthest neighbor search with query time matching the best known oblivious results for many parameter regimes.
-
Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems
Develops a quantum algorithm for linear matrix differential equations with query complexity O~(ν L t / ε) that is nearly optimal and yields polynomial to exponential speedups for open quantum system simulation.
-
On Scalable Pseudorandom Unitaries and the Unitary Synthesis Problem
Scalable ROM-PRUs imply a positive resolution to the Aaronson-Kuperberg unitary synthesis problem, with any such algorithm requiring a classical oracle of input length (2-o(1))log d that rules out existing candidates.
-
Online Steiner Forest with Recourse
An algorithm for online Steiner forest achieves constant competitiveness with amortized O(log n) recourse.
-
Fully Dynamic Algorithms for Coloring Triangle-Free Graphs
A randomized algorithm maintains O(Δ / ln Δ) coloring of dynamically changing triangle-free graphs with amortized Δ^{o(1)} log n update time per edge update against an adaptive adversary.
-
Suffix Random Access via Function Inversion: A Key for Asymmetric Streaming String Algorithms
A bidirectional reduction between suffix random access and function inversion enables improved asymmetric streaming algorithms for exact/approximate pattern matching and relative Lempel-Ziv compression.
-
The Presort Hierarchy for Geometric Problems
Quadtrees and related structures are 2-Presortable, admitting expected O(n sqrt(log n)) algorithms given presorts along both axes.
-
Modified logarithmic Sobolev inequalities for Abelian quantum double models
Modified logarithmic Sobolev inequalities hold for Davies semigroups in 2D Abelian quantum double models at positive temperatures via a Dobrushin-Shlosman condition and verified strong martingale property for conditional expectations.
-
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.
-
Differentially Private Runtime Monitoring
A technique for enforcing differential privacy in temporal runtime monitoring by analyzing dependencies and injecting noise into specifications while using tree mechanisms to limit accuracy loss.
-
Offline Local Search for Online Stochastic Bandits
A generic conversion turns offline local search algorithms into online stochastic combinatorial bandit algorithms with O(log^3 T) approximate regret.
-
Dominating Set with Quotas: Balancing Coverage and Constraints
DSQ is W[1]-hard on degeneracy-2 and K_{3,3}-free graphs but FPT parameterized by solution size plus treewidth, FPT on nowhere dense classes, and admits subexponential algorithms on apex-minor-free graphs via bidimensionality.
-
Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
Introduces strong sparsification for 1-in-3-SAT by merging variables, relying on a sub-quadratic vector-set bound derived from the Polynomial Freiman-Ruzsa Theorem, with an application to hypergraph coloring approximation.
-
Colorful Minors
Defines colorful minors on q-colored graphs and proves three structural theorems for H-colorful-minor-free graphs, a q-parameterized Erdős-Pósa classification, and FPT results for testing and colorful-minor-monotone parameters.
-
The planar edge-coloring theorem of Vizing in $O(n\log n)$ time
O(n log n) algorithm for edge-coloring planar graphs with Delta >= 8 using Delta colors, extending prior O(n log n) result for Delta >= 9 and generalizing to bounded-genus graphs.
-
Incremental Approximate Maximum Flow via Residual Graph Sparsification
Incremental (1-ε)-approximate s-t max-flow algorithm achieving Õ(m + n F*/ε) total update time, first with polylog amortized updates for dense graphs.
-
Finding irrelevant vertices in linear time on bounded-genus graphs
A decomposition-based framework finds entire sets of irrelevant vertices in linear time on bounded-genus graphs, enabling linear-time algorithms for minor containment, disjoint paths, and deletion problems.
-
Engineering Algorithms for Dynamic Greedy Set Cover
First experimental study of dynamic greedy set cover algorithms reveals practical tradeoffs in quality and efficiency across real instances.
-
Quantum Simulation of Non-Hermitian Special Functions and Dynamics via Contour-based Matrix Decomposition
CBMD decomposes non-Hermitian operators via contour residues to enable optimal-query quantum simulation of first-order dynamics and special functions such as Bessel and Airy evolutions without requiring diagonalizability.
-
Are controlled unitaries helpful?
Controlled unitaries can be decontrolled into standard unitaries with random phase, showing they do not help beyond global phase information for a large class of quantum problems.