6 citations · 8 across the 11 of their papers we have counts for
Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
David Gamarnik, Miklós Z. Rácz, Gabe Schoenbach
We study the problem of efficiently finding large common induced subgraphs of two independent Erdős--Rényi random graphs . Recently, Chatterjee and…
cs.DS2024
Integrating High-Dimensional Functions Deterministically
David Gamarnik, Devin Smedira
We design a Quasi-Polynomial time deterministic approximation algorithm for computing the integral of a multi-dimensional separable function, supported by some underlying hyper-gra…
cs.DS2023★ 1 cited
Computing the Volume of a Restricted Independent Set Polytope Deterministically
David Gamarnik, Devin Smedira
We construct a quasi-polynomial time deterministic approximation algorithm for computing the volume of an independent set polytope with restrictions. Randomized polynomial time app…