| 301 |
PPSZ is better than you think
Dominik Scheder
|
👻
Ghosted
|
cs.DS
|
19 |
3 years ago |
| 302 |
Sparsifying sums of norms
Arun Jambulapati, James R. Lee, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
18 |
3 years ago |
| 303 |
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
Tomasz Kociumaka, Barna Saha
|
👻
Ghosted
|
cs.DS
|
18 |
5 years ago |
| 304 |
Scheduling with Communication Delays via LP Hierarchies and Clustering
Sami Davies, Janardhan Kulkarni, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
18 |
6 years ago |
| 305 |
Faster Minimum k-cut of a Simple Graph
Jason Li
|
👻
Ghosted
|
cs.DS
|
18 |
6 years ago |
| 306 |
Noisy population recovery in polynomial time
Anindya De, Michael Saks, Sijian Tang
|
🔮
The Ethereal
|
cs.CC
|
18 |
10 years ago |
| 307 |
Approximating ATSP by Relaxing Connectivity
Ola Svensson
|
👻
Ghosted
|
cs.DS
|
18 |
11 years ago |
| 308 |
Local Computation of Maximal Independent Set
Mohsen Ghaffari
|
👻
Ghosted
|
cs.DS
|
18 |
3 years ago |
| 309 |
Fast Multivariate Multipoint Evaluation Over All Finite Fields
Vishwas Bhargava, Sumanta Ghosh, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
18 |
4 years ago |
| 310 |
Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence
Nima Anari, Yang P. Liu, Thuy-Duong Vuong
|
👻
Ghosted
|
cs.DS
|
18 |
4 years ago |
| 311 |
Streaming Facility Location in High Dimension via Geometric Hashing
Artur Czumaj, Arnold Filtser, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
18 |
4 years ago |
| 312 |
Low Treewidth Embeddings of Planar and Minor-Free Metrics
Arnold Filtser, Hung Le
|
👻
Ghosted
|
cs.DS
|
18 |
4 years ago |
| 313 |
Streaming Euclidean $k$-median and $k$-means with $o(\log n)$ Space
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
|
👻
Ghosted
|
cs.DS
|
17 |
2 years ago |
| 314 |
Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, ... (+3 more)
|
🔮
The Ethereal
|
cs.CC
|
17 |
3 years ago |
| 315 |
Network Coding Gaps for Completion Times of Multiple Unicasts
Bernhard Haeupler, David Wajc, Goran Zuzic
|
👻
Ghosted
|
cs.DS
|
17 |
7 years ago |
| 316 |
A Tight Analysis of Bethe Approximation for Permanent
Nima Anari, Alireza Rezaei
|
👻
Ghosted
|
cs.DS
|
17 |
7 years ago |
| 317 |
Polylogarithmic approximation for minimum planarization (almost)
Ken-ichi Kawarabayashi, Anastasios Sidiropoulos
|
👻
Ghosted
|
cs.DS
|
17 |
8 years ago |
| 318 |
Better Unrelated Machine Scheduling for Weighted Completion Time via Random Offsets from Non-Uniform Distributions
Sungjin Im, Shi Li
|
👻
Ghosted
|
cs.DS
|
17 |
9 years ago |
| 319 |
High-Dimensional Geometric Streaming in Polynomial Space
David P. Woodruff, Taisuke Yasuda
|
👻
Ghosted
|
cs.DS
|
17 |
4 years ago |
| 320 |
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
Jan van den Brand, Li Chen, ... (+5 more)
|
👻
Ghosted
|
cs.DS
|
16 |
1 year ago |
| 321 |
Query lower bounds for log-concave sampling
Sinho Chewi, Jaume de Dios Pont, ... (+3 more)
|
👻
Ghosted
|
math.ST
|
16 |
3 years ago |
| 322 |
Hypergraph $k$-cut for fixed $k$ in deterministic polynomial time
Karthekeyan Chandrasekaran, Chandra Chekuri
|
👻
Ghosted
|
cs.DS
|
16 |
5 years ago |
| 323 |
On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
András Gilyén, Or Sattath
|
👻
Ghosted
|
quant-ph
|
16 |
9 years ago |
| 324 |
Tight Bounds on Low-degree Spectral Concentration of Submodular and XOS functions
Vitaly Feldman, Jan Vondrak
|
👻
Ghosted
|
cs.DS
|
16 |
11 years ago |
| 325 |
An Optimized Hybrid Approach for Path Finding
Ahlam Ansari, Mohd Amin Sayyed, ... (+2 more)
|
👻
Ghosted
|
cs.AI
|
16 |
11 years ago |
| 326 |
Minimax Rates for Robust Community Detection
Allen Liu, Ankur Moitra
|
👻
Ghosted
|
cs.DS
|
16 |
3 years ago |
| 327 |
A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches
Elena Gribelyuk, Honghao Lin, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
15 |
1 year ago |
| 328 |
Certified Hardness vs. Randomness for Log-Space
Edward Pyne, Ran Raz, Wei Zhan
|
🔮
The Ethereal
|
cs.CC
|
15 |
3 years ago |
| 329 |
Approximation Algorithms for Stochastic Minimum Norm Combinatorial Optimization
Sharat Ibrahimpur, Chaitanya Swamy
|
👻
Ghosted
|
cs.DS
|
15 |
5 years ago |
| 330 |
Explicit near-fully X-Ramanujan graphs
Ryan O'Donnell, Xinyu Wu
|
🔮
The Ethereal
|
math.CO
|
15 |
5 years ago |
| 331 |
Testing Positive Semi-Definiteness via Random Submatrices
Ainesh Bakshi, Nadiia Chepurko, Rajesh Jayaram
|
👻
Ghosted
|
cs.DS
|
15 |
6 years ago |
| 332 |
Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs
Akash Kumar, C. Seshadhri, Andrew Stolman
|
🔮
The Ethereal
|
cs.DM
|
15 |
8 years ago |
| 333 |
Towards derandomising Markov chain Monte Carlo
Weiming Feng, Heng Guo, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
15 |
3 years ago |
| 334 |
The ESPRIT algorithm under high noise: Optimal error scaling and noisy super-resolution
Zhiyan Ding, Ethan N. Epperly, ... (+2 more)
|
👻
Ghosted
|
cs.IT
|
14 |
2 years ago |
| 335 |
Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
Rohan Goyal, Prahladh Harsha, ... (+2 more)
|
👻
Ghosted
|
cs.IT
|
14 |
2 years ago |
| 336 |
Amortized Dynamic Cell-Probe Lower Bounds from Four-Party Communication
Omri Weinstein, Huacheng Yu
|
👻
Ghosted
|
cs.DS
|
14 |
10 years ago |
| 337 |
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
|
👻
Ghosted
|
cs.IT
|
14 |
9 years ago |
| 338 |
Deterministic Small Vertex Connectivity in Almost Linear Time
Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
|
👻
Ghosted
|
cs.DS
|
14 |
3 years ago |
| 339 |
Interior point methods are not worse than Simplex
Xavier Allamigeon, Daniel Dadush, ... (+3 more)
|
👻
Ghosted
|
math.OC
|
14 |
3 years ago |
| 340 |
Faster Pattern Matching under Edit Distance
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
|
👻
Ghosted
|
cs.DS
|
14 |
4 years ago |
| 341 |
Algorithms for the ferromagnetic Potts model on expanders
Charlie Carlson, Ewan Davies, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
14 |
4 years ago |
| 342 |
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1
Vincent Cohen-Addad, Hung Le, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
13 |
3 years ago |
| 343 |
A Tight Lower Bound on Adaptively Secure Full-Information Coin Flip
Iftach Haitner, Yonatan Karidi-Heller
|
👻
Ghosted
|
cs.CR
|
13 |
6 years ago |
| 344 |
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
Sándor Kisfaludi-Bak, Jesper Nederlof, Karol Węgrzycki
|
👻
Ghosted
|
cs.CG
|
13 |
5 years ago |
| 345 |
Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Matthew Fahrbach, Gary L. Miller, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
13 |
8 years ago |
| 346 |
Improved Online Algorithm for Weighted Flow Time
Yossi Azar, Noam Touitou
|
👻
Ghosted
|
cs.DS
|
13 |
8 years ago |
| 347 |
Testing Assignments to Constraint Satisfaction Problems
Hubie Chen, Matt Valeriote, Yuichi Yoshida
|
👻
Ghosted
|
cs.DS
|
13 |
9 years ago |
| 348 |
Induced Cycles and Paths Are Harder Than You Think
Mina Dalirrooyfard, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
13 |
3 years ago |
| 349 |
Killing a Vortex
Dimitrios M. Thilikos, Sebastian Wiederrecht
|
🔮
The Ethereal
|
math.CO
|
13 |
3 years ago |
| 350 |
Computing in Anonymous Dynamic Networks Is Linear
Giuseppe A. Di Luna, Giovanni Viglietta
|
👻
Ghosted
|
cs.DC
|
13 |
4 years ago |