| 551 |
Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
Jakob Nogler, Adam Polak, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
3 |
1 year ago |
| 552 |
Near-Optimal Dimension Reduction for Facility Location
Lingxiao Huang, Shaofeng H. -C. Jiang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
3 |
1 year ago |
| 553 |
Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics
Jason Gaitonde, Ankur Moitra, Elchanan Mossel
|
👻
Ghosted
|
cs.LG
|
3 |
1 year ago |
| 554 |
A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman, Sumegha Garg, ... (+4 more)
|
🔮
The Ethereal
|
cs.CC
|
3 |
2 years ago |
| 555 |
Hypergraph Unreliability in Quasi-Polynomial Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
|
👻
Ghosted
|
cs.DS
|
3 |
2 years ago |
| 556 |
Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
Uriya A. First, Tali Kaufman
|
🔮
The Ethereal
|
math.CO
|
3 |
2 years ago |
| 557 |
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
Spencer Compton, Gregory Valiant
|
👻
Ghosted
|
math.ST
|
3 |
2 years ago |
| 558 |
Work-Efficient Parallel Derandomization II: Optimal Concentrations via Bootstrapping
Mohsen Ghaffari, Christoph Grunau
|
👻
Ghosted
|
cs.DS
|
3 |
2 years ago |
| 559 |
Almost-Optimal Sublinear Additive Spanners
Zihan Tan, Tianyi Zhang
|
👻
Ghosted
|
cs.DS
|
3 |
3 years ago |
| 560 |
Combinatorial Bernoulli Factories
Rad Niazadeh, Renato Paes Leme, Jon Schneider
|
👻
Ghosted
|
cs.DS
|
3 |
5 years ago |
| 561 |
Optimal transport between determinantal point processes and application to fast simulation
Laurent Decreusefond, Guillaume Moroz
|
👻
Ghosted
|
cs.DS
|
3 |
5 years ago |
| 562 |
Unbounded lower bound for k-server against weak adversaries
Marcin Bienkowski, Jarosław Byrka, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
3 |
6 years ago |
| 563 |
Testing noisy linear functions for sparsity
Xue Chen, Anindya De, Rocco A. Servedio
|
🔮
The Ethereal
|
cs.CC
|
3 |
6 years ago |
| 564 |
A Concentration Bound for TD(0) with Function Approximation
Siddharth Chandak, Vivek S. Borkar
|
👻
Ghosted
|
cs.LG
|
3 |
2 years ago |
| 565 |
DNF Learning via Locally Mixing Random Walks
Josh Alman, Shivam Nadimpalli, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 566 |
Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
Zengfeng Huang, Zhongzheng Xiong, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 567 |
Covering Approximate Shortest Paths with DAGs
Sepehr Assadi, Gary Hoppenworth, Nicole Wein
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 568 |
Privately Evaluating Untrusted Black-Box Functions
Ephraim Linder, Sofya Raskhodnikova, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 569 |
Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
Deeparnab Chakrabarty, Xi Chen, ... (+3 more)
|
👻
Ghosted
|
math.ST
|
2 |
1 year ago |
| 570 |
On the Locality of the Lovász Local Lemma
Peter Davies-Peck
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 571 |
Fingerprinting Codes Meet Geometry: Improved Lower Bounds for Private Query Release and Adaptive Data Analysis
Xin Lyu, Kunal Talwar
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 572 |
Optimal Static Dictionary with Worst-Case Constant Query Time
Yang Hu, Jingxun Liang, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 573 |
The Cost of Consistency: Submodular Maximization with Constant Recourse
Paul Dütting, Federico Fusco, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 574 |
Approximating the Held-Karp Bound for Metric TSP in Nearly Linear Work and Polylogarithmic Depth
Zhuan Khye Koh, Omri Weinstein, Sorrachai Yingchareonthawornchai
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 575 |
Learning the Sherrington-Kirkpatrick Model Even at Low Temperature
Gautam Chandrasekaran, Adam Klivans
|
👻
Ghosted
|
cs.LG
|
2 |
1 year ago |
| 576 |
Testing Support Size More Efficiently Than Learning Histograms
Renato Ferreira Pinto, Nathaniel Harms
|
👻
Ghosted
|
cs.DS
|
2 |
1 year ago |
| 577 |
Almost Linear Size Edit Distance Sketch
Michal Koucký, Michael Saks
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 578 |
Distribution-Free Testing of Decision Lists with a Sublinear Number of Queries
Xi Chen, Yumou Fei, Shyamal Patel
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 579 |
On approximability of the Permanent of PSD matrices
Farzam Ebrahimnejad, Ansh Nagda, Shayan Oveis Gharan
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 580 |
Super Non-singular Decompositions of Polynomials and their Application to Robustly Learning Low-degree PTFs
Ilias Diakonikolas, Daniel M. Kane, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 581 |
Private graphon estimation via sum-of-squares
Hongjie Chen, Jingqiu Ding, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 582 |
Approximating Small Sparse Cuts
Aditya Anand, Euiwoong Lee, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 583 |
Evolving privacy: drift parameter estimation for discretely observed i.i.d. diffusion processes under LDP
Chiara Amorino, Arnaud Gloter, Hélène Halconruy
|
👻
Ghosted
|
math.ST
|
2 |
2 years ago |
| 584 |
Near-Optimal Streaming Ellipsoidal Rounding for General Convex Polytopes
Yury Makarychev, Naren Sarayu Manoj, Max Ovsiankin
|
👻
Ghosted
|
cs.DS
|
2 |
2 years ago |
| 585 |
Interior Point Methods with a Gradient Oracle
Adrian Vladu
|
👻
Ghosted
|
cs.DS
|
2 |
3 years ago |
| 586 |
On Stein's lemma in hypotheses testing in general non-asymptotic case
Marat V. Burnashev
|
👻
Ghosted
|
cs.IT
|
2 |
3 years ago |
| 587 |
Approximating Generalized Network Design under (Dis)economies of Scale with Applications to Energy Efficiency
Yuval Emek, Shay Kutten, ... (+2 more)
|
👻
Ghosted
|
cs.GT
|
2 |
8 years ago |
| 588 |
Process convergence for the complexity of Radix Selection on Markov sources
Kevin Leckey, Ralph Neininger, Henning Sulzbach
|
👻
Ghosted
|
math.PR
|
2 |
10 years ago |
| 589 |
Oblivious Defense in ML Models: Backdoor Removal without Detection
Shafi Goldwasser, Jonathan Shafer, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
2 |
1 year ago |
| 590 |
Computing better approximate pure Nash equilibria in cut games via semidefinite programming
Ioannis Caragiannis, Zhile Jiang
|
👻
Ghosted
|
cs.GT
|
2 |
3 years ago |
| 591 |
All-Pairs Shortest Paths with Few Weights per Node
Amir Abboud, Nick Fischer, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 592 |
Deterministic Dynamic Maximal Matching in Sublinear Update Time
Aaron Bernstein, Sayan Bhattacharya, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 593 |
Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs
Li Chen, Andrei Graur, Aaron Sidford
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 594 |
Sample-Optimal Private Regression in Polynomial Time
Prashanti Anderson, Ainesh Bakshi, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 595 |
Network Unreliability in Almost-Linear Time
Ruoxu Cen, Jason Li, Debmalya Panigrahi
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 596 |
Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 597 |
Long Arithmetic Progressions in Sumsets and Subset Sums: Constructive Proofs and Efficient Witnesses
Lin Chen, Yuchen Mao, Guochuan Zhang
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 598 |
Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
Itai Boneh, Shiri Chechik, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 599 |
Optimal Non-Oblivious Open Addressing
Michael A. Bender, William Kuszmaul, Renfei Zhou
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |
| 600 |
Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time
Talya Eden, Reut Levi, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
1 |
1 year ago |