6 citations · 6 across the 2 of their papers we have counts for
2 papers
cs.CC2024
Partial Minimum Branching Program Size Problem is ETH-hard
Ludmila Glinskih, Artur Riazanov
We show that assuming the Exponential Time Hypothesis, the Partial Minimum Branching Program Size Problem (MBPSP*) requires superpolynomial time. This result also applies to the pa…
cs.CR2023★ 6 cited
The Complexity of Verifying Boolean Programs as Differentially Private
Mark Bun, Marco Gaboardi, Ludmila Glinskih
We study the complexity of the problem of verifying differential privacy for while-like programs working over boolean values and making probabilistic choices. Programs in this clas…