🏛️ The Computational Complexity Crypt

🔮 🔮 The Ethereal

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

Karl Bringmann, Marvin Künnemann

cs.CC 🏛 FOCS 📚 259 cites 11 years ago

🔮 🔮 The Ethereal

An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Yi-Jun Chang, Tsvi Kopelowitz, Seth Pettie

cs.CC 🏛 FOCS 📚 177 cites 10 years ago

🔮 🔮 The Ethereal

The Parallelism Tradeoff: Limitations of Log-Precision Transformers

William Merrill, Ashish Sabharwal

cs.CC 🏛 TACL 📚 171 cites 3 years ago

🔮 🔮 The Ethereal

The Hardness of Approximation of Euclidean k-means

Pranjal Awasthi, Moses Charikar, ... (+2 more)

cs.CC 🏛 SoCG 📚 162 cites 11 years ago

🔮 🔮 The Ethereal

Slightly Superexponential Parameterized Problems

Daniel Lokshtanov, Daniel Marx, Saket Saurabh

cs.CC 🏛 SODA 📚 147 cites 7 years ago

🔮 🔮 The Ethereal

Complexity Theoretic Limitations on Learning Halfspaces

Amit Daniely

cs.CC 🏛 STOC 📚 146 cites 10 years ago

🔮 🔮 The Ethereal

The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness

Cristopher Moore

cs.CC 🏛 Bull. EATCS 📚 136 cites 9 years ago

🔮 🔮 The Ethereal

If the Current Clique Algorithms are Optimal, so is Valiant's Parser

Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams

cs.CC 🏛 FOCS 📚 129 cites 10 years ago

🔮 🔮 The Ethereal

Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made

Amir Abboud, Thomas Dueholm Hansen, ... (+2 more)

cs.CC 🏛 STOC 📚 125 cites 10 years ago

🔮 🔮 The Ethereal

Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure

Matthew Brennan, Guy Bresler, Wasim Huleihel

cs.CC 🏛 COLT 📚 120 cites 7 years ago

🔮 🔮 The Ethereal

Sum-of-squares lower bounds for planted clique

Raghu Meka, Aaron Potechin, Avi Wigderson

cs.CC 🏛 STOC 📚 119 cites 11 years ago

🔮 🔮 The Ethereal

Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors

Xin Li

cs.CC 🏛 ECCC 📚 117 cites 9 years ago

🔮 🔮 The Ethereal

Hardness of Approximate Nearest Neighbor Search

Aviad Rubinstein

cs.CC 🏛 STOC 📚 112 cites 8 years ago

🔮 🔮 The Ethereal

Which Regular Expression Patterns are Hard to Match?

Arturs Backurs, Piotr Indyk

cs.CC 🏛 FOCS 📚 109 cites 10 years ago

🔮 🔮 The Ethereal

Red-blue pebbling revisited: near optimal parallel matrix-matrix multiplication

Grzegorz Kwasniewski, Marko Kabić, ... (+4 more)

cs.CC 🏛 SC 📚 106 cites 6 years ago

🔮 🔮 The Ethereal

When can Graph Hyperbolicity be computed in Linear Time?

Till Fluschnik, Christian Komusiewicz, ... (+4 more)

cs.CC 🏛 Algorithmica 📚 105 cites 9 years ago

🔮 🔮 The Ethereal

Algorithmic and optimization aspects of Brascamp-Lieb inequalities, via Operator Scaling

Ankit Garg, Leonid Gurvits, ... (+2 more)

cs.CC 🏛 Geometric and Functional Analysis 📚 105 cites 9 years ago

🔮 🔮 The Ethereal

APX-Hardness of Maximizing Nash Social Welfare with Indivisible Items

Euiwoong Lee

cs.CC 🏛 IPL 📚 105 cites 10 years ago

🔮 🔮 The Ethereal

On Unbalanced Optimal Transport: An Analysis of Sinkhorn Algorithm

Khiem Pham, Khang Le, ... (+3 more)

cs.CC 🏛 ICML 📚 98 cites 6 years ago

🔮 🔮 The Ethereal

How to refute a random CSP

Sarah R. Allen, Ryan O'Donnell, David Witmer

cs.CC 🏛 FOCS 📚 95 cites 10 years ago

🔮 🔮 The Ethereal

Bipartite Perfect Matching is in quasi-NC

Stephen A. Fenner, Rohit Gurjar, Thomas Thierauf

cs.CC 🏛 STOC 📚 91 cites 10 years ago

🔮 🔮 The Ethereal

The Complexity of Gradient Descent: CLS = PPAD $\cap$ PLS

John Fearnley, Paul W. Goldberg, ... (+2 more)

cs.CC 🏛 STOC 📚 90 cites 5 years ago

🔮 🔮 The Ethereal

Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

Yash Deshpande, Andrea Montanari

cs.CC 🏛 COLT 📚 85 cites 11 years ago

🔮 🔮 The Ethereal

DEEP-FRI: Sampling outside the box improves soundness

Eli Ben-Sasson, Lior Goldberg, ... (+2 more)

cs.CC 🏛 IACR ePrint 📚 84 cites 7 years ago