| 401 |
Approximating Edit Distance in the Fully Dynamic Model
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
|
👻
Ghosted
|
cs.DS
|
9 |
3 years ago |
| 402 |
Properly Learning Decision Trees with Queries Is NP-Hard
Caleb Koch, Carmen Strassle, Li-Yang Tan
|
🔮
The Ethereal
|
cs.CC
|
9 |
3 years ago |
| 403 |
Improved Extractors for Small-Space Sources
Eshan Chattopadhyay, Jesse Goodman
|
🔮
The Ethereal
|
cs.CC
|
9 |
6 years ago |
| 404 |
Subexponential LPs Approximate Max-Cut
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
|
👻
Ghosted
|
cs.DS
|
9 |
6 years ago |
| 405 |
Linear Hashing is Awesome
Mathias Bæk Tejs Knudsen
|
👻
Ghosted
|
cs.DS
|
9 |
9 years ago |
| 406 |
Breaking the Variance: Approximating the Hamming Distance in $\tilde O(1/ε)$ Time Per Alignment
Tsvi Kopelowitz, Ely Porat
|
👻
Ghosted
|
cs.DS
|
9 |
10 years ago |
| 407 |
Lipschitz Continuous Algorithms for Graph Problems
Soh Kumabe, Yuichi Yoshida
|
👻
Ghosted
|
cs.DS
|
9 |
3 years ago |
| 408 |
Explicit Lossless Vertex Expanders
Jun-Ting Hsieh, Alexander Lubotzky, ... (+3 more)
|
🔮
The Ethereal
|
math.CO
|
8 |
1 year ago |
| 409 |
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Dominik Kempa, Tomasz Kociumaka
|
👻
Ghosted
|
cs.DS
|
8 |
1 year ago |
| 410 |
Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
Dmitriy Kunisky, Xifan Yu
|
🔮
The Ethereal
|
cs.CC
|
8 |
2 years ago |
| 411 |
New Structures and Algorithms for Length-Constrained Expander Decompositions
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 412 |
Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
Soheil Behnezhad, Alma Ghafari
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 413 |
Near-Tight Bounds for 3-Query Locally Correctable Binary Linear Codes via Rainbow Cycles
Omar Alrabiah, Venkatesan Guruswami
|
👻
Ghosted
|
cs.IT
|
8 |
2 years ago |
| 414 |
List Decoding of Tanner and Expander Amplified Codes from Distance Certificates
Fernando Granha Jeronimo, Shashank Srivastava, Madhur Tulsiani
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 415 |
The Full Landscape of Robust Mean Testing: Sharp Separations between Oblivious and Adaptive Contamination
Clément L. Canonne, Samuel B. Hopkins, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 416 |
Planar Disjoint Paths, Treewidth, and Kernels
Michał Włodarczyk, Meirav Zehavi
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 417 |
New Lower Bounds for Adaptive Tolerant Junta Testing
Xi Chen, Shyamal Patel
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 418 |
The Price of Explainability for Clustering
Anupam Gupta, Madhusudhan Reddy Pittu, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 419 |
The Bit Complexity of Efficient Continuous Optimization
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 420 |
Interior-point methods on manifolds: theory and applications
Hiroshi Hirai, Harold Nieuwboer, Michael Walter
|
👻
Ghosted
|
math.OC
|
8 |
3 years ago |
| 421 |
Towards Better Approximation of Graph Crossing Number
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan
|
👻
Ghosted
|
cs.DS
|
8 |
5 years ago |
| 422 |
Unique Decoding of Explicit $ε$-balanced Codes Near the Gilbert-Varshamov Bound
Fernando Granha Jeronimo, Dylan Quintana, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
5 years ago |
| 423 |
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
Fernando Granha Jeronimo, Tushant Mittal, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 424 |
Testing Positive Semidefiniteness Using Linear Measurements
Deanna Needell, William Swartworth, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
8 |
4 years ago |
| 425 |
Bipartite Matching is in Catalytic Logspace
Aryan Agarwala, Ian Mertz
|
🔮
The Ethereal
|
cs.CC
|
7 |
1 year ago |
| 426 |
Deterministic counting from coupling independence
Xiaoyu Chen, Weiming Feng, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
7 |
1 year ago |
| 427 |
Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
Sanjeev Khanna, Aaron L. Putterman, Madhu Sudan
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 428 |
Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
|
👻
Ghosted
|
cs.LG
|
7 |
2 years ago |
| 429 |
On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
Yang P. Liu
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 430 |
Maximally Extendable Product Codes are Good Coboundary Expanders
Gleb Kalachev, Pavel Panteleev
|
👻
Ghosted
|
cs.IT
|
7 |
1 year ago |
| 431 |
Generalizations of Matrix Multiplication can solve the Light Bulb Problem
Josh Alman, Hengjie Zhang
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 432 |
Dynamic "Succincter"
Tianxiao Li, Jingxun Liang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 433 |
One Tree to Rule Them All: Poly-Logarithmic Universal Steiner Tree
Costas Busch, Da Qi Chen, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 434 |
Memory-Query Tradeoffs for Randomized Convex Optimization
Xi Chen, Binghui Peng
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 435 |
Traversing combinatorial 0/1-polytopes via optimization
Arturo Merino, Torsten Mütze
|
🔮
The Ethereal
|
cs.DM
|
7 |
3 years ago |
| 436 |
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
Michael Elkin, Idan Shabat
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 437 |
Dynamic treewidth
Tuukka Korhonen, Konrad Majewski, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 438 |
Streaming Lower Bounds and Asymmetric Set-Disjointness
Shachar Lovett, Jiapeng Zhang
|
🔮
The Ethereal
|
cs.CC
|
7 |
3 years ago |
| 439 |
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Ariel Kulik, Hadas Shachnai
|
👻
Ghosted
|
cs.DS
|
7 |
6 years ago |
| 440 |
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
Pranjal Awasthi, Aravindan Vijayaraghavan
|
👻
Ghosted
|
cs.LG
|
7 |
8 years ago |
| 441 |
A characterization of testable hypergraph properties
Felix Joos, Jaehoon Kim, ... (+2 more)
|
🔮
The Ethereal
|
math.CO
|
7 |
9 years ago |
| 442 |
Succinct arguments for QMA from standard assumptions via compiled nonlocal games
Tony Metger, Anand Natarajan, Tina Zhang
|
👻
Ghosted
|
quant-ph
|
7 |
2 years ago |
| 443 |
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!
Divesh Aggarwal, Rajendra Kumar
|
🔮
The Ethereal
|
cs.CC
|
7 |
3 years ago |
| 444 |
Bridge Girth: A Unifying Notion in Network Design
Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 445 |
A deterministic near-linear time approximation scheme for geometric transportation
Emily Fox, Jiashuai Lu
|
👻
Ghosted
|
cs.CG
|
7 |
3 years ago |
| 446 |
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 447 |
Derandomizing Directed Random Walks in Almost-Linear Time
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 448 |
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
Greg Bodwin, Gary Hoppenworth
|
👻
Ghosted
|
cs.DS
|
7 |
4 years ago |
| 449 |
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut
John Kallaugher, Ojas Parekh
|
👻
Ghosted
|
quant-ph
|
7 |
4 years ago |
| 450 |
Survivable Network Design Revisited: Group-Connectivity
Qingyun Chen, Bundit Laekhanukit, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
7 |
4 years ago |