research
∙
06/19/2023
Quasipolynomiality of the Smallest Missing Induced Subgraph
We study the problem of finding the smallest graph that does not occur a...
share
research
∙
12/10/2021
How Compression and Approximation Affect Efficiency in String Distance Measures
Real-world data often comes in compressed form. Analyzing compressed dat...
research
∙
09/30/2020
Monochromatic Triangles, Intermediate Matrix Products, and Convolutions
The most studied linear algebraic operation, matrix multiplication, has ...
research
∙
08/14/2020
New Techniques for Proving Fine-Grained Average-Case Hardness
The recent emergence of fine-grained cryptography strongly motivates dev...
research
∙
03/25/2019
Faster Random k-CNF Satisfiability
We describe an algorithm to solve the problem of Boolean CNF-Satisfiabil...
research
∙
12/21/2017
Tight Hardness for Shortest Cycles and Paths in Sparse Graphs
Fine-grained reductions have established equivalences between many core ...
research
∙
11/21/2017
