| 451 |
Tractable Agreement Protocols
Natalie Collina, Surbhi Goel, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
8 |
1 year ago |
| 452 |
Sampling and Integration of Logconcave Functions by Algorithmic Diffusion
Yunbum Kook, Santosh S. Vempala
|
👻
Ghosted
|
cs.DS
|
8 |
1 year ago |
| 453 |
Positive bias makes tensor-network contraction tractable
Jiaqing Jiang, Jielun Chen, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
8 |
1 year ago |
| 454 |
Improving the Bit Complexity of Communication for Distributed Convex Optimization
Mehrdad Ghadiri, Yin Tat Lee, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 455 |
Explicit Codes approaching Generalized Singleton Bound using Expanders
Fernando Granha Jeronimo, Tushant Mittal, ... (+2 more)
|
👻
Ghosted
|
cs.IT
|
8 |
1 year ago |
| 456 |
Ghost Value Augmentation for $k$-Edge-Connectivity
D Ellis Hershkowitz, Nathan Klein, Rico Zenklusen
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 457 |
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 458 |
Semidefinite programming and linear equations vs. homomorphism problems
Lorenzo Ciardo, Stanislav Živný
|
🔮
The Ethereal
|
cs.CC
|
8 |
2 years ago |
| 459 |
Breaking the VLB Barrier for Oblivious Reconfigurable Networks
Tegan Wilson, Daniel Amir, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
8 |
2 years ago |
| 460 |
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
Mina Dalirrooyfard, Surya Mathialagan, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 461 |
Gradient-Based Empirical Risk Minimization using Local Polynomial Regression
Ali Jadbabaie, Anuran Makur, Devavrat Shah
|
👻
Ghosted
|
cs.LG
|
8 |
5 years ago |
| 462 |
Optimal Sequence Length Requirements for Phylogenetic Tree Reconstruction with Indels
Arun Ganesh, Qiuyi Zhang
|
👻
Ghosted
|
cs.DS
|
8 |
7 years ago |
| 463 |
Tight Conditional Lower Bounds for Vertex Connectivity Problems
Zhiyi Huang, Yaowei Long, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 464 |
Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor
Daniel Lokshtanov, Marcin Pilipczuk, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
3 years ago |
| 465 |
List-Decodable Covariance Estimation
Misha Ivkov, Pravesh K. Kothari
|
👻
Ghosted
|
cs.DS
|
8 |
4 years ago |
| 466 |
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
Karl Bringmann, Alejandro Cassis, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
8 |
4 years ago |
| 467 |
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
Elena Gribelyuk, Honghao Lin, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
7 |
1 year ago |
| 468 |
Redundancy Is All You Need
Joshua Brakensiek, Venkatesan Guruswami
|
👻
Ghosted
|
cs.DS
|
7 |
1 year ago |
| 469 |
Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
Tuukka Korhonen
|
👻
Ghosted
|
cs.DS
|
7 |
1 year ago |
| 470 |
Treewidth Inapproximability and Tight ETH Lower Bound
Édouard Bonnet
|
🔮
The Ethereal
|
cs.CC
|
7 |
2 years ago |
| 471 |
Approximating Maximum Matching Requires Almost Quadratic Time
Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 472 |
Bounded Edit Distance: Optimal Static and Dynamic Algorithms for Small Integer Weights
Egor Gorbachev, Tomasz Kociumaka
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 473 |
Efficient Algorithms and New Characterizations for CSP Sparsification
Sanjeev Khanna, Aaron L. Putterman, Madhu Sudan
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 474 |
A Fine-grained Classification of Subquadratic Patterns for Subgraph Listing and Friends
Karl Bringmann, Egor Gorbachev
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 475 |
Nearly Optimal Fault Tolerant Distance Oracle
Dipan Dey, Manoj Gupta
|
👻
Ghosted
|
cs.DS
|
7 |
2 years ago |
| 476 |
Detecting Low-Degree Truncation
Anindya De, Huan Li, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
7 |
2 years ago |
| 477 |
Weak recovery, hypothesis testing, and mutual information in stochastic block models and planted factor graphs
Elchanan Mossel, Allan Sly, Youngtak Sohn
|
👻
Ghosted
|
math.PR
|
7 |
2 years ago |
| 478 |
Locality vs Quantum Codes
Samuel Dai, Ray Li
|
👻
Ghosted
|
quant-ph
|
7 |
1 year ago |
| 479 |
Improved Complexity for Smooth Nonconvex Optimization: A Two-Level Online Learning Approach with Quasi-Newton Methods
Ruichen Jiang, Aryan Mokhtari, Francisco Patitucci
|
👻
Ghosted
|
math.OC
|
7 |
1 year ago |
| 480 |
The Power of Adaptivity in Quantum Query Algorithms
Uma Girish, Makrand Sinha, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
7 |
2 years ago |
| 481 |
Connectivity Labeling and Routing with Multiple Vertex Failures
Merav Parter, Asaf Petruschka, Seth Pettie
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 482 |
On the complexity of isomorphism problems for tensors, groups, and polynomials IV: linear-length reductions and their applications
Joshua A. Grochow, Youming Qiao
|
🔮
The Ethereal
|
cs.CC
|
7 |
3 years ago |
| 483 |
Near-Optimal Dynamic Rounding of Fractional Matchings in Bipartite Graphs
Sayan Bhattacharya, Peter Kiss, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 484 |
Static Pricing Guarantees for Queueing Systems
Jacob Bergquist, Adam N. Elmachtoub
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 485 |
Locally consistent decomposition of strings with applications to edit distance sketching
Sudatta Bhattacharya, Michal Koucký
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 486 |
A $(2+\varepsilon)$-approximation algorithm for preemptive weighted flow time on a single machine
Lars Rohwedder, Andreas Wiese
|
👻
Ghosted
|
cs.DS
|
7 |
5 years ago |
| 487 |
On the Complexity of CSP-based Ideal Membership Problems
Andrei A. Bulatov, Akbar Rafiey
|
🔮
The Ethereal
|
cs.CC
|
7 |
5 years ago |
| 488 |
Approximation Algorithms for Distributionally Robust Stochastic Optimization with Black-Box Distributions
Andre Linhares, Chaitanya Swamy
|
👻
Ghosted
|
cs.DS
|
7 |
7 years ago |
| 489 |
Testing Unateness Nearly Optimally
Xi Chen, Erik Waingarten
|
👻
Ghosted
|
cs.DS
|
7 |
7 years ago |
| 490 |
Approximate Modularity Revisited
Uriel Feige, Michal Feldman, Inbal Talgam-Cohen
|
👻
Ghosted
|
cs.DS
|
7 |
9 years ago |
| 491 |
A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection
Kyle Fox, Philip N. Klein, Shay Mozes
|
👻
Ghosted
|
cs.DS
|
7 |
11 years ago |
| 492 |
Online Unrelated-Machine Load Balancing and Generalized Flow with Recourse
Ravishankar Krishnaswamy, Shi Li, Varun Suriyanarayana
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 493 |
Approximate Max-Flow Min-Multicut Theorem for Graphs of Bounded Treewidth
Tobias Friedrich, Davis Issac, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
7 |
3 years ago |
| 494 |
Local and global expansion in random geometric graphs
Siqi Liu, Sidhanth Mohanty, ... (+2 more)
|
🔮
The Ethereal
|
math.CO
|
7 |
3 years ago |
| 495 |
Merge-width and First-Order Model Checking
Jan Dreier, Szymon Toruńczyk
|
🔮
The Ethereal
|
math.CO
|
6 |
1 year ago |
| 496 |
Adaptive and oblivious statistical adversaries are equivalent
Guy Blanc, Gregory Valiant
|
👻
Ghosted
|
cs.LG
|
6 |
1 year ago |
| 497 |
Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
Pravesh Kothari, Aaron Potechin, Jeff Xu
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |
| 498 |
Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
Shivam Nadimpalli, Shyamal Patel
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |
| 499 |
On the Power of Interactive Proofs for Learning
Tom Gur, Mohammad Mahdi Jahanara, ... (+4 more)
|
🔮
The Ethereal
|
cs.CC
|
6 |
2 years ago |
| 500 |
Data-Dependent LSH for the Earth Mover's Distance
Rajesh Jayaram, Erik Waingarten, Tian Zhang
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |