activity
20112026
most citedQuantum Lower and Upper Bounds for 2D-Grid and Dyck Language

10 citations · 19 across the 11 of their papers we have counts for

collaborators
Showing 2026 · cs.CCShow all

1 paper · 2 filters

cs.CC2026

An Optimal Separation Between Certificate Complexity and Approximate Degree

Kaspars Balodis

We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions with $$ C(G) = \tildeΩ(…