research
∙
08/14/2023
Dependent rounding with strong negative-correlation, and scheduling on unrelated machines to minimize completion time
We describe a new dependent-rounding algorithmic framework for bipartite...
share
research
∙
03/10/2023
Simple and efficient four-cycle counting on sparse graphs
We consider the problem of counting 4-cycles (C_4) in a general undirect...
research
∙
05/16/2022
A faster algorithm for Vertex Cover parameterized by solution size
We describe a new algorithm for vertex cover with runtime O^*(1.25400^k)...
research
∙
09/27/2021
Improved algorithms for Boolean matrix multiplication via opportunistic matrix multiplication
Karppa Kaski (2019) proposed a novel type of "broken" or "opportunis...
research
∙
11/13/2020
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture
A classic conjecture of Füredi, Kahn and Seymour (1993) states that give...
research
∙
09/22/2020
On the Locality of Nash-Williams Forest Decomposition and Star-Forest Decomposition
Given a graph G=(V,E) with arboricity α, we study the problem of decompo...
research
∙
08/12/2020
A new notion of commutativity for the algorithmic Lovász Local Lemma
The Lovász Local Lemma (LLL) is a powerful tool in probabilistic combina...
research
∙
08/07/2020
Approximation Algorithms for Radius-Based, Two-Stage Stochastic Clustering Problems with Budget Constraints
The main focus of this paper is radius-based clustering problems in the ...
research
∙
07/17/2020
Parameter estimation for Gibbs distributions
We consider Gibbs distributions, which are families of probability distr...
research
∙
05/17/2020
Optimal Bounds for the k-cut Problem
In the k-cut problem, we want to find the smallest set of edges whose de...
research
∙
09/17/2019
Deterministic algorithms for the Lovasz Local Lemma: simpler, more general, and more parallel
The Lovasz Local Lemma (LLL) is a keystone principle in probability theo...
research
∙
06/28/2019
Algorithms for weighted independent transversals and strong colouring
An independent transversal (IT) in a graph with a given vertex partition...
research
∙
04/05/2019
Parameter estimation for integer-valued Gibbs distributions
We consider the family of Gibbs distributions, which are probability dis...
research
∙
01/11/2019
Exponentially Faster Massively Parallel Maximal Matching
The study of graph problems in the Massively Parallel Computations (MPC)...
research
∙
09/07/2018
Approximation algorithms for stochastic clustering
We consider stochastic settings for clustering, and develop provably-goo...
research
∙
07/19/2018
Distributed approximation algorithms for maximum matching in graphs and hypergraphs
We describe randomized and deterministic approximation algorithms in Lin...
research
∙
07/17/2018
Derandomizing the Lovasz Local Lemma via log-space statistical tests
The Lovász Local Lemma (LLL) is a keystone principle in probability theo...
research
∙
06/14/2018
Bounds and algorithms for k-truss
A k-truss is a relaxation of a k-clique developed by Cohen (2005), speci...
research
∙
11/22/2017
Deterministic parallel algorithms for bilinear objective functions
Many randomized algorithms can be derandomized efficiently using either ...
research
∙
11/06/2017