Experimental Design Using Interlacing Polynomials

Lap Chi Lau, Robert Wang, Hong Zhou

Abstract

We present a unified deterministic approach for experimental design problems using the method of interlacing polynomials. Our framework recovers the best-known approximation guarantees for the well-studied D/A/E-design problems with simple analysis. Furthermore, we obtain improved non-trivial approximation guarantee for E-design in the challenging small budget regime. Additionally, our approach provides an optimal approximation guarantee for a generalized ratio objective that generalizes both D-design and A-design.
BibTeX
@inproceedings{lau2025experimental,
  author = {Lap Chi Lau and Robert Wang and Hong Zhou},
  title = {{Experimental Design Using Interlacing Polynomials}},
  booktitle = {SOSA},
  year = {2025},
  url = {https://openreview.net/forum?id=KYrGzgfQGV},
}

Loading related content...

Figure