PhD Seminar • Algorithms and Complexity • Time Lower Bounds for Property Testing

Please note: This PhD seminar will take place in DC 1304 and online.

Renato Ferreira Pinto Junior, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Eric Blais

We initiate a systematic study of the computational complexity of property testing, focusing on the relationship between query and time complexity. While traditional work in property testing has emphasized query complexity—often via information-theoretic techniques—relatively little is known about the computational hardness of property testers. Our goal is to chart the landscape of time-query trade-offs and develop tools for proving time complexity lower bounds.

Our first contribution is a pair of time-query hierarchy theorems for property testing. For all suitable nondecreasing functions $q(n)$ and $t(n)$ with $t(n) = \Omega(\text{polylog}(n))$, we construct properties with query complexity $\widetilde{\Theta}(q(n))$ and time complexity at least $\Omega(t(n))$. Our weak hierarchy holds unconditionally, while the strong version—assuming the Strong Exponential Time Hypothesis—guarantees time complexity between $\widetilde{\Omega}(t(n))$ and $\widetilde{O}(t(n)^{1+\gamma})$ for arbitrarily small $\gamma > 0$.

We then turn to halfspaces in $\mathbb{R}^d$, a fundamental class in property testing and learning theory. For the distribution-free distance approximation problem, known algorithms achieve query complexity $O(d/\epsilon^2)$, but run in time $\widetilde{O}(1/\epsilon^d)$. We provide a fine-grained justification for this gap: assuming the (integer) $k$-SUM conjecture, any algorithm must have running time ${\Omega}(1/\epsilon^{d/2})$.

Joint work with Diptaksho Palit and Sofya Raskhodnikova.

To attend this PhD seminar in person, please go to DC 1304. You can also attend virtually on Zoom.