Showing 2023Show all
3 papers · 1 filter
cs.CC2023
Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis
Gregory Valiant
We describe two algorithms for multiplying n x n matrices using time and energy n^2 polylog(n) under basic models of classical physics. The first algorithm is for multiplying integ…
math.ST2023
Near-Optimal Mean Estimation with Unknown, Heteroskedastic Variances
Spencer Compton, Gregory Valiant
Given data drawn from a collection of Gaussian variables with a common mean but different and unknown variances, what is the best algorithm for estimating their common mean? We pre…
cs.DS2023
Testing with Non-identically Distributed Samples
Shivam Garg, Chirag Pabbaraju, Kirankumar Shiragur +1
We examine the extent to which sublinear-sample property testing and estimation apply to settings where samples are independently but not identically distributed. Specifically, we…