| 151 |
Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation
Christian Borgs, Jennifer Chayes, ... (+2 more)
|
👻
Ghosted
|
math.ST
|
47 |
7 years ago |
| 152 |
Random Order Contention Resolution Schemes
Marek Adamczyk, Michał Włodarczyk
|
👻
Ghosted
|
cs.DS
|
47 |
8 years ago |
| 153 |
Isomorphism Testing for Graphs of Bounded Rank Width
Martin Grohe, Pascal Schweitzer
|
🔮
The Ethereal
|
cs.DM
|
47 |
11 years ago |
| 154 |
Simple constructions of linear-depth t-designs and pseudorandom unitaries
Tony Metger, Alexander Poremba, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
47 |
2 years ago |
| 155 |
Adwords in a Panorama
Zhiyi Huang, Qiankun Zhang, Yuhao Zhang
|
👻
Ghosted
|
cs.DS
|
46 |
5 years ago |
| 156 |
Circulation Control for Faster Minimum Cost Flow in Unit-Capacity Graphs
Kyriakos Axiotis, Aleksander Mądry, Adrian Vladu
|
👻
Ghosted
|
cs.DS
|
46 |
6 years ago |
| 157 |
Distributed Lower Bounds for Ruling Sets
Alkida Balliu, Sebastian Brandt, Dennis Olivetti
|
👻
Ghosted
|
cs.DC
|
46 |
6 years ago |
| 158 |
Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
Joao Basso, David Gamarnik, ... (+2 more)
|
👻
Ghosted
|
quant-ph
|
46 |
4 years ago |
| 159 |
Perfect $L_p$ Sampling in a Data Stream
Rajesh Jayaram, David P. Woodruff
|
👻
Ghosted
|
cs.DS
|
45 |
7 years ago |
| 160 |
Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds
Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak
|
👻
Ghosted
|
cs.DC
|
45 |
8 years ago |
| 161 |
Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers
Li Chen, Gramoz Goranci, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
44 |
6 years ago |
| 162 |
Continuous LWE is as Hard as LWE & Applications to Learning Gaussian Mixtures
Aparna Gupte, Neekon Vafa, Vinod Vaikuntanathan
|
👻
Ghosted
|
cs.CR
|
44 |
4 years ago |
| 163 |
The Power of Uniform Sampling for Coresets
Vladimir Braverman, Vincent Cohen-Addad, ... (+5 more)
|
👻
Ghosted
|
cs.DS
|
44 |
3 years ago |
| 164 |
Multi-Pass Graph Streaming Lower Bounds for Cycle Counting, MAX-CUT, Matching Size, and Other Problems
Sepehr Assadi, Gillat Kol, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
43 |
5 years ago |
| 165 |
Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
Jan van den Brand, Danupon Nanongkai
|
👻
Ghosted
|
cs.DS
|
43 |
6 years ago |
| 166 |
Fast and Compact Exact Distance Oracle for Planar Graphs
Vincent Cohen-Addad, Søren Dahlgaard, Christian Wulff-Nilsen
|
👻
Ghosted
|
cs.DS
|
43 |
9 years ago |
| 167 |
Universal Optimality of Dijkstra via Beyond-Worst-Case Heaps
Bernhard Haeupler, Richard Hladík, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
42 |
2 years ago |
| 168 |
QMA-hardness of Consistency of Local Density Matrices with Applications to Quantum Zero-Knowledge
Anne Broadbent, Alex B. Grilo
|
👻
Ghosted
|
quant-ph
|
42 |
6 years ago |
| 169 |
Improved Truthful Mechanisms for Combinatorial Auctions with Submodular Bidders
Sepehr Assadi, Sahil Singla
|
👻
Ghosted
|
cs.GT
|
42 |
6 years ago |
| 170 |
Coded trace reconstruction in a constant number of traces
Joshua Brakensiek, Ray Li, Bruce Spang
|
👻
Ghosted
|
cs.IT
|
42 |
6 years ago |
| 171 |
The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs
Enric Boix-Adserà, Matthew Brennan, Guy Bresler
|
🔮
The Ethereal
|
cs.CC
|
42 |
7 years ago |
| 172 |
Fusible HSTs and the randomized k-server conjecture
James R. Lee
|
👻
Ghosted
|
cs.DS
|
42 |
8 years ago |
| 173 |
On the Quantitative Hardness of CVP
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
|
🔮
The Ethereal
|
cs.CC
|
42 |
9 years ago |
| 174 |
A Robust Sparse Fourier Transform in the Continuous Setting
Eric Price, Zhao Song
|
👻
Ghosted
|
cs.DS
|
42 |
9 years ago |
| 175 |
The Submodular Secretary Problem Goes Linear
Moran Feldman, Rico Zenklusen
|
👻
Ghosted
|
cs.DS
|
42 |
10 years ago |
| 176 |
Algorithms and Barriers in the Symmetric Binary Perceptron Model
David Gamarnik, Eren C. Kızıldağ, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
42 |
4 years ago |
| 177 |
Pandora's Box with Correlations: Learning and Approximation
Shuchi Chawla, Evangelia Gergatsouli, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
41 |
6 years ago |
| 178 |
New Notions and Constructions of Sparsification for Graphs and Hypergraphs
Nikhil Bansal, Ola Svensson, Luca Trevisan
|
👻
Ghosted
|
cs.DS
|
41 |
7 years ago |
| 179 |
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
Amir Abboud, Arturs Backurs, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
41 |
8 years ago |
| 180 |
Improved decoding of Folded Reed-Solomon and Multiplicity Codes
Swastik Kopparty, Noga Ron-Zewi, ... (+2 more)
|
👻
Ghosted
|
cs.IT
|
41 |
8 years ago |
| 181 |
Generalized Uniformity Testing
Tuğkan Batu, Clément L. Canonne
|
👻
Ghosted
|
cs.DS
|
41 |
8 years ago |
| 182 |
Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols
Eshan Chattopadhyay, Xin Li
|
👻
Ghosted
|
cs.CR
|
41 |
10 years ago |
| 183 |
Certifying almost all quantum states with few single-qubit measurements
Hsin-Yuan Huang, John Preskill, Mehdi Soleimanifar
|
👻
Ghosted
|
quant-ph
|
40 |
2 years ago |
| 184 |
Learning Deep ReLU Networks Is Fixed-Parameter Tractable
Sitan Chen, Adam R. Klivans, Raghu Meka
|
👻
Ghosted
|
cs.LG
|
40 |
5 years ago |
| 185 |
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
Simon Apers, Ronald de Wolf
|
👻
Ghosted
|
quant-ph
|
40 |
6 years ago |
| 186 |
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Shiri Chechik, Tianyi Zhang
|
👻
Ghosted
|
cs.DS
|
40 |
6 years ago |
| 187 |
Beyond trace reconstruction: Population recovery from the deletion channel
Frank Ban, Xi Chen, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
40 |
7 years ago |
| 188 |
Faster Exact and Approximate Algorithms for $k$-Cut
Anupam Gupta, Euiwoong Lee, Jason Li
|
👻
Ghosted
|
cs.DS
|
40 |
7 years ago |
| 189 |
Uniform generation of random regular graphs
Pu Gao, Nicholas Wormald
|
🔮
The Ethereal
|
math.CO
|
40 |
10 years ago |
| 190 |
Differential Privacy from Locally Adjustable Graph Algorithms: $k$-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
Laxman Dhulipala, Quanquan C. Liu, ... (+4 more)
|
👻
Ghosted
|
cs.DS
|
40 |
3 years ago |
| 191 |
Kernel Density Estimation through Density Constrained Near Neighbor Search
Moses Charikar, Michael Kapralov, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
39 |
5 years ago |
| 192 |
Deterministic Distributed Expander Decomposition and Routing with Applications in Distributed Derandomization
Yi-Jun Chang, Thatchaphol Saranurak
|
👻
Ghosted
|
cs.DS
|
39 |
5 years ago |
| 193 |
Pattern-avoiding access in binary search trees
Parinya Chalermsook, Mayank Goswami, ... (+3 more)
|
👻
Ghosted
|
cs.DS
|
39 |
10 years ago |
| 194 |
Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets
Zeyu Guo, Zihan Zhang
|
👻
Ghosted
|
cs.IT
|
38 |
3 years ago |
| 195 |
On Light Spanners, Low-treewidth Embeddings and Efficient Traversing in Minor-free Graphs
Vincent Cohen-Addad, Arnold Filtser, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
38 |
5 years ago |
| 196 |
Tight Bounds for Online Edge Coloring
Ilan Reuven Cohen, Binghui Peng, David Wajc
|
👻
Ghosted
|
cs.DS
|
37 |
7 years ago |
| 197 |
LDPC Codes Achieve List Decoding Capacity
Jonathan Mosheiff, Nicolas Resch, ... (+3 more)
|
👻
Ghosted
|
cs.IT
|
37 |
6 years ago |
| 198 |
Handling Correlated Rounding Error via Preclustering: A 1.73-approximation for Correlation Clustering
Vincent Cohen-Addad, Euiwoong Lee, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
36 |
2 years ago |
| 199 |
Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contamination
Sitan Chen, Frederic Koehler, ... (+2 more)
|
👻
Ghosted
|
cs.LG
|
36 |
5 years ago |
| 200 |
Coordinate Methods for Matrix Games
Yair Carmon, Yujia Jin, ... (+2 more)
|
👻
Ghosted
|
cs.DS
|
36 |
5 years ago |