| 101 |
An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
Paul Dütting, Thomas Kesselheim, Brendan Lucier
|
👻
Ghosted
|
cs.GT
|
69 |
6 years ago |
| 102 |
The Role of Interactivity in Local Differential Privacy
Matthew Joseph, Jieming Mao, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
69 |
7 years ago |
| 103 |
Adjacency Labelling for Planar Graphs (and Beyond)
Vida Dujmović, Louis Esperet, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
68 |
6 years ago |
| 104 |
A Faster Distributed Single-Source Shortest Paths Algorithm
Sebastian Forster, Danupon Nanongkai
|
👻
Ghosted
|
cs.DC
|
68 |
8 years ago |
| 105 |
Three-Source Extractors for Polylogarithmic Min-Entropy
Xin Li
|
🔮
The Ethereal
|
cs.CC
|
68 |
11 years ago |
| 106 |
Average-case reconstruction for the deletion channel: subpolynomially many traces suffice
Yuval Peres, Alex Zhai
|
👻
Ghosted
|
cs.DS
|
67 |
8 years ago |
| 107 |
Oracle-Efficient Online Learning and Auction Design
Miroslav Dudík, Nika Haghtalab, ... (+4 more)
|
👻
Ghosted
|
cs.LG
|
67 |
9 years ago |
| 108 |
Localization Schemes: A Framework for Proving Mixing Bounds for Markov Chains
Yuansi Chen, Ronen Eldan
|
👻
Ghosted
|
math.PR
|
67 |
4 years ago |
| 109 |
Faster Algorithms for Computing the Stationary Distribution, Simulating Random Walks, and More
Michael B. Cohen, Jon Kelner, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
66 |
9 years ago |
| 110 |
An Algorithm for Komlós Conjecture Matching Banaszczyk's bound
Nikhil Bansal, Daniel Dadush, Shashwat Garg
|
👻
Ghosted
|
cs.DS
|
66 |
9 years ago |
| 111 |
Exponentially Faster Massively Parallel Maximal Matching
Soheil Behnezhad, MohammadTaghi Hajiaghayi, David G. Harris
|
👻
Ghosted
|
cs.DS
|
64 |
7 years ago |
| 112 |
Collaborative Learning with Limited Interaction: Tight Bounds for Distributed Exploration in Multi-Armed Bandits
Chao Tao, Qin Zhang, Yuan Zhou
|
👻
Ghosted
|
cs.LG
|
64 |
7 years ago |
| 113 |
Query-optimal estimation of unitary channels in diamond distance
Jeongwan Haah, Robin Kothari, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
61 |
3 years ago |
| 114 |
Entanglement is Necessary for Optimal Quantum Property Testing
Sebastien Bubeck, Sitan Chen, Jerry Li
|
👻
Ghosted
|
quant-ph
|
61 |
6 years ago |
| 115 |
Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices
Cameron Musco, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
61 |
9 years ago |
| 116 |
Near Optimal Linear Algebra in the Online and Sliding Window Models
Vladimir Braverman, Petros Drineas, ... (+5 more)
|
👻
Ghosted
|
cs.DS
|
58 |
7 years ago |
| 117 |
Edit Distance: Sketching, Streaming and Document Exchange
Djamal Belazzougui, Qin Zhang
|
👻
Ghosted
|
cs.DS
|
58 |
9 years ago |
| 118 |
High-Temperature Gibbs States are Unentangled and Efficiently Preparable
Ainesh Bakshi, Allen Liu, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
57 |
2 years ago |
| 119 |
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, ... (+5 more)
|
👻
Ghosted
|
cs.DS
|
57 |
7 years ago |
| 120 |
Bloom Filters, Adaptivity, and the Dictionary Problem
Michael A. Bender, Martin Farach-Colton, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
57 |
8 years ago |
| 121 |
Correlation Clustering with Sherali-Adams
Vincent Cohen-Addad, Euiwoong Lee, Alantha Newman
|
👻
Ghosted
|
cs.DS
|
57 |
3 years ago |
| 122 |
Truly Optimal Euclidean Spanners
Hung Le, Shay Solomon
|
👻
Ghosted
|
cs.CG
|
56 |
6 years ago |
| 123 |
Efficient algorithms for tensor scaling, quantum marginals and moment polytopes
Peter Bürgisser, Cole Franks, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
56 |
8 years ago |
| 124 |
Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
Shi Li
|
👻
Ghosted
|
cs.DS
|
56 |
8 years ago |
| 125 |
Zero-knowledge proof systems for QMA
Anne Broadbent, Zhengfeng Ji, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
56 |
10 years ago |
| 126 |
A Dichotomy for Regular Expression Membership Testing
Karl Bringmann, Allan Grønlund, Kasper Green Larsen
|
👻
Ghosted
|
cs.DS
|
56 |
9 years ago |
| 127 |
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
|
👻
Ghosted
|
cs.DS
|
55 |
5 years ago |
| 128 |
Smoothing the gap between NP and ER
Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
|
👻
Ghosted
|
cs.CG
|
55 |
6 years ago |
| 129 |
Mixture Selection, Mechanism Design, and Signaling
Yu Cheng, Ho Yee Cheung, ... (+4 more)
|
👻
Ghosted
|
cs.GT
|
55 |
10 years ago |
| 130 |
Negative-Weight Single-Source Shortest Paths in Near-linear Time
Aaron Bernstein, Danupon Nanongkai, Christian Wulff-Nilsen
|
👻
Ghosted
|
cs.DS
|
55 |
4 years ago |
| 131 |
Faster Approximate Pattern Matching: A Unified Approach
Panagiotis Charalampopoulos, Tomasz Kociumaka, Philip Wellnitz
|
👻
Ghosted
|
cs.DS
|
54 |
6 years ago |
| 132 |
Near-Optimal Massively Parallel Graph Connectivity
Soheil Behnezhad, Laxman Dhulipala, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
54 |
6 years ago |
| 133 |
Efficient Statistics, in High Dimensions, from Truncated Samples
Constantinos Daskalakis, Themis Gouleakis, ... (+2 more)
|
👻
Ghosted
|
math.ST
|
54 |
7 years ago |
| 134 |
Ramanujan Graphs in Polynomial Time
Michael B. Cohen
|
👻
Ghosted
|
cs.DS
|
54 |
10 years ago |
| 135 |
Parallel Reachability in Almost Linear Work and Square Root Depth
Arun Jambulapati, Yang P. Liu, Aaron Sidford
|
👻
Ghosted
|
cs.DS
|
53 |
6 years ago |
| 136 |
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Josh Alman, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
53 |
7 years ago |
| 137 |
Distributed local approximation algorithms for maximum matching in graphs and hypergraphs
David G. Harris
|
👻
Ghosted
|
cs.DS
|
52 |
7 years ago |
| 138 |
On the Local Structure of Stable Clustering Instances
Vincent Cohen-Addad, Chris Schwiegelshohn
|
👻
Ghosted
|
cs.DS
|
52 |
9 years ago |
| 139 |
Faster high-accuracy log-concave sampling via algorithmic warm starts
Jason M. Altschuler, Sinho Chewi
|
👻
Ghosted
|
math.ST
|
51 |
3 years ago |
| 140 |
Approximating Geometric Knapsack via L-packings
Waldo Gálvez, Fabrizio Grandoni, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
51 |
8 years ago |
| 141 |
The Subspace Flatness Conjecture and Faster Integer Programming
Victor Reis, Thomas Rothvoss
|
👻
Ghosted
|
math.OC
|
50 |
3 years ago |
| 142 |
Contextual Search via Intrinsic Volumes
Renato Paes Leme, Jon Schneider
|
👻
Ghosted
|
cs.DS
|
50 |
8 years ago |
| 143 |
Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions
Ilias Diakonikolas, Daniel M. Kane, Vladimir Nikishkin
|
👻
Ghosted
|
cs.DS
|
50 |
10 years ago |
| 144 |
Sensitive Distance and Reachability Oracles for Large Batch Updates
Jan van den Brand, Thatchaphol Saranurak
|
👻
Ghosted
|
cs.DS
|
49 |
6 years ago |
| 145 |
Fourier-sparse interpolation without a frequency gap
Xue Chen, Daniel M. Kane, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
49 |
9 years ago |
| 146 |
Tight Quantum Time-Space Tradeoffs for Function Inversion
Kai-Min Chung, Siyao Guo, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
48 |
5 years ago |
| 147 |
Edit Distance in Near-Linear Time: it's a Constant Factor
Alexandr Andoni, Negev Shekel Nosatzki
|
👻
Ghosted
|
cs.DS
|
48 |
5 years ago |
| 148 |
Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams
Michael Kapralov, Jelani Nelson, ... (+4 more)
|
🔮
The Ethereal
|
cs.CC
|
48 |
9 years ago |
| 149 |
Optimal induced universal graphs and adjacency labeling for trees
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen
|
👻
Ghosted
|
cs.DS
|
48 |
11 years ago |
| 150 |
Approximating Constraint Satisfaction Problems on High-Dimensional Expanders
Vedat Levi Alev, Fernando Granha Jeronimo, Madhur Tulsiani
|
👻
Ghosted
|
cs.DS
|
47 |
6 years ago |