Hello all,
I've been looking at the discrepancy bounds in the repository, specifically the unverified upper bound of $3.65^*$ for $C_{10c}$ (Spencer's constant). To explore the worst-case behavior numerically, I modeled a Bansal-style Semidefinite Relaxation (SDR) using CVXPY and the SCS solver for $n=512$.
Empirical Findings ($n=512$):
-
Structured Systems: For a $512 \times 512$ subset of a Hadamard matrix, the SDR yields a tight lower bound of exactly $0.5\sqrt{n}$.
-
Unstructured Systems: For a $512 \times 512$ random Bernoulli matrix ($p=0.5$), the SDR yields a highly relaxed bound of $\approx 0.027\sqrt{n}$.
Discussion:
These numerical results cleanly illustrate the theoretical expectation: random instances are "soft" in the SDR, while structured orthogonality (Hadamard) raises the bound. However, both fall vastly short of the $3.67$ universal constant. This suggests that any computational effort to strictly verify or tighten the $3.65^*$ bound using relaxations will require generating highly correlated, adversarial non-orthogonal incidence matrices.
If the maintainers are interested, I would be happy to submit a PR adding this CVXPY formulation to a /scripts directory so others can easily benchmark specific adversarial set systems against these relaxations.
Hello all,
I've been looking at the discrepancy bounds in the repository, specifically the unverified upper bound of$3.65^*$ for $C_{10c}$ (Spencer's constant). To explore the worst-case behavior numerically, I modeled a Bansal-style Semidefinite Relaxation (SDR) using CVXPY and the SCS solver for $n=512$ .
Empirical Findings ($n=512$ ):
Discussion:$3.67$ universal constant. This suggests that any computational effort to strictly verify or tighten the $3.65^*$ bound using relaxations will require generating highly correlated, adversarial non-orthogonal incidence matrices.
These numerical results cleanly illustrate the theoretical expectation: random instances are "soft" in the SDR, while structured orthogonality (Hadamard) raises the bound. However, both fall vastly short of the
If the maintainers are interested, I would be happy to submit a PR adding this CVXPY formulation to a
/scriptsdirectory so others can easily benchmark specific adversarial set systems against these relaxations.