Results 1821 - 1830 of 23856

Justin Chen

Title: On the Structure of Replicable Hypothesis Testers

Abstract: We study replicable algorithms for hypothesis testing as defined by Impagliazzo, Lei, Pitassi, and Sorell [STOC’22]. We develop general tools to prove upper and lower bounds on the sample complexity of replicable testers, improving upon and unifying existing results.

For lower bounds, our main contribution is a description of a canonical replicable tester, which performs as well as any other algorithm while satisfying certain structural properties. By reasoning about sample complexity of such a canonical tester, we show improved lower bounds for uniformity, identity, and closeness testing.

For upper bounds, we systematize and improve a common strategy for replicable algorithm design based on test statistics with known expectation and bounded variance. Our general estimators allow testers which have been extensively analyzed in the non-replicable setting to be made replicable with minimal overhead. As direct applications of our framework combined with existing non-replicable testers, we obtain constant-factor optimal bounds for coin testing and closeness testing. We also give state-of-the-art bounds for replicable Gaussian mean testing and hypothesis selection.

This is joint work with Anders Aamand, Maryam Aliakbarpour, Shyam Narayanan, and Sandeep Silwal.

No abstract available.

This talk will survey a number of recent results in the recently introduced relative-error property testing model, and highlight directions for future work.

We study streaming algorithms for Correlation Clustering. Given a graph as an arbitrary-order stream of edges, with each edge labeled as positive or negative, the goal is to partition the vertices into disjoint clusters, such that the number of disagreements is minimized. In this paper, we give the first learning-augmented streaming algorithms for the problem on both complete and general graphs, improving the best-known space-approximation tradeoffs. Based on the works of Cambus et al. (SODA'24) and Ahn et al. (ICML'15), our algorithms use the predictions of pairwise distances between vertices provided by a predictor. For complete graphs, our algorithm achieves a better-than-$3$ approximation under good prediction quality, while using $\tilde{O}(n)$ total space. For general graphs, our algorithm achieves an $O(\log |E^-|)$ approximation under good prediction quality using $\tilde{O}(n)$ total space, improving the best-known non-learning algorithm in terms of space efficiency. Experimental results on synthetic and real-world datasets demonstrate the superiority of our proposed algorithms over their non-learning counterparts.

We study learning-augmented streaming algorithms for estimating the value of MAX-CUT in a graph. In the classical streaming model, while a $1/2$-approximation for estimating the value of MAX-CUT can be trivially achieved with $O(1)$ words of space, Kapralov and Krachun [STOC’19] showed that this is essentially the best possible: for any $\epsilon > 0$, any (randomized) single-pass streaming algorithm that achieves an approximation ratio of at least $1/2 + \epsilon$ requires $\Omega(n / 2^{\text{poly}(1/\epsilon)})$ space. We show that it is possible to surpass the $1/2$-approximation barrier using just $O(1)$ words of space by leveraging a (machine learned) oracle. Specifically, we consider streaming algorithms that are equipped with an $\epsilon$-accurate oracle that for each vertex in the graph, returns its correct label in $\{-1, +1\}$, corresponding to an optimal MAX-CUT solution in the graph, with some probability $1/2 + \epsilon$, and the incorrect label otherwise. Within this framework, we present a single-pass algorithm that approximates the value of MAX-CUT to within a factor of $1/2 + \Omega(\epsilon^2)$ with probability at least $2/3$ for insertion-only streams, using only $\text{poly}(1/\epsilon)$ words of space. We also extend our algorithm to fully dynamic streams while maintaining a space complexity of $\poly(1/\eps,\log n)$ words.

No abstract available.