| 451 |
Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
Tuukka Korhonen
|
👻
Ghosted
|
cs.DS
|
7 |
1 year ago |
| 452 |
Redundancy Is All You Need
Joshua Brakensiek, Venkatesan Guruswami
|
👻
Ghosted
|
cs.DS
|
7 |
1 year ago |
| 453 |
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 |
| 454 |
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
Elena Gribelyuk, Honghao Lin, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
7 |
1 year ago |
| 455 |
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
6 |
7 years ago |
| 456 |
The Query Complexity of Certification
Guy Blanc, Caleb Koch, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
6 |
4 years ago |
| 457 |
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
Julia Chuzhoy, Zihan Tan
|
👻
Ghosted
|
cs.DS
|
6 |
4 years ago |
| 458 |
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang, Sagnik Mukhopadhyay
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 459 |
Lifting uniform learners via distributional decomposition
Guy Blanc, Jane Lange, ... (+2 more)
|
👻
Ghosted
|
stat.ML
|
6 |
3 years ago |
| 460 |
Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
Yulin Wang, Chihao Zhang, Zihan Zhang
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 461 |
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
|
👻
Ghosted
|
cs.LG
|
6 |
2 years ago |
| 462 |
Data-Dependent LSH for the Earth Mover's Distance
Rajesh Jayaram, Erik Waingarten, Tian Zhang
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |
| 463 |
Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
Shivam Nadimpalli, Shyamal Patel
|
👻
Ghosted
|
cs.DS
|
6 |
2 years ago |
| 464 |
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 |
| 465 |
Adaptive and oblivious statistical adversaries are equivalent
Guy Blanc, Gregory Valiant
|
👻
Ghosted
|
cs.LG
|
6 |
1 year ago |
| 466 |
Clique and cycle frequencies in a sparse random graph model with overlapping communities
Tommi Gröhn, Joona Karjalainen, Lasse Leskelä
|
👻
Ghosted
|
math.PR
|
5 |
6 years ago |
| 467 |
On the coercivity condition in the learning of interacting particle systems
Zhongyang Li, Fei Lu
|
👻
Ghosted
|
stat.ML
|
5 |
5 years ago |
| 468 |
A Characterization of Approximability for Biased CSPs
Suprovat Ghoshal, Euiwoong Lee
|
👻
Ghosted
|
cs.DS
|
5 |
4 years ago |
| 469 |
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
|
👻
Ghosted
|
cs.DS
|
5 |
3 years ago |
| 470 |
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg
|
👻
Ghosted
|
cs.DS
|
5 |
3 years ago |
| 471 |
(Noisy) Gap Cycle Counting Strikes Back: Random Order Streaming Lower Bounds for Connected Components and Beyond
Sepehr Assadi, Janani Sundaresan
|
👻
Ghosted
|
cs.DS
|
5 |
3 years ago |
| 472 |
Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
Xiao Mao
|
👻
Ghosted
|
cs.DS
|
5 |
3 years ago |
| 473 |
Optimization with pattern-avoiding input
Benjamin Aram Berendsohn, László Kozma, Michal Opler
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 474 |
Testing Closeness of Multivariate Distributions via Ramsey Theory
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 475 |
On the Communication Complexity of Approximate Pattern Matching
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 476 |
New Tools for Smoothed Analysis: Least Singular Value Bounds for Random Matrices with Dependent Entries
Aditya Bhaskara, Eric Evert, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 477 |
Supermodular Approximation of Norms and Applications
Thomas Kesselheim, Marco Molinaro, Sahil Singla
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 478 |
Phase Transitions via Complex Extensions of Markov Chains
Jingcheng Liu, Chunyang Wang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 479 |
Adaptive Approximation Schemes for Matching Queues
Alireza AmaniHamedani, Ali Aouad, Amin Saberi
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 480 |
Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
Siu-Wing Cheng, Haoqiang Huang, Shuo Zhang
|
👻
Ghosted
|
cs.CG
|
5 |
1 year ago |
| 481 |
Online Stochastic Matching with Unknown Arrival Order: Beating $0.5$ against the Online Optimum
Enze Sun, Zhihao Gavin Tang, Yifan Wang
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 482 |
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 483 |
Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
Hsien-Chih Chang, Jonathan Conroy, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 484 |
Single-Sample and Robust Online Resource Allocation
Rohan Ghuge, Sahil Singla, Yifan Wang
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 485 |
Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
Josh Alman, Kevin Rao
|
👻
Ghosted
|
cs.DS
|
4 |
3 years ago |
| 486 |
Better Trees for Santa Claus
Étienne Bamas, Lars Rohwedder
|
👻
Ghosted
|
cs.DS
|
4 |
3 years ago |
| 487 |
Stochastic Minimum Vertex Cover in General Graphs: a $3/2$-Approximation
Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab
|
👻
Ghosted
|
cs.DS
|
4 |
3 years ago |
| 488 |
Approximate Earth Mover's Distance in Truly-Subquadratic Time
Lorenzo Beretta, Aviad Rubinstein
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 489 |
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
Tuukka Korhonen, Marek Sokołowski
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 490 |
Robust recovery for stochastic block models, simplified and generalized
Sidhanth Mohanty, Prasad Raghavendra, David X. Wu
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 491 |
New Graph and Hypergraph Container Lemmas with Applications in Property Testing
Eric Blais, Cameron Seth
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 492 |
Prophet Inequalities with Cancellation Costs
Farbod Ekbatani, Rad Niazadeh, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 493 |
Rounding Large Independent Sets on Expanders
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 494 |
A $5/4$-Approximation for Two-Edge Connectivity
Miguel Bosch-Calvo, Mohit Garg, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 495 |
Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
Niv Buchbinder, Moran Feldman
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 496 |
The state hidden subgroup problem and an efficient algorithm for locating unentanglement
Adam Bouland, Tudor Giurgica-Tiron, John Wright
|
👻
Ghosted
|
quant-ph
|
4 |
1 year ago |
| 497 |
Dynamic O(arboricity) coloring in polylogarithmic worst-case time
Mohsen Ghaffari, Christoph Grunau
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 498 |
Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
Yuda Feng, Yang Hu, ... (+2 more)
|
👻
Ghosted
|
cs.GT
|
4 |
1 year ago |
| 499 |
On Differentially Private Linear Algebra
Haim Kaplan, Yishay Mansour, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 500 |
Omnipredicting Single-Index Models with Multi-Index Models
Lunjia Hu, Kevin Tian, Chutong Yang
|
👻
Ghosted
|
cs.LG
|
4 |
1 year ago |