Showing cs.CCShow all
3 papers · 1 filter
cs.CC2025
The communication complexity of distributed estimation
Parikshit Gopalan, Raghu Meka, Prasad Raghavendra +2
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions and over domains and , respectively. Their…
cs.CC2025
Constant-Depth Arithmetic Circuits for Linear Algebra Problems
Robert Andrews, Avi Wigderson
We design polynomial size, constant depth (namely, ) arithmetic formulae for the greatest common divisor (GCD) of two polynomials, as well as the related problems of…
cs.CC2024
Complexity of Robust Orbit Problems for Torus Actions and the abc-conjecture
Peter Bürgisser, Mahmut Levent DoÄan, Visu Makam +2
When a group acts on a set, it naturally partitions it into orbits, giving rise to orbit problems. These are natural algorithmic problems, as symmetries are central in numerous que…