| 501 |
Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles
Noah Golowich, Ankur Moitra, Dhruv Rohatgi
|
👻
Ghosted
|
cs.LG
|
6 |
2 years ago |
| 502 |
Sampling Proper Colorings on Line Graphs Using $(1+o(1))Δ$ Colors
Yulin Wang, Chihao Zhang, Zihan Zhang
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 503 |
Lifting uniform learners via distributional decomposition
Guy Blanc, Jane Lange, ... (+2 more)
|
👻
Ghosted
|
stat.ML
|
6 |
3 years ago |
| 504 |
Finding a Small Vertex Cut on Distributed Networks
Yonggang Jiang, Sagnik Mukhopadhyay
|
👻
Ghosted
|
cs.DS
|
6 |
3 years ago |
| 505 |
Walking Randomly, Massively, and Efficiently
Jakub Łącki, Slobodan Mitrović, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
6 |
7 years ago |
| 506 |
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
Julia Chuzhoy, Zihan Tan
|
👻
Ghosted
|
cs.DS
|
6 |
4 years ago |
| 507 |
The Query Complexity of Certification
Guy Blanc, Caleb Koch, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
6 |
4 years ago |
| 508 |
Single-Sample and Robust Online Resource Allocation
Rohan Ghuge, Sahil Singla, Yifan Wang
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 509 |
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 |
| 510 |
Deterministic Vertex Connectivity via Common-Neighborhood Clustering and Pseudorandomness
Yonggang Jiang, Chaitanya Nalam, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 511 |
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 |
| 512 |
Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
Siu-Wing Cheng, Haoqiang Huang, Shuo Zhang
|
👻
Ghosted
|
cs.CG
|
5 |
1 year ago |
| 513 |
Adaptive Approximation Schemes for Matching Queues
Alireza AmaniHamedani, Ali Aouad, Amin Saberi
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 514 |
Explicit Two-Sided Vertex Expanders Beyond the Spectral Barrier
Jun-Ting Hsieh, Ting-Chun Lin, ... (+3 more)
|
🔮
The Ethereal
|
math.CO
|
5 |
1 year ago |
| 515 |
Phase Transitions via Complex Extensions of Markov Chains
Jingcheng Liu, Chunyang Wang, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
5 |
1 year ago |
| 516 |
Supermodular Approximation of Norms and Applications
Thomas Kesselheim, Marco Molinaro, Sahil Singla
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 517 |
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 |
| 518 |
On the Communication Complexity of Approximate Pattern Matching
Tomasz Kociumaka, Jakob Nogler, Philip Wellnitz
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 519 |
Testing Closeness of Multivariate Distributions via Ramsey Theory
Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 520 |
Optimization with pattern-avoiding input
Benjamin Aram Berendsohn, László Kozma, Michal Opler
|
👻
Ghosted
|
cs.DS
|
5 |
2 years ago |
| 521 |
Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
Xiao Mao
|
👻
Ghosted
|
cs.DS
|
5 |
3 years ago |
| 522 |
(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 |
| 523 |
On the coercivity condition in the learning of interacting particle systems
Zhongyang Li, Fei Lu
|
👻
Ghosted
|
stat.ML
|
5 |
5 years ago |
| 524 |
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 |
| 525 |
Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
Kiril Bangachev, Guy Bresler, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
5 |
1 year ago |
| 526 |
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg
|
👻
Ghosted
|
cs.DS
|
5 |
3 years ago |
| 527 |
A PTAS for Minimizing Weighted Flow Time on a Single Machine
Alexander Armbruster, Lars Rohwedder, Andreas Wiese
|
👻
Ghosted
|
cs.DS
|
5 |
4 years ago |
| 528 |
A Characterization of Approximability for Biased CSPs
Suprovat Ghoshal, Euiwoong Lee
|
👻
Ghosted
|
cs.DS
|
5 |
4 years ago |
| 529 |
Near-optimal Linear Sketches and Fully-Dynamic Algorithms for Hypergraph Spectral Sparsification
Sanjeev Khanna, Huan Li, Aaron Putterman
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 530 |
Constant Degree Networks for Almost-Everywhere Reliable Transmission
Mitali Bafna, Dor Minzer
|
👻
Ghosted
|
cs.DC
|
4 |
1 year ago |
| 531 |
SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More
Ilias Diakonikolas, Samuel B. Hopkins, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 532 |
Omnipredicting Single-Index Models with Multi-Index Models
Lunjia Hu, Kevin Tian, Chutong Yang
|
👻
Ghosted
|
cs.LG
|
4 |
1 year ago |
| 533 |
On Differentially Private Linear Algebra
Haim Kaplan, Yishay Mansour, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 534 |
Constant Approximation for Weighted Nash Social Welfare with Submodular Valuations
Yuda Feng, Yang Hu, ... (+2 more)
|
👻
Ghosted
|
cs.GT
|
4 |
1 year ago |
| 535 |
Dynamic O(arboricity) coloring in polylogarithmic worst-case time
Mohsen Ghaffari, Christoph Grunau
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 536 |
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 |
| 537 |
Smoothed analysis for graph isomorphism
Michael Anastos, Matthew Kwan, Benjamin Moore
|
🔮
The Ethereal
|
math.CO
|
4 |
1 year ago |
| 538 |
Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
Niv Buchbinder, Moran Feldman
|
👻
Ghosted
|
cs.DS
|
4 |
1 year ago |
| 539 |
A $5/4$-Approximation for Two-Edge Connectivity
Miguel Bosch-Calvo, Mohit Garg, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 540 |
Rounding Large Independent Sets on Expanders
Mitali Bafna, Jun-Ting Hsieh, Pravesh K. Kothari
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 541 |
Prophet Inequalities with Cancellation Costs
Farbod Ekbatani, Rad Niazadeh, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 542 |
New Graph and Hypergraph Container Lemmas with Applications in Property Testing
Eric Blais, Cameron Seth
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 543 |
Robust recovery for stochastic block models, simplified and generalized
Sidhanth Mohanty, Prasad Raghavendra, David X. Wu
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 544 |
Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
Tuukka Korhonen, Marek Sokołowski
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 545 |
Approximate Earth Mover's Distance in Truly-Subquadratic Time
Lorenzo Beretta, Aviad Rubinstein
|
👻
Ghosted
|
cs.DS
|
4 |
2 years ago |
| 546 |
Stochastic Minimum Vertex Cover in General Graphs: a $3/2$-Approximation
Mahsa Derakhshan, Naveen Durvasula, Nika Haghtalab
|
👻
Ghosted
|
cs.DS
|
4 |
3 years ago |
| 547 |
Better Trees for Santa Claus
Étienne Bamas, Lars Rohwedder
|
👻
Ghosted
|
cs.DS
|
4 |
3 years ago |
| 548 |
Faster Walsh-Hadamard and Discrete Fourier Transforms From Matrix Non-Rigidity
Josh Alman, Kevin Rao
|
👻
Ghosted
|
cs.DS
|
4 |
3 years ago |
| 549 |
Correlation Clustering and (De)Sparsification: Graph Sketches Can Match Classical Algorithms
Sepehr Assadi, Sanjeev Khanna, Aaron Putterman
|
👻
Ghosted
|
cs.DS
|
3 |
1 year ago |
| 550 |
Stochastic Matching via In-n-Out Local Computation Algorithms
Amir Azarmehr, Soheil Behnezhad, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
3 |
1 year ago |