| 1 |
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Karl Bringmann, Marvin Künnemann
|
🔮
The Ethereal
|
cs.CC
|
259 |
11 years ago |
| 2 |
An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie
|
🔮
The Ethereal
|
cs.CC
|
177 |
10 years ago |
| 3 |
If the Current Clique Algorithms are Optimal, so is Valiant's Parser
Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
129 |
10 years ago |
| 4 |
Which Regular Expression Patterns are Hard to Match?
Arturs Backurs, Piotr Indyk
|
🔮
The Ethereal
|
cs.CC
|
109 |
10 years ago |
| 5 |
How to refute a random CSP
Sarah R. Allen, Ryan O'Donnell, David Witmer
|
🔮
The Ethereal
|
cs.CC
|
95 |
10 years ago |
| 6 |
Three-Source Extractors for Polylogarithmic Min-Entropy
Xin Li
|
🔮
The Ethereal
|
cs.CC
|
68 |
11 years ago |
| 7 |
Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
Josh Alman, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
53 |
7 years ago |
| 8 |
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 |
8 years ago |
| 9 |
Isomorphism Testing for Graphs of Bounded Rank Width
Martin Grohe, Pascal Schweitzer
|
🔮
The Ethereal
|
cs.DM
|
47 |
10 years ago |
| 10 |
On the Quantitative Hardness of CVP
Huck Bennett, Alexander Golovnev, Noah Stephens-Davidowitz
|
🔮
The Ethereal
|
cs.CC
|
42 |
8 years ago |
| 11 |
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 |
| 12 |
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 |
| 13 |
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 |
| 14 |
Uniform generation of random regular graphs
Pu Gao, Nicholas Wormald
|
🔮
The Ethereal
|
math.CO
|
40 |
10 years ago |
| 15 |
Near-optimal bounds on bounded-round quantum communication complexity of disjointness
Mark Braverman, Ankit Garg, ... (+3 more)
|
🔮
The Ethereal
|
cs.CC
|
35 |
10 years ago |
| 16 |
Non-Malleable Codes for Small-Depth Circuits
Marshall Ball, Dana Dachman-Soled, ... (+3 more)
|
🔮
The Ethereal
|
cs.CC
|
35 |
8 years ago |
| 17 |
PPP-Completeness with Connections to Cryptography
Katerina Sotiraki, Manolis Zampetakis, Giorgos Zirdelis
|
🔮
The Ethereal
|
cs.CC
|
35 |
7 years ago |
| 18 |
A Holant Dichotomy: Is the FKT Algorithm Universal?
Jin-Yi Cai, Zhiguo Fu, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
32 |
10 years ago |
| 19 |
Two Source Extractors for Asymptotically Optimal Entropy, and (Many) More
Xin Li
|
🔮
The Ethereal
|
cs.CC
|
32 |
3 years ago |
| 20 |
Sublinear Algorithms for Gap Edit Distance
Elazar Goldenberg, Robert Krauthgamer, Barna Saha
|
🔮
The Ethereal
|
cs.CC
|
31 |
6 years ago |
| 21 |
Flip-width: Cops and Robber on dense graphs
Szymon Toruńczyk
|
🔮
The Ethereal
|
math.CO
|
31 |
3 years ago |
| 22 |
Fast uniform generation of random graphs with given degree sequences
Andrii Arman, Pu Gao, Nicholas Wormald
|
🔮
The Ethereal
|
math.CO
|
29 |
6 years ago |
| 23 |
New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
28 |
5 years ago |
| 24 |
Learning sums of powers of low-degree polynomials in the non-degenerate case
Ankit Garg, Neeraj Kayal, Chandan Saha
|
🔮
The Ethereal
|
cs.CC
|
27 |
5 years ago |
| 25 |
Simply Exponential Approximation of the Permanent of Positive Semidefinite Matrices
Nima Anari, Leonid Gurvits, ... (+2 more)
|
🔮
The Ethereal
|
math.CO
|
25 |
8 years ago |
| 26 |
Junta correlation is testable
Anindya De, Elchanan Mossel, Joe Neeman
|
🔮
The Ethereal
|
cs.CC
|
22 |
6 years ago |
| 27 |
Hardness Results for Structured Linear Systems
Rasmus Kyng, Peng Zhang
|
🔮
The Ethereal
|
cs.CC
|
21 |
8 years ago |
| 28 |
Noisy population recovery in polynomial time
Anindya De, Michael Saks, Sijian Tang
|
🔮
The Ethereal
|
cs.CC
|
18 |
10 years ago |
| 29 |
Polynomial-Time Pseudodeterministic Construction of Primes
Lijie Chen, Zhenjian Lu, ... (+3 more)
|
🔮
The Ethereal
|
cs.CC
|
17 |
2 years ago |
| 30 |
Finding forbidden minors in sublinear time: a $n^{1/2+o(1)}$-query one-sided tester for minor closed properties on bounded degree graphs
Akash Kumar, C. Seshadhri, Andrew Stolman
|
🔮
The Ethereal
|
cs.DM
|
15 |
7 years ago |
| 31 |
Explicit near-fully X-Ramanujan graphs
Ryan O'Donnell, Xinyu Wu
|
🔮
The Ethereal
|
math.CO
|
15 |
5 years ago |
| 32 |
Certified Hardness vs. Randomness for Log-Space
Edward Pyne, Ran Raz, Wei Zhan
|
🔮
The Ethereal
|
cs.CC
|
15 |
3 years ago |
| 33 |
Killing a Vortex
Dimitrios M. Thilikos, Sebastian Wiederrecht
|
🔮
The Ethereal
|
math.CO
|
13 |
3 years ago |
| 34 |
Induced Cycles and Paths Are Harder Than You Think
Mina Dalirrooyfard, Virginia Vassilevska Williams
|
🔮
The Ethereal
|
cs.CC
|
13 |
3 years ago |
| 35 |
Random $k$-out subgraph leaves only $O(n/k)$ inter-component edges
Jacob Holm, Valerie King, ... (+3 more)
|
🔮
The Ethereal
|
cs.DM
|
12 |
6 years ago |
| 36 |
Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements
Martin Grohe, Moritz Lichter, ... (+2 more)
|
🔮
The Ethereal
|
cs.DM
|
12 |
2 years ago |
| 37 |
Linear-Time and Efficient Distributed Algorithms for List Coloring Graphs on Surfaces
Luke Postle
|
🔮
The Ethereal
|
math.CO
|
11 |
6 years ago |
| 38 |
Linear Hashing with $\ell_\infty$ guarantees and two-sided Kakeya bounds
Manik Dhar, Zeev Dvir
|
🔮
The Ethereal
|
math.CO
|
10 |
3 years ago |
| 39 |
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, ... (+2 more)
|
🔮
The Ethereal
|
cs.CC
|
10 |
3 years ago |
| 40 |
Improved Extractors for Small-Space Sources
Eshan Chattopadhyay, Jesse Goodman
|
🔮
The Ethereal
|
cs.CC
|
9 |
5 years ago |
| 41 |
Properly Learning Decision Trees with Queries Is NP-Hard
Caleb Koch, Carmen Strassle, Li-Yang Tan
|
🔮
The Ethereal
|
cs.CC
|
9 |
2 years ago |
| 42 |
Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
Dmitriy Kunisky, Xifan Yu
|
🔮
The Ethereal
|
cs.CC
|
8 |
1 year ago |
| 43 |
Explicit Lossless Vertex Expanders
Jun-Ting Hsieh, Alexander Lubotzky, ... (+3 more)
|
🔮
The Ethereal
|
math.CO
|
8 |
11 months ago |
| 44 |
A characterization of testable hypergraph properties
Felix Joos, Jaehoon Kim, ... (+2 more)
|
🔮
The Ethereal
|
math.CO
|
7 |
8 years ago |
| 45 |
Why we couldn't prove SETH hardness of the Closest Vector Problem for even norms!
Divesh Aggarwal, Rajendra Kumar
|
🔮
The Ethereal
|
cs.CC
|
7 |
3 years ago |
| 46 |
Streaming Lower Bounds and Asymmetric Set-Disjointness
Shachar Lovett, Jiapeng Zhang
|
🔮
The Ethereal
|
cs.CC
|
7 |
3 years ago |
| 47 |
Traversing combinatorial 0/1-polytopes via optimization
Arturo Merino, Torsten Mütze
|
🔮
The Ethereal
|
cs.DM
|
7 |
2 years ago |
| 48 |
Bipartite Matching is in Catalytic Logspace
Aryan Agarwala, Ian Mertz
|
🔮
The Ethereal
|
cs.CC
|
7 |
11 months ago |
| 49 |
The Salesman's Improved Paths: 3/2+1/34 Integrality Gap and Approximation Ratio
András Sebő, Anke van Zuylen
|
🔮
The Ethereal
|
cs.DM
|
6 |
9 years ago |
| 50 |
The complexity of general-valued CSPs seen from the other side
Clement Carbonnel, Miguel Romero, Stanislav Zivny
|
🔮
The Ethereal
|
cs.CC
|
6 |
8 years ago |