research
∙
08/08/2023
0-1 Knapsack in Nearly Quadratic Time
We study pseudo-polynomial time algorithms for the fundamental 0-1 Knaps...
share
research
∙
07/18/2023
Solving Knapsack with Small Items via L0-Proximity
We study pseudo-polynomial time algorithms for the fundamental 0-1 Knaps...
research
∙
05/03/2023
An Efficient Algorithm for All-Pairs Bounded Edge Connectivity
Our work concerns algorithms for an unweighted variant of Maximum Flow. ...
research
∙
01/23/2023
Approximating Knapsack and Partition via Dense Subset Sums
Knapsack and Partition are two important additive problems whose fine-gr...
research
∙
11/29/2022
Quantum Speed-ups for String Synchronizing Sets, Longest Common Substring, and k-mismatch Matching
Longest Common Substring (LCS) is an important text processing problem, ...
research
∙
11/14/2022
Removing Additive Structure in 3SUM-Based Reductions
Our work explores the hardness of 3SUM instances without certain additiv...
research
∙
04/06/2022
Approximation Algorithms and Hardness for n-Pairs Shortest Paths and All-Nodes Shortest Cycles
We study the approximability of two related problems: n-Pairs Shortest P...
research
∙
03/27/2022
Constructive Separations and Their Consequences
For a complexity class C and language L, a constructive separation of L ...
research
∙
02/23/2022
Tight Dynamic Problem Lower Bounds from Generalized BMM and OMv
The main theme of this paper is using k-dimensional generalizations of t...
research
∙
11/02/2021
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
We consider low-space algorithms for the classic Element Distinctness pr...
research
∙
10/19/2021
Near-Optimal Quantum Algorithms for String Problems
We study quantum algorithms for several fundamental string problems, inc...
research
∙
05/06/2021
Faster Algorithms for Bounded Tree Edit Distance
Tree edit distance is a well-studied measure of dissimilarity between ro...
research
∙
11/07/2020
Fast Low-Space Algorithms for Subset Sum
We consider the canonical Subset Sum problem: given a list of positive i...
research
∙
10/25/2020
An Improved Sketching Bound for Edit Distance
We provide improved upper bounds for the simultaneous sketching complexi...
research
∙
08/24/2020
Fast and Simple Modular Subset Sum
We revisit the Subset Sum problem over the finite cyclic group ℤ_m for s...
research
∙
05/21/2020
A Massively Parallel Algorithm for Minimum Weight Vertex Cover
We present a massively parallel algorithm, with near-linear memory per m...
research
∙
02/22/2020
Improved MPC Algorithms for MIS, Matching, and Coloring on Trees and Beyond
We present O(loglog n) round scalable Massively Parallel Computation alg...
research
∙
04/24/2019
Faster Algorithms for All Pairs Non-decreasing Paths Problem
In this paper, we present an improved algorithm for the All Pairs Non-de...
research
∙
04/21/2019
An Improved FPTAS for 0-1 Knapsack
The 0-1 knapsack problem is an important NP-hard problem that admits ful...
research
∙
11/20/2018
Simulating Random Walks on Graphs in the Streaming Model
We study the problem of approximately simulating a t-step random walk on...
research
∙
07/30/2018
