| 351 |
Properly learning monotone functions via local reconstruction
Jane Lange, Ronitt Rubinfeld, Arsen Vasilyan
|
👻
Ghosted
|
cs.DS
|
10 |
4 years ago |
| 352 |
Balanced Allocations: The Heavily Loaded Case with Deletions
Nikhil Bansal, William Kuszmaul
|
👻
Ghosted
|
cs.DS
|
10 |
4 years ago |
| 353 |
Polynomial-Time Power-Sum Decomposition of Polynomials
Mitali Bafna, Jun-Ting Hsieh, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
10 |
3 years ago |
| 354 |
Improved Streaming Algorithms for Maximum Directed Cut via Smoothed Snapshots
Raghuvansh R. Saxena, Noah G. Singer, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
10 |
3 years ago |
| 355 |
Faster High Accuracy Multi-Commodity Flow from Single-Commodity Techniques
Jan van den Brand, Daniel Zhang
|
👻
Ghosted
|
cs.DS
|
10 |
3 years ago |
| 356 |
Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries
Tianxiao Li, Jingxun Liang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
10 |
3 years ago |
| 357 |
Local Computation Algorithms for Maximum Matching: New Lower Bounds
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
|
👻
Ghosted
|
cs.DS
|
10 |
2 years ago |
| 358 |
An Improved Pseudopolynomial Time Algorithm for Subset Sum
Lin Chen, Jiayi Lian, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
10 |
2 years ago |
| 359 |
Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
Aaron Bernstein, Joakim Blikstad, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
10 |
2 years ago |
| 360 |
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 |
| 361 |
Linear Hashing is Awesome
Mathias Bæk Tejs Knudsen
|
👻
Ghosted
|
cs.DS
|
9 |
9 years ago |
| 362 |
Subexponential LPs Approximate Max-Cut
Samuel B. Hopkins, Tselil Schramm, Luca Trevisan
|
👻
Ghosted
|
cs.DS
|
9 |
6 years ago |
| 363 |
Lipschitz Continuous Algorithms for Graph Problems
Soh Kumabe, Yuichi Yoshida
|
👻
Ghosted
|
cs.DS
|
9 |
3 years ago |
| 364 |
Approximating Edit Distance in the Fully Dynamic Model
Tomasz Kociumaka, Anish Mukherjee, Barna Saha
|
👻
Ghosted
|
cs.DS
|
9 |
3 years ago |
| 365 |
Agnostically Learning Multi-index Models with Queries
Ilias Diakonikolas, Daniel M. Kane, ... (+3 more)
|
👻
Ghosted
|
cs.LG
|
9 |
2 years ago |
| 366 |
Random Reed-Solomon Codes and Random Linear Codes are Locally Equivalent
Matan Levi, Jonathan Mosheiff, Nikhil Shagrithaya
|
👻
Ghosted
|
cs.IT
|
9 |
2 years ago |
| 367 |
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 |
| 368 |
Towards Better Approximation of Graph Crossing Number
Julia Chuzhoy, Sepideh Mahabadi, Zihan Tan
|
👻
Ghosted
|
cs.DS
|
8 |
5 years ago |
| 369 |
Testing Positive Semidefiniteness Using Linear Measurements
Deanna Needell, William Swartworth, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
8 |
4 years ago |
| 370 |
Almost Ramanujan Expanders from Arbitrary Expanders via Operator Amplification
Fernando Granha Jeronimo, Tushant Mittal, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 371 |
Interior-point methods on manifolds: theory and applications
Hiroshi Hirai, Harold Nieuwboer, Michael Walter
|
👻
Ghosted
|
math.OC
|
8 |
3 years ago |
| 372 |
The Bit Complexity of Efficient Continuous Optimization
Mehrdad Ghadiri, Richard Peng, Santosh S. Vempala
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 373 |
The Price of Explainability for Clustering
Anupam Gupta, Madhusudhan Reddy Pittu, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 374 |
New Lower Bounds for Adaptive Tolerant Junta Testing
Xi Chen, Shyamal Patel
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 375 |
Planar Disjoint Paths, Treewidth, and Kernels
Michał Włodarczyk, Meirav Zehavi
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 376 |
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 |
| 377 |
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 |
| 378 |
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 |
| 379 |
Fully Dynamic Matching and Ordered Ruzsa-Szemerédi Graphs
Soheil Behnezhad, Alma Ghafari
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 380 |
New Structures and Algorithms for Length-Constrained Expander Decompositions
Bernhard Haeupler, D Ellis Hershkowitz, Zihan Tan
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 381 |
Lempel-Ziv (LZ77) Factorization in Sublinear Time
Dominik Kempa, Tomasz Kociumaka
|
👻
Ghosted
|
cs.DS
|
8 |
1 year ago |
| 382 |
Towards Learning Sparsely Used Dictionaries with Arbitrary Supports
Pranjal Awasthi, Aravindan Vijayaraghavan
|
👻
Ghosted
|
cs.LG
|
7 |
8 years ago |
| 383 |
Analysis of Two-variable Recurrence Relations with Application to Parameterized Approximations
Ariel Kulik, Hadas Shachnai
|
👻
Ghosted
|
cs.DS
|
7 |
6 years ago |
| 384 |
Online List Labeling: Breaking the $\log^2n$ Barrier
Michael A. Bender, Alex Conway, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
7 |
4 years ago |
| 385 |
Survivable Network Design Revisited: Group-Connectivity
Qingyun Chen, Bundit Laekhanukit, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
7 |
4 years ago |
| 386 |
The Quantum and Classical Streaming Complexity of Quantum and Classical Max-Cut
John Kallaugher, Ojas Parekh
|
👻
Ghosted
|
quant-ph
|
7 |
4 years ago |
| 387 |
New Additive Spanner Lower Bounds by an Unlayered Obstacle Product
Greg Bodwin, Gary Hoppenworth
|
👻
Ghosted
|
cs.DS
|
7 |
4 years ago |
| 388 |
Derandomizing Directed Random Walks in Almost-Linear Time
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 389 |
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 |
| 390 |
A deterministic near-linear time approximation scheme for geometric transportation
Emily Fox, Jiashuai Lu
|
👻
Ghosted
|
cs.CG
|
7 |
3 years ago |
| 391 |
Bridge Girth: A Unifying Notion in Network Design
Greg Bodwin, Gary Hoppenworth, Ohad Trabelsi
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 392 |
Dynamic treewidth
Tuukka Korhonen, Konrad Majewski, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 393 |
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
Michael Elkin, Idan Shabat
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 394 |
Memory-Query Tradeoffs for Randomized Convex Optimization
Xi Chen, Binghui Peng
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 395 |
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 |
| 396 |
Dynamic "Succincter"
Tianxiao Li, Jingxun Liang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 397 |
Generalizations of Matrix Multiplication can solve the Light Bulb Problem
Josh Alman, Hengjie Zhang
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 398 |
On Approximate Fully-Dynamic Matching and Online Matrix-Vector Multiplication
Yang P. Liu
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 399 |
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 |
| 400 |
Succinct arguments for QMA from standard assumptions via compiled nonlocal games
Tony Metger, Anand Natarajan, Tina Zhang
|
👻
Ghosted
|
quant-ph
|
7 |
2 years ago |