research
∙
05/24/2023
Automated Tail Bound Analysis for Probabilistic Recurrence Relations
Probabilistic recurrence relations (PRRs) are a standard formalism for d...
share
research
∙
04/06/2023
Improved Hardness of Approximating k-Clique under ETH
In this paper, we prove that assuming the exponential time hypothesis (E...
research
∙
02/09/2022
Constant Approximating Parameterized k-SetCover is W[2]-hard
In this paper, we prove that it is W[2]-hard to approximate k-SetCover w...
research
∙
11/28/2021
On Lower Bounds of Approximating Parameterized k-Clique
Given a simple graph G and an integer k, the goal of k-Clique problem is...
research
∙
11/30/2020
Quantitative Analysis of Assertion Violations in Probabilistic Programs
In this work, we consider the fundamental problem of deriving quantitati...
research
∙
08/02/2020
Concentration-Bound Analysis for Probabilistic Programs and Probabilistic Recurrence Relations
Analyzing probabilistic programs and randomized algorithms are classical...
research
∙
11/22/2019