David Gamarnik

works on

circuit complexity 1 nlts 1 quantum spin glasses 1 random Hamiltonians 1 shallow circuits 1

From the 1 of 8 linked papers with an AI index.

activity

20242026

collaborators

Showing cs.DSShow all

1 paper · 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 $G_{1}, G_{2} \sim G (n, 1/2)$ . Recently, Chatterjee a…